Árbol de hachís

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 5 de agosto de 2021; las comprobaciones requieren 2 ediciones .

Un árbol hash , un árbol Merkle se llama un árbol binario completo , en los vértices de las hojas se colocan hashes de bloques de datos, y los vértices internos contienen hashes de agregar valores en vértices secundarios. El nodo raíz del árbol contiene el hash de todo el conjunto de datos, es decir, el árbol hash es una función hash unidireccional. El árbol de Merkle se utiliza para el almacenamiento eficiente de transacciones en la cadena de bloques de las criptomonedas (por ejemplo, en Bitcoin , Ethereum ). Le permite obtener una "huella digital" de todas las transacciones en el bloque, así como verificar transacciones de manera efectiva [1] .

Edificio

El llenado de valores en los nodos del árbol va de abajo hacia arriba. Primero, se aplica hash a cada bloque de datos , y así sucesivamente. Los valores resultantes se escriben en las hojas del árbol. Los bloques de un nivel superior se rellenan como hashes de la suma de sus hijos , donde normalmente significa concatenación . Esta operación se repite hasta que se obtiene el valor superior - o [1] . $Hash_{00}=hash(L_{1})$ $Hash_{01}=hash(L_{2})$ $Hash_{0}=hash(Hash_{00}+Hash_{01})$ $+$ $TopHash$ merkle_root

Bitcoin usa el doble SHA-256 como su función hash , es decir, [1] . Sin embargo, la función hash puede ser cualquier cosa, por ejemplo, el Tiger Tree Hash (TTH), utilizado en redes de intercambio de archivos p2p , es un árbol Merkle con una función Tiger hash [2] . $hash(x)=\operatorname {SHA256} (\operatorname {SHA256} (x))$

Si el número de bloques en algún nivel del árbol resulta impar, entonces un bloque se duplica [1] o se transfiere sin cambios al siguiente nivel, como sucede cuando se calcula el Tiger Tree Hash [2] .

Eficiencia

Los árboles hash tienen una ventaja sobre las cadenas hash o las funciones hash. Cuando se utilizan árboles hash, es mucho menos costoso demostrar que un determinado bloque de datos pertenece al conjunto. Dado que los diferentes bloques suelen ser datos independientes, como transacciones o partes de archivos, estamos interesados en la capacidad de verificar solo un bloque sin volver a calcular hash para otros nodos del árbol. Deje que el bloque que nos interesa sea este (ver Fig.). Entonces la prueba de su existencia y validez será el hash raíz, así como los hash superiores de otras ramas ( y ) [1] [3] . En este caso, la comprobación falla si . $L_{3}$ ${autorización_{L}}_{4}=Hash_{11}$ ${autorización_{L}}_{2}=Hash_{0}$ $TopHash\neq hash(Hash_{0}+hash(hash(L_{3})+Hash_{11}))$

En general, se puede escribir

$signature(L)=(L\ |\ {auth_{L}}_{1},\dots,{auth_{L}}_{K-1})$ ,

y comprobar cómo , dónde $TopHash==Hash_{K}$

$Hash_{k}={\begin{cases}hash(L),&{\mbox{if }}k=1,\\hash(Hash_{k-1}+{auth_{L}}_{ k-1}),&{\mbox{if }}2\leq k\leq K\end{casos}}$ .

El conjunto de bloques se denomina ruta de autenticación o ruta Merkle [1] . $\{{auth_{L}}_{1},\dots,{auth_{L}}_{K-1}\}$

Se puede ver que la verificación anterior se puede realizar en pasos, donde es la altura del árbol o la longitud de la ruta de autenticación, y es el número de bloques de datos. La misma verificación en el caso de una cadena hash tendría complejidad [1] [4] . $O(K)=O(\log _{2}N)$ $k$ $norte$ $EN)$

La siguiente tabla demuestra que incluso con un número significativo de transacciones en un bloque, no tiene que preocuparse por la complejidad de los cálculos [1] .

Número de transacciones	Tamaño aproximado del bloque	Tamaño de la ruta (en hashes)	Tamaño de la ruta (en bytes)
16 transacciones	4 kilobytes	4 hashes	128 bytes
512 transacciones	128 kilobytes	9 hashes	288 bytes
2048 transacciones	512 kilobytes	11 hashes	352 bytes
65535 transacciones	16 megabytes	16 hashes	512 bytes

Verificación de pago simplificada

Un bloque de Bitcoin solo almacena el valor de merkle_rootsus transacciones. Esto le permite obtener ciertos beneficios y reducir la carga en la red.

Después de acumular una cantidad suficiente de bloques, las transacciones antiguas se pueden eliminar para ahorrar espacio. Al mismo tiempo, el bloque en sí permanece sin cambios, ya que almacena solo archivos merkle_root. Un bloque sin transacciones ocupa 80 B, o 4,2 MB por año (cuando se genera un bloque cada 10 minutos) [5] .

La verificación de pago simplificada se hace posible . El nodo SPV no descarga el bloque completo, sino solo el encabezado del bloque. Para la transacción que le interesa, también solicita su ruta de autenticación. Por lo tanto, descarga solo unos pocos kilobytes, mientras que el tamaño total del bloque puede ser de más de 10 megabytes (ver tabla) [1] . Sin embargo, el uso de este método requiere que el usuario confíe en el host desde el que consultar los encabezados de bloque. Una forma de evitar un ataque, es decir, la sustitución de un nodo por una parte sin escrúpulos, es enviar alertas a través de la red cuando se detecta un error en un bloque, obligando al usuario a descargar el bloque completo [5] .

