Árvore de Merkle

Emparelhe os hashes das transações, calcule o hash de cada par e repita até que reste um único hash. Esse valor único vai no cabeçalho do bloco, e provar que uma transação pertence a ele exige apenas os hashes ao longo de um caminho: onze deles, 352 bytes, para um bloco que contém 2.000 pagamentos. É por isso que uma carteira no celular consegue verificar que seus bitcoins chegaram sem baixar o bloco.

Como funciona

Uma árvore de Merkle transforma uma lista em uma pirâmide calculando o hash de vizinhos em pares, nível por nível, até que reste apenas um hash.

As folhas são os IDs de transação, na ordem em que o minerador os colocou. O Bitcoin combina cada par concatenando os dois valores de 32 bytes e aplicando SHA-256 ao resultado duas vezes. Quando um nível contém um número ímpar de entradas, a última é emparelhada com uma cópia de si mesma, o que mantém o algoritmo simples e uma vez causou problemas reais: a vulnerabilidade catalogada como CVE-2012-2459, divulgada em maio de 2012 e corrigida no mesmo mês, abusava dessa duplicação para construir um bloco que parecia inválido aos nós, ainda que as transações subjacentes estivessem corretas.

O ganho é logarítmico. Dobrar o número de transações acrescenta um nível, não um hash por transação. Um bloco com 1.024 pagamentos precisa de dez hashes para provar a inclusão, 320 bytes. Quatro mil e noventa e seis precisam de doze, 384 bytes. Quem verifica a prova recalcula o caminho de baixo para cima e compara o resultado com a raiz em que já confia a partir do cabeçalho, e não há como falsificar um caminho sem quebrar o SHA-256.

Nada disso tem origem no bitcoin. Ralph Merkle descreveu a construção no pedido de patente que se tornou a US 4.309.569, depositado em 1979 e concedido em janeiro de 1982. O whitepaper cita o trabalho dele e dá à árvore dois usos: podar transações gastas de blocos antigos para economizar disco, na seção 7, e permitir que um cliente verifique um pagamento mantendo apenas cabeçalhos, na seção 8.

Onde você o encontra

Árvores de Merkle aparecem onde um sistema precisa provar que um item pertence a um conjunto grande sem enviar o conjunto.

Dentro do bitcoin, cada cabeçalho de bloco carrega o topo de uma. Um nó reconstrói a árvore a partir das transações que recebeu e rejeita o bloco se o resultado não coincidir. O Bitcoin Core expõe o mecanismo diretamente: gettxoutproof produz uma prova serializada de que uma transação foi incluída em um bloco, e verifytxoutproof verifica uma, o que é uma forma prática de entregar a alguém evidência de um pagamento sem lhe dar uma carteira.

Em outras partes do bitcoin, o Taproot constrói uma segunda: as condições de gasto alternativas de uma saída Taproot são organizadas como uma árvore, de modo que revelar o ramo que você usou não divulga nada sobre os ramos que você não usou. Fora do bitcoin, a mesma forma sustenta o histórico de commits do Git, os registros de Certificate Transparency que detectam certificados web emitidos indevidamente e as verificações de integridade de dados do sistema de arquivos ZFS.

Para quem usa uma carteira, a consequência visível é pequena e útil. Um cliente leve que guarda algumas dezenas de megabytes de cabeçalhos consegue confirmar que sua transação está em um bloco específico, a uma profundidade específica, e só recebe uma resposta falsa se alguém tiver produzido prova de trabalho válida sobre uma cadeia falsa, o que custa dinheiro real.

Árvore de Merkle vs raiz de Merkle

A árvore de Merkle é a estrutura de trabalho; a raiz de Merkle é o único valor mantido depois. Um nó constrói a pirâmide inteira na memória enquanto valida um bloco e depois a descarta, armazenando apenas os 32 bytes que ficaram no topo, porque tudo o que está abaixo pode ser regenerado a partir das transações. Quando um explorador mostra um campo chamado raiz de Merkle, esse é o sobrevivente. Ninguém armazena a árvore, e ninguém precisa.