¿Qué son los Árboles Merkle?
El concepto de árboles Merkle fue propuesto a principios de los años 80 por Ralph Merkle, un científico informático reconocido por su trabajo en criptografía de clave pública.Un árbol 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 las redes peer-to-peer, donde los participantes necesitan compartir y validar información de forma independiente.
Las funciones hash están en el núcleo de las estructuras del árbol Merkle, por lo que le recomendamos que consulte ¿Qué es el hash? antes de continuar.
¿Cómo Funcionan los Árboles Merkle?
Suponga 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 que los desarrolladores hicieron público. Si es así, sabrá que el archivo que tiene en su computadora es exactamente el mismo que el de ellos.
Si los hashes no coinciden, tienes un problema. Ha descargado un archivo malicioso que se hace pasar por el software o no se ha descargado 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 corrompa nuevamente.
Si tan solo hubiera una manera más fácil de hacer esto, piensas. Afortunadamente, ahí es donde entran los árboles Merkle. Con uno de estos, su archivo se dividiría en pedazos. Si fuera un archivo de 50 GB, puede 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 usas archivos torrent.
En este caso, su fuente le habrá proporcionado un hash conocido como raíz de Merkle. Este único hash es una representación de cada fragmento de datos que componen su archivo. Pero la raíz de Merkle hace que sea mucho más fácil verificar los datos.
Ejemplo de Árboles Merkle
Para simplificarlo, tomemos un ejemplo en el que usamos un archivo de 8 GB dividido en ocho partes. Llame a los diferentes fragmentos A a través de H. Luego, cada fragmento se pasa a través de una función hash, lo que nos da ocho hash diferentes.
Bien, 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 va a hacer un hash de todos ellos y comparar meticulosamente los resultados?
No. En su lugar, vamos a tomar cada par de hashes, combinarlos y luego mezclarlos juntos. Así que hash hA + hB, hC + hD, hE + hF y hG + hH. Terminamos con cuatro hashes. Luego hacemos otra ronda de hashing 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 de 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. Entonces, cualquier pequeña modificación de los datos nos dará una raíz de Merkle totalmente diferente.
Afortunadamente, tenemos una forma práctica de comprobar qué fragmento está defectuoso. En nuestro caso, digamos que es él. Comenzaría preguntando a un par 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 registrarte allí. Luego solicita hEF y hGH y los compara con los suyos. hGH se verá bien, por lo que sabe que hEF es nuestro culpable. Por último, compara los valores hash de hE y hF. Ahora ya sabe que hE es incorrecta, por lo que puede volver a descargar ese fragmento.
Resumiendo todo, se crea un árbol Merkle dividiendo los datos en muchas partes, que luego se procesan repetidamente para formar la raíz Merkle. Luego, puede verificar de manera eficiente si algo ha salido mal con un dato. Como veremos en la siguiente sección, también hay otras aplicaciones interesantes.
¿Por Qué se Utilizan las Raíces de Merkle en Bitcoin?
Hay algunos casos de uso para los árboles de 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, usamos el hash de transacción (el TXID) de cada transacción incluida en el bloque.
La raíz de Merkle sirve para un par de propósitos en este caso. Echemos un vistazo a sus aplicaciones en la minería de criptomonedas y la 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 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 para producir una salida diferente. Pero gran parte del bloque sigue siendo el mismo. Puede haber miles de transacciones, y aún así necesitará hacer un hash cada vez.
Una raíz de Merkle agiliza considerablemente el proceso. Cuando comienza a minar, alinea todas las transacciones que desea incluir y construye un árbol Merkle. Pones el hash raíz resultante (32 bytes) en el encabezado del bloque. Luego, cuando esté extrayendo, solo necesita hash en el encabezado del bloque, en lugar de todo el bloque.
Esto funciona porque es a prueba de manipulaciones. Efectivamente, resume 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, 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 raíces de Merkle que podemos aprovechar. Este 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 desea descargar y aplicar hash a todas las transacciones de un bloque.
Lo que puede hacer en su lugar es simplemente solicitar una prueba de Merkle, evidencia proporcionada por el nodo completo que prueba que su transacción está 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 documento técnico de Bitcoin.
Considere el escenario en el que queremos conocer información sobre la transacción cuyo TXID es hD. Si se nos proporciona hC, podemos resolver 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 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 necesitado hacerlo siete veces. Dado que los bloques actualmente 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 de Merkle permiten una fácil verificación de la información sin inundar la red con datos innecesarios.
Sin los árboles Merkle (y las raíces Merkle), 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.
