Árbol Merkle, la clave para la verificación de la blockchain

Introducción

Mucha de la tecnología detrás del funcionamiento de la blockchain, es tecnología que ha sido desarrollada en lo últimos 50 años. Y es que desde el nacimiento de la informática tal como la conocemos, esta nos ha permitido crear herramientas muy útiles. Todo con el fin de resolver problemas de diversa índole. Precisamente esa premisa fue la que llevó a Satoshi Nakamoto a utilizar tecnología conocida y unirla con nueva tecnología para crear la primera criptomoneda, el Bitcoin.

Una de esas piezas tecnológicas es el Árbol Merkle. Una creación que realiza una función vital dentro de blockchain: la verificación de los datos y el historial de la blockchain. Pero ¿Qué es un Árbol Merkle? ¿Cómo funciona? ¿Quién creó esta función? ¿Cuál ha sido su impacto en la blockchain y más allá?   Pues bien, todas estas interrogantes las responderemos a continuación en este nuevo capítulo.

¿Qué es un Árbol Merkle?

Un Árbol Merkle hace mención a una estructura de datos estratificada y organizada, donde cada conjunto de datos está identificado con un hash que lo identifica de forma particular y exclusiva. De esta forma, se puede relacionar cada conjunto de datos y agruparlos junto con otro conjunto de datos, para que, en última instancia, estos generen un hash que resuma todos los datos globalmente.

Gracias a esta estructura y organización de datos, un Árbol Merkle puede asociar y resumir grandes cantidades de información en un único hash o Merkle Root. Este Merkle Root, no es más que un hash formado por la suma de hashes de los conjuntos de datos que forman el árbol en su totalidad. Un proceso que hace que la verificación y validación de esos datos resulte muy eficiente. Ya que solo basta con verificar el Merkle Root para validar toda la estructura de datos asociada. 

Pero ¿Qué llevó a la creación de esta función? ¿Quién fue la persona detrás de su creación? Todo eso lo examinaremos a continuación.

Historia de su creación

Uno de los problemas más complejos del mundo de la informática es garantizar la veracidad y la integridad de la información. Esto es así porque en informática, los bits que conforman algún conjunto de datos pueden alterarse por procesos propios de la tecnología, como errores de hardware o programación, así como factores externos, como lo son los atacantes o hackers maliciosos.

De allí que una de las necesidades fundamentales de los informáticos y desarrolladores fuera el de crear mecanismos de verificación de datos. Una tarea nada sencilla y que en principio requería de gran conocimiento, no solo para hacer sistemas seguros, sino altamente optimizados. Todo con el fin de que no supusieran una sobrecarga de cómputo a equipos que eran bastante limitados en este sentido.

Ante esta situación, Ralph Merkle, un informático y criptógrafo, diseñó en 1979 un sistema de verificación de datos altamente eficiente. Lo llamó Árbol Merkle, un tipo de árbol binario que proveía una solución de primer nivel al problema de verificación de datos. Merkle presentó y patentó este trabajo poco antes de terminar sus estudios de Doctorado en Ingeniería Eléctrica en la University of Stanford.

Al presentarlo, Ralph Merkle brindó un trabajo y conocimientos que resultaron fundamentales para el futuro de la informática. Pero no solo eso, dejaba en claro el futuro promisorio que le aguardaba tras otras creaciones adelantadas a su época. Como el caso de primer algoritmo de criptografía asimétrica (Puzzle Merkle) en 1974, un sistema de Evaluadores para atributos gramaticales para lenguajes de programación (1977) y su trabajo Secreto, autenticación y sistemas de clave pública (1979).

Pero el trabajo que lo dio a conocer mundialmente hasta nuestro tiempo fue el criptosistema Merkle-Hellman. Logros que se unieron a su valioso trabajo en criptografía asimétrica, pilar de la criptografía en blockchain.

Relacionado: Orígenes: El rol de los cypherpunks en la creación de Bitcoin

¿Cómo funciona un Árbol Merkle?

