Árbol de Merkle

Un árbol hash de Merkle (en inglés: Merkle hash tree) o árbol de Merkle o árbol hash es una estructura de datos en árbol, binario o no, en el que cada nodo que no es una hoja está etiquetado con el hash de la concatenación de las etiquetas o valores (para nodos hoja) de sus nodos hijo. Son una generalización de las listas hash y las cadenas hash.

Un ejemplo de árbol de Merkle binario. Los hashes 0-0 y 0-1 son los valores de los hash de los bloques de datos 1 y 2 respectivamente, y 0 es el hash de la concatenación de hashes 0-0 y 0-1.

Permite que gran número de datos separados puedan ser ligados a un único valor de hash, el hash del nodo raíz del árbol. De esta forma proporciona un método de verificación segura y eficiente de los contenidos de grandes estructuras de datos. En sus aplicaciones prácticas, normalmente el hash del nodo raíz va firmado para asegurar su integridad y que la verificación sea totalmente fiable. La demostración de que un nodo hoja es parte de un árbol hash dado requiere una cantidad de datos proporcional al logaritmo del número de nodos del árbol.

Fue patentado en 1979 por Ralph Merkle.

Aplicaciones

Actualmente el mayor uso de los árboles de Merkle es hacer seguros los bloques de datos recibidos de otros pares en las redes peer-to-peer, asegurar que estos son recibidos sin daños y sin ser alterados. Además permiten que los datos de un bloque puedan ser entregados por partes: un nodo puede descargar solamente la cabecera de un bloque (árbol) desde una fuente, y otra pequeña parte del árbol relevante para él, desde otra fuente, y todavía asegurar que los datos son correctos. La razón por lo que esto funciona es porque los hashes se propagan hacia arriba: si un usuario malintencionado intenta hacer un cambio en una transacción falsa en la parte inferior del árbol de Merkle, este cambio provocará un cambio en el nodo superior y seguidamente otro cambio en el nodo por encima de este, hasta que finalmente, se produzca un cambio en la raíz del árbol y por tanto en el hash del bloque, haciendo que el protocolo tenga que registrarlo como un bloque completamente diferente (y casi con toda seguridad con una prueba de trabajo inválida).

Referencias

• Mastering Bitcoin. Unlocking Digital Cryptocurrencies. Andreas M. Antonopoulos. O'Reilly 2014
• Bitcoins. ¿Revolución o Historia? Jaime Sánchez de Diego Martínez-Cabrera. Universidad Pontificia de Comillas. Junio 2014
• Estructuras de Datos Autenticadas para gestionar. Datos de Revocación en VANETs. Carlos Gañán et al.

• Datos: Q14746