Árbol de Merkle

Para probar que un dato pertenece al conjunto basta una prueba de inclusión (Merkle proof): el conjunto mínimo de hashes hermanos a lo largo del camino desde la hoja hasta la raíz. El verificador recomputa los hashes hasta la raíz y compara, con coste logarítmico, del orden de log n hashes para n elementos, sin necesitar el conjunto completo. El concepto procede de Ralph Merkle, que lo patentó en su solicitud de 1979 sobre firmas digitales, y se construye enteramente sobre funciones hash criptográficas.

Es una estructura fundacional de blockchain: permite verificar integridad e inclusión de grandes volúmenes con datos mínimos. Habilita los clientes ligeros (SPV), que verifican una transacción contra la raíz del bloque sin descargar el bloque entero, algo clave para que dispositivos modestos confíen en la red.

En Bitcoin, cada cabecera de bloque guarda la raíz de Merkle de sus transacciones, y los nodos SPV usan pruebas de Merkle. Ethereum emplea una variante, el Merkle-Patricia Trie, para estado, transacciones y recibos. Muchos airdrops, como el de Uniswap (UNI) o el de Optimism (OP), comprometen la lista de elegibilidad como raíz de Merkle y cada usuario reclama con su prueba de inclusión. Es además la estructura de compromiso interna de los zk-STARK y un soporte habitual de las pruebas de pertenencia en zk-SNARK.