Árvores de Merkle: integridade de transações em escala

Um bloco do Bitcoin contém cerca de 2000 transações. Para provar que a transação T está incluída sem baixar todas as 2000 transações, precisamos de uma prova compacta. As árvores de Merkle resolvem isso: o tamanho da prova é O(log n) resumos criptográficos, em vez de O(n) transações.

Folhas: SHA256d (SHA256 duplo) de cada transação. Pai: SHA256d(left_child_hash || right_child_hash). Repita até obter um único resumo criptográfico raiz. Se houver um número ímpar de nós, duplique o último nó. A raiz é a raiz de Merkle armazenada no cabeçalho do bloco (32 bytes).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Para provar que a transação T está na posição i: forneça os resumos criptográficos irmãos em cada nível, da folha de T até a raiz (O(log n) resumos criptográficos). O verificador recalcula a raiz a partir de T e do caminho de resumos criptográficos irmãos. Se a raiz calculada corresponder à raiz de Merkle do cabeçalho do bloco, a inclusão de T estará comprovada.

1024 transações → a prova de Merkle = 10 resumos criptográficos = 320 bytes. Bloco completo = ~1 MB. Os clientes SPV baixam apenas o cabeçalho de 80 bytes + a prova de Merkle de 320 bytes para cada transação de seu interesse — economia de 99,97% na largura de banda em comparação com o download do bloco completo.

Se qualquer transação na árvore mudar, o resumo criptográfico de sua folha será alterado e essa alteração se propagará até modificar a raiz de Merkle. A raiz alterada não corresponderá mais ao cabeçalho do bloco (protegido pela prova de trabalho). Qualquer modificação poderá ser detectada calculando a raiz a partir das transações.

O Ethereum amplia as árvores de Merkle com árvores de prefixos (árvore de prefixos de Merkle Patricia): uma árvore de prefixos radix codificada com cada nó resumido por Merkle. Usada para: árvore de estado (saldos de contas), árvore de transações e árvore de recibos. Permite provar com eficiência o estado de uma conta sem os dados de um nó completo.

Uma estrutura montanhosa de Merkle (MMR) é uma estrutura de Merkle somente para acréscimo, adequada a dados em formato de registro. Novos elementos são acrescentados; os picos (raízes de subárvores com tamanho potência de 2) são mantidos. É usada em Grin/MimbleWimble e ZCash para obter provas compactas e eficientes sobre um registro somente para acréscimo.

As árvores Verkle substituem as árvores de Merkle no roteiro do Ethereum (EIP-6800): usam compromissos vetoriais (compromissos polinomiais KZG) em vez de resumos criptográficos. Tamanho da prova: O(1), contra O(log n) nas árvores de Merkle. Isso permite que clientes sem estado verifiquem o estado sem armazenar a árvore de prefixos completa.

A Transparência de certificados (RFC 6962) usa um registro de Merkle somente para acréscimo: cada certificado emitido por uma CA é uma folha. As provas de inclusão verificam se um certificado foi registrado. As provas de consistência verificam se o registro foi mantido somente para acréscimo (sem exclusões ou inserções). Os fornecedores de navegadores verificam SCTs por meio desse registro.

As árvores do Git (instantâneos de diretórios) são árvores de Merkle: cada nó da árvore calcula o resumo criptográfico de seus blobs de arquivos e subárvores. Um resumo criptográfico de commit identifica exclusivamente o estado de toda a base de código. É por isso que git checkout sempre fornece exatamente os mesmos arquivos.

Quantos resumos criptográficos uma prova de Merkle exige para comprovar a inclusão em uma árvore com 1024 folhas?

As árvores de Merkle permitem provas de inclusão O(log n). O Bitcoin armazena a raiz de Merkle nos cabeçalhos dos blocos; os clientes SPV usam provas. O Ethereum amplia esse conceito para árvores de prefixos de Merkle Patricia. As árvores Verkle substituirão as árvores de Merkle para fornecer provas O(1). Próximo tópico: mineração por prova de trabalho e dificuldade.