En criptografía y ciencias de la computación , un árbol hash o árbol de Merkle es un árbol en el que cada nodo "hoja" está etiquetado con el hash criptográfico de un bloque de datos, y cada nodo que no es una hoja (llamado rama , nodo interno o inodo ) está etiquetado con el hash criptográfico de las etiquetas de sus nodos secundarios. Un árbol hash permite una verificación eficiente y segura del contenido de una gran estructura de datos . Un árbol hash es una generalización de una lista hash y una cadena hash .
Para demostrar que un nodo hoja es parte de un árbol hash binario dado, es necesario calcular una cantidad de hashes proporcional al logaritmo de la cantidad de nodos hoja en el árbol. [1] Por el contrario, en una lista hash, la cantidad es proporcional a la cantidad de nodos hoja en sí. Por lo tanto, un árbol Merkle es un ejemplo eficiente de un esquema de compromiso criptográfico , en el que la raíz del árbol se considera un compromiso y los nodos hoja pueden revelarse y demostrarse como parte del compromiso original. [2]
El concepto de árbol hash debe su nombre a Ralph Merkle , quien lo patentó en 1979. [3] [4]
Los árboles hash se pueden utilizar para verificar cualquier tipo de datos almacenados, manipulados y transferidos en y entre computadoras. Pueden ayudar a garantizar que los bloques de datos recibidos de otros pares en una red peer to peer se reciban intactos y sin alteraciones, e incluso para verificar que los otros pares no mientan y envíen bloques falsos.
Los árboles hash se utilizan en:
Se han hecho sugerencias para utilizar árboles hash en sistemas informáticos confiables . [11]
La implementación inicial de árboles Merkle en Bitcoin por Satoshi Nakamoto aplica el paso de compresión de la función hash en un grado excesivo, lo que se mitiga mediante el uso de árboles Merkle rápidos. [12]
Un árbol hash es un árbol de hashes en el que las hojas (es decir, los nodos de hoja, a veces también llamados "hojas") son hashes de bloques de datos en, por ejemplo, un archivo o un conjunto de archivos. Los nodos más arriba en el árbol son los hashes de sus respectivos hijos. Por ejemplo, en la imagen anterior, el hash 0 es el resultado de aplicar un hash a la concatenación de hash 0-0 y hash 0-1 . Es decir, hash 0 = hash ( hash 0-0 + hash 0-1 ) donde "+" denota concatenación.
La mayoría de las implementaciones de árboles hash son binarias (dos nodos secundarios debajo de cada nodo) pero también pueden usar muchos más nodos secundarios debajo de cada nodo.
Por lo general, se utiliza una función hash criptográfica como SHA-2 para el hash. Si el árbol hash solo necesita proteger contra daños involuntarios, se pueden utilizar sumas de comprobación no seguras como las CRC .
En la parte superior de un árbol hash hay un hash superior (o hash raíz o hash maestro ). Antes de descargar un archivo en una red P2P , en la mayoría de los casos el hash superior se obtiene de una fuente confiable, por ejemplo un amigo o un sitio web que se sabe que tiene buenas recomendaciones de archivos para descargar. Cuando el hash superior está disponible, el árbol hash se puede recibir de cualquier fuente no confiable, como cualquier par en la red P2P. Luego, el árbol hash recibido se verifica con el hash superior confiable, y si el árbol hash está dañado o es falso, se probará otro árbol hash de otra fuente hasta que el programa encuentre uno que coincida con el hash superior. [13]
La principal diferencia con una lista hash es que se puede descargar una rama del árbol hash a la vez y se puede verificar la integridad de cada rama inmediatamente, aunque el árbol completo aún no esté disponible. Por ejemplo, en la imagen, la integridad del bloque de datos L2 se puede verificar inmediatamente si el árbol ya contiene hash 0-0 y hash 1 al aplicar hash al bloque de datos y combinar iterativamente el resultado con hash 0-0 y luego hash 1 y finalmente comparar el resultado con el hash superior . De manera similar, se puede verificar la integridad del bloque de datos L3 si el árbol ya tiene hash 1-1 y hash 0. Esto puede ser una ventaja ya que es eficiente dividir archivos en bloques de datos muy pequeños de modo que solo se deban volver a descargar los bloques pequeños si se dañan. Si el archivo hash es grande, dicha lista hash o cadena hash se vuelve bastante grande. Pero si es un árbol, se puede descargar rápidamente una rama pequeña, se puede verificar la integridad de la rama y luego puede comenzar la descarga de bloques de datos. [ cita requerida ]
La raíz del hash de Merkle no indica la profundidad del árbol, lo que permite un ataque de segunda preimagen en el que un atacante crea un documento distinto del original que tiene la misma raíz del hash de Merkle. En el ejemplo anterior, un atacante puede crear un nuevo documento que contenga dos bloques de datos, donde el primero es el hash 0-0 + hash 0-1 y el segundo es el hash 1-0 + hash 1-1 . [14] [15]
Una solución simple se define en Certificate Transparency : cuando se calculan hashes de nodos de hoja, se antepone un byte 0x00 a los datos hash, mientras que se antepone 0x01 cuando se calculan hashes de nodos internos. [13] Limitar el tamaño del árbol hash es un prerrequisito de algunas pruebas de seguridad formales y ayuda a hacer que algunas pruebas sean más estrictas. Algunas implementaciones limitan la profundidad del árbol usando prefijos de profundidad de árbol hash antes de los hashes, por lo que cualquier cadena hash extraída se define como válida solo si el prefijo disminuye en cada paso y sigue siendo positivo cuando se alcanza la hoja.
El hash de árbol Tiger es una forma muy utilizada de árbol hash. Utiliza un árbol hash binario (dos nodos secundarios debajo de cada nodo), normalmente tiene un tamaño de bloque de datos de 1024 bytes y utiliza el hash Tiger . [16]
Los hashes de árbol de tigre se utilizan en los protocolos de intercambio de archivos P2P Gnutella , [17] Gnutella2 y Direct Connect [18] y en aplicaciones de intercambio de archivos como Phex , [19] BearShare , LimeWire , Shareaza , DC++ [20] y gtk-gnutella . [21]
Cuando una réplica está inactiva durante un período prolongado de tiempo, o la máquina que almacena las transferencias sugeridas para una réplica no disponible también se inactiva, las réplicas deben sincronizarse entre sí. En este caso, Cassandra y Riak implementan un proceso inspirado en Dynamo llamado antientropía. En la antientropía, las réplicas intercambian árboles Merkle para identificar partes de sus rangos de claves replicadas que están desincronizadas. Un árbol Merkle es una verificación de hash jerárquica: si el hash sobre todo el espacio de claves no es el mismo entre dos réplicas, intercambiarán hashes de porciones cada vez más pequeñas del espacio de claves replicado hasta que se identifiquen las claves desincronizadas. Este enfoque reduce la transferencia innecesaria de datos entre réplicas que contienen principalmente datos similares.
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )