Árvore de Merkle

Para provar que um dado pertence ao conjunto, basta uma prova de inclusão (Merkle proof): o conjunto mínimo de hashes irmãos ao longo do caminho da folha até a raiz. O verificador recalcula os hashes até a raiz e compara, com custo logarítmico, da ordem de log n hashes para n elementos, sem precisar do conjunto completo. O conceito vem de Ralph Merkle, que o patenteou em seu pedido de 1979 sobre assinaturas digitais, e se constrói inteiramente sobre funções hash criptográficas.

É uma estrutura fundamental de blockchain: permite verificar integridade e inclusão de grandes volumes com dados mínimos. Viabiliza os clientes leves (SPV), que verificam uma transação contra a raiz do bloco sem baixar o bloco inteiro, algo essencial para que dispositivos modestos confiem na rede.

No Bitcoin, cada cabeçalho de bloco guarda a raiz de Merkle de suas transações, e os nós SPV usam provas de Merkle. O Ethereum emprega uma variante, a Merkle-Patricia Trie, para estado, transações e recibos. Muitos airdrops, como o da Uniswap (UNI) ou o da Optimism (OP), comprometem a lista de elegibilidade como raiz de Merkle, e cada usuário reivindica com sua prova de inclusão. É, além disso, a estrutura de compromisso interna dos zk-STARKs e um suporte habitual das provas de pertencimento em zk-SNARKs.