Los árboles Merkle son una estructura de datos creada con la meta de facilitar la verificación de grandes cantidades de datos organizados relacionando exactamente los mismos a través de distintas técnicas criptográficas y de manejo de información.

Dentro de cualquier bloque de la red Bitcoin nos hallamos con una estructura llamada “Árbol de Merkle”.

Un árbol Merkle, es una estructura de datos divida en múltiples capas que tiene como finalidad relacionar cada nodo con una raíz única asociada a exactamente los mismos. Para conseguir esto, cada nodo ha de estar identificado con un identificador único (hash). Estos nodos iniciales, llamados nodos hijos (hojas), se asocian entonces con un no superior llamado nodo padre (rama). El nodo padre, va a tener un identificador único resultado del hash de sus nodos hijos. Esta estructura se repite hasta llegar al nodo raíz o bien raíz Merkle (Merkle Root), cuya impronta está asociada a todos y cada uno de los nodos del árbol.

Gracias a esta estructura única, los árboles Merkle dejan relacionar un sinnúmero de datos en único punto (Merkle Root). De este modo, la verificación y validación de esos datos, puede pasar a ser realmente eficaz, al tener que solo contrastar el Merkle Root en vez de toda la estructura.

Este diseño fue creado por Ralph Merkle, en el año de mil novecientos setenta y nueve, con el propósito de agilizar el proceso de comprobación de grandes cantidades de datos.

¿De qué forma marcha un árbol Merkle?

Un árbol Merkle es una estructura que relaciona todas y cada una de las transacciones y las reúne entre pares para conseguir un Root Hash o bien dirección raíz”. Este Root Hash, está relacionado con todos y cada uno de los hash del árbol. Contrastar todas y cada una de las transacciones de una red sería algo exageradamente lento y también ineficiente. Por tal razón, se incorporó este sistema. En tanto que, si un hash es alterado, cambiarían todos los otros hasta llegar a la raíz (root hash). Esto inutilizará la autenticidad de la información de todo el árbol.  Es exactamente esta función, la que deja a los árboles Merkels conceder el alto nivel de seguridad que los caracteriza.

Para comprender de qué manera marcha un árbol Merkle más en profundidad, examine el próximo ejemplo:

Imagine un bloque de datos el que lleva una impronta o bien hash único y también inigualable. Cada uno de ellos de estos bloques está organizado en capas en lo que veríamos como una estructura piramidal. Estos bloques están vinculados cara una capa superior a través de estos hashs. De esa forma, los bloques superiores apuntan siempre y en todo momento a los bloques inferiores, mas más esencial todavía, es que el hash de estos bloques superiores es el resultado de la suma de la información que contiene el nuevo bloque con el hash del bloque precedente. De esa forma, al continuar escalando, exactamente la misma estructura se repite mientras que se conectan todos y cada uno de los bloques a un enorme bloque de datos.

El hecho de que funcione así, hace que la perturbación del hash de un bloque, invalide los hashes del resto de los bloques. Así el sistema facilita 2 cosas. Primeramente, facilita la verificación de los bloques de datos. Seguidamente,  sirve de mecanismo para eludir la manipulación. Esto merced a que este mecanismo deja advertir cambios de hashes en todos y cada bloque de datos. De advertirse un cambio, se inutiliza todo el árbol puesto que ha sido perturbado y sus datos no son válidos.

Ejemplo de un árbol Merkle, Como se hace un árbol merkle

Características de los árboles Merkle

Algunas de las peculiaridades más resaltables de los árboles Merkle son:

  1. Son un medio eficaz para producir una estructura distribuida de datos.
  2. Proveen de una enorme seguridad y resistencia a perturbaciones de datos.
  3. Permiten un elevado nivel de desempeño de transmisión de datos en redes distribuidas. Merced a esto, reducen la cantidad de datos precisos para su adecuado funcionamiento.
  4. Son computacionalmente poco costosos y eficaces en el momento de crear, procesar y contrastar información.
  5. Permiten “disección” para hacer buscas de verificación más veloces. Todo ello, sin comprometer la seguridad y trazabilidad de las transacciones que se efectúen.
  6. Gracias a la característica de “disección” asimismo son capaces de permitir ahorrar recursos de almacenaje.
  7. Ofrecen una enorme adaptabilidad a diferentes inconvenientes informáticos. Merced a esto, los árboles Merkle han sido extensamente usados en diferentes sistemas. Por poner un ejemplo, software de base de datos, sistemas de ficheros, estructuras de llaves públicas, sistemas de versionamiento, redes distribuidas (Peer to Peer), entre otros muchos.

¿Cuánto sabes, criptonauta?

¿Los árboles Merkle por si acaso solos son una solución idónea para la verificación de datos?

Usos en la actualidad

