Merkle Trees y prueba de inclusión con TypeScript y TDD

Los árboles de Merkle fueron desarrollados en 1979 por Ralph Merkle, el padre de la criptografía asimétrica y de las funciones hash.

Miguel A. Gómez · Seguir16 min read ·

Hace un tiempo que estoy estudiando sistemas Blockchain en general y en particular el código de Bitcoin. Durante este proceso me he topado con los conocidos como árboles de Merkle, o Merkle Trees en inglés. Estos árboles son un elemento fundamental en el algoritmo de validación de transacciones de Bitcoin, formando parte a su vez del famoso mecanismo de consenso. Esta estructura es una pieza criptográfica muy interesante de implementar desde un punto de vista didáctico, ya que se interconectan conceptos de criptografía con estructuras jerárquicas de datos. La idea de este artículo es realizar una implementación aplicando un enfoque híbrido, interconectando conceptos de POO con elementos programación funcional como inmutabilidad, recursividad y high order functions, todo ello aplicando TDD y buenas prácticas. Así que independientemente de que te interese el mundo Blockchain o no, te invito que sigas el artículo hasta el final.

Los árboles de Merkle no son un concepto nuevo, fueron desarrollados y patentados en 1979 por Ralph Merkle, el padre de la criptografía asimétrica y de las funciones hash. En esencia un árbol de Merkle, también conocido como un árbol hash binario, es una estructura de datos jerárquica, en concreto un árbol binario balanceado y completo en el que cada uno de los elementos viene representado por un hash criptográfico. Se usa para resumir y verificar de manera eficiente la integridad de grandes conjuntos de datos. Recuerda, un árbol es binario cuando tiene cero, uno o dos nodos hijos, y además es balanceado cuando las alturas de los dos subárboles de todos sus nodos no difiere en más de uno. Por otro lado, un árbol binario completo es aquel en el que todos los niveles (excepto el más profundo) están completamente llenos de nodos. El nivel más profundo puede llenarse parcialmente, pero todos los nodos deben generarse transversalmente desde la izquierda hasta la derecha y sin que se formen espacios entre ellos.

Aplicaciones

Los árboles de Merkle tienen múltiples utilidades. En Bitcoin, por ejemplo, se usan para resumir todas las transacciones de un bloque concreto mediante una huella digital conocida como raíz de Merkle o Merkle root. Mediante esta raíz y un subconjunto del árbol conocido como Merkle path se puede verificar si un dato concreto (en el caso de Bitcoin, una transacción) se encuentra dentro de un bloque sin tener que disponer del árbol entero o de toda la colección de datos, en los siguientes párrafos veremos como implementar esto con TypeScript. Los árboles de Merkle, además de usarse en tecnologías blockchain, tienen otras aplicaciones, como pueden ser:

• Bases de datos: Apache Cassandra y otros sistemas NoSQL los usan para mantener la integridad de sus datos sin sacrificar rendimiento.
• Sistemas de control de versiones como Git, Mercurial y Subversion.
• También los podemos encontrar en sistemas de ficheros distribuidos. Desarrollos como Ceph, BTRFS, ZFS e IPFS; usan estos árboles de hash con el fin de verificar y mantener la integridad de la información.
• Sin lugar a dudas, el mayor uso de los árboles de Merkle es hacer seguros los bloques de datos recibidos de otros nodos en redes P2P, como por ejemplo BitTorrent. Ya que verifican que los fragmentos de diferentes archivos son recibidos sin haber sido alterados.

El algoritmo

El árbol de merkle se construye de abajo hacia arriba, es decir, desde las hojas hasta la raíz, y de forma transversal, de izquierda a derecha. Para ello se ejecuta una función de hash en pares de nodos recursivamente hasta que solo queda un único hash, este último se le conoce como raíz de Merkle. En nuestra implementación usaremos como función de hash el algoritmo SHA-256, para ello nos apoyaremos en la librería crypto-js. En Bitcoin también se usa este algoritmo, con la diferencia de que se aplica doblemente, es decir, se genera un hash a partir del hash anterior. Nosotros para simplificar, sólo lo aplicaremos una vez.

