Glosario / Minería y consenso
Árbol de Merkle
- ¿Qué es un árbol de Merkle?
- Un árbol de Merkle es la pirámide de hash que comprime todas las transacciones de un bloque en un único valor de 32 bytes, de modo que cualquier pago puede demostrarse sin el resto.
Empareje los hash de las transacciones, calcule el hash de cada par y repita hasta que quede un solo hash. Ese único valor va en el encabezado del bloque, y demostrar que una transacción cuelga de él solo exige los hash que hay a lo largo de una ruta: once, 352 bytes, para un bloque que contiene 2.000 pagos. Por eso una billetera en el teléfono puede comprobar que sus monedas llegaron sin descargar el bloque.
Cómo funciona
Un árbol de Merkle convierte una lista en una pirámide calculando el hash de los elementos vecinos por pares, nivel a nivel, hasta que solo queda un hash.
Las hojas son los ID de transacción, en el orden en que el minero los colocó. Bitcoin combina cada par concatenando los dos valores de 32 bytes y aplicando SHA-256 dos veces al resultado. Cuando un nivel contiene un número impar de elementos, el último se empareja con una copia de sí mismo, lo que mantiene simple el algoritmo y en una ocasión causó problemas reales: la vulnerabilidad catalogada como CVE-2012-2459, divulgada en mayo de 2012 y corregida ese mismo mes, aprovechaba esa duplicación para construir un bloque que a los nodos les parecía inválido aunque las transacciones subyacentes estaban bien.
La ventaja es logarítmica. Duplicar el número de transacciones añade un nivel, no un hash por transacción. Un bloque con 1.024 pagos necesita diez hash para demostrar la pertenencia, 320 bytes. Uno con cuatro mil noventa y seis necesita doce, 384 bytes. Quien verifica la prueba recalcula la ruta hacia arriba y compara el resultado con la raíz en la que ya confía por el encabezado, y no hay forma de falsificar una ruta sin romper SHA-256.
Nada de esto tiene su origen en bitcoin. Ralph Merkle describió la construcción en la solicitud de patente que se convirtió en la patente US 4,309,569, presentada en 1979 y concedida en enero de 1982. El whitepaper cita su trabajo y le da al árbol dos usos: podar las transacciones gastadas de los bloques antiguos para ahorrar espacio en disco, en la sección 7, y permitir que un cliente verifique un pago conservando solo los encabezados, en la sección 8.
Dónde aparece
Los árboles de Merkle aparecen allí donde un sistema necesita demostrar que un elemento pertenece a un conjunto grande sin enviar el conjunto.
Dentro de bitcoin, cada encabezado de bloque lleva la cúspide de uno. Un nodo reconstruye el árbol a partir de las transacciones que recibió y rechaza el bloque si el resultado no coincide. Bitcoin Core expone el mecanismo directamente: la llamada RPC gettxoutproof produce una prueba serializada de que una transacción se incluyó en un bloque, y la llamada RPC verifytxoutproof comprueba una, lo que es una forma práctica de dar a alguien constancia de un pago sin darle una billetera.
En otra parte de bitcoin, Taproot construye un segundo árbol: las condiciones de gasto alternativas de una salida Taproot se organizan en forma de árbol, así que revelar la rama que se usó no divulga nada sobre las ramas que no se usaron. Fuera de bitcoin, la misma forma sustenta el historial de confirmaciones de Git, los registros de Certificate Transparency que detectan certificados web emitidos indebidamente y las comprobaciones de integridad de datos del sistema de archivos ZFS.
Para quien usa una billetera, la consecuencia visible es pequeña y útil. Un cliente ligero que conserva unas pocas decenas de megabytes de encabezados puede confirmar que su transacción está en un bloque concreto, a una profundidad concreta, y solo recibe una respuesta falsa si alguien ha producido prueba de trabajo válida sobre una cadena falsa, lo que cuesta dinero real.
Árbol de Merkle frente a raíz de Merkle
El árbol de Merkle es la estructura de trabajo; la raíz de Merkle es el único valor que se conserva después. Un nodo construye la pirámide entera en memoria mientras valida un bloque y luego la descarta, y almacena solo los 32 bytes que quedaron en la cúspide, porque todo lo que hay debajo puede regenerarse a partir de las transacciones. Cuando un explorador de bloques le muestra un campo llamado raíz de Merkle, ese es el superviviente. Nadie almacena el árbol, y nadie necesita hacerlo.