Árbol de Merkle
Tipo de estructura de datos
Ejemplo de un á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 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 la 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]

Usos

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]

Descripción general

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 del hash 0-0 y el 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 ]

Segundo ataque de preimagen

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.

Hachís de árbol de tigre

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]

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 . Apuntes de clase en informática. 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 de Síndicos de la Universidad Leland Stanford Junior 
  5. ^ Bonwick, Jeff (8 de diciembre de 2005). "Integridad de datos de extremo a extremo de ZFS". blogs.oracle.com . Archivado desde el original el 3 de abril de 2012. Consultado el 19 de septiembre de 2013 .
  6. ^ Likai Liu. "Resistencia Bitrot en una sola unidad". likai.org .
  7. ^ "Federación verificable general". Protocolo Google Wave . Archivado desde el original el 8 de abril de 2018. Consultado el 9 de marzo de 2017 .
  8. ^ Koblitz, Neal; Menezes, Alfred J. (enero de 2016). «Criptodinero en efectivo, criptomonedas y criptocontratos». Diseños, códigos y criptografía . 78 (1): 87–102. CiteSeerX 10.1.1.701.8721 . doi :10.1007/s10623-015-0148-5. S2CID  16594958. 
  9. ^ Dolstra, E. El modelo de implementación de software puramente funcional. Tesis doctoral, Facultad de Ciencias, Utrecht, Países Bajos. Enero de 2006. p.21 ISBN 90-393-4130-3 . 
  10. ^ Adam Marcus. "El ecosistema NoSQL". aosabook.org . 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.
  11. ^ Kilian, J. (1995). "Argumentos eficientes mejorados (versión preliminar)" (PDF) . CRYPTO . doi : 10.1007/3-540-44750-4_25 .
  12. ^ Mark Friedenbach: Árboles de Merkle rápidos
  13. ^ ab Laurie, B.; Langley, A.; Kasper, E. (junio de 2013). "Transparencia de certificados". IETF : RFC6962. doi :10.17487/rfc6962.
  14. ^ Elena Andreeva; Charles Bouillaguet; Orr Dunkelman; John Kelsey (enero de 2009). "Herding, Second Preimage y ataques de mensajes troyanos más allá de Merkle-Damgård". Áreas seleccionadas en criptografía . Apuntes de clase en informática. Vol. 5867. SAC. págs. 393–414. doi :10.1007/978-3-642-05445-7_25. ISBN . 978-3-642-05443-3.
  15. ^ Elena Andreeva; Charles Bouillaguet; Pierre-Alain Fouque; Jonathan J. Hoch; John Kelsey; Adi Shamir; Sebastien Zimmer (2008). "Ataques de segunda preimagen en funciones hash dithered". En Smart, Nigel (ed.). Avances en criptología – EUROCRYPT 2008. Apuntes de clase en informática. Vol. 4965. Estambul, Turquía. págs. 270–288. doi :10.1007/978-3-540-78967-3_16. ISBN 978-3-540-78966-6. Número de identificación del sujeto  12844017.{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
  16. ^ Chapweske, J.; Mohr, G. (4 de marzo de 2003). "Formato de intercambio de hash de árbol (THEX)". Archivado desde el original el 3 de agosto de 2009.
  17. ^ "Referencia del archivo tigertree.c". Gtk-Gnutella . Consultado el 23 de septiembre de 2018 .
  18. ^ "Auditoría: aplicación P2P DirectConnect". Symantec . Archivado desde el original el 29 de enero de 2015. Consultado el 23 de septiembre de 2018 .
  19. ^ Arne Babenhauserheide (7 de enero de 2007). "Phex 3.0.0 lanzado". Phex . Consultado el 23 de septiembre de 2018 .
  20. ^ "Lista de características de DC++". dcplusplus.sourceforge.net .
  21. ^ "Desarrollo". GTK-Gnutella . Consultado el 23 de septiembre de 2018 .

Lectura adicional

  • Patente de árbol Merkle 4.309.569  : explica tanto la estructura del árbol hash como su uso para gestionar muchas firmas de un solo uso
  • Formato Tree Hash EXchange (THEX): una descripción detallada de los árboles Tiger
Escuche este artículo ( 5 minutos )
Icono de Wikipedia hablado
Este archivo de audio se creó a partir de una revisión de este artículo con fecha del 17 de septiembre de 2013 y no refleja ediciones posteriores. ( 17-09-2013 )
( Ayuda de audio  · Más artículos hablados )
  • Implementación de AC de un árbol hash binario SHA-256 redimensionable dinámicamente (árbol Merkle)
  • Implementación del á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
Obtenido de "https://es.wikipedia.org/w/index.php?title=Árbol_de_Merkle&oldid=1245066542"