¿Qué es un árbol de Merkle?

Breve resumen

✔️ Un Merkle tree divide los datos, crea valores hash de estos datos y los fusiona en una estructura de árbol, lo que permite una verificación y transferencia eficaces.

✔️ Inventado por Ralph Merkle, el árbol de Merkle es un diagrama de árbol utilizado para la integridad de los datos.

✔️ Los árboles de Merkle se utilizan ampliamente en las tecnologías de cadena de bloques, como Bitcoin y Ethereum, donde ayudan a validar las transacciones y a reducir la carga de datos.

¿Qué es un Merkle tree?

El concepto de árbol de Merkle fue inventado por el matemático estadounidense Ralph Merkle y patentado en 1979. Así que el ex canciller alemán no tiene nada que ver con él. Fue descrito en el papers "Una firma digital certificada".

En el nombre Merkle tree, la última parte significa árbol. No es sin razón, ya que se trata de un diagrama de árbol, o modelo de ramificación, en el que cada vez más ramas conducen a una rama principal. Es similar al modelo de ramificación de un árbol genealógico.

Otro nombre para el Merkle tree es el hash tree. Un hash es un derivado algorítmico de una entrada, es decir, puedes extraer un hash (derivado) de, por ejemplo, una palabra (entrada) mediante un determinado sistema de algoritmos.

Un sistema muy conocido es el SHA (Secure Hash Algorithm) 256. Consiste en extraer un hash de 256 bits a partir de una entrada dada. El resultado (salida) se convierte entonces en una cadena de 64 dígitos y letras.

Un derivado típico del hash SHA 256:

"Anycoindirect" tiene como salida cuando ejecutas SHA 256 en él

98948d20dc70322d424ea5bbf37970e20b6aafa90c498116779ea964042c2c64

"anycoindirect" tiene como salida

a730a577d61512581afdd9c74e68abb2c43b0f7db3c70a92583464277b7abc81

Puedes ver que una sola letra mayúscula ya lo cambia todo. A partir de hashes como éste, se crea un árbol. Como en Navidad, ¿verdad?

¿Cómo funciona un Merkle tree?

Supón que quieres enviar un mensaje o un archivo a otra persona, pero no quieres que otros puedan verlo. Podría tratarse de información secreta, como una contraseña, pero también de compartir un archivo con información importante. En ese caso, puedes utilizar SHA 256 para cifrar el mensaje.

Un mensaje se divide en trozos y se convierte en un hash. Cada hash aparece en el árbol, con la raíz en la parte superior del árbol. Éste es el mensaje o archivo completo. Una gran ventaja es que el mensaje puede dividirse en trozos pequeños, lo que significa que los archivos enormes no tienen que ser entregados en su totalidad por un solo ordenador y puede hacerse mucho más rápido.

Así que el árbol se construye de abajo arriba, de forma muy parecida a como se hace con Bittorrent. Todo el mundo tiene entonces un pequeño trozo del archivo (redes peer to peer) y en el extremo del usuario final, se vuelven a unir todos los trozos pequeños, tras lo cual el árbol vuelve a estar completo. Entonces el usuario final puede calcular con su Merkle tree si todos los trozos son originales (los hashes que se pueden calcular deben coincidir entonces con su tabla).

La raíz tiene un resultado concreto, por lo que si la conoce, también sabrá si el mensaje o el archivo son originales. En cuanto no lo sean, se hará un nuevo intento de recibir el original. Cuando el árbol raíz y el resultado coincidan en tu caso, habrás recibido la información correcta.

Arriba hemos explicado cómo crear un hash. En el diagrama de árbol, algunas de estas salidas se fusionan y se colocan en un nuevo hash utilizando el mismo método. Así, a medida que llegues a la parte superior del árbol, aparecerá cada vez más información en un hash superior. Hasta que llegas a la cima y fusionas todos los hashes del árbol en 1 hash, tras lo cual estás listo para enviar la información.

Al receptor del mensaje se le comunica el árbol raíz y empieza a descargar las ramas, los hashes. Estas ramas pueden proceder de múltiples fuentes. Después, empieza a reconstruir todos los hashes del árbol. Cada parte del árbol debe ser correcta, en cuanto no lo sea, el árbol raíz no es correcto, pero mediante la reconstrucción puede determinar qué parte no es correcta. Entonces suele intentar descargar de nuevo todo el árbol.

Como estos árboles de Merkle trabajan con datos binarios, también se llaman árboles binarios.

¿Para qué se utilizan los árboles de Merkle en crypto?

Ahora que sabes que para comprobar la corrección de un hash, en realidad sólo necesitas conocer el árbol raíz, puedes imaginar que podría haber sistemas que hagan uso de esto.

Una cadena de bloques importante que lo utiliza es Bitcoin. En esta cadena de bloques, hay que procesar mucha información en un bloque. Cuanta menos información haya que comprobar e introducir en un bloque, mejor.

Como un Merkle tree puede agregar bastantes datos en un solo número, esto es muy útil a la hora de construir un bloque.

Supongamos que has procesado 200 transacciones como Miner en los últimos 10 minutos (se añade un nuevo bloque a la red Bitcoin aproximadamente cada 10 minutos). Entonces el Merkle tree se pone a trabajar reduciendo todas estas transacciones en un único árbol raíz.

Los validadores de la red Bitcoin tienen que seguir el estado de la cadena de bloques, validar las transacciones y añadir nuevas monedas. Si sólo tienen que comprobar que 1 secuencia es correcta, no sólo son mucho más rápidos, sino que además un block es mucho más pequeño. Si el 51% de estos mineros están de acuerdo en que el árbol raíz es correcto, el bloque puede añadirse.

Este hash del árbol raíz se coloca al principio del siguiente bloque, de modo que todos los mineros conocen el valor del hash del bloque anterior. Así, cuando crean un nuevo bloque, establecen todo el estado de la red con una sola cadena de cifrado. Luego se añaden nuevas transacciones, que pasan por el mismo proceso y así sucesivamente. Si el árbol raíz no es correcto, por ejemplo porque hay registros deshonestos entre ellos, los mineros tampoco pueden ponerse de acuerdo y empiezan a buscar un Merkle tree con el árbol raíz correcto. Ethereum también utiliza un árbol de Merkle, pero, por supuesto, volvieron a inventar algo especial: el árbol de Merkle Patricia.

Si las redes no utilizaran árboles de Merkle, habría que transmitir todos los datos y puedes imaginar lo que eso supondría para la velocidad, por no hablar de la seguridad.