Árvores de Merkle

Curiosidade

1. Como um único valor de hash pode certificar a inclusão de quatro mil transações distintas?
2. Por que Satoshi escolheu emparelhar uma única última entrada consigo mesma, e qual foi o custo dessa escolha?
3. Qual vulnerabilidade específica a regra de emparelhamento duplicado introduziu na implementação inicial do Bitcoin?

Explorar

1. Ralph Merkle registrou uma patente para a árvore de hash binária em 1979 (concedida em 1982), uma estrutura de dados projetada para resumir conjuntos de dados grandes de forma eficiente. No Bitcoin, essa arquitetura reduz milhares de identificadores de transações a um único valor de 32 bytes, conhecido como raiz Merkle. Essa raiz é incorporada diretamente no cabeçalho do bloco de 80 bytes, criando um compromisso criptográfico imutável para cada transação dentro daquele bloco específico.
2. A construção prossegue de forma recursiva, de baixo para cima. Os IDs das transações são concatenados em pares e processados por meio de hashing duplo SHA-256 para gerar os nós pai. Esse emparelhamento continua nível por nível até restar apenas um hash raiz. Se algum nível contiver um número ímpar de entradas, a última entrada é emparelhada consigo mesma para manter a estrutura binária, garantindo que a árvore fique equilibrada em todas as etapas.
3. A natureza logarítmica dessa estrutura permite uma verificação de pagamento simplificada (SPV). Um cliente leve não baixa os blocos completos; em vez disso, solicita um ramo Merkle a um nó completo. Esse ramo consiste apenas nos hashes dos nós irmãos ao longo do caminho desde uma transação específica até a raiz. Para um bloco com 4.000 transações, essa prova requer aproximadamente doze valores de hash, o que representa uma fração do tamanho total dos dados.
4. Ao combinar seu próprio hash de transação com esses hashes fornecidos, um cliente leve recalcula a raiz Merkle e a compara com o valor no cabeçalho do bloco baixado. Se eles corresponderem, a inclusão é verificada criptograficamente sem a necessidade de armazenar toda a cadeia. Esse mecanismo permite que carteiras móveis funcionem com segurança em dispositivos com capacidade de armazenamento e processamento limitadas.
5. O Segregated Witness (SegWit), ativado em agosto de 2017, introduziu uma segunda estrutura de árvore Merkle. Enquanto a árvore original registra os IDs das transações, a árvore “witness” registra os IDs das transações “witness”. A raiz dessa segunda árvore não é armazenada no cabeçalho; ela é registrada em uma saída OP_RETURN da transação coinbase, que os nós antigos tratam como dados comuns, preservando assim a compatibilidade.
6. A regra de emparelhamento automático escondia uma falha (CVE-2012-2459). Como a última entrada isolada é emparelhada consigo mesma, uma lista de transações que termina com um par duplicado gera a mesma raiz Merkle que a lista sem o duplicado. Um atacante poderia transmitir essa variante malformada de um bloco válido; os nós que a rejeitassem poderiam marcar o hash do bloco legítimo como inválido e ficar desalinhados com a rede. A correção de 2012 faz com que os nós reconheçam esse padrão em vez de armazenarem o bloco como inválido.

Fatos-chave

Exercício nove, seis, três, um

Verificação de fatos

Datas, números e afirmações verificados com as fontes publicadas listadas abaixo.

• R. Merkle, US Patent 4,309,569 (1982)
• Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System (2008), sections 7-8
• BIP 141: Segregated Witness (Consensus layer)
• A. M. Antonopoulos & D. A. Harding, Mastering Bitcoin, 3rd ed. (2023), ch. 11