El funcionamiento de un Árbol Merkle es bastante sencillo. El algoritmo está diseñado para generar una estructura de datos en la cada uno de sus conjuntos de datos (nodos hijos) se va agrupando en conjunto de datos más grandes (nodos padres o ramas). Estos grupos se relacionan a su vez con otros nodos padres hasta reunir a todos los datos del sistema. Como resultado se obtiene el llamado Merkle Root. 

Un funcionamiento en cascada que poco a poco va absorbiendo los datos del sistema hasta minimizarlos en un solo punto. Este punto o Merkle Root, está deterministicamente relacionado con todos los conjuntos de datos y el hash que identifica a cada uno de ellos. El hecho de que este proceso sea determinístico es vital. Ya que garantiza que cualquier modificación que se haga en el conjunto de datos, por mínima que sea, cambiará el resultado del Merkle Root. 

De esta forma, podemos garantizar que los datos no han sido alterados en ningún punto, y de haber sido alterados, toda la estructura queda invalidada. El proceso de verificación en este punto tiene un punto a favor, y es que resulta computacional y algorítmicamente sencillo de realizar. Esto significa que no se necesita de potentes computadoras para realizarlo de forma rápida.

Estas características son las que convierten al Árbol Merkle en una potente opción para crear sistemas de verificación e integridad de datos informáticos.

Ejemplo de cómo funciona un Árbol Merkle

Ahora bien, lo anterior seguramente puede resultar complejo para quienes no tienen conocimientos básicos de informática. Así que para señalar de mejor manera su funcionamiento tomemos en cuenta el siguiente ejemplo:

En primer lugar, imagine que debe organizar y crear una firma de verificación global para una base de datos. Pero además debe garantizar que cada conjunto de datos pueda ser verificado de forma individual. El complejo problema lo lleva a dividir esta base de datos en las unidades de datos más pequeñas que pueda crear. Partiendo de este punto, usted computa un hash para esta pequeña unidad de datos. De esa forma, cada unidad de datos tendrá un hash único e irrepetible que lo identificará de forma única entre todos los demás fragmentos.

A partir de este punto, usted comienza con la segunda fase del proceso. En este punto, comienza a unir y agrupar estos conjuntos de datos en otros más grandes.  Para ello toma los hashes individuales de cada uno de los elementos del grupo, los suma algorítmicamente y crea un nuevo hash que representa a todo el grupo. 

Continua con este proceso de agrupación y creación de hashes, consciente de que este proceso le permite establecer una vinculación entre los distintos conjuntos de datos. Esto gracias a que el hash de un conjunto de datos superior siempre será el resultado de la suma de hash del conjunto anterior. 

De esa forma, al seguir escalando, la misma estructura se repite mientras se conectan todos los conjuntos a un conjunto de datos mucho mayor. Al terminar el proceso, tendrá un Merkle Root o la representación resumida de todos los datos dentro de la base de datos. Este le servirá para verificar y proteger la integridad de su base de datos.

Gracias a esta estructura usted soluciona dos problemas. El primero, puede detectar cualquier alteración que se haga en la base de datos. Esto gracias a que el más mínimo cambio en la información afectará a los hashes y la suma de los mismos diferirá, invalidando el proceso.

El segundo problema, es la dificultad y la necesidad de potencia de cómputo.  Las funciones de generación de hashes han sido creadas para resumir grandes cantidades de información en cortas cadenas de datos, que se generan muy rápidamente. De esta forma, su sistema no debe leer toda la información de la base de datos, tan solo basta revisar los hashes y verificar que el Merkle Root que originó en el primer proceso.

Características de un Árbol Merkle

Algunas de las propiedades atribuibles a un Árbol Merkle son las siguientes:

  1. Son altamente eficientes.
  2. Ofrecen una gran capacidad para verificar grandes cantidades de información.
  3. Tienen un funcionamiento estratificado. Por lo que permiten relacionar todos los datos de un sistema en un punto único (Merkle Root).
  4. Es algorítmicamente sencillo de programar.
  5. Ofrecer una gran adaptabilidad a distintos problemas o programas informáticos. Por ejemplo, se puede usar y adaptar a base de datos, sistemas de archivos, estructuras de llaves públicas, sistemas de versionamiento, redes distribuidas (P2P), entre otros.
  6. Tienen una alta eficiencia en la sincronización de datos. Esto es posible gracias a que un Árbol Merkle puede podarse, para que desde una pequeña unidad de datos se pueda considerar una sincronización efectiva y continuar con el trabajo del nodo. Una propiedad especialmente útil en sistemas distribuidos

