Escuche este articulo
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Un ejemplo de árbol hash binario. Los hash 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 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 no hoja está etiquetado con el hash criptográfico de las etiquetas de sus nodos secundarios. . Los árboles hash permiten una verificación eficiente y segura del contenido de grandes estructuras de datos . Los árboles hash son una generalización de listas hash y cadenas hash .

Demostrar que un nodo hoja es parte de un árbol hash binario dado requiere calcular un número de hash proporcional al logaritmo del número de nodos hoja del árbol; [1] esto contrasta con las listas hash, donde el número es proporcional al número de nodos hoja en sí.

El concepto de árboles de hachís lleva el nombre de Ralph Merkle , quien lo patentó en 1979. [2] [3]

Usos [ editar ]

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 hash se utilizan en la criptografía basada en hash . Los árboles hash también se utilizan en los sistemas de archivos IPFS , Btrfs y ZFS [4] (para contrarrestar la degradación de los datos [5] ); Protocolo Dat ; Protocolo Apache Wave ; [6] Sistemas de control de revisión distribuidos Git y Mercurial ; el sistema de respaldo Tahoe-LAFS ; Zeronet ; las redes peer-to-peer de Bitcoin y Ethereum ; [7] el marco de transparencia de certificados ; y una serie deSistemas NoSQL como Apache Cassandra , Riak y Dynamo . [8] Se han hecho sugerencias para utilizar árboles hash en sistemas informáticos fiables . [9]

La implementación inicial de Bitcoin de los árboles Merkle por Satoshi Nakamoto aplica el paso de compresión de la función hash en un grado excesivo, que se mitiga mediante el uso de Fast Merkle Trees. [10]

Resumen [ editar ]

Un árbol hash es un árbol de hashes en el que las 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 valores hash de sus respectivos hijos. Por ejemplo, en la imagen, 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 árbol 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 de hachís solo necesita protegerse contra daños no intencionales, se pueden utilizar sumas de control no seguras , como CRC .

En la parte superior de un árbol de hash hay un hash superior (o hash de 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 que se sabe que tiene buenas recomendaciones de archivos para descargar. Cuando el hash superior está disponible, el árbol de hash se puede recibir de cualquier fuente no confiable, 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 intentará con otro árbol hash de otra fuente hasta que el programa encuentre uno que coincida con el hash superior. [11]

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 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 aplicando hash al bloque de datos y combinando iterativamente el resultado con hash 0-0 y luego 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 eficiente dividir archivos en bloques de datos muy pequeños, de modo que solo los bloques pequeños tengan que volver a descargarse si se dañan. Si el archivo hash es muy grande, dicho árbol hash o lista 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 se puede iniciar la descarga de bloques de datos. [ cita requerida ]

Segundo ataque de preimagen [ editar ]

La raíz de 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 diferente al original que tiene la misma raíz de 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. [12] [13]

Una solución simple se define en Transparencia de certificado : cuando se calculan los hashes del nodo hoja, se antepone un byte 0x00 a los datos hash, mientras que se antepone 0x01 cuando se calculan los hashes del nodo interno. [11] Limitar el tamaño del árbol de 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 de á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.

Hash del árbol del tigre [ editar ]

El hachís del árbol del tigre es una forma de hachís muy utilizada. 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 . [14]

Los hashes de árbol de tigre se utilizan en Gnutella , [15] Gnutella2 y los protocolos de intercambio de archivos Direct Connect P2P [16] y en aplicaciones de intercambio de archivos como Phex , [17] BearShare , LimeWire , Shareaza , DC ++ [18] y Valknut . [19]

Ejemplo [ editar ]

Base32 :R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN :urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

imán :magnet:?xt=urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Ver también [ editar ]

  • Árbol binario
  • Blockchain (base de datos)
  • Tabla hash distribuida
  • Tabla de picadillo
  • Hachís trie
  • Sellado de tiempo vinculado
  • Árbol de radix

Referencias [ editar ]

  1. ↑ Becker, Georg (18 de julio de 2008). "Esquemas de firma de Merkle, árboles de Merkle y su criptoanálisis" (PDF) . Ruhr-Universität Bochum. pag. 16 . Consultado el 20 de noviembre de 2013 .
  2. ^ Merkle, RC (1988). "Una firma digital basada en una función de cifrado convencional". Avances en Criptología - CRYPTO '87 . Apuntes de conferencias en Ciencias de la Computación. 293 . págs. 369–378. doi : 10.1007 / 3-540-48184-2_32 . ISBN 978-3-540-18796-7.
  3. ^ Patente estadounidense 4309569 , Ralph Merkle, "Método de proporcionar firmas digitales", publicada el 5 de enero de 1982, asignada al Patronato de la Universidad Juvenil de Leland Stanford 
  4. ^ Bonwick, Jeff. "Integridad de datos de extremo a extremo de ZFS" . Blog de Jeff Bonwick .
  5. ^ Likai Liu. "Resistencia Bitrot en una sola unidad" . likai.org .
  6. ^ "Federación general comprobable" . Protocolo de Google Wave . Archivado desde el original el 8 de abril de 2018 . Consultado el 9 de marzo de 2017 .
  7. ^ Koblitz, Neal; Menezes, Alfred J. (enero de 2016). "Cryptocash, 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 .  
  8. ^ 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 transferencias sugeridas para una réplica no disponible también se desconecta, las réplicas deben sincronizarse entre sí. En este caso, Cassandra y Riak implementan un proceso inspirado en Dynamo llamado anti-entropía. En anti-entropía, las réplicas intercambian árboles de Merkle para identificar partes de sus rangos de claves replicados que no están sincronizados. Un árbol de Merkle es una verificación de hash jerárquica: si el hash en todo el espacio de claves no es el mismo entre dos réplicas, intercambiarán hash 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 en su mayoría datos similares.
  9. ^ Kilian, J. (1995). "Argumentos eficientes mejorados (versión preliminar)" (PDF) . CRYPTO . doi : 10.1007 / 3-540-44750-4_25 .
  10. ^ Mark Friedenbach: Árboles rápidos de Merkle
  11. ↑ a b Laurie, B .; Langley, A .; Kasper, E. (junio de 2013). "Certificado de transparencia" . IETF : RFC6962. doi : 10.17487 / rfc6962 .
  12. ^ Elena Andreeva; Charles Bouillaguet; Orr Dunkelman; John Kelsey (enero de 2009). "Herding, Second Preimage y Trojan Message Attacks más allá de Merkle – Damgård". Áreas seleccionadas en criptografía . Apuntes de conferencias en Ciencias de la Computación. 5867 . SACO. págs. 393–414. doi : 10.1007 / 978-3-642-05445-7_25 . ISBN 978-3-642-05443-3.
  13. ^ Elena Andreeva; Charles Bouillaguet; Pierre-Alain Fouque; Jonathan J. Hoch; John Kelsey; Adi Shamir; Sebastien Zimmer (2008). "Segundos ataques de preimagen en funciones de hash difuminado". En Smart, Nigel (ed.). Avances en Criptología - EUROCRYPT 2008 . Apuntes de conferencias en Ciencias de la Computación. 4965 . Istanbul, Turquía. págs. 270–288. doi : 10.1007 / 978-3-540-78967-3_16 . ISBN 978-3-540-78966-6.
  14. ↑ 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.
  15. ^ "Referencia de archivo tigertree.c" . Gtk-Gnutella . Consultado el 23 de septiembre de 2018 .
  16. ^ "Auditoría: aplicación P2P DirectConnect" . Symantec . Consultado el 23 de septiembre de 2018 .
  17. ^ Arne Babenhauserheide (7 de enero de 2007). "Lanzamiento de Phex 3.0.0" . Phex . Consultado el 23 de septiembre de 2018 .
  18. ^ "Lista de funciones de DC ++" . dcplusplus.sourceforge.net .
  19. ^ "Desarrollo" . GTK-Gnutella . Consultado el 23 de septiembre de 2018 .

Lectura adicional [ editar ]

  • Patente del árbol de Merkle 4.309.569  : explica tanto la estructura del árbol hash como su uso para manejar muchas firmas de una sola vez
  • Formato de intercambio de hash de árbol (THEX)  : una descripción detallada de los árboles de tigre

Enlaces externos [ editar ]

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 de septiembre de 2013 )
( Ayuda de audio  · Más artículos hablados )
  • Implementación de CA de un árbol hash SHA-256 binario dinámicamente redimensionable (árbol Merkle)
  • Implementación del árbol 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