¿Qué es un árbol de Merkle?

Un árbol de Merkle es una estructura de datos estratificada que tiene como finalidad relacionar cada nodo con una raíz única asociada a éste. Para lograrlo, cada nodo debe estar identificado con un identificador único (hash).

Estos nodos iniciales, llamados nodos hijos (hojas), se asocian luego con un nodo superior llamado nodo padre (rama). El nodo padre tendrá un identificador único, como resultado del hash de sus nodos hijos. Esta estructura se repite hasta llegar al nodo raíz o raíz Merkle (Merkle root), cuya impronta está asociada a todos los nodos del árbol.

Gracias a esta estructura única, los árboles de Merkle permiten relacionar una gran cantidad de datos en único punto (Merkle root). De esta forma, la verificación y validación de esos datos puede pasar a ser muy eficiente, al tener que verificar únicamente el Merkle root en lugar de toda la estructura.

Este diseño fue creado por Ralph Merkle, en el año 1979, con el fin de agilizar el proceso de verificación de grandes cantidades de datos.

Características

Los árboles de Merkle se caracterizan por las siguientes propiedades:

  1. Ser extremadamente eficientes a la hora de verificar grandes cantidades de información. Esto es así gracias a que su estructura estratificada permite relacionar un único punto (nodo raíz o Merkle root) con una serie de datos superiores. De esta forma, al verificar la validez de dicho punto podemos estar seguros de la validez del resto del árbol.
  2. Ofrecer una gran adaptabilidad a distintos problemas informáticos. Gracias a esto, los árboles de Merkle han sido ampliamente utilizados en distintos sistemas. Por ejemplo, software de base de datos, sistemas de archivos, estructuras de llaves públicas, sistemas de versionamiento, redes distribuidas (P2P), entre otros.
  3. Alta eficiencia en la sincronización de datos. Esto sucede gracias a que los árboles de Merkle se pueden usar para sincronizar datos a través de múltiples nodos (pares) en un sistema distribuido. Con los árboles de Merkle, no necesitamos comparar los datos completos para descubrir qué ha cambiado. Sólo necesitamos hacer una comparación del hash de los árboles. Una vez que descubramos qué nodos hijos se han cambiado, la porción de datos correspondiente se puede enviar a través de la red y sincronizarse en todos los nodos.

¿Cómo funcionan?

El funcionamiento de un árbol de Merkle reside en la capacidad de resumir una gran cantidad de datos en un único bloque de datos verificable. Para lograr esto, los árboles de Merkle hacen uso intensivo de las funciones de hashing entre todos sus nodos, hasta llegar a un único hash derivado del resto.

Este proceso de hashing se realiza desde abajo hacia arriba, a partir de los hashes que identifican a cada nodo. Para ejemplificarlo de mejor manera, tengamos en cuenta el siguiente ejercicio sencillo.

En primer lugar, supongamos que tenemos una serie de ocho bloques, cada uno de ellos con un texto único:

A los datos de estos ocho bloques le aplicaremos la función hash SHA-256, con el fin de asegurar que cada hash sea único e irrepetible. El resultado de este proceso lo podemos observar en la siguiente imagen:

Realizada la primera ronda hash, comenzamos a escalar hacia los nodos superiores. Para esto, tomamos dos bloques y sus hashes, los concatenamos (sumamos) y hacemos otra ronda hash sobre el resultado.

Este proceso de concatenación se hace para cada par de bloques de datos. En nuestro caso, sobre ocho bloques, generamos cuatro pares de nuevos bloques de datos con un hash distinto, como consecuencia de la concatenación. El resultado se ve en las siguientes imágenes:

Este proceso de concatenación se vuelve a repetir, hasta llegar a la raíz de Merkle. Así pues, nos queda la siguiente estructura:

De esta forma, la raíz de Merkle resume todos los datos de los bloques. Esto tiene algunas implicaciones muy importantes:

  1. Mantiene la integridad de los datos.
  2. La alteración de un bloque cambia todo el valor de la estructura del árbol.
  3. Permite una prueba rápida y sencilla para saber si un bloque de datos está incluido realmente dentro del árbol.
  4. No es necesario descargar todo el conjunto de datos para verificar la integridad de la información.

Usos en la actualidad