Veamos un ejemplo, imagina que tenemos una con una colección que contiene los siguientes cuatro elementos: 'A', 'B', 'C' y 'D'. A cada uno de estos elementos se le aplica la función hash, cuyos hashes resultantes (HA, HB, HC, y HD) forman las hojas del árbol. Es importante tener en cuenta que la colección de elementos en sí misma no se almacena en el árbol de merkle. A continuación, los pares de hojas consecutivas se concatenan y se les vuelve a aplicar la función hash, de esta manera se obtiene el siguiente nivel de nodos, en este caso HAB y HCD. En el siguiente paso, se aplica la función hash en estos dos últimos nodos obteniendo así la raíz de Merkle (HABCD):

¿Qué pasaría en el caso de tener un número impar de hojas o de nodos intermedios? En ese caso lo que se haría es calcular el hash del elemento concatenado consigo mismo, de esta manera mantendremos constantemente los nodos con un número par de elementos. Por ejemplo, si en lugar de la colección anterior tuviéramos A, B y C, tendremos como primer nivel de nodos padre HAB y HCC y como raíz de Merkle HABCC:

¿Cómo lo vamos a implementar?

Para la implementación del algoritmo vamos aplicar un estilo híbrido donde combinaremos algunos elementos de orientación a objetos, como clases y value objects, con algunos elementos de programación funcional como inmutabilidad, recursividad y las funciones de alto nivel map, filter y reduce; además nos pondremos algunas restricciones que me gusta aplicar en mi dia a dia, como evitar el uso de bucles y de bloques else.

Los árboles en general se pueden representar de múltiples formas, en nuestro caso lo vamos a hacer mediante una matrix de bidimensional en la que cada uno de las filas se corresponde con un nivel del árbol, como veremos implementarlo a través de una matriz simplifica la representación y la generación. La matriz la vamos a construir como si de una pila se tratase, apilando las filas. Donde la primera fila insertada contendrá el nodo de hojas y el último la raíz de Merkle. Esta estructura la vamos a definir como una matriz de hashes de solo lectura para evitar mutar su contenido, además la vamos a encapsular dentro de un tipo rico en comportamiento e inmutable, un value object. Para representarlo vamos a utilizar una clase, cuyos métodos estáticos contendrán toda la lógica necesaria para construir la estructura e instanciar el objeto. Y, por otro lado, los métodos de instancia expondrán la API mínima necesaria para poder realizar la prueba de inclusión.

Generando el Merkle Tree con TDD

Vamos a implementar la solución al algoritmo aplicando TDD. Empezamos por el primer test, en el que comprobaremos que se genera un árbol de hash binario para una colección dada de elementos. Tratar de resolver directamente este test puede ser un paso demasiado grande. Lo que vamos a hacer es ir añadiendo aserciones intermedias que nos permitan dar pequeños pasos hasta la solución. Luego decidiremos si las dejamos en el test o simplemente las eliminamos. Comenzamos por una aserción que evalúa si las hojas se están generando correctamente para la colección dada. Para generar los hashes nos podemos apoyar en cualquier generador online de SHA256. Recuerda las funciones hash son deterministas, es decir, para una misma entrada siempre se obtiene la misma salida.

describe('The Merkle Tree', () => {
        it('generates a binary hash tree from a given collection with an even number of elements', () => {
                const merkelTree = MerkleTree.createTree(['a', 'b', 'c', 'd']);

                expect(merkelTree.getLeaves()).toEqual([
                        'ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb',
                        '3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d',
                        '2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6',
                        '18ac3e7343f016890c510e93f935261169d9e3f565436429830faf0934f4f8e4',
                ]);
        });
});

Después, comenzamos a implementar los métodos getLeaves y createTree. Para ello creamos el esqueleto básico de la clase y sus tipos.

import * as CryptoJS from 'crypto-js';

export type Hash = string;