Usos de los Árboles Merkle

La primera aplicación de un Árbol Merkle se dio sobre los primeros prototipos de sistemas de archivos y base de datos modernas. Esta creación demostró ser perfecta para estas tareas debido a su simplicidad y sencillez de desarrollo. 

Sin embargo, donde más se desarrolló inicialmente fue en los softwares de control versiones. Desarrollos como SCM, RCS y CVS, aplicaron con gran éxito el uso de árboles merkle para verificar los datos que manejaban y ayudar al software a resolver los cambios que se realizaban. Algo que resultó especialmente útil con la aparición de las primeras redes de computadoras.

De hecho, en la actualidad sistemas de control de versiones como Git, Mercurial y Subversion, usan árboles merkle para verificar los datos tanto en origen (computador remoto) como en cada computador que tiene una copia de dicho origen. Esto con el fin de ofrecer a todos la misma información, cambios e historial de datos hasta el más mínimo detalle.

Más recientemente, los árboles merkle tomaron una relevancia vital en los sistemas de archivos. Desarrollos como Ceph, BTRFS, ZFS e IPFS, usan esta estructura con el fin de verificar y mantener la integridad de la información en sus sistemas distribuidos.

En bases de datos, ejemplo como Apache Cassandra y sistemas NoSQL usan también árboles merkle para mantener la integridad de sus datos, sin sacrificar rendimiento.

Relacionado: Informe del Bitcoin - 10 años desde que la visión de Satoshi cobró vida

Usos en la tecnología blockchain

En el caso del mundo blockchain, el Árbol Merkle resulta vital para la verificación de datos. De hecho, el uso de los árboles merkle está implícito en el nombre blockchain o cadena de bloque. Y es que gracias al uso de estos, es posible crear la "cadena" entre esos bloques de datos.

Dicha "cadena" viene dada por la relación entre los hashes de cada bloque. Recordemos que el hash de un bloque es formado por la información que estos contienen. Cualquier cambio en dicha información y el hash resultante es completamente distinto. Así cuando los mineros generan un nuevo bloque, estos generan un nuevo hash para dicho nuevo bloque. 

En este proceso se toma en cuenta el hash del bloque anterior sumando los datos del nuevo bloque. Como resultado, el hash del nuevo bloque está deterministicamente relacionado con el hash del bloque anterior. Así cualquier alteración en los datos de los bloques anteriores termina invalidando el historial de la blockchain desde el punto de modificación. Ese es el origen de la "cadena" de bloques.

Por supuesto, su uso en blockchain no solo se limita a esta funcionalidad. Gracias al Árbol Merkle también podemos velar por la seguridad y la integridad de los datos distribuidos en la red. Basta con que los nodos se comuniquen entre ellos y comuniquen sus comprobaciones de Merkle Root. Como resultado los nodos pueden saber que la red funciona y sus datos se mantienen íntegros.

Adicionalmente, también permite que los nuevos nodos puedan sincronizarse rápidamente con la blockchain si estos eligen "podar" la cadena de bloques. Este procedimiento lo que hace es descargar una parte de todo el historial de la cadena de bloques junto a la información del Árbol Merkle. Así con una descarga más pequeño el nodo puede verificar esos datos y compararlos con el Árbol Merkle existente. El resultado final debería ser el mismo Merkle Root habilitado en la red para el momento final de la verificación.

Basta decir que esta estructura es utilizada en Bitcoin y en toda blockchain creada después de esta. La razón: es una solución elegante y óptima para verificar los datos en sistemas distribuidos como el caso de las redes blockchain.

En este punto, ya no queda ninguna duda que el Árbol Merkle es una creación vital en el mundo informático moderno. Su utilidad se ha mantenido en el tiempo especialmente por su elegancia y sencillez.