Merkle tree carrega a fama de coisa de blockchain, o que afasta muita gente que teria uso pra ela. Git usa. O certificate transparency da web usa. Sistema de arquivos distribuído usa. Backup com deduplicação usa.
A ideia inteira cabe em dois parágrafos, e resolve um problema concreto: provar que um item específico faz parte de um conjunto grande, sem precisar enviar o conjunto.
A construção
Você tem uma lista de itens. Hasheia cada um. Depois hasheia os pares, formando um nível acima. Repete até sobrar um hash só, a raiz.
raiz
/ \
h(AB) h(CD)
/ \ / \
h(A) h(B) h(C) h(D)
| | | |
A B C DA raiz depende de todos os itens. Mudar um bit em C muda h(C), que muda h(CD), que muda a raiz.
Até aqui, um hash de tudo concatenado faria o mesmo. A diferença aparece agora.
A prova de inclusão
Alguém quer verificar que o item C está no conjunto. Você não manda o conjunto. Manda C e dois hashes: h(D) e h(AB).
A pessoa calcula h(C), combina com h(D) pra obter h(CD), combina com h(AB) e chega na raiz. Se bater com a raiz publicada, C está no conjunto. Ponto.
Com um milhão de itens, a prova tem vinte hashes. Umas centenas de bytes pra provar pertencimento a um conjunto de um milhão.
function verifyProof(leaf: Buffer, proof: ProofStep[], root: Buffer): boolean {
let current = sha256(Buffer.concat([LEAF_PREFIX, leaf]));
for (const step of proof) {
current = step.side === "left"
? sha256(Buffer.concat([NODE_PREFIX, step.hash, current]))
: sha256(Buffer.concat([NODE_PREFIX, current, step.hash]));
}
return current.equals(root);
}Os prefixos diferentes para folha e nó interno não são enfeite. Sem eles existe um ataque conhecido em que um nó interno é apresentado como folha e a prova valida algo que não estava na lista. Duas constantes resolvem, e a maioria das implementações caseiras esquece.
Onde isso ganha de um hash simples
Se você só precisa detectar que algo mudou no conjunto inteiro, um hash de tudo basta.
Merkle tree ganha em três situações.
Prova pontual sem revelar o resto. Você prova que a transação do cliente está no lote do dia sem mostrar as outras transações. Em contexto com dado sensível ou concorrente, isso é a diferença entre poder e não poder publicar.
Verificação incremental. Comparando duas árvores, você desce só pelos ramos cujo hash difere e encontra os itens diferentes em tempo logarítmico. É assim que sistema distribuído descobre o que precisa sincronizar sem comparar tudo com tudo. Cassandra e Dynamo fazem exatamente isso.
Prova de consistência. Dado que você publicou a raiz ontem e outra hoje, dá pra provar que a árvore de hoje é uma extensão da de ontem, e que nada do passado foi alterado. Essa é a propriedade que sustenta o certificate transparency, e é a mais útil pra audit trail.
O uso que eu acho mais subestimado
Ancorar histórico.
Você tem um log append-only com eventos. Uma vez por dia, monta a Merkle tree dos eventos daquele dia, guarda a raiz e publica ela em algum lugar que você não controla. Um repositório público, um tweet, um serviço de timestamp, o que for barato.
Custo: um job de madrugada e trinta e dois bytes por dia.
Ganho: se alguém questionar um registro seis meses depois, você fornece o registro e a prova de inclusão. Qualquer pessoa verifica contra a raiz publicada na época, sem confiar no seu banco.
Isso muda a natureza do argumento. Sem a âncora, o seu histórico vale o quanto a sua palavra vale. Com ela, o histórico é verificável por quem não confia em você, que é a definição de auditável.
Detalhes que mordem
Número ímpar de folhas. A convenção mais comum é promover o nó solitário pro nível de cima. Alguns duplicam o último, o que abriu uma vulnerabilidade histórica no Bitcoin. Escolha uma convenção, documente e teste.
Ordem importa. A raiz depende da ordem das folhas. Se você quer que dois conjuntos com os mesmos itens produzam a mesma raiz, ordene as folhas antes. Se você quer que a ordem seja parte da prova, não ordene. As duas escolhas são válidas e precisam ser explícitas.
Guardar ou recalcular. Para lote pequeno, recalcular na hora é mais simples. Para árvore grande e crescente, guarde os nós internos, senão cada prova custa uma varredura completa.
Quando não usar
Se a verificação é sempre interna e você confia no seu banco, é complexidade sem retorno. Um hash por registro e um encadeamento simples já cobrem.
Merkle tree se paga quando existe alguém do lado de fora que precisa verificar sem acesso ao conjunto todo. Se esse alguém não existe no seu problema, o custo cognitivo não compensa.
A pergunta é sempre a mesma que abre qualquer desenho de rastreabilidade: quem verifica. Escrevi sobre ela em system design de rastreabilidade com hash único.