El concepto de Merkle tree (árbol de Merkle) fue propuesto a principios de los 80 por Ralph Merkle –un científico informático famoso por sus trabajos sobre
criptografía de clave pública.
Un árbol de Merkle es una estructura utilizada para verificar de manera eficiente la integridad de un conjunto de datos. Resulta especialmente interesante en el marco de las redes
peer-to-peer, en las que los participantes deben compartir y validar de manera independiente información.
Las funciones hash son una parte fundamental de las estructuras de tipo Merkle tree, por lo que te recomendamos que le eches un vistazo a
¿Qué es el Hashing? antes de proseguir.
Supongamos que deseas descargar un archivo grande. En el caso de un
software de código abierto, normalmente querrás comprobar que el hash del archivo descargado coincida con el que han hecho público los desarrolladores. Si coincide, sabrás que el archivo que tienes en el ordenador es exactamente el mismo que el de ellos.
Si los hashes no coinciden, tendrás un problema. O bien habrás descargado un archivo malicioso que se hace pasar por el software, o bien no lo habrás descargado correctamente y, por tanto, no funcionará. En este segundo caso, seguramente no estarás muy satisfecho, tras haber tenido que dedicar cierto tiempo a descargar el archivo. Ahora, deberás reiniciar el proceso y confiar en que no vuelva a corromperse.
"Si existiera una forma más sencilla de abordar esta cuestión...", pensarás. Afortunadamente, ahí es donde entran en juego los Merkle trees. Con uno de ellos, tu archivo acaba dividido en fragmentos. Si se trata de un archivo de 50GB, podrías dividirlo en cien fragmentos, para que cada uno tenga un tamaño de 0.5GB. A continuación, éste sería descargado por partes, una a una. Esto es básicamente lo que se hace con los archivos torrent.
En este caso, tu fuente te habrá proporcionado un hash conocido como Merkle root (raíz de Merkle). Este hash individual es una representación de cada uno de los fragmentos de los datos que componen el archivo. Pero la Merkle root hace que resulte mucho más fácil verificar los datos.
Para no complicarnos, pongamos por caso que tenemos un archivo de 8GB que dividimos en ocho fragmentos. Denominaremos a los distintos fragmentos con una letra, de la A a la H. Cada fragmento se pasará por un función hash, lo que nos dará ocho hashes distintos.
Pasamos cada uno de nuestros ocho fragmentos por una función hash, para así obtener sus respectivos hashes.
Bien, ahora ya tenemos algo un poco más razonable. Disponemos del hash de todos los fragmentos, así que si uno es erróneo, lo sabremos al compararlo con el hash de la fuente, ¿no es así? Es una posibilidad, pero sumamente ineficiente. Si tu archivo dispone de miles de fragmentos, ¿vas a someter a hash cada uno de ellos y, meticulosamente, comparar los resultados?
No. En su lugar, lo que haremos es tomar cada par de hashes, combinarlos y someterlos a hash los dos juntos. De esta forma, haremos hashing con hA + hB, hC + hD, hE + hF y hG + hH. Y terminamos con cuatro hashes. A continuación, realizamos otra ronda de hashing con éstos, para acabar teniendo dos. Finalmente, sometemos a hash los dos que quedan, para así obtener nuestro hash maestro – la Merkle root (o hash raíz).
La estructura tiene aspecto de un árbol invertido. En la fila de abajo del todo se encuentran las hojas, que se combinan para producir los nodos, y, finalmente, la raíz.
Ahora ya tenemos la Merkle root (raíz de Merkle) que representa el archivo que hemos descargado. Podemos comparar este hash raíz con el que nos ha proporcionado la fuente. Si coinciden, ¡perfecto! Pero si los hashes son distintos, tendremos la certeza de que los datos han sido modificados. En otras palabras, un fragmento o más de uno habrá producido un hash distinto. Y es que cualquier ligera modificación de los datos nos proporcionará una Merkle root totalmente distinta.
Afortunadamente, contamos con una manera práctica de comprobar qué fragmento es erróneo. En nuestro caso, digamos que se trata de hE. Lo primero que haría uno es solicitarle a un par (peer) los dos hashes que produjeron la Merkle root (hABCD y hEFGH). Tu valor hABCD debería coincidir con el de ellos, dado que no hay ningún error en ese subtree. Pero hEFGH no coincidirá, así que sabes que habrá que mirar ahí. Solicitas a continuación hEF y hGH, y los comparas con los tuyos. hGH estará bien, por lo que sabrás que hEF es el culpable. Finalmente, compararás los hashes de hE y hF. Ahora sabrás que hE es incorrecto, por lo que podrás descargar de nuevo esa parte.
Resumiendo todo esto, se crea un Merkle tree dividiendo los datos en muchas partes, que luego se hashean repetidamente para formar la Merkle root. Luego puedes verificar eficientemente si algo ha salido mal con una pieza de datos. Como veremos en la siguiente sección, también hay otras aplicaciones interesantes.
¿Estás buscando comenzar con las criptomonedas? ¡Compra Bitcoin en Binance!
Hay un puñado de casos de uso para los Merkle trees, pero aquí nos centraremos en su importancia en
blockchains. Los Merkle trees son esenciales en
Bitcoin y muchas otras criptomonedas. Son un componente integral de cada
bloque, que se pueden encontrar en los
encabezados de los bloques. Para obtener las hojas de nuestro árbol, utilizamos el hash de transacción (el
TXID) de cada transacción incluida en el bloque.
La Merkle root sirve para un par de propósitos en este caso. Echemos un vistazo a tus aplicaciones en minería de criptomonedas y verificación de transacciones.
Minería
Un bloque de Bitcoin se compone de dos piezas. La primera parte es el encabezado del bloque, un segmento de tamaño fijo que contiene
metadatos para el bloque. La segunda parte es una lista de transacciones cuyo tamaño es variable, pero tiende a ser mucho más grande que el encabezado.
Los mineros necesitan hash repetidamente datos para producir una salida que coincida con ciertas condiciones para minar un bloque válido. Pueden hacer billones de intentos antes de encontrar uno. Con cada intento, cambian un número aleatorio en el encabezado del bloque (el
nonce) para producir una salida diferente. Pero gran parte del bloque sigue siendo el mismo. Puede haber miles de transacciones, y aún necesitarías hacer hashearlas cada vez.
Una Merkle root agiliza el proceso considerablemente. Cuando comienzas a minar, alinea todas las transacciones que deseas incluir y construye un Merkle tree. Pones el hash raíz resultante (32 bytes) en el encabezado del bloque. Luego, cuando estás minando, solo necesitas hash el encabezado del bloque, en lugar de todo el bloque.
Esto funciona porque es a prueba de manipulaciones. Resume de manera efectiva todas las transacciones del bloque en un formato compacto. No puedes encontrar un encabezado de bloque válido y luego cambiar la lista de transacciones, porque eso cambiaría la Merkle root. Cuando el bloque se envía a otros nodos, calculan la raíz de la lista de transacciones. Si no coincide con el del encabezado, rechazan el bloque.
Verificación
Hay otra propiedad interesante de las Merkle roots que podemos aprovechar. Este se refiere a los clientes ligeros (nodos que no tienen una copia completa de la blockchain). Si estás ejecutando un nodo en un dispositivo con recursos limitados, no deseas descargar y hashear todas las transacciones de un bloque. Lo que puedes hacer en su lugar es simplemente solicitar una prueba de Merkle: evidencia proporcionada por el nodo completo que demuestra que tu transacción se encuentra en un bloque en particular. Esto se conoce más comúnmente como Verificación de pago simplificado, o SPV, y fue detallado por
Satoshi Nakamoto en el whitepaper de Bitcoin.
Para comprobar hD, solo necesitamos los hashes mostrados en rojo.
Considera el escenario en el que queremos conocer información sobre la transacción cuyo TXID es hD. Si se nos proporciona hC, podemos calcular hCD. Entonces, necesitamos hAB para calcular hABCD. Por último, con hEFGH, podemos verificar que la Merkle root resultante coincida con la del encabezado del bloque. Si lo hace, es una prueba de que la transacción se incluyó en el bloque; sería casi imposible crear el mismo hash con datos diferentes.
En el ejemplo anterior, solo hemos tenido que hacer hash tres veces. Sin una prueba de Merkle, habríamos tenido que hacerlo siete veces. Dado que hoy en día los bloques contienen miles de transacciones, el uso de las pruebas de Merkle nos ahorra mucho tiempo y recursos informáticos.
Los Merkle trees han demostrado ser muy útiles en una variedad de aplicaciones informáticas: como hemos visto, son increíblemente valiosos en blockchains. En los sistemas distribuidos, los Merkle trees permiten una fácil verificación de la información sin inundar la red con datos innecesarios.
Sin los Merkle trees (y las Merkle roots), los bloques de
Bitcoin y otras
criptomonedas no serían tan compactos como lo son hoy. Y aunque faltan clientes ligeros en los frentes de privacidad y seguridad, las pruebas de Merkle permiten a los usuarios verificar si sus transacciones se han incluido en un bloque con una sobrecarga mínima.
