Un árbol de Merkle o Merkle Tree es una estructura de datos que es utilizada en aplicaciones informáticas. En Bitcoin y otras criptomonedas, los árboles de Merkle sirven para codificar la información de forma más eficiente y segura.
Contenido
¿Cómo utilizan Blockchain los árboles de Merkle?
Los árboles de Merkle son una pieza fundamental de la tecnología blockchain, ya que ayudan a su buen funcionamiento.
Permiten verificar eficazmente y seguramente grandes estructuras de datos y, en el caso de las cadenas de bloques, de conjuntos de datos potencialmente ilimitados.
La implementación de los árboles de Merkle en la blockchains tiene múltiples efectos. Les permite escalar mientras también provee de una arquitectura basada en hash para mantener la integridad de la información y hacer que la certificación sea algo trivial.
Las funciones de hash criptográficas son una parte importantísima de la tecnológica que permiten a los árboles de Merkle funcionar, por eso vamos a detenernos un rato en ellos para comprender como funcionan.
¿Cómo utiliza el árbol de Merkle Bitcoin?
El algoritmo de hashing de Bitcoin es el SHA-256. Que son las siglas de “Secure Hashing Algorithm” (algoritmo de hash seguro) y cuyo resultado es una longitud fija de 256 bits.
El uso que le da Bitcoin a los árboles de Merkle es para almacenar y eventualmente podar las transacciones de cada bloque.
En la cadena de bloques, los bloques están conectados a través de hashes de los bloques anteriores. En el caso de Bitcoin en particular, cada bloque contiene todas las transacciones que hay dentro y también una cabecera de bloque que consisten en:
- Número de versión del bloque
- Hash del bloque anterior
- Marca de tiempo
- Dificultad de minería
- Nonce
- Hash de la raíz Merkle
Una imagen extraída del whitepaper de Bitcoin nos muestra como el árbol de Merkle se relaciona con el bloque.
Las transacciones son incluidas en el bloque por los mineros y luego son pasadas por una función hash para formar parte de un árbol de Merkle. Finalmente, es la raíz (root hash) la que se almacena en la cabecera.
Todo esto tiene grandes beneficios.
El más interesante, como lo indica el documento, es que permite la existencia de lo que se conoce como nodos de verificación de pagos simples (SPV), también conocidos como “clientes ligeros”.
Estos nodos no tienen que descargar toda la cadena de bloques de Bitcoin, solo las cabeceras de los bloques de la cadena más larga.
Los nodos SPV pueden lograr esto consultando a sus nodos pares hasta que estén convencidos de que las cabeceras de bloque almacenadas con las que están operando forman parte de la cadena más larga.
Un nodo SPV puede entonces determinar el estado de una transacción utilizando la prueba Merkle para asignar la transacción a un árbol Merkle específico con el respectivo hash de la raíz del árbol Merkle en una cabecera de bloque que forma parte de la cadena más larga.
Además, la implementación de los árboles Merkle de Bitcoin permite la poda de la cadena de bloques para ahorrar espacio.
Esto se debe a que solo se almacena el hash de la raíz en la cabecera del bloque, por lo que los bloques antiguos pueden ser podados eliminando las ramas innecesarias del árbol de Merkle y conservando solo las necesarias para la prueba de Merkle.
¿Cómo utiliza el árbol de Merkle Ethereum?
Si bien Bitcoin fue el primero en implementar el árbol de Merkle, ya que fue la primera criptomoneda, muchas otras blockchains han seguido un camino similar y optado por esta estructura. Incluso hay algunas que ha elegido una más compleja.
Ethereum, la segunda criptomoneda más reconocida, es también un gran ejemplo de implementación de esto. La diferencia es que como Ethereum es de tipo turing-completo, ya que se trata de una plataforma donde podemos construir aplicaciones sobre ella, su implementación de árbol de Merkle es diferente también, más compleja.
Esta se llama árbol de Merkle Patricia y son 3 árboles de Merkle por separado que se utilizan para distintas cosas.
¿Qué es la función hash criptográfica?
En términos sencillos, una función hash es una función que permite mapear la información de una entrada de cualquier tamaño en una salida de tamaño fijo.
Un algoritmo de hashing se aplica a la información que ingresa para que el resultado siempre sea de la misma longitud. Esta salida de la información se la conoce como hash.
El resultado de la función de hash no solo es de un tamaño fijo, sino que también es única con respecto a la entrada, lo que se conoce como determinista.
No importa cuantas veces corramos el algoritmo, siempre va a producir la misma salida si la entrada es la misma.
Por ejemplo, si tenemos la siguiente lista de entradas, el resultado siempre es único para cada una de ellas. Pero eso no es todo, también podemos ver que si cambiamos apenas una palabra o una letra el resultado es completamente diferente.
Esto último es importante para que nadie pueda adivinar la información luego.
El hecho de que la salida siempre tenga la misma longitud permite que podamos codificar una enorme cantidad de información utilizando un algoritmo como este. No es necesario almacenar la información original si contamos con el hash.
En sistemas donde existe una gran cantidad de información, los beneficios de poder almacenar e identificarla con una cantidad fija de caracteres puede ayudar a ahorrar espacio y a mejorar la eficiencia.
En el caso de las cadenas de bloques, este algoritmo es utilizado para determinar el estado de la blockchain.
La cadena de bloques o blockchain es un conjunto de bloques enlazados entre sí que contienen información y hashes al bloque anterior, lo que crea la cadena de bloques conectados, y por eso su nombre.
Cada bloque es conectado a otro a través de un puntero hash, que es un hash de la información del bloque previo junto con la dirección de este.
Al enlazarlos los bloques de información de esta forma, cada hash que se crea en un nuevo bloque representan el estado total de la cadena de bloques. Es como si fuera una de esas muñecas rusas que contienen una a la otra (cada hash es el resultado de otro hash, que es el resultado de otro hash, etc.).
Un hash puede haber sido creado con diferentes algoritmos, pero el que utiliza Bitcoin y el más extendido es el SHA-256. Uno que luce así:
183492419c7b553a05328725f7a754d3293f790a31d2d1c95a0a09736e223059
Si bien podemos utilizar hashes criptográficos sin la necesidad de un árbol de Merkle, la realidad es que no es muy recomendable debido a lo ineficiente y lo poco escalable que es. Si almacenamos los hashes de los bloques cronológicamente, por ejemplo, luego a la hora de buscar es necesario mucho más esfuerzo.
Como veremos ahora, los árboles de Merkle permiten resolver muy fácilmente el problema de la integridad de los datos, así como el mapo de estos a través de esta estructura y la utilización de las pruebas de Mekle.
Ejemplo de Árbol de Merkle
Llamado así por la persona que patento el concepto en 1979, Ralph Merkle, estas estructuras tienen un formato de árbol en donde cada nodo que no sea un hijo es el hash de sus respectivos nodos hijos.
Los nodos hoja son aquellos que se encuentran en el fondo de la estructura. Puede que sea complicado de entender de esta forma, pero si lo miras en el gráfico de abajo seguro que lo entenderás.
Importante notar como los nodos que no son hojas, también conocidos como ramas (representados aquí por los hash 0-0 y hash 0-1) en la parte izquierda, son hashes de los respectivos hijos Información 1 e información 2. Luego vemos que el hash raíz concatena los hijos Hash 0 y Hash 1.
Este ejemplo es el más común y simple de árbol de Merkle, ya que se trata de un árbol binario.
Como podrás ver, en la cima hay un hash superior que representa el hash de todo el árbol, y se lo conoce como raíz de Merkle o hash raíz.
Resumiendo un poco, un árbol Merkle es una estructura de datos que puede tomar “n” números de hashes y represéntalos con uno solo.
La estructura del árbol permite mapear de forma eficiente grandes cantidades de información y permite determinar donde ha ocurrido un cambio en la misma.
¿Qué es la Prueba de Merkle?
Una Prueba de Merkle o Merkle Proof es lo que permite que cualquiera puede verificar que el hash de una información es consistente durante todo el árbol hasta la raíz. Y esto lo consigue sin tener que analizar todos los hashes, solamente la rama en donde se encuentra.
Simplemente, verificamos la información de un subconjunto de hashes hasta llegar a la cima, lo cual es mucho más rápido y consume menos recursos que analizar todos los que existen. En especial si el árbol es extremadamente grande.
Mientras el hash de la raíz sea conocido públicamente y de confianza, es posible que cualquiera que quiera hacer una búsqueda de valores clave en una base de datos utilice una prueba Merkle para verificar la posición y la integridad de un dato dentro de una base de datos que tenga una raíz concreta.
Cuando el hash de la raíz está disponible, el árbol de hash puede recibirse de cualquier fuente no confiable y una rama del árbol puede comprobarse al mismo tiempo con la verificación inmediata de la integridad de los datos, incluso si todavía no hemos terminado de descargar todo el árbol.
Una de las ventajas más importantes de la estructura del árbol de Merkle es la capacidad de autentificar conjuntos de datos arbitrariamente grandes mediante un mecanismo de hash similar al que se utiliza para verificar cantidades de datos mucho más pequeñas.
El árbol es interesante para distribuir grandes conjuntos de datos en partes más pequeñas y manejables en las que la complejidad para la verificación de la integridad se reduce sustancialmente a pesar del mayor tamaño global de los datos.
El hash raíz puede utilizarse como huella digital de todo un conjunto de datos, incluyendo una base de datos completa, o representando todo el estado de una cadena de bloques.
¿Qué es un Merkle Root?
Una raíz de merkle es el hash de todos los hashes de las transacciones que son parte de un bloque en la cadena de bloques.
¿Cómo funciona el hash raíz?
Dentro de una cadena de bloques encontramos bloques que están relacionados entre sí, de ahí su nombre. Cada bloque a su vez cuenta con transacciones, que son lo que le dan vida a las criptomonedas en la tecnología blockchain.
Sin embargo, estas transacciones se encuentran vinculadas dentro del bloque en una estructura de árbol de Merkle o árbol de hashes.
Esta codifica la información de forma eficiente y la vuelve más segura, al permitir que cualquiera pueda verificar que no se ha modificado nada dentro de ellas. Algo que podría suceder si alguien lo hiciera intencionalmente o si bien hubiese un error en la red cuando se transmite.
Cada transacción que se ejecuta sobre una cadena de bloques tiene un hash asociado a ella. Sin embargo, estos no son guardados cronológicamente, sino que se almacenan en una estructura de árbol, donde cada hash apunta a un hash padre siguiendo una relación de padre e hijo.
Debido a que existen múltiples transacciones dentro de un bloque, también se pasa por una función hash a todo el árbol para obtener lo que se conoce como raíz de Merkle.
Por ejemplo, supónganos que tenemos un bloque que solo contiene 3 transaccione (para el caso de Bitcoin sería uno con muy pocas).
En el nivel más bajo del árbol, que se conoce como nivel hoja, encontramos todas las transacciones, o en el caso de este árbol los hashes. A su vez, vemos que las transacciones se encuentran agrupadas de a dos y conectan con otro nivel que es un hash también.
Por último, llegamos al nivel superior que se conoce como raíz, y conectara con todo los hashes de las transacciones a través de una estructura que nos hace acordar a un árbol.
Pero para verlo tenemos que darlo vuelta, ya que en realidad la raíz en este caso se encuentra arriba en lugar del suelo.
Cada rama de este árbol conecta con solo dos nodos por debajo, también por eso se lo conoce como árbol binario. Es así que de la raíz solo salen dos hashes, y de cada uno de ellos otros dos más hasta llegar al último nivel.
El hashing comienza en los nodos de nivel más bajo (nivel de hoja), y los cuatro hashes se incluyen en el hash de los nodos que están vinculados a él en el nivel uno.
Del mismo modo, el hashing continúa en el nivel uno, lo que lleva a hashes de hashes que llegan a niveles superiores. Finalmente, llegando al único hash raíz.
Este hash raíz se denomina raíz Merkle, y debido a la vinculación en forma de árbol de los hashes, contiene toda la información sobre cada uno de los hash de transacciones que existen en el bloque. Con este único hash podemos validar toda la información que existe en el árbol.
Por ejemplo, si debemos verificar una transacción que dice provenir del bloque #117, solo necesitamos comprobar el árbol Merkle del bloque, sin preocuparnos de verificar nada en otros bloques de la cadena de bloques, como el bloque #116 o el bloque #118.
Resumen de los Árboles de Merkle
- Los árboles de Merkle son árboles de hashes que permiten estructurar la información.
- La raíz del árbol de Merkle es la manera sencilla de verificar matemáticamente la información del árbol de Merkle con las transacciones.
- Las raíces de Merkle son utilizadas en criptomonedas para asegurarse que la información que es enviada entre nodos no se haya perdido o alterado.
- Los árboles de Merkle son un aspecto fundamental de monedas como Bitcoin y Ethereum para su correcto funcionamiento.
Agrega un Comentario