El artículo Vocabulario de la wiki de Bitcoin explica por qué existe la raíz de Merkle:
Cada transacción tiene un hash asociado. En un bloque, todos los hash de transacciones en el bloque se codifican (a veces varias veces; el proceso exacto es complejo), y el resultado es la raíz de Merkle. En otras palabras, la raíz de Merkle es el hash de todos los hash de todas las transacciones en el bloque. La raíz de Merkle se incluye en el encabezado del bloque. Con este esquema, es posible verificar de forma segura que la red ha aceptado una transacción (y obtener el número de confirmaciones) descargando solo los encabezados de bloque diminutos y el árbol de Merkle; no es necesario descargar toda la cadena de bloques. Esta función no se usa actualmente en Bitcoin, pero lo hará en el futuro.
¿Cómo puede verificar si una transacción se ha verificado solo con las raíces de Merkle? ¿Cómo funciona ese mecanismo?
La idea (según tengo entendido) es que el árbol de Merkle le permite verificar las transacciones según sea necesario y no incluir el cuerpo de cada transacción en el encabezado del bloque, al mismo tiempo que proporciona una forma de verificar toda la cadena de bloques (y, por lo tanto, la prueba de trabajo). ) en cada transacción.
Para entender esto, primero entienda el concepto de un árbol. Considere un bloque de 8 transacciones. Imagina cada una de esas 8 transacciones en la base de una pirámide: estas se llaman hojas. Coloque cuatro "ramas" en el segundo nivel de la pirámide y dibuje dos líneas desde cada una de ellas hasta las hojas para que cada rama tenga dos hojas unidas. Ahora une esas cuatro ramas a dos ramas en el nivel 3 de la pirámide y hasta una rama (lo que se llama la raíz del árbol) en la parte superior de la pirámide. (Nuestro árbol está creciendo al revés en este ejemplo).
Ahora podemos empezar a entender el proceso de hashing. Haga un hash de los hashes de las "hojas" e inclúyalos como parte de las ramas de segundo nivel a las que se adjuntan esas hojas (estos se denominan nodos secundarios y nodos principales). Ahora haga un hash de los hash de esos hash e inclúyalo como parte de las ramas de tercer nivel. Y así. (Y si tuvo más de 8 transacciones, todo lo que necesita son más niveles en la pirámide).
Ahora tiene un nodo raíz que efectivamente tiene un hash que verifica la integridad de todas las transacciones. Si se agrega/elimina o cambia una transacción, cambiará el hash de su padre. Lo que cambiará el hash de su padre, y así sucesivamente, lo que dará como resultado que el hash del nodo raíz (que es la raíz de Merkle) también cambie.
Entonces, ¿cómo nos ayuda esto a no tener que tener toda la cadena de bloques? Porque pudimos verificar las transacciones según fuera necesario. Si tenemos una transacción que afirma haber sido del bloque #234133, podemos obtener las transacciones de ese bloque, verificar el árbol de Merkle y saber que la transacción es válida. Podemos hacerlo sin conocer necesariamente todas las transacciones de #234132 o #234134 porque sabemos que los bloques son a prueba de manipulaciones.
Aún mejor, si sabemos dónde está en el árbol de Merkle y conocemos los valores hash de las ramas, ni siquiera necesitamos todas las transacciones de #234132. (Había 868 en ese bloque). Comenzamos solo con nuestra transacción y su hermano (si tiene uno) y calculamos el hash de esos dos y verificamos que coincida con el valor esperado. A partir de eso, podemos pedir la rama hermana de eso y calcular el hash de eso y verificarlo. Y continúa con este proceso, arriba del árbol. Lo que solo requiere diez verificaciones para 868 transacciones. (Esa es una de las mejores cosas de los árboles, pueden contener muchos valores con solo una cantidad relativamente pequeña de capas).
¿Cómo sabemos que la fuente de estos datos no nos miente sobre los valores hash? Debido a que una función hash es unidireccional, no hay forma de que una parte engañosa pueda adivinar un valor que haría hash con nuestro penúltimo valor para crear la raíz de Merkle. (Lo que sabemos por nuestra cadena de bloques verificada). Este razonamiento se mantiene más abajo en el árbol: no hay forma de crear un valor falso que se convierta en nuestro valor esperado. Otra forma de verlo es que incluso una sola alteración de una transacción en la base del árbol daría como resultado un cambio en cadena en todos los valores hash de los nodos en su rama hasta el valor hash de la raíz.
En resumen, el árbol de Merkle crea un valor único que prueba la integridad de todas las transacciones en él. Satoshi podría haber incluido el hash de una gran lista de todas las transacciones en el encabezado de Bitcoin. Pero si hubiera hecho eso, habría requerido que usted hiciera un hash de la lista completa de transacciones para verificar su integridad. De esta manera, incluso si hay una cantidad extremadamente grande de transacciones, el trabajo que necesita hacer (y la cantidad de hashes que necesita solicitar/descargar) para verificar la integridad es solo registro (O).
[Como siempre, siéntete libre de editar esto. Esto es principalmente solo una inferencia de mi parte al mirar la especificación.]
"Figura 7-2. Cálculo de los nodos en un árbol merkle" de Mastering Bitcoin muestra la raíz Merkle (H ABCD ) de una lista de cuatro transacciones: Tx A, Tx B, Tx C y Tx D:
Si H K conduce a la raíz de Merkle correcta, entonces T K estaba en la lista de transacciones.
Y la ruta de Merkle , necesaria para verificar que Hk se corresponde con la raíz de Merkle, solo contiene 4 hashes en el ejemplo anterior. La ruta de Merkle ocupa mucho menos espacio que almacenar todas las transacciones en un bloque. (En el ejemplo anterior: 4 hashes ocupan mucho menos espacio que 16). Es por eso que SPV es más liviano.
En este caso N = 16, y 2*log 2 (16) = 5.55… es de hecho menor que 16.
y=2log(N)/log(2)
vs y=N
.No es cierto que use solo la raíz de merkle (ni el artículo dice eso). Más bien, usa solo las partes del árbol merkle que se relacionan con su transacción. Eso incluye la raíz.
Esta puede ser una buena introducción. Ripple puede estar usando el árbol Merkle, pero no estoy seguro: http://en.m.wikipedia.org/wiki/Hash_tree También verifique esto: https://stackoverflow.com/questions/5486304/explain-merkle-trees-for -uso-en-consistencia-eventual
El Merkle Root, tal como lo entiendo, es básicamente un hash de muchos hashes (buen ejemplo aquí ): para crear un Merkle Root, debe comenzar tomando un hash doble SHA-256 de los flujos de bytes de las transacciones en el bloque. Sin embargo, qué son estos datos (los flujos de bytes), cómo se ven y de dónde provienen sigue siendo un misterio para mí.
¡SÉ CONSCIENTE! La raíz de merkle es importante para la minería. dado que la raíz de merkle es el valor hash de TODOS los hash de transacciones del bloque, el valor de la raíz de merkle se tiene en cuenta cuando los mineros hacen su trabajo. Ver: https://en.bitcoin.it/wiki/Block_hashing_algorithm . Hachís anterior:
81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000
Aquí un extracto del algoritmo allí:
>>> import hashlib
>>> header_hex = ("01000000" +
"81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000" +
"e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b" +
"c7f5d74d" +
"f2b9441a" +
"42a14695")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
>>> hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'
En primer lugar, todos los valores aquí están en notación little endian, por lo que debe preparar byte por byte de derecha a izquierda (recuerde que un byte son DOS caracteres). Entonces, el primer valor es el hash del bloque anterior, luego THE MERKLE ROOT, luego el tiempo de creación y luego los bits. Para comparar los valores, solo eche un vistazo a: https://blockexplorer.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d
Conclusión: ¡la cadena de bloques de bitcoin utiliza implícitamente la raíz de merkle! ¡Desempeña un papel importante cuando se trata de minería!
RT Denver