Diccionario de Criptomonedas

¿Qué Es Un Árbol De Merkle? [Criptomonedas]

Qué Es Un Árbol De Merkle

Un árbol de Merkle 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 seguras.

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.

Función Hash Criptografica

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.

Ejemplo de función hash

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 Merkle.

Árbol de Merkle y Prueba 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 arbol permite mapear de forma eficiente grandes cantidades de información y permite determinar donde ha ocurrido un cambio en la misma.

Esto es lo que hace posible la prueba de Merkle, en el 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.

En las siguientes secciones, profundizaremos cómo Bitcoin y otros sistemas implementan los árboles de Merkle.

Árbol de Merkle en Bitcoin

Ya vimos que 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 que consisten en:

Una imagen extraída del whitepaper de Bitcoin nos muestra como el árbol de Merkle se relaciona con el bloque.

Arbol de Merkle en el whitepaper de bitcoin

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.

Implementación en otras cadenas de bloques y sistemas

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.

No creas que los árboles de Merkle solo sirven para las cadenas de bloques. Su uso se extiende mucho más y los podemos encontrar en distintos sistemas.

A estas estructuras también las podemos hallar en sistemas de versiones distribuidas como Git o IPFS. Debido a que son perfecto para asegurar y verificar la información que es compartida entre ordenadores de forma P2P.

Conclusión

Los árboles de Merkle son importantes para el ecosistema de las cadenas de bloques porque les permiten funcionar conservando la integridad y la imposibilidad de cambiar la información.

Si te interesa esta tecnología, seguro quieras saber más como es posible que una red distribuida funcione. Los hash y las estructuras vistas hoy son los conceptos básicos que debes dominar para poder sumergirte en todo los tecnicismos.

Criptotario

Me llamo Martin, soy ingeniero y apasionado de las inversiones y la tecnología. Me gusta mucho leer libros y todo aquello que me haga mejorar día a día.

Agrega un Comentario

Haz clic aquí para añadir un comentario