export class MerkleTree {
        private readonly layers: ReadonlyArray<ReadonlyArray<Hash>>;

        constructor(layers: ReadonlyArray<ReadonlyArray<Hash>>) {
                this.layers = layers;
        }

        static createTree(elements: ReadonlyArray<string>): MerkleTree {
                const leaves = elements.map(element => CryptoJS.SHA256(element).toString());
                
                return new MerkleTree([leaves]);
        }

        getLeaves(): ReadonlyArray<Hash> {
                return this.layers[0];
        }
}

Ejecutamos el test y observamos como pasa correctamente, por lo que podemos dar por solucionado este primer paso. A continuación, añadimos aserciones para comprobar que las capas intermedias y la raíz del árbol se generan correctamente.

// the getLayer is the algorithm that we are testing
// so we are adding those assertions in the first test.
// We should refactor this when we implement the verifyProof method.
expect(merkelTree.getLayer(1)).toEqual([
        'e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a',
        '52f879dbd33d96dfa20de0503b61ae53ef1bf7a41efda3c6f751d53db7d8f368'
]);

expect(merkelTree.getLayer(2)).toEqual([
        'd6ed4fadc79abf8d9ef527aee5bb54b3c45fa878a8ea90a926e12446c63d0fd1'
]);

expect(merkelTree.getRoot()).toBe(
        'd6ed4fadc79abf8d9ef527aee5bb54b3c45fa878a8ea90a926e12446c63d0fd1'
);

Luego implementamos los métodos getLayer, getRoot y el algoritmo para generar las capas intermedias del árbol hasta la raíz. Para ello nos vamos a apoyar en técnicas recursivas:

static createTree(elements: ReadonlyArray<string>): MerkleTree {
        const leaves = elements.map(element => CryptoJS.SHA256(element).toString());

        if(elements.length === 0) return new MerkleTree([]);
        
        return new MerkleTree(MerkleTree.getLayers(leaves));
}

private static getLayers(leaves: ReadonlyArray<Hash>): ReadonlyArray<ReadonlyArray<Hash>> {
        const layers: Array<ReadonlyArray<Hash>> = [];
        layers.push(leaves);

        // Get next layer until we reach the root
        MerkleTree.buildTree(leaves, layers);

        return layers;
}

private static buildTree(firstLayer: ReadonlyArray<Hash>, layers: Array<ReadonlyArray<Hash>>): void {
        const currentLayer = firstLayer;
        // Return if input is empty or only has one hash
        if(currentLayer.length <= 1) return;

        const nextLayer: Array<Hash> = [];

        // Combine each pair
        // I'm using a for loop because it's more readable than recursion
        for(let i = 0; i < currentLayer.length; i += 2) {
                const left = currentLayer[i];
                // If right element doesn't exist, the pair will be combined with itself
                const right = i + 1 === currentLayer.length
                        ? left
                        : currentLayer[i + 1];
                const combined = MerkleTree.combineHash(left, right);
                nextLayer.push(combined);
        }

        layers.push(nextLayer);

        // We continue the recursion with the higher layer
        MerkleTree.buildTree(nextLayer, layers);
}

private static combineHash(left: Hash, right: Hash): Hash {
        // See the different bit shift operators at https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_OR
        // Concat left and right hashes and hash the result
        return CryptoJS.SHA256(left + right).toString();        
}

getLayer(index: number): ReadonlyArray<Hash> {
        return this.layers[index];
}

getRoot(): Hash {
        return this.layers[this.layers.length - 1][0];
}

Ejecutamos de nuevo los tests y vemos que ahora todo pasa sin problemas. Hemos implementado la funcionalidad básica del árbol de Merkle.

Con la solución anterior logramos que pase el test para una colección de elementos pares. Ahora vamos a comprobar que el algoritmo genera correctamente un árbol cuando la colección tiene un número impar de elementos.

