O conceito de Merkle Tree (árvore de Merkle) foi proposto no início da década de 80 por Ralph Merkle – um cientista da computação conhecido por seu trabalho sobre
criptografia de chave pública.
Uma Merkle Tree é uma estrutura usada para verificar de maneira eficiente a integridade de um conjunto de dados. Essa estrutura é especialmente interessante no contexto de redes
peer-to-peer, onde os participantes precisam compartilhar e validar informações de forma independente.
As funções de hash são parte fundamental das estruturas de Merkle Trees, por isso recomendamos a leitura do artigo
O que é Hashing? antes de prosseguir.
Suponha que você queira fazer o download de um arquivo grande. Com o
software de código aberto, normalmente você quer verificar se o hash do arquivo baixado corresponde ao que foi divulgado pelos desenvolvedores. Se esse for o caso, você sabe que o arquivo em seu computador é exatamente o mesmo que o deles.
Se os hashes não coincidirem, você tem um problema. Ou você baixou um arquivo malicioso disfarçado de software, ou ele não foi baixado corretamente e, portanto, não funcionará. Se este for o caso, você provavelmente não ficará muito feliz em esperar novamente pelo tempo de download do arquivo. Agora, você deve reiniciar o processo e esperar que o arquivo não se corrompa novamente.
Então você pensa, se ao menos houvesse uma maneira mais fácil de fazer isso. Felizmente existem as Merkle Trees. Você pode ter seu arquivo dividido em partes. Se for um arquivo de 50 GB, você pode dividi-lo em cem partes, de modo que cada um tenha um tamanho de 0,5 GB. Em seguida, você faz o download de cada parte. Isto é essencialmente o que acontece quando você faz downloads de arquivos torrent.
Nesse caso, sua fonte fornecerá um hash conhecido como Merkle root. Esse hash único é uma representação de todos os fragmentos de dados que compõem seu arquivo. A Merkle Root facilita consideravelmente a verificação dos dados.
Para simplificar, vamos dar um exemplo em que usamos um arquivo de 8 GB dividido em oito partes. Nomeamos os diferentes fragmentos de A a H. Cada fragmento é submetido a uma função hash, fornecendo oito hashes diferentes.
Passando cada um dos oito fragmentos pela função hash para obter seus respectivos hashes.
Certo, agora temos algo que faz um pouco mais de sentido. Temos o hash de todos os fragmentos; portanto, se um deles estiver com defeito, saberemos disso comparando-o com o da fonte, certo? É uma possibilidade, mas muito ineficiente. Se o seu arquivo tiver milhares de fragmentos, você pretende obter o hash de todos eles e comparar meticulosamente com os resultados?
Não. Em vez disso, vamos pegar cada par de hashes, combiná-los e depois submeter todos juntos à função de hash. Então, faremos hashing de hA + hB, hC + hD, hE + hF e hG + hH. Agora, temos quatro hashes. Em seguida, fazemos outra rodada de hashing com estes, obtendo dois hashes. Finalmente, usamos os dois restantes para obter nosso hash principal – a Merkle Root (ou Root Hash).
É semelhante à estrutura invertida de uma árvore. Na linha inferior, temos as folhas, que são combinadas para produzir os galhos e finalmente, a raiz.
Agora temos a Merkle Root que representa o arquivo que baixamos. Podemos comparar esse root hash (hash raiz) com o fornecido pela fonte. Se combinar, perfeito! Mas se os hashes forem diferentes, podemos ter certeza de que os dados foram modificados. Ou seja, um ou mais fragmentos produziram um hash diferente. Portanto, qualquer pequena modificação nos dados, resultará em uma Merkle Root totalmente diferente.
Felizmente, existe uma maneira prática de verificar qual fragmento está com defeito. Nesse caso, digamos que é o hE. Você começaria pedindo a um Peer (par da rede), os dois hashes que produziram a Merkle Root (hABCD e hEFGH). Seu valor hABCD deve corresponder ao deles, pois não há nenhum erro nessa subárvore. Entretanto, o hEFGH não vai corresponder, então você sabe que deve verificar neste ponto. Você então solicita os hashes hEF e hGH e os compara ao seu. O hGH parece correto, então você sabe que o problema está no hEF. Por fim, você compara os hashes hE e hF. Agora você sabe que hE é o hash incorreto e pode fazer o download desse fragmento novamente.
Resumindo, uma Merkle Tree é criada dividindo dados em várias partes, que são repetidamente submetidas à funções hash para formar a Merkle Root. Assim, você pode verificar com eficiência se algo deu errado com algum dado. Como veremos na próxima seção, existem outras aplicações interessantes.
Pensando em investir em criptomoedas? Compre Bitcoin na Binance!
As Merkle Trees possuem muitas utilidades, mas aqui vamos nos concentrar em sua importância para
blockchains. As Merkle Trees são essenciais ao
Bitcoin e para muitas outras criptomoedas. São um componente integral de todos os
blocos e podem ser encontradas nos
block headers (identificação individual de cada bloco). Para obter as folhas da nossa árvore, usamos o hash da transação (o
TXID) de todas as transações contidas no bloco.
Neste caso, a Merkle Root serve a alguns propósitos. Vamos analisar suas aplicações na mineração de criptomoedas e na verificação de transações.
Mineração
Um bloco de Bitcoin é composto de duas peças. A primeira parte é o Block Header (identificação individual do bloco), um segmento de tamanho fixo contendo
metadados do bloco. A segunda parte é uma lista de transações cujo tamanho é variável, mas tende a ser bem maior que o Block Header.
Os mineradores precisam, repetidamente, fazer hashing dos dados para produzir um output (saída) que atenda a determinadas condições, extraindo assim, um bloco válido. Eles podem fazer trilhões de tentativas até encontrar a solução. A cada tentativa, eles alteram um número aleatório no Block Header (o
nonce) para produzir um output diferente. Entretanto, boa parte do bloco permanece inalterada. Um bloco pode conter milhares de transações e você ainda precisará fazer hashing de todas elas, em todas as tentativas.
Uma Merkle Root simplifica consideravelmente o processo. Quando você começa a minerar, você junta todas as transações que deseja incluir e constrói uma Merkle Tree. Você insere o root hash (hash raiz) resultante (de 32 bytes) no Block Header. Então, quando você estiver minerando, você só precisará fazer hashing do Block Header, em vez de fazer o processo no bloco todo.
Esse processo funciona porque é inviolável. Você efetivamente resume todas as transações do bloco em um formato mais compacto. Não é possível encontrar um Block Header válido e, posteriormente, alterar a lista de transações, pois isso alteraria a Merkle Root. Quando o bloco é enviado aos outros nodes (nós), eles calculam a root (raiz) da lista de transações. Se não a root não corresponder ao Block Header, o bloco será rejeitado.
Verificação
Existe outra propriedade interessante das Merkle Roots que podem ser aproveitadas. Esta que vamos citar é relacionada aos light clients (nodes que não possuem uma cópia completa da blockchain). Se você estiver executando um node em um dispositivo com recursos limitados, você não vai querer fazer o download e o hash de todas as transações de um bloco. O que você pode fazer é simplesmente solicitar uma Merkle Proof – ou seja, uma evidência fornecida pelo node completo, que comprova que sua transação está em um bloco específico. Esse processo é mais conhecido como Simplified Payment Verification (verificação de pagamento simplificada) ou SPV e foi explicado por
Satoshi Nakamoto no whitepaper do Bitcoin.
Para verificar hD, só precisamos dos hashes em vermelho.
Considere o cenário em que queremos saber informações sobre a transação cujo TXID é hD. Se hC for fornecido, podemos calcular hCD. Então, precisamos de hAB para calcular hABCD. Por fim, com hEFGH, podemos verificar se a Merkle Root resultante corresponde à do Block Header. Se isso acontecer, é uma prova de que a transação foi inserida no bloco – seria praticamente impossível criar o mesmo hash com dados diferentes.
No exemplo acima, tivemos que fazer hashing três vezes. Sem uma Merkle Proof, seriam necessárias sete vezes. Como hoje em dia os blocos contêm milhares de transações, o uso das Merkle Proofs nos poupa muito tempo e recursos computacionais.
As Merkle Trees se provaram extremamente úteis em diversas aplicações da ciência da computação – como vimos, elas são incrivelmente valiosas para blockchains. Em sistemas distribuídos, as Merkle Trees permitem fácil verificação de informações, sem causar inundação da rede com dados desnecessários.
Sem as Merkle Trees (e as Merkle Roots), os blocos de
Bitcoin de outras
criptomoedas não seriam compactos como são hoje. E enquanto light clients enfrentam a falta de privacidade e segurança, as Merkle Proofs permitem que os usuários verifiquem se as transações foram adicionadas à um bloco, sem sobrecarregar a rede.