Los árboles de Merkle en la actualidad tienen una amplia cantidad de usos en sistemas informáticos. Algunos de ellos resultan incluso desconocidos por la mayoría, toda vez que la atención se centra en su mayor exponente en estos momentos: la tecnología blockchain.

Es cierto que la tecnología blockchain ha catapultado al conocimiento público estas estructuras. Tanto es así que, sin ellas, el funcionamiento de la blockchain tal como la conocemos sería imposible. Pero más allá hay un mundo de posibilidades, donde los árboles de Merkle están siendo utilizados. Aquí hablaremos de algunos de ellos.

Sistemas de archivos

Ésta es una utilidad que pasa desapercibida para muchos, pese a que solemos hacer uso de ella en nuestras vidas diarias. Un sistema de archivos es una estructura de datos que un sistema operativo utiliza para seguir la pista de los archivos que almacena dentro de un disco duro e incluso dentro de las tarjetas de memoria que usan nuestros smartphones.

Algunas de estas peculiares creaciones hacen uso de árboles de Merkle con el fin de manejar y garantizar la corrección de los datos almacenados. Casos especiales de mención en este grupo son los sistemas de archivos ZFS y Btrfs.

ZFS, conocido como Zettabyte File System, es considerado en el mundo de la informática como el mejor sistema de archivos para sistemas empresariales. Sus capacidades de resistencia a fallos, recuperación y corrección de errores, deduplicación de datos, replicación, copy-on-write (CoW) y escalabilidad lo hacen una opción perfecta para ser desplegado en ambientes críticos. Diseñado por Sun Microsystems y presentado en 2004, de momento es el líder de los sistemas de archivos para ordenadores.

Para lograr esto, ZFS tiene un secreto en medio de todo su código: el uso extensivo de árboles de Merkle. La finalidad de ello es clara: contar con un sistema que permita la rápida verificación de los datos que almacena dentro de sus estructuras. Sus propiedades de recuperacion de errores, deduplicación, CoW y replicación dependen fuertemente de esta técnica, pues de otra forma supondría un elevado coste computacional que echaría por tierra sus ventajas.

Sistemas de versionamiento de software

Otro uso de los árboles de Merkle lo podemos ver en los sistemas de versionamiento de software, casos muy conocidos de Git y Mercurial. De ambos, el más ampliamente conocido es Git, el mismo que posibilita el funcionamiento de plataformas como Gitlab y Github, o el desarrollo del kernel Linux. Este último fue el primer proyecto en usarlo en producción, pues el creador de Git es Linus Torvalds.

El uso de los árboles de Merkle en este tipo de software viene relacionado con el sistema de seguimiento de cambios dentro del repositorio o espacio de trabajo donde se almacenan los archivos. De esta forma, cada cambio realizado (bloques nuevos de datos) pasa por un proceso de hashing que, al pasar por todo el contenido del repositorio, genera un hash único de dicho espacio de trabajo, que recibe el nombre de commit.

Este sistema de marcado nos permite, por ejemplo, ir a un commit específico para ver cuál era el estado del código del proyecto en un determinado momento, mientras que el estado general del proyecto se mantiene intacto.

Viéndolo de una manera más sencilla, los árboles de Merkle en Git nos permiten crear una especie de máquina del tiempo, que nos permite navegar por los distintos commit del proyecto, manteniendo los archivos y sus cambios tal como estaban en ese determinado momento.

Esta utilidad resulta muy útil a la hora de diseñar software en ambientes de trabajo distribuidos y de alto tráfico, tal y como no los ha demostrado Linus Torvalds en su grandioso proyecto del kernel Linux.

Conclusión

Sin lugar a dudas, los árboles de Merkle son una de las estructuras informáticas más relevantes y poderosas que podamos tener a disposición. Su uso en distintos proyectos y en la blockchain nos hace ver que sus cualidades y características resultan perfectas para atacar el problema de la distribución y descentralización de la información de forma segura, sobre todo cuando se usa junto a sistemas de hashing y criptografía fuerte, lo que hace aún más segura la estructura y su ubicuidad dentro de las necesidades de uso del proyecto donde se ejecute.

Descubre este y otros interesantes artículos en el número #10 de #ÁGORA: 

Colaborar para llegar más alto 

#agoramagazine10

#Decentraliced #Cultural #Magazine