it("generates a binary hash tree from a given collection with an odd number of elements", () => {
        const merkelTree = MerkleTree.createTree(['a', 'b', 'c']);

        expect(merkelTree.getLeaves()).toEqual([
                'ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb',
                '3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d',
                '2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6',
        ]);
        
        expect(merkelTree.getLayer(1)).toEqual([
                'e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a',
                '2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6'
        ]);
        
        expect(merkelTree.getLayer(2)).toEqual([
                '82f2cf5e01a1e6d6a83b0736231fa295a6a12efd1547c3965ef84e1ab8f42da0'
        ]);
        
        expect(merkelTree.getRoot()).toBe(
                '82f2cf5e01a1e6d6a83b0736231fa295a6a12efd1547c3965ef84e1ab8f42da0'
        );
});

En este caso, con la implementación actual, el test debería fallar debido a que no estamos duplicando el elemento cuando es impar.

Para resolver esto vamos a modificar el método buildTree para que duplique el último elemento cuando el número de elementos sea impar:

private static buildTree(firstLayer: ReadonlyArray<Hash>, layers: Array<ReadonlyArray<Hash>>): void {
        const currentLayer = firstLayer;
        // Return if input is empty or only has one hash
        if(currentLayer.length <= 1) return;

        const nextLayer: Array<Hash> = [];

        // Combine each pair
        for(let i = 0; i < currentLayer.length; i += 2) {
                const left = currentLayer[i];
                // If right element doesn't exist, the pair will be combined with itself
                const right = i + 1 === currentLayer.length
                        ? left
                        : currentLayer[i + 1];
                const combined = MerkleTree.combineHash(left, right);
                nextLayer.push(combined);
        }

        layers.push(nextLayer);

        // We continue the recursion with the higher layer
        MerkleTree.buildTree(nextLayer, layers);
}

En realidad, esto ya lo habíamos implementado, pues si te fijas en el código anterior, cuando no existe el elemento derecho (i + 1), se usa el elemento izquierdo (left) al hacer el hash. Así, al ejecutar los tests, veremos que también pasa sin problemas.

Generando una prueba de inclusión

Ahora vamos a centrarnos en el algoritmo de verificación o prueba de inclusión. La idea es demostrar que un elemento específico está incluido en el árbol sin necesidad de tener todos los elementos de la colección original. La prueba de inclusión implica proporcionar un camino desde un elemento particular hasta la raíz del árbol. Si podemos reproducir la raíz del árbol utilizando este camino, entonces el elemento está incluido.

Comenzamos con un test para verificar que podemos obtener la prueba de inclusión para un elemento dado, vamos a utilizar un árbol con 4 elementos para simplificar:

it("gets a merkle proof for a leaf", () => {
        const elements = ['a', 'b', 'c', 'd'];
        const merkleTree = MerkleTree.createTree(elements);
        
        const proof = merkleTree.getProof(0); // Proof for element 'a' at index 0
        
        expect(proof).toEqual([
                {
                        position: 'right',
                        data: '3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d'
                },
                {
                        position: 'right',
                        data: '52f879dbd33d96dfa20de0503b61ae53ef1bf7a41efda3c6f751d53db7d8f368'
                }
        ]);
});

Esto es básicamente el camino o ruta de hash que necesitamos seguir desde la hoja hasta la raíz. Cada elemento de la prueba indica la posición (izquierda o derecha) donde tendríamos que concatenar este hash para llegar a la raíz.

Implementamos el método getProof:

export type Position = 'left' | 'right';

export interface ProofStep {
        position: Position;
        data: Hash;
}

export type Proof = ReadonlyArray<ProofStep>;

getProof(index: number): Proof {
        if (index < 0 || index >= this.getLeaves().length) {
                return [];
        }
        
        const proof: Array<ProofStep> = [];
        let currentIndex = index;
        
        for (let i = 0; i < this.layers.length - 1; i++) {
                const currentLayer = this.layers[i];
                const isRightNode = currentIndex % 2 === 0;
                const pairIndex = isRightNode ? currentIndex + 1 : currentIndex - 1;
                
                if (pairIndex < currentLayer.length) {
                        proof.push({
                                position: isRightNode ? 'right' : 'left',
                                data: currentLayer[pairIndex]
                        });
                }
                
                // Move to the parent index in the next layer
                currentIndex = Math.floor(currentIndex / 2);
        }
        
        return proof;
}

