Cómo implementar un árbol Merkle en Solidity

Un árbol Merkle es un árbol binario que permite verificar de manera eficiente y segura el contenido de grandes estructuras de datos. El concepto de este árbol fue propuesto y patentado en 1982 por Ralph Merkle, un criptógrafo estadounidense.

La longitud del hash sigue siendo la misma para cualquier cantidad de datos de entrada. Los vértices de las hojas contienen hashes de bloques de datos, mientras que los vértices internos incluyen hashes de la suma de valores en dos vértices secundarios. A su vez, el vértice raíz comprende el hash de todo el conjunto de datos.

Teoría

Inicialmente, hay un conjunto de datos que no están relacionados entre sí de ninguna manera. Para cada bloque de datos (en el contexto de una cadena de bloques de transacciones), necesitamos calcular un hash del bloque. El número de bloques de datos debe ser 2^N , porque a medida que se construye el árbol, los bloques anteriores se procesan en pares en cada iteración. Luego se agrupa un par de hashes y se crea un nuevo hash basado en ellos. El hash continuará mientras haya algo que agrupar en cada nivel, y se detendrá cuando solo quede un par del cual se obtenga el hash raíz, la raíz de Merkle.

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

Una vez que tenemos la raíz, podemos validar los datos. Si el hash raíz coincide con el hash original, todo está bien, los datos son válidos. También es posible comprobar de forma eficaz si determinados datos están presentes en la estructura de árbol.

Digamos que queremos comprobar que el hash H2 está presente en el árbol. La prueba será una serie de datos: H1 , H3-4 , H5-6-7-8 . Gracias a estos hashes, podemos reconstruir el hash raíz:

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

Luego comparamos el hash resultante con el original. Si coinciden, significa que el hash H2 está presente en el árbol.

Práctica

Veamos ahora cómo implementar un árbol Merkle y validación de datos en Solidity.

Para simplificar, escribiremos la matriz de transacciones directamente en la cadena de bloques, así como la matriz de hashes. Dado que usaremos la función keccak256 incorporada, que devuelve un hash de 32 bytes, el tipo de datos de la matriz hashes será bytes32 . La matriz también tendrá una longitud dinámica. En general, la longitud de la matriz de hashes no será la misma que la longitud de la matriz de transacciones, porque contendrá los hashes producidos. Podríamos calcular la longitud por adelantado, pero por razones de simplificación del código no lo haremos. Si lo desea, puede hacer public cada uno de estos arreglos y leer los hashes de las transacciones.

Produciremos hashes en el constructor. El primer paso es contar los hashes de los bloques con transactions en el bucle. Luego, en cada nivel del árbol, la cantidad de hashes se reduce en un factor de 2. Dado que almacenaremos los hashes en la matriz de hashes, las compensaciones de índice deben almacenarse por separado. El iterador en el bucle interno se incrementa en 2 porque tomaremos un par de elementos al calcular y agregar hashes. En abi.encodePacked esta vez agregaremos 2 hashes a cada uno de los cuales configuraremos los índices correctamente: para el elemento izquierdo – el valor del desplazamiento de desplazamiento actual + el índice en el nivel de árbol actual, y para el elemento derecho – lo mismo + 1.

Entonces hemos construido el árbol, pero el interés consiste en validar los datos. Para hacer esto, escribamos una función validateTransaction que tome una transacción y su índice. Desafortunadamente, Solidity no tiene un método find para matrices, por lo que es más fácil simplemente pasar el índice de transacción.

Primero, calculemos el hash de la transacción y creemos una serie de pruebas. Encontramos el número de pruebas dependiendo de la longitud de la matriz de transacciones y establecemos la longitud proofsIndexes . A continuación, en cada nivel del árbol, encontramos el elemento necesario, dependiendo del índice, tomando el elemento derecho o izquierdo, teniendo en cuenta los desplazamientos en los hashes . Luego revisamos la matriz de índices de prueba, verificamos la paridad del índice y calculamos el hash dependiendo de si el elemento está a la izquierda o a la derecha en el par. Finalmente, comparamos el hash resultante con el hash raíz y devolvemos el resultado.

Solicitud

Hay varias aplicaciones de un árbol Merkle en blockchain.

• Almacenamiento de transacciones : en Bitcoin, por ejemplo, un bloque de transacciones almacena solo el merkle_root de sus transacciones. Esto reduce el tamaño del bloque y la carga en la red. Después de acumular una cierta cantidad de transacciones, es posible eliminar transacciones antiguas para ahorrar espacio, pero los bloques en sí permanecen sin cambios porque solo almacenan la raíz del árbol.
• Minería : un bloque de bitcoin consta de dos partes: el encabezado del bloque y la lista de transacciones. Para evitar tener que volver a calcular los hashes de las transacciones cada vez, se alinean en un árbol Merkle, después de lo cual se procesa el encabezado del bloque en lugar de todo el bloque, y se toma un número nonce aleatorio. Cuando el bloque se envía a otros nodos, se calcula la raíz de la lista de transacciones y, si no coincide con la raíz del encabezado, se rechaza el bloque.
• Verificación : La esencia de la verificación es auditar sin tener que descargar toda la cadena de bloques. El proceso se simplifica enormemente y también permite confirmar la existencia de datos sin revelar información sobre los datos, lo que puede resultar útil para verificar información sensible.

Resumen

Sin los árboles Merkle, las cadenas de bloques serían demasiado engorrosas y las pruebas de Merkle permiten una verificación rentable de la autenticidad de los datos.

Los árboles Merkle se utilizan activamente en cadenas de bloques (por ejemplo, Bitcoin, Ethereum) para almacenar transacciones de manera eficiente, pero esta no es la única aplicación. Por ejemplo, después del colapso del intercambio FTX, muchos intercambios implementaron un mecanismo de prueba de reserva, que utiliza un árbol Merkle.