Entendiendo las Estructuras de Datos en Blockchain: Merkle Tree, Radix Trie y Merkle Patricia Trie

Bitcoin, la primera red descentralizada basada en blockchain, popularizó el uso de Merkle trees para la inclusión escalable de transacciones. Ethereum también utiliza Merkle tree, pero además emplea Patricia Merkle Tries para sus necesidades de almacenamiento de datos.

En la imagen podemos ver una cadena de bloques de Bitcoin, donde cada bloque tiene un encabezado (header) con los siguientes campos: previous hash, timestamp, nonce y merkle root.

• Previous hash: El hash del bloque anterior, que actúa como un puntero hash, similar a un puntero en memoria. Esto asegura la integridad y continuidad de la cadena de bloques.
• Timestamp: La fecha en la que se minó el bloque, que ayuda a mantener el orden cronológico de la cadena.
• Nonce: Un identificador único del bloque, utilizado en el proceso de prueba de trabajo (Proof of Work) para encontrar un hash válido.
• Merkle root: Contiene los hashes de todas las transacciones del bloque. Esto permite la verificación eficiente y segura de la integridad de las transacciones del bloque. (Cabe recalcar que cada bloque tiene un límite de transacciones).

Radix trie

Antes de continuar aprendiendo sobre la estructura de datos Merkle Tree, es importante conocer el Radix Trie. El Radix Trie es una estructura de datos utilizada para recuperar valores de tipo string recorriendo las ramas del árbol hacia abajo. Los nodos en el Radix Trie almacenan referencias asociadas (keys), que juntas conducen al valor final que se puede devolver. Esta estructura es eficiente para operaciones de búsqueda y es comúnmente utilizada en aplicaciones de redes y sistemas de archivos debido a su capacidad para manejar grandes conjuntos de datos de manera eficiente. en la imagen siguiente podemos ver como seria un radix trie.

Merkle Tree

El concepto de Merkle Tree fue propuesto a principios de los años 80 por Ralph Merkle, un científico informático reconocido por sus trabajos sobre criptografía de clave pública. Un árbol de Merkle es una estructura de datos utilizada para verificar de manera eficiente la integridad de un conjunto de datos. Es especialmente útil en redes peer-to-peer, donde los participantes necesitan compartir y validar información de manera independiente y segura.

Merkle tree en bitcoin

Los árboles de Merkle son ideales para las transacciones, ya que son una estructura de datos perfecta para este propósito. Las transacciones son estáticas y no deben cambiar después de ser confirmadas, quedando “grabadas en piedra” mediante la construcción de la raíz hash de Merkle. Dado que los árboles de Merkle no son aptos para la edición, la eficiencia de modificación de registros no es relevante en este caso.

El principal objetivo de su uso es demostrar la coherencia de los datos a medida que crece la cadena de bloques. Gracias a los árboles de Merkle, podemos estar seguros de que una transacción existió en un momento dado en un bloque. Esto se logra construyendo un Merkle proof. Además, la construcción de merkle proof es extremadamente eficiente a escala, ya que son rápidas de calcular y sólo requieren pequeños fragmentos de datos para ser comunicados a través de la red.

El proceso de hashing en un árbol de Merkle en Bitcoin comienza en los nodos del nivel más bajo (leaf — level). Los hashes de estos nodos se combinan para formar los hashes de los nodos del siguiente nivel. Este proceso continúa nivel por nivel, combinando los hashes, hasta llegar al hash único en la raíz del árbol.

El árbol de Merkle se utiliza para verificar la integridad y consistencia de los datos de las transacciones en un bloque de manera eficiente. La estructura jerárquica permite que cualquier modificación en una transacción se propague hacia la raíz, facilitando la detección de manipulaciones. Además, permite verificar la pertenencia de una transacción específica en un bloque sin necesidad de revisar todas las transacciones, mejorando la eficiencia y reduciendo la carga computacional.

Trees in Ethereum

Ethereum utiliza una estructura de datos llamada Radix Trie, también conocida como Patricia Trie o Radix tree, y la combina con un Merkle tree para crear un Patricia Merkle Trie.

Patricia Trie + Merkle Tree = Patricia Merkle Trie

Patricia Merkle Trie son básicamente Merkle tree con esteroides. Eficientes para las necesidades de verificación de datos, pero también eficientes para editar esos datos.

Ethereum utiliza un Merkle Patricia Trie (MPT) para su representación de estado. El MPT combina las ventajas tanto de los Patricia Tries como de los Merkle Trees, permitiendo un almacenamiento y verificación eficientes y seguros del estado de la blockchain.

Patricia
P = Práctico
A = Algoritmo
T = Para
R = Recuperar
I = Información
C = Codificado
I = En
A = Alfanumérico

Características principales

Patricia Trie:
Almacenamiento eficiente: Comprime los prefijos comunes de las claves, reduciendo el espacio de almacenamiento.
Consultas rápidas: Proporciona búsquedas, inserciones y eliminaciones eficientes de claves-valores.

Merkle Tree
Integridad criptográfica: Utiliza hashes para garantizar la integridad de los datos y verificar su inclusión de forma eficiente.
Pruebas: Permite crear pruebas Merkle para verificar la presencia de datos sin revelar todo el conjunto de datos.

En las imagen anterior podemos ver el block header que tiene campos similares a los de Bitcoin. En este post, nos centraremos en receiptsRoot, transactionsRoot y stateRoot

1. stateRoot

stateRoot es el hash raíz del state trie (o state Merkle Patricia trie) después de que se hayan procesado todas las transacciones del bloque. el stateRoot es una estructura de datos compleja que almacena el estado actual de todas las cuentas, incluidos balance, contract storage y otros datos relevantes.

El stateRoot garantiza que cualquier alteración del estado sea fácilmente detectable. Después de ejecutar todas las transacciones de un bloque, el estado de la red cambia y estado resultante se convierte en hash para formar el stateRoot.

• State:Incluye información como balances, contract code y storage. Cada cuenta y contrato en Ethereum tiene una dirección única que apunta a su estado.

2. transactionsRoot

The transactionsRoot es el hash raíz del trie de transacciones (o trie Merkle Patricia de transacciones) del bloque. Este trie contiene todas las transacciones incluidas en el bloque.

3. receiptsRoot

The receiptsRoot ies el hash raíz del receipt trie (o trie Merkle Patricia de recibos) del bloque. Este trie contiene los recibos de cada transacción del bloque.

• Receipt Trie: Un Merkle Patricia Trie donde cada leaf node contiene el hash de un recibo de transacción. Un recibo incluye información como si la transacción se ha realizado correctamente, cuánto gas se ha utilizado y cualquier entrada de registro creada por la transacción.

En resumen, stateRoot, transactionsRoot y receiptsRoot son componentes cruciales de un bloque de Ethereum que garantizan la integridad, seguridad y eficiencia de la cadena de bloques. Se derivan de state trie, transaction trie y receipt trie, respectivamente, y desempeñan un papel vital en los procesos de consenso y verificación.