Árboles de Merkle: integridad de transacciones a escala

Un bloque de Bitcoin contiene aproximadamente 2000 transacciones. Para demostrar que la transacción T está incluida sin descargar las 2000 transacciones, necesitamos una prueba compacta. Los árboles de Merkle resuelven este problema: el tamaño de la prueba es O(log n) hashes en lugar de O(n) transacciones.

Hojas: SHA256d (doble SHA-256) de cada transacción. Padre: SHA256d(left_child_hash || right_child_hash). Repita el proceso hasta obtener un único hash raíz. Si hay un número impar de nodos, duplique el último nodo. La raíz es la raíz de Merkle almacenada en el encabezado del bloque (32 bytes).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Para demostrar que la transacción T está en la posición i, proporcione los hashes hermanos de cada nivel desde la hoja de T hasta la raíz (O(log n) hashes). El verificador vuelve a calcular la raíz a partir de T y de la ruta de hashes hermanos. Si la raíz calculada coincide con la raíz de Merkle del encabezado del bloque, queda demostrada la inclusión de T.

1024 transacciones → una prueba de Merkle = 10 hashes = 320 bytes. Bloque completo = aproximadamente 1 MB. Los clientes SPV descargan solo el encabezado de 80 bytes + la prueba de Merkle de 320 bytes por cada transacción que les interesa, lo que supone un ahorro de ancho de banda del 99,97 % frente a descargar el bloque completo.

Si cambia cualquier transacción del árbol, cambia el hash de su hoja y el cambio se propaga hasta modificar la raíz de Merkle. La raíz modificada ya no coincide con la del encabezado del bloque (que está protegida mediante PoW). Cualquier modificación se puede detectar calculando la raíz a partir de las transacciones.

Ethereum amplía los árboles de Merkle con tries (Trie de Merkle de Patricia): un radix trie codificado con prefijo hexadecimal en el que cada nodo tiene un hash de Merkle. Se utiliza para: el state trie (saldos de cuentas), el transaction trie y el receipt trie. Permite demostrar de forma eficiente el estado de una cuenta sin disponer de los datos del nodo completo.

Una Merkle Mountain Range (MMR) es una estructura de Merkle de solo adición para datos similares a registros. Se añaden nuevos elementos y se mantienen los picos (raíces de subárboles cuyo tamaño es una potencia de 2). Se utiliza en Grin/MimbleWimble y ZCash para obtener pruebas compactas y eficientes sobre un registro de solo adición.

Los árboles de Verkle sustituyen a los árboles de Merkle en la hoja de ruta de Ethereum (EIP-6800): utilizan compromisos vectoriales (compromisos polinómicos KZG) en lugar de hashes. Tamaño de la prueba: O(1) frente a O(log n) en Merkle. Permiten que los clientes sin estado verifiquen el estado sin almacenar el trie completo.

Certificate Transparency (RFC 6962) utiliza un registro de Merkle de solo adición: cada certificado emitido por una CA es una hoja. Las pruebas de inclusión verifican que un certificado se registró. Las pruebas de coherencia verifican que el registro solo admite adiciones (sin eliminaciones ni inserciones). Los proveedores de navegadores verifican los SCT mediante este registro.

Los árboles de Git (instantáneas de directorios) son árboles de Merkle: cada nodo del árbol aplica un hash a sus blobs de archivos y subárboles. El hash de un commit identifica de forma única el estado completo del código. Por eso git checkout siempre proporciona exactamente los mismos archivos.

¿Cuántos hashes requiere una prueba de Merkle para demostrar la inclusión en un árbol de 1024 hojas?

Los árboles de Merkle permiten realizar pruebas de inclusión de O(log n). Bitcoin almacena la raíz de Merkle en los encabezados de los bloques; los clientes SPV utilizan pruebas. Ethereum los amplía mediante los Tries de Merkle de Patricia. Los árboles de Verkle sustituirán a los árboles de Merkle para ofrecer pruebas de O(1). Siguiente tema: minería mediante prueba de trabajo y dificultad.