Ralph Merkle

Você quer enviar uma mensagem criptografada. O destinatário precisa de uma chave secreta para lê-la, mas como entregá-la se alguém acompanha toda a comunicação? No artigo de 1978, Ralph Merkle descreveu uma solução surpreendente: o remetente prepara muitos quebra-cabeças criptografados; o destinatário resolve um escolhido ao acaso e devolve publicamente o identificador escondido nele. Ambos passam a conhecer uma chave compartilhada. O observador também vê o identificador, mas não sabe qual quebra-cabeça o continha. No modelo descrito, seu trabalho cresce de forma quadrática com o tamanho do problema, enquanto o dos participantes cresce linearmente. A diferença é quadrática, não exponencial. Esse avanço histórico não é uma recomendação atual para criptografar mensagens. [1]

É importante saber o que o adversário pode fazer no artigo de 1978. Ele pode escutar, mas alterações e falsificações ainda devem ser detectáveis. Imagine alguém que lê cartas e alguém que também as reescreve e assina seu nome. O segundo caso precisa de outra proteção: verificar com quem você está realmente falando. A diferença no esforço computacional não resolve essa questão. Os quebra-cabeças não tornam segura qualquer comunicação através de um intermediário ativo. Sua contribuição é mostrar que, sob as hipóteses apresentadas, é possível chegar a um acordo sem uma chave secreta previamente compartilhada. [1]

O Merkle Tree resolve outro problema. Essa árvore de autenticação aparece na tese de Merkle de 1979. Imagine um arquivo de contratos: você quer conferir um contrato específico sem baixar todo o arquivo. Calcula-se para cada item um hash, uma curta impressão digital dos dados. Os hashes são combinados em pares e processados novamente, até restar uma raiz comum. Calcular um hash não criptografa o conteúdo; permite verificar uma correspondência. Para isso ter valor, você precisa de uma raiz previamente autenticada, uma impressão digital confirmada do arquivo correto. Se um fraudador fornece tanto seu documento quanto uma raiz arbitrária, a correspondência entre eles não demonstra nada sobre o arquivo original. [2]

Considere uma árvore binária equilibrada com 8 itens. Para verificar uma folha escolhida, são necessários 3 hashes irmãos: em cada nível, a impressão digital do ramo vizinho. Partindo da sua folha e desses hashes, você calcula a raiz e a compara com a raiz autenticada. A própria folha e a raiz não entram nessa contagem de hashes auxiliares. É preciso conhecer também a estrutura da árvore e a ordem de combinação: cada vizinho fica à esquerda ou à direita? A economia não é um truque com dados ocultos. Partes distantes do arquivo são representadas por suas impressões digitais; seus documentos completos não são necessários para essa verificação. [2]

Um Merkle Tree comprova a relação entre um item e um conjunto específico de dados. Ele não transforma uma informação errada em verdadeira. Nosso arquivo pode conter um contrato com o nome incorreto; uma prova pode confirmar sua inclusão sem detectar o erro no nome. Da mesma forma, uma impressão digital não confirma a autoridade de quem criou o documento. Separe as perguntas: este item corresponde a esta raiz? De onde conheço a raiz? Quais regras uso para aceitar o conteúdo? Essa distinção ajuda a entender o que a mesma técnica faz no Bitcoin e o que precisa ser feito por outras partes do sistema. [2]

O Bitcoin usa um Merkle Tree para ligar as transações ao cabeçalho do bloco, seu registro compacto. A raiz faz parte do cabeçalho; mudanças nas transações incluídas afetam a impressão digital conjunta. Satoshi Nakamoto descreve essa construção na seção 7 do whitepaper e cita o trabalho de Merkle. Isso documenta influência técnica, não a autoria do Bitcoin. A árvore não escolhe um histórico válido nem verifica assinaturas de transações no lugar dos nós. O Bitcoin a combina com outras regras, incluindo a verificação de transações e Proof of Work, uma prova de esforço computacional. Entender um componente é mais útil do que lhe atribuir as capacidades do sistema inteiro. [3]

A seção 8 do whitepaper descreve SPV, a verificação simplificada de pagamentos. Um cliente leve usa cabeçalhos e um ramo da árvore que liga uma transação a um bloco escolhido. Isso economiza dados, mas depende de hipóteses sobre a cadeia com maior trabalho acumulado e o comportamento dos mineradores. A prova de inclusão sozinha não verifica todas as regras das transações como faz um Full Node, um nó que as valida integralmente. Também não informa se uma saída foi gasta depois: é necessário conhecer os acontecimentos seguintes. Para quem está começando, o importante é não confundir “este pagamento está neste bloco” com uma verificação completa do dinheiro disponível agora. [3]

A tese de 1979 também usa uma árvore de autenticação para um conjunto finito de assinaturas digitais de uso único. Uma assinatura digital permite verificar que o titular de uma chave secreta aprovou uma mensagem; não é uma imagem de uma assinatura no papel. A árvore pode ligar muitos valores de verificação a uma raiz conhecida. Nessa construção, porém, a quantidade de assinaturas é limitada e a raiz precisa ser renovada com o tempo. Isso não permite reutilizar indefinidamente a mesma chave de uso único. Essa parte mais avançada do trabalho de Merkle mostra uma ideia recorrente: verificar a parte necessária com uma prova pequena, sabendo exatamente em que condições a verificação se apoia. [2]