Al ejecutar el test, veremos que falla. Esto se debe a que nuestro algoritmo tiene un problema en la lógica de cómo se determinan las posiciones en la prueba. Vamos a revisarlo y corregirlo:

getProof(index: number): Proof {
        if (index < 0 || index >= this.getLeaves().length) {
                return [];
        }
        
        const proof: Array<ProofStep> = [];
        let currentIndex = index;
        
        for (let i = 0; i < this.layers.length - 1; i++) {
                const currentLayer = this.layers[i];
                // If it's an even index, the pair is to the right
                // If it's an odd index, the pair is to the left
                const isOddIndex = currentIndex % 2 === 1;
                const pairIndex = isOddIndex ? currentIndex - 1 : currentIndex + 1;
                
                if (pairIndex < currentLayer.length) {
                        proof.push({
                                position: isOddIndex ? 'left' : 'right',
                                data: currentLayer[pairIndex]
                        });
                }
                
                // Move to the parent index in the next layer
                currentIndex = Math.floor(currentIndex / 2);
        }
        
        return proof;
}

Ahora el test debería pasar. La corrección principal está en cómo determinamos la posición del par para el índice actual.

Verificando la prueba de inclusión

Una vez que tenemos la capacidad de obtener una prueba de inclusión, necesitamos una forma de verificarla. Esto es crucial en sistemas como Bitcoin, donde los nodos ligeros necesitan verificar transacciones sin tener que almacenar toda la cadena de bloques.

Creamos un test para el método verifyProof:

it("verifies a merkle proof correctly", () => {
        const elements = ['a', 'b', 'c', 'd'];
        const merkleTree = MerkleTree.createTree(elements);
        const root = merkleTree.getRoot();
        
        // Get proof for element 'a'
        const proof = merkleTree.getProof(0);
        
        // Hash of 'a'
        const leafHash = CryptoJS.SHA256('a').toString();
        
        expect(MerkleTree.verifyProof(proof, leafHash, root)).toBe(true);
        
        // This should be false for an incorrect hash
        const wrongHash = CryptoJS.SHA256('wrong').toString();
        expect(MerkleTree.verifyProof(proof, wrongHash, root)).toBe(false);
});

Y ahora implementamos el método estático verifyProof:

static verifyProof(proof: Proof, targetHash: Hash, root: Hash): boolean {
        let hash = targetHash;
        
        for (const step of proof) {
                if (step.position === 'left') {
                        hash = CryptoJS.SHA256(step.data + hash).toString();
                } else {
                        hash = CryptoJS.SHA256(hash + step.data).toString();
                }
        }
        
        return hash === root;
}

Este método toma una prueba, el hash del elemento objetivo y la raíz del árbol. Recorre cada paso de la prueba, concatenando los hashes según la posición indicada en cada paso, y finalmente compara el resultado con la raíz esperada.

Con esto, ya tenemos implementada la funcionalidad completa del árbol de Merkle con capacidad para generar y verificar pruebas de inclusión.

Mejorando la solución: Refactorización y optimización

Ahora que tenemos todos los tests pasando, vamos a refactorizar nuestro código para hacerlo más limpio, eliminar los bucles for y aplicar un enfoque más funcional:

import * as CryptoJS from 'crypto-js';

export type Hash = string;
export type Position = 'left' | 'right';
export interface ProofStep {
        position: Position;
        data: Hash;
}
export type Proof = ReadonlyArray<ProofStep>;

export class MerkleTree {
        private constructor(private readonly layers: ReadonlyArray<ReadonlyArray<Hash>>) {}

        static createTree(elements: ReadonlyArray<string>): MerkleTree {
                const leaves = elements.map(element => CryptoJS.SHA256(element).toString());
                
                if (elements.length === 0) return new MerkleTree([]);
                
                return new MerkleTree(MerkleTree.getLayers(leaves));
        }

