O que é Merkle Tree?

Merkle Tree é uma estrutura de dados que comprime um grande conjunto de registos numa única impressão digital curta. Permite provar que um item está numa lista enorme verificando apenas algumas peças pequenas, em vez de todo o conjunto. Imagine uma árvore genealógica em que cada nó pai resume os seus filhos, tudo convergindo para um único antepassado.

Mito

Merkle Tree “armazena” todas as transações por si só. Nem por isso. Armazena apenas impressões digitais compactas delas, e a árvore pode ser reconstruída a partir dos registos originais sempre que necessário.

Como funciona Merkle Tree

Imagine um bloco de pagamentos que precisa de um resumo rápido e verificável. Eis como o Merkle Tree funciona, em termos simples:

Passo 1: Comece com uma lista de itens, como transações, cada um uma folha na árvore.
Passo 2: Transforme cada item numa impressão digital curta usando uma função de hash.
Passo 3: Emparelhe impressões digitais adjacentes, combine cada par e aplique hash novamente para criar o nó pai.
Passo 4: Repita o processo de emparelhamento e hashing até que reste uma única impressão no topo. Essa é a Merkle root deste conjunto.
Passo 5: Para provar que um item pertence ao conjunto, precisa apenas desse item mais um caminho curto de impressões digitais dos nós irmãos. Rápido e compacto.

Esta é a ideia: provas pequenas, alta confiança.

Por que o Merkle Tree é importante

Ao resumir enormes conjuntos de dados de transações numa impressão digital compacta, o Merkle Tree torna a verificação rápida e barata.

Vantagem: Pode verificar a inclusão sem descarregar todo o bloco, poupando tempo e largura de banda.
Perspetiva: Encaixa-se no espírito atual da internet: confie mas verifique, Rolex encontra discussões do Reddit.
Relevância: Vai encontrá-lo em blocos do Bitcoin, recibos do Ethereum, listas de permissão de NFT, airdrops e rollups.

Dica

Se o número de folhas for ímpar, muitos designs duplicam a última antes de aplicar o hash na árvore. Além disso, verifique bem o exato processo de hashing que a sua cadeia ou biblioteca usa, pois pequenas diferenças nas regras podem alterar as provas.

Principais características do Merkle Tree

Isto é o que o torna especial e útil:

Eficiência: As provas permanecem pequenas mesmo quando o conjunto de dados cresce muito, por isso clientes leves continuam leves.
Integridade: Mude um byte numa folha e a alteração propaga-se até ao topo, tornando a manipulação evidente.
Raiz: Tudo se reduz a uma única Merkle root que pode ser armazenada ou assinada para verificações posteriores.

Variações

O Merkle Tree tem algumas variantes populares que vai encontrar:

Binária: A clássica árvore baseada em pares, usada nos blocos do Bitcoin.
Merkle Patricia: Uma variação baseada em trie para dados de chave e valor, usada no estado e em recibos do Ethereum.
Esparsa: Uma enorme árvore indexada onde a maioria das folhas está vazia, ótima para provas sucintas de pertença e não pertença.
Verkle: Um parente mais recente com provas mais curtas para ramificações muito grandes, estudado para futuras atualizações.

Lembrete

As provas Merkle Tree são tão confiáveis quanto o cabeçalho ou ponto de verificação que aceitar. Se confiar na raiz errada, mesmo a prova mais limpa não significa nada.

Exemplo

Uma carteira leve no estilo Bitcoin pode verificar o seu pagamento verificando um caminho curto de hashes desde a sua transação até ao cabeçalho do bloco, sem descarregar todo o histórico de transações.

Curiosidade

Ralph Merkle esboçou esta ideia no final dos anos setenta como um projeto de estudante, e ela permaneceu em círculos académicos durante anos antes de Satoshi a usar no Bitcoin. Prova de que boas ideias envelhecem bem.

Resumo

Em resumo? Merkle Tree oferece provas rápidas e pequenas de que algo pertence a um grande conjunto, sem complicações e sem downloads pesados.

Merkle Tree