Prova de Merkle

Uma árvore de Merkle é uma árvore binária de hashes: as folhas são hashes dos dados e cada nó interno é o hash da concatenação de seus dois filhos, até chegar à raiz. Para provar que uma folha pertence à árvore, o provador entrega os hashes irmãos ao longo do caminho até a raiz, cerca de log₂(N) hashes para N folhas. O verificador recombina de baixo para cima e confere se o resultado é igual à raiz conhecida. Para um milhão de folhas bastam cerca de 20 hashes, em vez de processar o conjunto inteiro.

Permite verificar pertencimento de forma sucinta sem baixar conjuntos de dados completos. Seus usos típicos são os airdrops, em que a lista de elegíveis é comprometida em uma raiz e cada usuário apresenta sua prova para fazer o resgate; as provas de reservas de exchanges; e os clientes leves (SPV no Bitcoin), que verificam que uma transação está em um bloco sem baixá-lo. Como boa prática, uma implementação sólida separa o domínio das folhas e dos nós internos para evitar ataques de segunda pré-imagem.