Los árboles Merkle hoy en día tienen una extensa cantidad de usos en sistemas informáticos, y acá vamos a hablar de ciertos de ellos.

Tecnología blockchain

El empleo de los árboles Merkle en la tecnología blockchain es esencial. Merced a su empleo, el software cliente del servicio puede descargar todo el historial de la blockchain y contrastarlo en caliente. En verdad, su empleo facilita el proceso al permitir “podar” (tomar solo parte del historial) el historial y reducir el tamaño de la descarga.

Por ejemplo, un usuario que quiere instalar un cliente del servicio Bitcoin no tiene por el hecho de que descargarse todo el historial de la blockchain. En vez de eso, puede reducir su descarga a solo unos cientos o bien miles y miles de bloques atrás. De este modo, tiene acceso a una versión más ligera del historial que se ajusta más a sus requerimientos.

Al contrario de lo que puedan meditar esto no resta seguridad al cliente del servicio. Puesto que merced al árbol Merkle, es posible bajar un “root hash” concreto y desde allá empezar a crear un historial.  Como ese “root hash” está relacionado con los bloques precedentes a él, lo único que debe hacerse es contrastarlo. Para esto, se puede asistir a una serie de nodos completos de Bitcoin (con todo el historial)  y contrastar que el “root hash” tomado coincida. Teniendo absoluto acuerdo en este punto, se da el “root hash” como válido. Y desde ese punto, el usuario puede utilizar de forma perfecta su nuevo nodo cliente del servicio Bitcoin.

Sistemas de archivos

Otra utilidad que podemos ver de los árboles Merkle se refleja en los sistemas de ficheros. Un sistema de ficheros, es una estructura de datos que un sistema operativo usa para continuar la pista de los ficheros que guarda. Por norma general esta estructura es aplicada sobre un disco duro e inclusive en las tarjetas de memoria que utilizan nuestros móviles.

Algunas de estas especiales creaciones emplean árboles Merkle con la intención de manejar y asegurar el empleo adecuado de los datos guardados. Casos singulares de mención en este conjunto son los sistemas de ficheros ZFS y btrfs.

ZFS conocido como Zettabyte Archivo System, es considerado en el planeta de la informática como el mejor sistema del archivo. Sus capacidades superan por mucho a sus contendientes más conocidos como NTFS, FAT, exFAT o bien ext3/4. Cuenta con resistencia a fallos, restauración y corrección de fallos, de-duplicación de datos, replicación, copy-on-write (CoW) y una alta escalabilidad. Todo esto lo hace una alternativa idónea para ser desplegado en entornos críticos. Desarrollado por Sun Microsystems y presentado en dos mil cuatro, por el momento es el líder de los sistemas de ficheros para computadores.

Pero para conseguir esto ZFS tiene una herramienta segrega en la mitad de su código: el empleo extensivo y también intensivo de árboles Merkle. Todo esto con la intención de contar con un sistema que deje la veloz verificación de los datos que guarda en sus estructuras. Sus propiedades de restauración de fallos, de-duplicación, CoW (Copy-On-Write) y replicación dependen con fuerza de esta técnica, puesto que de otra manera, supondría un elevado costo computacional que echaría por tierra sus ventajas.

Sistemas de control de versiones

Otro empleo de los árboles Merkle lo podemos ver en los sistemas de versionamiento de software, casos bien conocidos de Git y Mercurial. De los dos, el más extensamente conocido en Git, exactamente el mismo que permite el funcionamiento de plataformas como Gitlab y Github, o bien el desarrollo del kernel Linux, este último fue el primer proyecto en utilizarlo en producción, puesto que el autor de Git es Linus Torvalds.

El empleo de los árboles Merkle en esta clase de software viene relacionado con el sistema de seguimiento de cambios en el repositorio o bien espacio de trabajo donde se guardan los ficheros. Así, cada cambio efectuado (bloques nuevos de datos) pasa por un proceso de hashing que al pasar por todo el contenido del repositorio, produce un hash único de tal espacio de trabajo, que recibe el nombre de commit.

Este sistema de marcado nos deja por poner un ejemplo, ir a un commit concreto para poder ver como era el estado del código del proyecto en un determinado instante, al tiempo que el estado general del proyecto se sostiene íntegro. Viéndolo de una forma más fácil, los árboles Merkle en Git nos dejan crear una suerte de máquina del tiempo, que nos deja navegar por los diferentes commit del proyecto, sosteniendo los ficheros y sus cambios tal como como estaban en ese determinado instante.

Una utilidad que resulta realmente útil en el momento de diseñar software en entornos de trabajos distribuidos y de alto tráfico, como no los ha probado Linus Torvalds en su magnífico proyecto del kernel Linux.

  • Mercurial un CVS bien conocido en informática
  • GIT el CVS más conocido en informática