Árbol de Merkle
Un árbol de Merkle es una estructura de datos en árbol, binario o no, en el que cada nodo se une con otro para calcular un nodo superior. Cada dos hojas se crea una de orden superior. Por eso se le llama binario, «bi» de dos. Cada dos hijos se crea un nodo superior. La base del árbol son las transacciones A,B,C,D,E,F,G,H que hacen los usuarios. Cada dos transacciones se crea un nodo superior, y así sucesivamente hasta llegar a la copa del árbol. Toda la información está encriptada con el algoritmo SHA-256
Esta estructura de Merkle permite que gran número de datos separados puedan ser ligados a un único valor de hash, el hash del nodo raíz del árbol, llamado Merkle root. De esta forma proporciona un método de verificación segura y eficiente de los contenidos de grandes estructuras de datos. En sus aplicaciones prácticas normalmente el hash del nodo raíz va firmado (con clave pública y privada) para asegurar su integridad, para que la verificación sea totalmente fiable. La demostración de que un nodo hoja es parte de un árbol hash dado requiere una cantidad de datos proporcional al logaritmo en base 2 del número de nodos del árbol.
Log22400 = 11,228
En nuestro caso como que el logaritmo en base 2 de 2400 es menor de 12. De esta forma, para verificar si una transacción existe en el bloque o verificar que es correcta y no la han modificado, es muy fácil: 1) el algoritmo nos envía la Merkle proof, la cual es un resumen pequeñito con la transaccón y sus parientes hasta llegar a la merkle root o la cúpula del árbol. 2) Si el cálculo de la root de esa Merkle proof, coincide con la Merkle root, es todo perfecto. Esxe arbolito de Merkle proof es muy pequeñito (unas 12 hojas). El esquema de abajo es una imagen metafórica de la Merkle proof. La realidad de la Merkle proof variará dependiendo de la Transacción a buscar o comprobar y sus parientes hasta llegar a la copa del árbol (Merkle root)
Gracias a esta estructura única, los árboles de Merkle permiten comproabr una gran cantidad de datos en un único punto (Merkle root) y unos pocos nodos. De esta forma, la verificación y validación de esos datos puede pasar a ser muy eficiente, al tener que verificar únicamente el Merkle root y unos pocos nodos en lugar de toda la estructura.
Este diseño fue creado por Ralph Merkle, en el año 1979, con el fin de agilizar el proceso de verificación de grandes cantidades de datos.
Los árboles de Merkle son muy eficientes a la hora de verificar grandes cantidades de información. Esto es así gracias a que su estructura estratificada permite relacionar un único punto (nodo raíz o Merkle root) junto a unos pocos nodos del árbol con una serie de datos superiores. De esta forma, al verificar la validez de la raiz de Merkle o raiz del árbol podemos estar seguros de la validez del resto del árbol.
¿Cómo funcionan?
El funcionamiento de un árbol de Merkle reside en la capacidad de resumir una gran cantidad de datos en un único bloque de datos verificable. Para lograr esto, los árboles de Merkle hacen uso intensivo de las funciones de hashing entre todos sus nodos, hasta llegar a un único hash derivado del resto. Dicho hash o resumen de todo el árbol es la cabecera del árbol.
Este proceso de hashing se realiza desde abajo hacia arriba, a partir de los hashes que identifican a cada nodo. Es decir las 2400 transacciones tienen un solo hash cada una. Cogiendo de 2 en 2 se va creando el árbol binario hasta llegar a la raiz del árbol o Merkle root.
A cada nodo, se le aplica el algoritmo SHA-256 para calcular el hash del nodo. De esta forma el hash es único e irrepetible.
Se le llama algoritmo SHA 256 porque son 256 bits. Es decir 256/8 = 32 bytes Esos 32 bytes estarán representados en 64 caracteres en código hexadecimal porque cada letra ( 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f) son 4 bits.
Aquí tenéis un enlace para calcular el hash, con el algoritmo SHA 256, de cualquier cosa que escribáis.
https://cutt.ly/UxSzsU0
Por ejemplo la palabra Hola en SHA 256 es el hash E633F4FC79BADEA1DC5DB970CF397C8248BAC47CC3ACF9915BA60B5D76B0E88F
que son 64 caracteres. Cada carácter son 4 bits:
La E6 es el byte 1110 0110 porque: la E es el número 14 . El 14 en binario es el 1110 y el 6 en binario es el 0110
La primera columna es en código decimal, la segunda en hexadecimal y la tercera en binario con 4 bits.
| 0 (en código decimal) | 0 (en código hexadecimal) | 0 (en binario con 4 bits) |
| 1 | 1 | 0001 |
| 2 | 2 | 0010 |
| 3 | 3 | 0011 |
| 4 | 4 | 0100 |
| 5 | 5 | 0101 |
| 6 | 6 | 0110 |
| 7 | 7 | 0111 |
| 8 | 8 | 1000 |
| 9 | 9 | 1001 |
| 10 | A | 1010 |
| 11 | B | 1011 |
| 12 | C | 1100 |
| 13 | D | 1101 |
| 14 | E | 1110 |
| 15 | F | 1111 |