El funcionamiento de los llamados clientes bitcoin "thin" [6] [7] se basa en la verificación de pago simplificada .

Extras

Problema de recorrido del árbol de Merkle

El árbol Merkle también tiene desventajas, que se manifiestan con un número creciente de hojas. Como se mostró anteriormente, para calcular la firma de un bloque arbitrario , debe conocer todos los valores del conjunto . Esto no es un problema si es posible almacenar todos los nodos internos del árbol en la memoria, pero para árboles grandes (el número de hojas puede aumentar hasta ) esto no es adecuado. También es posible recalcular los bloques internos cada vez, pero esto ralentizará significativamente el rendimiento de dicho sistema. Por lo tanto, surge el problema del recorrido eficiente del árbol y la generación de firmas ( problema del recorrido del árbol de Merkle ) [4] . Hasta la fecha, existen soluciones que utilizan el tiempo y la memoria, donde está el número de hojas. También se ha demostrado que no existe un algoritmo transversal que sea mejor tanto en tiempo como en memoria [8] . ${\ estilo de visualización L}$ $\{{auth_{L}}_{i}\}$ ${\ estilo de visualización 2^{40}}$ ${\ estilo de visualización 2 \ registro _ {2} (N)}$ ${\ estilo de visualización 3 \ registro _ {2} (N)}$ ${\ estilo de visualización N}$ ${\ estilo de visualización O (\ registro _ {2} (N))}$

Notas

↑ 1 2 3 4 5 6 7 8 9 Antonopoulos, Andreas M.,. Dominar bitcoin: desbloquear criptomonedas digitales . - Primera edición. — Sebastopol, CA. — xxi, 272 páginas p. — ISBN 9781449374044 . Archivado el 19 de enero de 2018 en Wayback Machine .
↑ 1 2 J. Chapweske , G. Mohr . Formato Tree Hash EXchange (THEX ) . cebolla redes inc. (4 de marzo de 2003). - El estándar para intercambiar árboles hash sobre archivos. Consultado el 8 de diciembre de 2017. Archivado desde el original el 4 de marzo de 2018.
↑ Einar Mykletun , Maithili Narasimha , Gene Tsudik . Proporcionar autenticación e integridad en bases de datos subcontratadas utilizando Merkle Hash Tree // ACM Transactions on Storage : Journal. - 2006. - Mayo ( vol. 2 , no. 2 ). - pág. 107-138 . Archivado desde el original el 19 de febrero de 2020.
↑ 1 2 Georg Becker, Ruhr-universität Bochum. Esquemas de firma de Merkle, árboles de Merkle y su criptoanálisis . Archivado el 14 de diciembre de 2017 en Wayback Machine .
↑ 1 2 Satoshi Nakamoto. Bitcoin: un sistema de efectivo digital peer-to-peer // bitcoin.org. Archivado desde el original el 5 de abril de 2018. (Ruso)
↑ Israa Alqassem, Davor Svetinovic. Hacia la arquitectura de referencia para las criptomonedas: análisis arquitectónico de Bitcoin // Conferencia internacional IEEE sobre Internet de las cosas ( iThings) e IEEE Green Computing and Communications (GreenCom) e IEEE Cyber, Physical and Social Computing (CPSCom): Revista. - 2014. - Septiembre. — ISBN 978-1-4799-5967-9 . -doi : 10.1109/ iCosas.2014.78 . Archivado desde el original el 2 de abril de 2018.
↑ Verificación de pago simplificada . Glosario de Bitcoin . Fecha de acceso: 7 de diciembre de 2017. Archivado desde el original el 7 de diciembre de 2017.
↑ Michael Szydlo. Merkle Tree Traversal in Log Space and Time (inglés) // Avances en criptología - EUROCRYPT 2004. - Springer, Berlín, Heidelberg, 2004-05-02. — pág. 541–554 . — ISBN 9783540219354 , 9783540246763 . -doi : 10.1007 / 978-3-540-24676-3_32 . Archivado desde el original el 15 de diciembre de 2017.

Véase también

Enlaces

Merkle Patricia Tree es una implementación mejorada del árbol Merkle utilizado en Ethereum.
Tiger Tree Torrent es una propuesta para reemplazar SHA-1 con Tiger Tree Hash en archivos .torrent .

Funciones hash
propósito general	Adler-32 CDN Suma de comprobación de Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Árbol de hachís picadillo de jenkins suma de hash
Criptográfico	Stribog GOST R 34.11-94 Cinturón BLAKE BMW CubeHash ECO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna Hachís de LM luffa MD2 MD4 MD5 MD6 N-hachís RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD RÁPIDO Piel Snefru Tigre Torbellino
Funciones de generación de claves	cripta PBKDF2 cripta Argón2 Lyra2
Número de cheque ( comparación )	Suma de verificación Algoritmo de Verhouff Algoritmo lunar Maldito algoritmo Código de barras cuentas bancarias tarjetas bancarias ES EN SNILES OKPO ESTAÑO OKATO ISBN OGRN y OGRNIP VIN
Hachís	Comparación de números de cheque Protocolos de autenticación Comparación de códigos de barras Criptografía Enlace magnético firma Merkle ed2k URNA

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión