¿Qué es un árbol Merkle?
El concepto de árbol de Merkle fue propuesto a principios de los años 80 por Ralph Merkle, un informático conocido por su trabajo sobre criptografía de clave pública.
Un árbol de Merkle es una estructura que se utiliza para verificar de manera eficiente la integridad de los datos en un conjunto. Son particularmente interesantes en el contexto de redes entre pares, donde los participantes necesitan compartir y validar información de forma independiente.
Las funciones hash son el núcleo de las estructuras de árbol de Merkle, por lo que le recomendamos que consulte ¿Qué es el hash? antes de continuar.
¿Cómo funcionan los árboles Merkle?
Supongamos que desea descargar un archivo grande. Con el software de código abierto, normalmente querrás comprobar que el hash del archivo que descargaste coincide con uno hecho público por los desarrolladores. Si es así, sabrás que el archivo que tienes en tu computadora es exactamente el mismo que el de ellos.
Si los hashes no coinciden, tienes un problema. O descargó un archivo malicioso que se hace pasar por el software o no se descargó correctamente y, por lo tanto, no funcionará. Si este último es el caso, probablemente no estará muy contento si ha tenido que esperar un tiempo para que se descargue el archivo. Ahora debe reiniciar el proceso y esperar que no se vuelva a dañar.
Piensas que si hubiera una manera más fácil de hacer esto. Afortunadamente, ahí es donde entran los árboles Merkle. Con uno de estos, su archivo se dividiría en partes. Si fuera un archivo de 50 GB, podría dividirlo en cien partes, de modo que cada una tenga un tamaño de 0,5 GB. Luego, se descargaría pieza por pieza. Esto es esencialmente lo que haces cuando descargas archivos torrent.
En este caso, su fuente le habrá proporcionado un hash conocido como raíz de Merkle. Este hash único es una representación de cada fragmento de datos que compone su archivo. Pero la raíz de Merkle hace que sea mucho más fácil verificar los datos.
Para simplificarlo, tomemos un ejemplo en el que utilizamos un archivo de 8 GB dividido en ocho partes. Llame a los diferentes fragmentos A a H. Luego, cada fragmento pasa a través de una función hash, lo que nos da ocho hashes diferentes.
Pasamos cada uno de nuestros ocho fragmentos a través de una función hash para obtener sus hashes.
Bien, entonces tenemos algo que tiene un poco más de sentido. Tenemos el hash de todos los fragmentos, así que si alguno está defectuoso lo sabremos comparándolo con el de la fuente, ¿verdad? Posiblemente, pero eso también es increíblemente ineficiente. Si su archivo tiene miles de fragmentos, ¿realmente los analizará todos y comparará meticulosamente los resultados?
No. En lugar de eso, tomaremos cada par de hashes, los combinaremos y luego los combinaremos. Entonces calculamos hA + hB, hC + hD, hE + hF y hG + hH. Terminamos con cuatro hashes. Luego hacemos otra ronda de hash con estos para terminar con dos. Finalmente, aplicamos hash a los dos restantes para llegar a nuestro hash maestro: la raíz de Merkle (o hash raíz).
La estructura parece un árbol al revés. En la fila inferior tenemos las hojas, que se combinan para producir los nudos y, finalmente, la raíz.
Ahora tenemos la raíz de Merkle que representa el archivo que descargamos. Podemos comparar este hash raíz con el proporcionado por la fuente. Si coincide, ¡perfecto! Pero si los hashes son diferentes, podemos estar seguros de que los datos fueron modificados. En otras palabras, uno o más fragmentos han producido un hash diferente. Por lo que cualquier ligera modificación de datos nos dará una raíz de Merkle totalmente diferente.
Afortunadamente, existe una forma práctica de comprobar qué fragmento es defectuoso. En nuestro caso, digamos que es él. Comenzaría preguntándole a un compañero por los dos hashes que produjeron la raíz de Merkle (hABCD y hEFGH). Su valor hABCD debe coincidir con el de ellos ya que no hay ningún error en ese subárbol. Pero hEFGH no lo hará, así que debes comprobarlo allí. Luego solicita hEF y hGH y las compara con las suyas. La hGH se verá bien, así que sepas que hEF es nuestro culpable. Por último, compara los hashes de hE y hF. Ahora sabes que hE es incorrecto, por lo que puedes volver a descargar ese fragmento.
Resumiendo todo, un árbol Merkle se crea dividiendo los datos en muchas partes, que luego se procesan repetidamente para formar la raíz de Merkle. Luego puede verificar de manera eficiente si algo salió mal con un dato. Como veremos en la siguiente sección, también existen otras aplicaciones interesantes.
¿Quiere empezar con las criptomonedas? ¡Compre Bitcoin en Binance!
¿Por qué se utilizan las raíces de Merkle en Bitcoin?
Hay varios casos de uso para los árboles Merkle, pero aquí nos centraremos en su importancia en las cadenas de bloques. Los árboles Merkle son esenciales en Bitcoin y muchas otras criptomonedas. Son un componente integral de cada bloque, donde 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 raíz de Merkle tiene un par de propósitos en este caso. Echemos un vistazo a sus 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 mayor que el encabezado.
Los mineros necesitan realizar hash de datos repetidamente para producir una salida que coincida con ciertas condiciones para extraer 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 igual. Puede haber miles de transacciones y aun así necesitarás realizar hash cada vez.
Una raíz de Merkle agiliza considerablemente el proceso. Cuando comienzas a minar, alineas todas las transacciones que deseas incluir y construyes un árbol Merkle. Colocas el hash raíz resultante (32 bytes) en el encabezado del bloque. Luego, cuando estés minando, solo necesitas aplicar hash al encabezado del bloque, en lugar de a todo el bloque.
Esto funciona porque es a prueba de manipulaciones. Resume efectivamente todas las transacciones del bloque en un formato compacto. No puede encontrar un encabezado de bloque válido y luego cambiar la lista de transacciones, porque eso cambiaría la raíz de Merkle. Cuando el bloque se envía a otros nodos, estos calculan la raíz a partir de la lista de transacciones. Si no coincide con el del encabezado, rechazan el bloqueo.
Verificación
Hay otra propiedad interesante de las raíces de Merkle que podemos aprovechar. Éste se refiere a los clientes ligeros (nodos que no contienen una copia completa de la cadena de bloques). Si está ejecutando un nodo en un dispositivo con recursos limitados, no querrá descargar ni procesar todas las transacciones de un bloque. En su lugar, lo que puede hacer es simplemente solicitar una prueba de Merkle: evidencia proporcionada por el nodo completo que demuestra que su transacción se encuentra en un bloque en particular. Esto se conoce más comúnmente como Verificación de Pago Simplificada, o SPV, y Satoshi Nakamoto lo detalló en el documento técnico de Bitcoin.
Para comprobar HD, sólo necesitamos los hashes que se muestran en rojo.
Considere 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 comprobar que la raíz de Merkle resultante coincide con la del encabezado del bloque. Si es así, es 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 tuvimos que aplicar hash tres veces. Sin una prueba de Merkle, habríamos necesitado hacerlo siete veces. Dado que hoy en día los bloques contienen miles de transacciones, el uso de pruebas de Merkle nos ahorra mucho tiempo y recursos informáticos.
Pensamientos finales
Los árboles Merkle 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 árboles Merkle permiten una fácil verificación de la información sin inundar la red con datos innecesarios.
Sin los árboles de Merkle (y las raíces de Merkle), los bloques de Bitcoin y otras criptomonedas no serían tan compactos como lo son hoy. Y aunque faltan clientes livianos 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.
