Uma árvore de Merkle organiza hashes de dados em uma árvore cujo hash superior, a raiz de Merkle, resume o conjunto comprometido. Cada nó pai é calculado a partir dos filhos conforme regras definidas. Alterar uma folha geralmente muda os hashes no caminho até a raiz.
Verificar um item
Uma prova de inclusão fornece os hashes vizinhos necessários para recalcular esse caminho, em vez de todos os itens. Em uma árvore binária balanceada com oito folhas, provar uma folha normalmente exige três hashes irmãos e informações de posição. O verificador também precisa do item ou de seu hash e de uma raiz confiável.
Uso no Bitcoin
O Bitcoin compromete identificadores de transações em uma raiz de Merkle no cabeçalho de cada bloco. Sua construção define a ordem das transações, o cálculo por pares e a duplicação quando um nível tem número ímpar de entradas. Outros sistemas podem usar estruturas e codificações diferentes.
O que a prova estabelece
Uma prova válida mostra que um item pertence ao conjunto representado pela raiz de referência, sob as premissas de segurança do hash. Ela não prova sozinha a validade da transação, o estado atual não gasto de uma saída ou a finalidade da cadeia. A raiz também não revela todos os dados originais: eles precisam continuar disponíveis em outro lugar para uma verificação completa.