        private static getLayers(leaves: ReadonlyArray<Hash>): ReadonlyArray<ReadonlyArray<Hash>> {
                const buildNextLayer = (layer: ReadonlyArray<Hash>): ReadonlyArray<Hash> => {
                        return Array.from({ length: Math.ceil(layer.length / 2) }, (_, i) => {
                                const left = layer[i * 2];
                                const right = i * 2 + 1 < layer.length ? layer[i * 2 + 1] : left;
                                return MerkleTree.combineHash(left, right);
                        });
                };

                const layers: ReadonlyArray<Hash>[] = [leaves];
                let currentLayer = leaves;

                while (currentLayer.length > 1) {
                        currentLayer = buildNextLayer(currentLayer);
                        layers.push(currentLayer);
                }

                return layers;
        }

        private static combineHash(left: Hash, right: Hash): Hash {
                return CryptoJS.SHA256(left + right).toString();
        }

        getLeaves(): ReadonlyArray<Hash> {
                return this.layers[0] || [];
        }

        getLayer(index: number): ReadonlyArray<Hash> {
                return this.layers[index] || [];
        }

        getRoot(): Hash {
                const lastLayer = this.layers[this.layers.length - 1];
                return lastLayer && lastLayer.length > 0 ? lastLayer[0] : '';
        }

        getProof(index: number): Proof {
                if (index < 0 || index >= this.getLeaves().length) {
                        return [];
                }
                
                const proof: ProofStep[] = [];
                let currentIndex = index;
                
                this.layers.slice(0, -1).forEach(layer => {
                        const isRightNode = currentIndex % 2 === 1;
                        const pairIndex = isRightNode ? currentIndex - 1 : currentIndex + 1;
                        
                        if (pairIndex < layer.length) {
                                proof.push({
                                        position: isRightNode ? 'left' : 'right',
                                        data: layer[pairIndex]
                                });
                        }
                        
                        currentIndex = Math.floor(currentIndex / 2);
                });
                
                return proof;
        }

        static verifyProof(proof: Proof, targetHash: Hash, root: Hash): boolean {
                return proof.reduce(
                        (hash, step) => MerkleTree.combineHash(
                                step.position === 'left' ? step.data : hash,
                                step.position === 'left' ? hash : step.data
                        ),
                        targetHash
                ) === root;
        }
}

Esta versión refactorizada utiliza un enfoque más funcional y evita los bucles for en favor de métodos de array como map, reduce y slice. También hemos mejorado la legibilidad y la organización del código.

Conclusión

En este artículo, hemos implementado un árbol de Merkle completo con TypeScript, aplicando buenas prácticas de programación como TDD, inmutabilidad y un enfoque funcional. Los árboles de Merkle son estructuras de datos fundamentales en sistemas como Bitcoin y otras tecnologías blockchain, proporcionando una forma eficiente de verificar la integridad de grandes conjuntos de datos.

Nuestra implementación permite:

1. Crear un árbol de Merkle a partir de cualquier colección de elementos
2. Manejar colecciones con números pares e impares de elementos
3. Generar pruebas de inclusión para cualquier elemento del árbol
4. Verificar estas pruebas sin necesidad de tener acceso a todo el árbol

Este tipo de estructuras de datos criptográficas son esenciales en sistemas distribuidos donde la confianza y la integridad son preocupaciones primordiales. Al implementar este algoritmo, hemos profundizado en cómo funcionan estas estructuras y cómo pueden utilizarse para resolver problemas reales de verificación de datos.

Si quieres ampliar tus conocimientos sobre este tema, te recomiendo explorar cómo se implementan los árboles de Merkle en sistemas reales como Bitcoin o Ethereum, y considerar otras variantes como los árboles de Merkle Patricia o los árboles Merkle-Damgard. Cada uno tiene sus propias características y aplicaciones específicas en el mundo de la criptografía y la blockchain.