En criptografía e informática , un árbol hash o árbol Merkle es un árbol en el que cada "hoja" ( nodo ) está etiquetada con el hash criptográfico de un bloque de datos, y cada nodo que no es una hoja (llamado rama , nodo interno , o inode ) 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 .
Demostrar que un nodo hoja es parte de un árbol hash binario determinado requiere calcular una cantidad de hashes proporcional al logaritmo del número de nodos hoja en el árbol. [1] Por el contrario, en una lista hash, el número es proporcional al número de nodos hoja. 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 que son parte del compromiso original [2] .
El concepto de árbol de hachís lleva el nombre de Ralph Merkle , quien lo patentó en 1979. [3] [4]
Los árboles hash se pueden utilizar para verificar cualquier tipo de datos almacenados, manejados y transferidos dentro y entre computadoras. Pueden ayudar a garantizar que los bloques de datos recibidos de otros pares en una red peer-to-peer se reciban sin daños ni alteraciones, e incluso para verificar que los otros pares no mientan y envíen bloques falsos.
Los árboles de hachís se utilizan en
Se han hecho sugerencias para utilizar árboles hash en sistemas informáticos confiables . [11]
La implementación inicial de Bitcoin de los árboles Merkle por parte de 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 Fast Merkle Trees. [12]
Un árbol hash es un árbol de hashes en el que las hojas (es decir, los nodos hoja, a veces también llamados "hojas") son hashes de bloques de datos en, por ejemplo, un archivo o conjunto de archivos. Los nodos más arriba en el árbol son los hashes de sus respectivos hijos. Por ejemplo, en la imagen de arriba, el hash 0 es el resultado del hash de 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 sólo necesita protegerse contra daños involuntarios, se pueden utilizar sumas de verificació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 adquiere de una fuente confiable, por ejemplo, un amigo o un sitio web conocido por tener buenas recomendaciones de archivos para descargar. Cuando el hash superior está disponible, el árbol hash se puede recibir de cualquier fuente que no sea de confianza, como cualquier par en la red P2P. Luego, el árbol hash recibido se compara con el hash superior confiable y, si el árbol hash está dañado o es falso, se probará con 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 la integridad de cada rama se puede verificar inmediatamente, aunque el árbol completo no esté disponible todavía. Por ejemplo, en la imagen, la integridad del bloque de datos L2 se puede verificar inmediatamente si el árbol ya contiene el hash 0-0 y el hash 1 aplicando hash al bloque de datos y combinando iterativamente el resultado con el hash 0-0 y luego el hash 1 y finalmente comparando el resultado con el hash superior . De manera similar, la integridad del bloque de datos L3 se puede verificar si el árbol ya tiene hash 1-1 y hash 0 . Esto puede ser una ventaja, ya que es eficaz dividir archivos en bloques de datos muy pequeños, de modo que sólo sea necesario volver a descargar 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 pequeña rama, se puede verificar la integridad de la rama y luego puede comenzar la descarga de bloques de datos. [ cita necesaria ]
La raíz 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 hash de Merkle. Para el ejemplo anterior, un atacante puede crear un nuevo documento que contenga dos bloques de datos, donde el primero es hash 0-0 + hash 0-1 y el segundo es hash 1-0 + hash 1-1 . [14] [15]
Se define una solución simple en Transparencia de certificados : cuando se calculan hashes de nodos 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 requisito previo de algunas pruebas de seguridad formales y ayuda a hacer algunas pruebas más estrictas. Algunas implementaciones limitan la profundidad del árbol utilizando prefijos de profundidad del árbol hash antes de los hash, 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 hachís del árbol del tigre es una forma muy utilizada de árbol de hachís. Utiliza un árbol hash binario (dos nodos secundarios debajo de cada nodo), generalmente tiene un tamaño de bloque de datos de 1024 bytes y usa el hash Tiger . [dieciséis]
Los hashes de árbol de tigre se utilizan en los protocolos de intercambio de archivos Gnutella , [17] Gnutella2 y Direct Connect P2P [18] y en aplicaciones para compartir 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 deja de funcionar, las réplicas deben sincronizarse entre sí.
En este caso, Cassandra y Riak implementan un proceso inspirado en Dynamo llamado antientropía.
En antientropía, las réplicas intercambian árboles Merkle para identificar partes de sus rangos de claves replicadas que no están sincronizadas.
Un árbol Merkle es una verificación de hash jerárquica: si el hash de 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 no sincronizadas.
Este enfoque reduce la transferencia de datos innecesaria entre réplicas que contienen datos en su mayoría similares.
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )