Hispanopedia Wiki
Articulo de referencia

Árbol de Merkle

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

Hispanopedia WikiContenido en espanolLectura gratuita
Escucha este artículo
Un ejemplo de árbol hash binario. Los hashes 0-0 y 0-1 son los valores hash de los bloques de datos L1 y L2, respectivamente, y el hash 0 es el hash de la concatenación de los hashes 0-0 y 0-1.

En criptografía e informática , un árbol hash o árbol 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 hijos. Un árbol hash permite una verificación eficiente y segura del contenido de una estructura de datos grande . Un árbol hash es una generalización de una lista hash y una cadena hash .

Demostrar que un nodo hoja forma parte de un árbol hash binario dado requiere calcular un número 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 forman parte del compromiso original. [ 2 ]

El concepto de árbol hash recibe su nombre de Ralph Merkle , quien lo patentó en 1979. [ 3 ] [ 4 ]

Usos

Los árboles hash se pueden usar para verificar cualquier tipo de datos almacenados, gestionados y transferidos entre ordenadores. Ayudan a garantizar que los bloques de datos recibidos de otros nodos en una red peer-to-peer se reciban intactos y sin alteraciones, e incluso permiten comprobar que los demás nodos no mientan ni envíen bloques falsos.

Los árboles hash se utilizan en:

Se han hecho sugerencias para utilizar árboles hash en sistemas de computación confiables . [ 14 ]

Descripción general

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 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, hash 0 es el resultado de calcular el 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 hijos debajo de cada nodo), pero también pueden usar muchos más nodos hijos debajo de cada nodo.

Generalmente, para el hash se utiliza una función hash criptográfica como SHA-2 . Si el árbol hash solo necesita proteger contra daños involuntarios, se pueden usar sumas de verificación no criptográficas como CRC .

En la parte superior de un árbol hash se encuentra el hash raíz (o hash maestro ) . Antes de descargar un archivo en una red P2P , en la mayoría de los casos, el hash raíz se obtiene de una fuente confiable, por ejemplo, un amigo o un sitio web conocido por ofrecer buenas recomendaciones de archivos para descargar. Una vez que se dispone del hash raíz, el árbol hash puede recibirse de cualquier fuente no confiable, como cualquier otro nodo en la red P2P. A continuación, el árbol hash recibido se compara con el hash raíz confiable y, si está dañado o es falso, se intenta con otro árbol hash de otra fuente hasta que el programa encuentre uno que coincida con el hash raíz. [ 15 ]

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 de inmediato, incluso si 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 los hashes 0-0 y 1, calculando el hash del bloque de datos y combinando iterativamente el resultado con los hashes 0-0 y 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 los hashes 1-1 y 0. Esto puede ser una ventaja, ya que es eficiente dividir los archivos en bloques de datos muy pequeños, de modo que solo se tengan que volver a descargar los bloques pequeños si se dañan. Si el archivo hash es grande, dicha lista o cadena hash se vuelve bastante grande. Pero si se trata de un árbol, se puede descargar rápidamente una rama pequeña, se puede verificar la integridad de la rama y luego se puede comenzar la descarga de los bloques de datos.

Segundo ataque de preimagen

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. En 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 . [ 16 ] [ 17 ]

Una solución sencilla se define en la Transparencia de Certificados : al calcular los hashes de los nodos hoja, se antepone un byte 0x00 a los datos del hash, mientras que se antepone 0x01 al calcular los hashes de los nodos internos. [ 15 ] Limitar el tamaño del árbol hash es un requisito previo de algunas pruebas de seguridad formales y ayuda a que algunas pruebas sean más sólidas. Algunas implementaciones limitan la profundidad del árbol usando prefijos de profundidad del á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 llega a la hoja.

Hachís de árbol de tigre

El hash de árbol Tiger es una forma ampliamente utilizada de árbol hash. Utiliza un árbol hash binario (dos nodos hijos debajo de cada nodo), generalmente tiene un tamaño de bloque de datos de 1024 bytes y utiliza el hash Tiger . [ 18 ]

Los hashes de árbol de tigre se utilizan en los protocolos de intercambio de archivos P2P Gnutella , [ 19 ] Gnutella2 y Direct Connect [ 20 ] y en aplicaciones de intercambio de archivos como Phex , [ 21 ] BearShare , LimeWire , Shareaza , DC++ [ 22 ] y gtk-gnutella . [ 23 ]

Véase también

Referencias

  1. ^ Becker, Georg (18 de julio de 2008). "Esquemas de firma de Merkle, árboles de Merkle y su criptoanálisis" (PDF) . Universidad del Ruhr de Bochum. pag.  16. Archivado desde el original (PDF) el 22 de diciembre de 2014 . Consultado el 20 de noviembre de 2013 .
  2. ↑ "Manual de criptografía aplicada" . cacr.uwaterloo.ca . Sección 13.4.1 . Consultado el 7 de marzo de 2024 .
  3. ↑ Merkle, RC (1988). "Una firma digital basada en una función de cifrado convencional". Avances en criptología – CRYPTO '87 . Notas de clase en ciencias de la computación. Vol. 293. págs. 369–378 . doi : 10.1007/3-540-48184-2_32 . ISBN   978-3-540-18796-7.
  4. ↑ Patente estadounidense 4309569 , Ralph Merkle, "Método para proporcionar firmas digitales", publicada el 5 de enero de 1982, asignada a la Junta Directiva de la Universidad Leland Stanford Junior. 
  5. ↑ "Página del desarrollador de hashtree" .
  6. ↑ Bonwick, Jeff (8 de diciembre de 2005). "Integridad de datos de extremo a extremo de ZFS" . blogs.oracle.com . Archivado del original el 3 de abril de 2012. Consultado el 19 de septiembre de 2013 .
  7. ↑ Likai Liu. "Resistencia al bitrot en una sola unidad" . likai.org .
  8. ↑ "Federación verificable general" . Protocolo Google Wave . Archivado del original el 8 de abril de 2018. Consultado el 9 de marzo de 2017 .
  9. ↑ "Introducción a ZFS: la documentación más reciente de openzfs" . openzfs.readthedocs.io . Consultado el 27 de mayo de 2025 .
  10. ↑ Koblitz, Neal; Menezes, Alfred J. (enero de 2016). "Cryptocash, criptomonedas y criptocontratos". Designs, Codes and Cryptography . 78 (1): 87– 102. CiteSeerX 10.1.1.701.8721 . doi : 10.1007/s10623-015-0148-5 . S2CID 16594958 .  
  11. ↑ D. Benjamín; D. O'Brien; SER Westerbaan; L.Valenta; F. Valsorda (24/05/2026). "Certificados de árbol Merkle" . Grupo de trabajo de ingeniería de Internet . IETF . Consultado el 11 de junio de 2026 .
  12. ↑ Dolstra, E. El modelo de despliegue de software puramente funcional. Tesis doctoral, Facultad de Ciencias, Utrecht, Países Bajos. Enero de 2006. pág. 21 ISBN 90-393-4130-3.
  13. ↑ Adam Marcus. "El ecosistema NoSQL" . aosabook.org . Cuando una réplica está inactiva durante un período prolongado, o la máquina que almacena las transferencias sugeridas para una réplica no disponible también falla, 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 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 de datos innecesaria entre réplicas que contienen principalmente datos similares.
  14. ↑ Kilian, J. (1995). «Argumentos eficientes mejorados» (PDF) . Avances en criptología — CRYPT0' 95. Notas de clase en ciencias de la computación. Vol. 963. págs. 311–324 . doi : 10.1007/3-540-44750-4_25 . ISBN   978-3-540-60221-7.
  15. 1 2 Laurie, B.; Langley, A.; Kasper, E. (junio de 2013). "Transparencia de los certificados" . IETF RFC6962. doi : 10.17487/rfc6962 .
  16. ↑ Elena Andreeva; Charles Bouillaguet; Orr Dunkelman; John Kelsey (enero de 2009). «Ataques de agrupamiento, segunda preimagen y mensajes troyanos más allá de Merkle-Damgård». Áreas selectas en criptografía . Notas de clase en ciencias de la computación. Vol. 5867. SAC. págs. 393–414 . doi : 10.1007/978-3-642-05445-7_25 . ISBN   978-3-642-05443-3.
  17. ↑ Elena Andreeva; Charles Bouillaguet; Pierre-Alain Fouque; Jonathan J. Hoch; John Kelsey; Adi Shamir; Sebastien Zimmer (2008). "Ataques de segunda preimagen a funciones hash con tramado". En Smart, Nigel (ed.). Avances en criptología – EUROCRYPT 2008. Lecture Notes in Computer Science. Vol. 4965. Estambul, Turquía. pp. 270–288 . doi : 10.1007/978-3-540-78967-3_16 . ISBN   978-3-540-78966-6. S2CID 12844017 . {{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  18. ↑ Chapweske, J.; Mohr, G. (4 de marzo de 2003). "Formato de intercambio de hash de árbol (THEX)" . Archivado del original el 3 de agosto de 2009.
  19. ↑ "Referencia al archivo tigertree.c" . Gtk-Gnutella . Consultado el 23 de septiembre de 2018 .
  20. ↑ "Auditoría: Aplicación P2P DirectConnect" . Symantec . Archivado del original el 29 de enero de 2015. Consultado el 23 de septiembre de 2018 .
  21. ↑ Arne Babenhauserheide (7 de enero de 2007). "Lanzamiento de Phex 3.0.0" . Phex . Consultado el 23 de septiembre de 2018 .
  22. ↑ "Lista de características de DC++" . dcplusplus.sourceforge.net .
  23. ↑ "Desarrollo" . GTK-Gnutella . Consultado el 23 de septiembre de 2018 .

Lecturas adicionales

  • La patente del árbol Merkle 4.309.569 explica tanto la estructura del árbol hash como su uso para gestionar múltiples firmas de un solo uso. 
  • Formato Tree Hash EXchange (THEX) : una descripción detallada de los árboles Tiger. 
  • Implementación AC de un árbol hash SHA-256 binario redimensionable dinámicamente (árbol Merkle)
  • Implementación de un árbol de Merkle en Java
  • Código fuente de Tiger Tree Hash (TTH) en C# , por Gil Schmidt
  • Implementaciones de Tiger Tree Hash (TTH) en C y Java
  • RHash , una herramienta de línea de comandos de código abierto, que puede calcular TTH y enlaces magnéticos con TTH.