Una introducción al árbol de Merkel: ¿Qué es y cómo funciona?

Un Merkle Tree es un árbol binario de valores hash, donde cada nodo de hoja representa un solo dato o un hash de un dato. Se utiliza para verificar la integridad de grandes cantidades de datos de manera eficiente. Fue inventado por Ralph Merkle en 1979 y es ampliamente utilizado en criptomonedas como Bitcoin y Ethereum.

Una función hash es como una máquina de huellas dactilares. Toma cualquier entrada, como un archivo, un texto o un número, y produce una salida única, llamada hash, que es mucho más corta que la entrada. El hash es como una huella digital de la entrada. Es difícil encontrar dos entradas diferentes que tengan el mismo hash. Y es imposible obtener la entrada original del hash.

Por ejemplo, si tiene un archivo llamado " kishan.jpg " que tiene un tamaño de 1 MB, puede usar una función hash para obtener un hash de solo 64 caracteres, como 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F .

Si cambia incluso un píxel en el archivo, el hash será completamente diferente, como C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF .

Entonces puede usar el hash para verificar que el archivo sea el mismo que antes.

Pero, ¿y si tienes muchos archivos? Calcular y almacenar el hash para cada archivo por separado sería tedioso. Ahí es donde los árboles de Merkle son útiles.

Un árbol de Merkle es como un árbol genealógico de hachís. Comienza con los valores hash de cada archivo como las hojas del árbol . Luego empareja los hashes y los combina para obtener nuevos hashes. Repites este proceso hasta llegar a la parte superior del árbol, donde solo te queda un hash. Este hash se llama raíz de Merkle .

La raíz de Merkle es como una huella digital de todos los archivos del árbol. Si algún archivo cambia, su hash cambiará, al igual que todos los hash que se encuentran por encima de él hasta que cambie la raíz de Merkle . Entonces puede usar la raíz de Merkle para verificar que todos los archivos sean los mismos que antes.

Pero, ¿cómo se verifica un archivo específico? No necesita descargar y verificar todos los archivos en el árbol. Solo necesita descargar y verificar algunos hashes a lo largo de la ruta desde el archivo hasta la raíz de Merkle. Este camino se llama prueba de Merkle .

Por ejemplo, suponga que desea verificar si el archivo "cat.jpg" es correcto. Solo necesita descargar su hash HA , que es 0a6df4 , el hash HB (ea12e7) , el hash H CD (b582ae) y la raíz Merkle H ABCD (7bd24f) .

Luego puede calcular H AB combinando HA y HB y calcular H ABCD combinando H AB y H CD. Si H ABCD coincide con la raíz de Merkle, puede estar seguro de que " cat.jpg " es correcto.

Puede usar la misma analogía para verificar si la transacción presente en el bloque está atenuada verificando la raíz de Merkle en lugar de cat.jpg o dog.txt. Será un montón de transacciones en los nodos hoja.

Tenga en cuenta: he truncado el valor hash a 6 caracteres en el ejemplo anterior para que el diagrama se vea limpio.

¿Qué sucede si solo tengo tres nodos de hoja? ¿Cómo crearé un Merkle Tree?

Este escenario se puede abordar rápidamente duplicando un nodo, lo que hace que el número total de nodos sea cuatro.

Por ejemplo, suponga que tiene transacciones. TA , TB y TC . Puedes calcular sus hashes. HA , HB y HC . Luego puede duplicar HC para obtener H C' . Después; puede emparejar y combinar los hashes para obtener H AB , H CC' y H ABCC' . La raíz de Merkle es H ABCC' .

En resumen, los árboles Merkle benefician a blockchain y otros sistemas distribuidos, donde muchas computadoras deben compartir y verificar grandes cantidades de datos. Mediante el uso de árboles de Merkle, pueden ahorrar ancho de banda, almacenamiento y tiempo de cálculo.

Aquí hay un ejemplo rápido de Java para mostrar cómo puede crear su propio árbol de Merkle:

 import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; class MerkleTree{ static class Node { String content; public Node(String content) { this.content = content; } public String getHash() throws NoSuchAlgorithmException { MessageDigest md = MessageDigest.getInstance("SHA-256"); byte[] hash = md.digest(content.getBytes(StandardCharsets.UTF_8)); StringBuilder buffer = new StringBuilder(); for (byte b : hash) { buffer.append(String.format("%02x", b)); } return buffer.toString(); } } public static void main(String[] args) throws NoSuchAlgorithmException{ Node cat = new Node("I am a cat, this is a cat file called cat.jpg"); Node dog = new Node("I am a dog, this is a dog file called dog.txt"); // we have two leaf nodes, in order to create a merkle root, // we simple need to get their individual hashes // and then combine those hashes and hash them again String HA = cat.getHash(); String HB = dog.getHash(); Node merkleRoot = new Node(HA + HB); String HAB = merkleRoot.getHash(); System.out.println("Merkle Root: " + merkleRoot.getHash()); // let's say we altered the cat file cat = new Node("I am a cat, this is a cat file called dog.jpg"); // notice we have changed the cat.jpg to dog.jpg String HA_MODIFIED = cat.getHash(); Node modifiedMerkleRoot = new Node(HA_MODIFIED + HB); String HAB_MODIFIED = modifiedMerkleRoot.getHash(); System.out.println("Merkle Root: " + HAB_MODIFIED); } }

Producción:

 Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e

Le agradezco por tomarse el tiempo de leer mi artículo. Apóyame siguiéndome en Hackernoon para que te notifiquen cada vez que publique un artículo.

Muchas gracias.

Sumérjase en artículos perspicaces sobre sistemas descentralizados, tecnología y tendencias de IA: https://www.0xkishan.com . Visite para mostrar su apoyo.

También publicado aquí.