Sin categoría

Introducción a los árboles de Merkle

Un caso de uso de la blockchain es el registro de certificaciones digitales. En este caso las tecnologías blockchain aportan propiedades de seguridad interesantes para el almacenamiento de la información para su posterior verificación, como la replicación y la inmutabilidad de dicha información.

El problema es que dichas propiedades vienen a cambio de un coste adicional: almacenar datos en la blockchain es caro. Puesto que esta información será replicada a todos los nodos de la red, es importante que ésta sea lo más reducida posible. De lo contrario, no cualquiera podría participar en la red activamente por los requisitos técnicos (gran cantidad de almacenamiento, gran ancho de banda, …), reduciendo la cantidad de participantes y por tanto, las propiedades de réplica e inmutabilidad deseadas.

Nuestro caso de uso

En el proyecto que estamos llevando a cabo de forma integral juntamente con Andorra Telecom, FEDA, Actua y el Ministerio de Educación del Govern d’Andorra sobre el registro de certificaciones digitales, ha surgido la necesidad de realizar registros de un gran volumen de datos teniendo en cuenta el escenario, la blockchain.

Pero aun así, hay lugar para la optimización. Podemos agrupar dicha información de integridad, para poder realizar verificaciones de acreditaciones en conjunto, usando tan sólo un hash para verificar la integridad de hasta n acreditaciones digitales. La estructura a usar para hacerlo de forma eficiente es un árbol de merkle o merkle tree.

Es por ello que al realizar las acreditaciones digitales sólo guardamos en la blockchain la información de verificación: tanto de integridad (un hash) como de autenticidad (una firma digital).

Así pues, se ha tomado la decisión de implementar de cero el código que diera el soporte necesario para crear esta estructura tal y como la necesitábamos, ajustándose a nuestras necesidades. El código desarollado para éste propósito puede consultarse en https://github.com/btcassessors/MerkleTree.

Árboles hash de Merkle

Un árbol hash de Merkle es una estructura de datos en forma de árbol, dónde cada uno de los nodos es el hash de los nodos subyacentes a éste.
De ésta manera se pueden agrupar una gran cantidad de datos ligándolos a un único valor, el del nodo raíz, llamado root o Merkle root.
Así, se puede proporcionar un método de verificación seguro y eficaz sobre la integridad de los datos contenidos en la estructura.

Los nodos se agrupan en una cantidad determinada por el árbol, se pueden agrupar de dos en dos, de tres en tres, etc… Y éste no es necesario que esté balanceado, es decir, que la cantidad de hojas sea exacta para la agrupación y no falte ni sobre ninguna. En el caso de que no fuera un árbol balanceado se podría añadir relleno para balancearlo o bien, se podría obviar el detalle y construir la estructura global con menos nodos, de modo que nos saltaríamos algunos pasos para algunos nodos intermedios.

En el siguiente ejemplo presentamos un árbol binario (sus nodos se agrupan de dos en dos), con ocho hojas y balanceado (todos los nodos tienen dos nodos subyacentes para poderse agrupar y calcular el nuevo paso).

Árbol de Merkle balanceado

Verificación de los elementos

Para verificar la inclusión de un documento en toda la estructura de datos, tan sólo necesitamos \(log_n(m)\) pruebas. Dónde \(n\) es la cantidad de agrupaciones que se hacen para calcular cada nuevo paso y \(m\) es el número de hojas del árbol.

Siguiendo el ejemplo anterior, para verificar la inclusión del elemento número 4 dentro de la estructura completa de árbol, tan sólo sería necesario contar con la información de \(log_2(8)=3\) nodos adyacentes.

Verificación de un documento

Concretamente, podríamos determinar si el elemento número 4 forma parte del árbol gracias a la información de los hashes 5, 11 y 12. Deberíamos calcular si la unión de éstos en el orden adecuado es equivalente a la raíz del árbol. De ser así, podríamos determinar que, efectivamente, el elemento número 4 forma parte del árbol. Procederíamos de forma análoga para cualquier otro elemento y sería necesaria la misma cantidad de información.e información

Información sensible

Y además, podemos hacer notar que en ningún momento hemos revelado información acerca de los otros elementos, tan sólo son necesarios los hashes de los nodos adyacentes durante la construcción de la estructura de datos completa.

Gracias a esta estructura se ha podido realizar un registro de una gran cantidad de información de forma compacta garantizando la integridad.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *