Árbol de Merkle

¿Qué es un árbol de Merkle?

Un árbol de Merkle es una estructura de datos criptográfica que organiza numerosos datos en un árbol de hashes.

En el mundo cripto, los árboles de Merkle ayudan a las blockchains a verificar transacciones, saldos, cuentas, valores de almacenamiento, reclamaciones de airdrops, listas de permitidos de NFT y otros conjuntos de datos grandes de forma eficiente.

Un árbol de Merkle también se denomina árbol hash, porque cada nivel del árbol se construye a partir de valores hash criptográficos.

El nivel inferior contiene elementos de datos individuales llamados hojas.

Cada hoja se procesa mediante un hash, se empareja con otro hash y se vuelve a procesar para crear el nivel siguiente.

El proceso continúa hasta que queda un único hash final en la parte superior.

Ese hash final se denomina raíz de Merkle.

La guía para desarrolladores de Bitcoin explica que los hashes de las transacciones se emparejan y se procesan mediante hashes de forma repetida hasta que queda una única raíz de Merkle en la cabecera del bloque.

La idea clave es sencilla: una raíz pequeña puede representar un conjunto de datos grande.

Si cambia algún elemento del conjunto de datos, también cambian los hashes que hay por encima y, por tanto, la raíz de Merkle.

Cómo funciona un árbol de Merkle

Un árbol de Merkle comienza con datos sin procesar, como transacciones, direcciones de wallet, registros de cuentas o entradas de reclamaciones.

Cada elemento se procesa mediante una función hash criptográfica para crear el hash de una hoja.

Se combinan dos hashes de hoja y se procesan juntos para crear un hash padre.

A continuación, se emparejan y procesan de nuevo los hashes padre para crear hashes de niveles superiores.

El proceso continúa hasta que solo queda un hash.

Ese hash final es la raíz de Merkle.

La raíz de Merkle actúa como una huella digital compacta del conjunto de datos completo.

Si los datos no cambian, el mismo método de construcción del árbol debería producir la misma raíz.

Si cambia una transacción, una dirección, un saldo o el importe de una reclamación, también debería cambiar la raíz final.

Por qué son importantes los árboles de Merkle en el mundo cripto

Los árboles de Merkle son importantes porque las blockchains deben verificar grandes cantidades de datos sin obligar a todos los usuarios a procesarlo todo constantemente.

Un bloque de una blockchain puede contener muchas transacciones.

Un airdrop de tokens puede incluir miles o millones de wallets que cumplen los requisitos.

Una base de datos del estado de una blockchain puede incluir cuentas, saldos, almacenamiento de contratos y código.

Los árboles de Merkle permiten a los sistemas comprometerse con conjuntos de datos grandes mediante una única raíz y, al mismo tiempo, verificar elementos individuales posteriormente.

Esto mejora la eficiencia, la escalabilidad y la integridad de los datos.

También reduce las necesidades de almacenamiento y ancho de banda de muchas aplicaciones cripto.

Sin árboles de Merkle u otras estructuras de datos autenticadas similares, muchas tareas de verificación de blockchain serían más lentas, complejas y caras.

Raíz de Merkle

La raíz de Merkle es el hash final situado en la parte superior de un árbol de Merkle.

Representa todos los datos que hay por debajo.

En un bloque de una blockchain, la raíz de Merkle puede resumir todas las transacciones incluidas en ese bloque.

En un contrato de airdrop, la raíz de Merkle puede resumir todas las direcciones de wallet que cumplen los requisitos y los importes que pueden reclamar.

En un árbol de estado, la raíz puede resumir numerosas cuentas o valores de almacenamiento.

La raíz no revela por sí sola el conjunto de datos completo.

Solo actúa como compromiso criptográfico con ese conjunto de datos.

Para confirmar que un elemento pertenece al árbol, un usuario sigue necesitando la prueba adecuada y las reglas de verificación correspondientes.

Hojas y ramas de un árbol de Merkle

Las hojas son los hashes del nivel inferior de un árbol de Merkle.

Cada hoja suele representar un elemento de datos.

Por ejemplo, una hoja puede representar un hash de transacción, una dirección de wallet, un registro de reclamación, un permiso de acuñación de NFT o un valor de cuenta.

Las ramas son los hashes intermedios que hay entre las hojas y la raíz.

Las ramas conectan las hojas individuales con la raíz de Merkle final.

Una prueba de Merkle utiliza estos hashes de rama para demostrar que una hoja pertenece al árbol.

Este diseño permite verificar la inclusión sin mostrar ni descargar las demás hojas.

Pruebas de árbol de Merkle

Una prueba de árbol de Merkle es el conjunto de hashes hermanos necesarios para demostrar que una hoja pertenece a un árbol cuya raíz es conocida.

El verificador comienza con la hoja objetivo y la combina con los hashes de la prueba en el orden correcto.

Si el hash final calculado coincide con la raíz de confianza, la prueba es válida.

Si el hash final calculado no coincide con la raíz de confianza, la prueba no es válida.

La documentación de OpenZeppelin MerkleProof describe herramientas para contratos inteligentes que permiten verificar si se puede demostrar que una hoja forma parte de un árbol de Merkle definido por una raíz.

Por eso, los árboles de Merkle son útiles para listas de permitidos, reclamaciones, recompensas y comprobaciones de acceso on-chain.

Árboles de Merkle en Bitcoin

Bitcoin utiliza árboles de Merkle para organizar las transacciones de los bloques.

Se aplica un hash a cada transacción; después, los hashes de las transacciones se emparejan y se procesan hacia arriba hasta generar una única raíz de Merkle.

La raíz de Merkle se almacena en la cabecera del bloque.

Esto ayuda a los nodos de Bitcoin a detectar si se han modificado los datos de las transacciones.

También permite una verificación ligera de las transacciones.

Un cliente ligero puede utilizar una prueba de Merkle para comprobar si una transacción está incluida en un bloque sin descargar todas las transacciones de ese bloque.

Esto permite la verificación de pagos simplificada, conocida habitualmente como SPV.

SPV ofrece una validación menos completa que la de un nodo completo, pero resulta más eficiente para dispositivos y wallets con recursos limitados.

Árboles de Merkle en Ethereum

Ethereum utiliza una estructura de datos autenticada relacionada llamada Merkle Patricia Trie.

La documentación de Ethereum sobre el Merkle Patricia Trie explica que la estructura de Ethereum es determinista y verificable criptográficamente.

Esta estructura ayuda a Ethereum a representar el estado de las cuentas, el almacenamiento y otros datos de clave-valor.

Si cambia el estado, también cambia la raíz de estado.

Esto permite a los clientes y las aplicaciones de Ethereum verificar los datos de estado frente a una raíz conocida.

El estándar EIP-1186 eth_getProof describe un método RPC para obtener pruebas de Merkle de cuentas y valores de almacenamiento de Ethereum.

La estructura de Ethereum no es igual que un árbol de Merkle binario sencillo, pero utiliza la misma idea fundamental de verificación mediante hashes enlazados.

Árboles de Merkle en airdrops

Los airdrops de criptomonedas suelen utilizar árboles de Merkle para gestionar listas de reclamaciones grandes.

Un proyecto puede crear una lista de direcciones de wallet que cumplen los requisitos y de los importes de tokens correspondientes.

Cada pareja de dirección e importe se convierte en una hoja del árbol de Merkle.

El proyecto solo almacena la raíz de Merkle en el contrato inteligente.

Cuando un usuario reclama el airdrop, envía una prueba de Merkle.

El contrato verifica que la wallet y el importe pertenecen al árbol representado por la raíz almacenada.

Esto ahorra comisiones de gas, ya que el contrato no necesita almacenar directamente on-chain todas las wallets que cumplen los requisitos.

También hace más prácticas las campañas de reclamación de gran tamaño.

Árboles de Merkle en listas de permitidos de NFT

Los proyectos de NFT suelen utilizar árboles de Merkle para listas de permitidos, preventas y acceso anticipado a la acuñación.

En lugar de almacenar cada dirección de wallet aprobada en un contrato, el proyecto almacena una única raíz de Merkle.

Cada wallet aprobada recibe una prueba que demuestra que forma parte de la lista de permitidos.

Durante la acuñación, el contrato inteligente comprueba la prueba frente a la raíz almacenada.

Si la prueba es válida, la wallet puede acuñar un NFT conforme a las reglas de la lista de permitidos.

Esto puede reducir los costes de almacenamiento on-chain y hacer más eficiente la verificación de la lista de permitidos.

Los usuarios deben comprobar que la página de acuñación, la dirección del contrato y la raíz de Merkle proceden de fuentes oficiales.

Árboles de Merkle en clientes ligeros

Los clientes ligeros utilizan métodos de verificación compactos para reducir la cantidad de datos de la blockchain que deben descargar.

Los árboles de Merkle ayudan a los clientes ligeros a verificar transacciones o datos de estado concretos frente a cabeceras de bloques o raíces de confianza.

Esto resulta útil para wallets móviles, navegadores y dispositivos con capacidad de almacenamiento o ancho de banda limitados.

Un cliente ligero no ofrece el mismo modelo de seguridad que un nodo con validación completa.

Sin embargo, la verificación basada en Merkle puede ser más sólida que confiar ciegamente en un único proveedor de datos.

Por eso, los árboles de Merkle son un elemento fundamental para lograr una infraestructura cripto más accesible.

Árboles de Merkle en juegos blockchain y aplicaciones del metaverso

Los juegos blockchain y las aplicaciones del metaverso pueden utilizar árboles de Merkle para verificar listas grandes de activos, recompensas, jugadores o permisos.

Un juego puede utilizar una raíz de Merkle para comprometerse con los requisitos para recibir recompensas durante una temporada.

Una aplicación del metaverso puede utilizar una raíz de Merkle para verificar reclamaciones de insignias de eventos o permisos sobre terrenos virtuales.

Un proyecto de NFT puede utilizar un árbol de Merkle para gestionar la revelación de atributos o el acceso a una whitelist.

Así, las aplicaciones pueden mantener fuera de la blockchain conjuntos de datos grandes y, al mismo tiempo, verificar entradas concretas on-chain.

El resultado puede ser un menor coste y una mayor escalabilidad.

La contrapartida es que el proceso de construcción del árbol off-chain debe ser transparente y correcto.

Árboles de Merkle e integridad de los datos

Los árboles de Merkle protegen la integridad de los datos al facilitar la detección de cambios.

Si cambia una hoja, cambia su hash.

Ese cambio afecta al hash padre, después al siguiente hash padre y, finalmente, a la raíz de Merkle.

Esto permite que un verificador compare raíces para detectar si el conjunto de datos es el mismo.

Los árboles de Merkle no impiden que alguien cree un conjunto de datos falso.

Ayudan a demostrar si los datos coinciden con una raíz comprometida concreta.

Por eso, la raíz debe proceder de una fuente de confianza o verificada mediante consenso.

Árbol de Merkle frente a lista de hashes

Una lista de hashes es una lista sencilla de hashes.

Un árbol de Merkle es una estructura jerárquica de hashes que permite generar pruebas compactas.

Con una lista de hashes, verificar un elemento puede requerir más datos de la lista completa.

Con un árbol de Merkle, el verificador normalmente solo necesita la hoja objetivo y un pequeño número de hashes hermanos.

Esto hace que los árboles de Merkle sean más eficientes para conjuntos de datos grandes.

La ventaja en eficiencia aumenta a medida que crece el conjunto de datos.

Árbol de Merkle frente a Merkle Patricia Trie

Un árbol de Merkle es una estructura general de datos basada en un árbol de hashes.

Un Merkle Patricia Trie es una estructura más especializada que se utiliza para datos de clave-valor.

Ethereum utiliza un Merkle Patricia Trie modificado para almacenar y verificar el estado de forma eficiente.

Un árbol de Merkle sencillo suele utilizarse para verificar la inclusión de transacciones, listas de permitidos de NFT y reclamaciones de airdrops.

Un trie resulta más adecuado cuando es necesario buscar datos mediante claves, como direcciones de cuentas o posiciones de almacenamiento.

Ambas estructuras utilizan hashes criptográficos para que se puedan detectar las manipulaciones de los datos.

Árbol de Merkle frente a árbol de Verkle

Un árbol de Verkle es una estructura de datos autenticada más reciente que utiliza compromisos vectoriales en lugar de basarse únicamente en pares de hashes.

Los árboles de Verkle suelen considerarse una posible mejora futura para los sistemas de estado de las blockchains, ya que pueden reducir el tamaño de algunas pruebas.

La documentación de Ethereum señala que Ethereum prevé migrar en el futuro de su estructura actual Merkle Patricia Trie a una estructura de árbol de Verkle.

Esto no significa que los árboles de Merkle vayan a quedar obsoletos.

Siguen utilizándose ampliamente porque son sencillos, fiables y conocidos.

Para muchos casos de uso, como los airdrops y las listas de permitidos, los árboles de Merkle siguen siendo prácticos y eficientes.

Ventajas de los árboles de Merkle

La primera ventaja es la eficiencia de la verificación.

Los usuarios pueden verificar un elemento sin descargar el conjunto de datos completo.

La segunda ventaja es la integridad de los datos.

Cualquier cambio en los datos subyacentes modifica los hashes superiores.

La tercera ventaja es la reducción de los costes de almacenamiento on-chain.

Los contratos inteligentes pueden almacenar una raíz en lugar de numerosos registros individuales.

La cuarta ventaja es la escalabilidad.

Una única raíz compacta puede representar conjuntos de datos grandes.

La quinta ventaja es la privacidad parcial.

Un usuario puede demostrar que un elemento está incluido sin revelar todos los demás elementos del conjunto de datos.

Riesgos y limitaciones de los árboles de Merkle

El primer riesgo es una raíz incorrecta.

Una prueba de Merkle solo demuestra la inclusión en el conjunto de datos representado por esa raíz, por lo que esta debe ser de confianza o estar verificada.

El segundo riesgo es una construcción incorrecta del árbol.

Si un proyecto utiliza un método de hashing, una codificación, una ordenación o un formato de hoja equivocados, las pruebas pueden fallar o dejar de ser seguras.

El tercer riesgo son los errores de repetición o de reclamación duplicada.

Los contratos de reclamación deben registrar si una wallet ya ha utilizado su prueba cuando las reclamaciones solo pueden realizarse una vez.

El cuarto riesgo es el phishing.

Los estafadores pueden crear sitios web de reclamación falsos que aparentan utilizar pruebas de Merkle, pero piden a los usuarios que firmen transacciones dañinas.

El quinto riesgo es la interpretación errónea.

Un árbol de Merkle demuestra la inclusión de datos, pero no demuestra que un proyecto sea honesto, valioso o seguro.

Cómo evaluar un sistema de árbol de Merkle

Empieza por comprobar si la raíz de Merkle procede de una fuente oficial o verificada mediante consenso.

Revisa cómo se codifican las hojas.

Comprueba qué función hash se utiliza.

Confirma si el árbol utiliza pares ordenados o un orden fijo de izquierda a derecha.

Comprueba si las pruebas se generan con herramientas oficiales o código de código abierto.

En los contratos inteligentes, revisa la función de verificación de pruebas y la lógica de seguimiento de reclamaciones.

En airdrops y listas de permitidos de NFT, verifica la dirección oficial del contrato antes de enviar una prueba o firmar una transacción.

Un sistema de árbol de Merkle bien diseñado debe explicar claramente la raíz, las reglas y el proceso de verificación.

Malentendidos habituales sobre los árboles de Merkle

Un malentendido habitual es pensar que un árbol de Merkle almacena todos los datos on-chain.

En muchas aplicaciones cripto, solo se almacena la raíz de Merkle on-chain, mientras que el conjunto de datos completo se construye y almacena off-chain.

Otro malentendido es pensar que una raíz de Merkle revela el conjunto de datos completo.

Una raíz es solo un compromiso hash y no muestra todas las hojas por sí sola.

Un tercer malentendido es pensar que una prueba de Merkle válida demuestra que un usuario merece una recompensa desde un punto de vista moral o legal.

Solo demuestra que los datos enviados están incluidos en el conjunto de datos representado por la raíz.

Un cuarto malentendido es pensar que todos los árboles de Merkle se construyen de la misma manera.

Los distintos sistemas pueden utilizar funciones hash, métodos de codificación, reglas de ordenación y estructuras de árbol diferentes.

Preguntas frecuentes

¿Qué es un árbol de Merkle, explicado de forma sencilla?

Un árbol de Merkle es un árbol de hashes que permite a los usuarios verificar un dato dentro de un conjunto grande mediante una prueba pequeña.

¿Qué es una raíz de Merkle?

Una raíz de Merkle es el hash final situado en la parte superior de un árbol de Merkle y actúa como una huella digital compacta del conjunto de datos completo.

¿Por qué utilizan las blockchains árboles de Merkle?

Las blockchains utilizan árboles de Merkle para verificar conjuntos de datos grandes de forma eficiente, reducir las necesidades de datos y detectar cambios en los datos de transacciones o de estado.

¿Cómo utiliza Bitcoin los árboles de Merkle?

Bitcoin utiliza árboles de Merkle para resumir las transacciones de los bloques y almacena la raíz de Merkle en la cabecera del bloque.

¿Cómo utiliza Ethereum las estructuras de Merkle?

Ethereum utiliza un Merkle Patricia Trie modificado para almacenar y verificar el estado de las cuentas y los datos de almacenamiento de los contratos.

¿Qué es una prueba de árbol de Merkle?

Una prueba de árbol de Merkle es un conjunto de hashes hermanos que demuestra que una hoja concreta pertenece a un árbol con una raíz de Merkle conocida.

¿Cómo se utilizan los árboles de Merkle en los airdrops?

Los contratos de airdrop pueden almacenar una única raíz de Merkle y verificar las reclamaciones de los usuarios con pruebas de Merkle, en lugar de almacenar on-chain todas las wallets que cumplen los requisitos.

¿Cómo se utilizan los árboles de Merkle en las listas de permitidos de NFT?

Los proyectos de NFT pueden utilizar una raíz de Merkle para representar las wallets aprobadas y verificar cada wallet mediante una prueba durante la acuñación.

¿Son privados los árboles de Merkle?

Los árboles de Merkle pueden ofrecer privacidad parcial, ya que los usuarios pueden demostrar que un dato está incluido sin revelar el conjunto de datos completo.

¿Son los árboles de Merkle lo mismo que las pruebas de conocimiento cero?

No. Los árboles de Merkle demuestran la inclusión de datos en un conjunto comprometido, mientras que las pruebas de conocimiento cero pueden demostrar afirmaciones más amplias sin revelar datos privados.

Conclusión

Un árbol de Merkle es una estructura de datos fundamental del mundo cripto que facilita la verificación de conjuntos de datos grandes.

Convierte numerosos datos en un árbol de hashes y genera una única raíz de Merkle final.

Esa raíz puede representar transacciones, saldos, direcciones, reclamaciones, valores de almacenamiento u otros datos de la blockchain.

Los árboles de Merkle son importantes porque permiten realizar verificaciones eficientes, reducir los costes de almacenamiento y garantizar la integridad de los datos, además de ser útiles para clientes ligeros, airdrops, listas de permitidos de NFT y pruebas del estado de la blockchain.

Bitcoin utiliza árboles de Merkle para resumir las transacciones de los bloques.

Ethereum utiliza una estructura relacionada, el Merkle Patricia Trie, para el estado de las cuentas y el almacenamiento.

Las aplicaciones cripto utilizan árboles de Merkle cuando necesitan demostrar que un elemento pertenece a un conjunto de datos grande sin incluir todo el conjunto en la blockchain.

Los árboles de Merkle son potentes, pero dependen de un hashing correcto, una codificación segura, raíces de confianza y una verificación segura de las pruebas.

Cuando se utilizan correctamente, hacen que los sistemas cripto sean más ligeros, baratos y fáciles de verificar.