O que é uma Árvore de Merkle?

As árvores de Merkle são uma estrutura que surgiu no início dos anos 80, proposta pelo cientista da computação Ralph Merkle. Elas são utilizadas para verificar eficientemente a integridade dos dados em um conjunto. Essas árvores são especialmente interessantes no contexto de redes peer-to-peer, onde os participantes precisam compartilhar e validar informações de forma independente.

No cerne das estruturas de árvores de Merkle estão as funções hash, por isso é recomendado entender o que é o conceito de hashing antes de prosseguir.

Como funcionam as árvores de Merkle?

Para entender como as árvores de Merkle funcionam, vamos supor que você queira baixar um arquivo grande. Com um software de código aberto, você normalmente deseja verificar se o hash do arquivo que você baixou corresponde ao hash público fornecido pelos desenvolvedores. Se corresponder, você sabe que o arquivo que você tem em seu computador é exatamente o mesmo que o deles.

Se os hashes não corresponderem, você tem um problema. Ou você baixou um arquivo malicioso disfarçado do software, ou ele não foi baixado corretamente e, portanto, não funcionará. Se for o último caso, você provavelmente não ficará muito feliz se tiver que esperar algum tempo para o arquivo ser baixado. Agora, você precisa reiniciar o processo e esperar que ele não se corrompa novamente.

Mas e se houvesse uma maneira mais fácil de fazer isso? Felizmente, é aí que entram as árvores de Merkle. Com elas, seu arquivo seria dividido em pedaços. Se fosse um arquivo de 50GB, por exemplo, você poderia dividi-lo em cem partes, cada uma com 0,5GB de tamanho. Em seguida, o arquivo seria baixado pedaço por pedaço. Isso é essencialmente o que você faz quando baixa arquivos por torrent.

Nesse caso, a fonte do arquivo teria fornecido um hash conhecido como a raiz de Merkle. Esse único hash é uma representação de cada pedaço de dados que compõe o arquivo. Mas a raiz de Merkle torna muito mais fácil verificar os dados.

Para simplificar, vamos considerar um exemplo em que dividimos um arquivo de 8GB em oito partes. Chamaremos os diferentes fragmentos de A a H. Cada fragmento é passado por uma função hash, resultando em oito hashes diferentes.

Cada um dos oito fragmentos é passado por uma função hash para obter seus hashes.

Agora temos algo que faz um pouco mais de sentido. Temos o hash de todos os fragmentos, então se um estiver com problema, saberemos comparando-o com o hash fornecido pela fonte, certo? Possivelmente, mas isso também seria incrivelmente ineficiente. Se o seu arquivo tiver milhares de fragmentos, você realmente vai calcular o hash de todos eles e comparar meticulosamente os resultados?

Não. Em vez disso, vamos pegar cada par de hashes, combiná-los e depois fazer um novo hash com esse resultado. Assim, obtemos os hashes hA + hB, hC + hD, hE + hF e hG + hH. Agora temos quatro hashes. Em seguida, fazemos mais uma rodada de hashing com esses quatro hashes, resultando em dois. Por fim, fazemos o hash dos dois restantes para obter nosso hash mestre – a raiz de Merkle (ou hash raiz).

A estrutura se assemelha a uma árvore de cabeça para baixo. Na última linha, temos as folhas, que são combinadas para produzir os nós e, finalmente, a raiz.

Agora temos a raiz de Merkle que representa o arquivo que baixamos. Podemos comparar essa raiz com a fornecida pela fonte. Se coincidir, perfeito! Mas se os hashes forem diferentes, podemos ter certeza de que os dados foram modificados. Em outras palavras, um ou mais fragmentos produziram um hash diferente. Portanto, qualquer modificação mínima nos dados resultará em uma raiz de Merkle totalmente diferente.

Felizmente, existe uma maneira prática de verificar qual fragmento está com problema. No nosso caso, vamos supor que seja o hE. Você começaria pedindo a um peer os dois hashes que produziram a raiz de Merkle (hABCD e hEFGH). O valor hABCD deve coincidir com o deles, já que não há erro naquela subárvore. Mas hEFGH não corresponderá, então você sabe que o problema está lá. Em seguida, você solicita hEF e hGH e os compara com os seus. hGH deve parecer correto, então você sabe que o problema está em hEF. Por fim, você compara os hashes de hE e hF. Agora você sabe que hE está incorreto, então pode baixar novamente aquele fragmento.

Resumindo, uma árvore de Merkle é criada dividindo-se os dados em várias partes, que são então repetidamente passadas por funções hash para formar a raiz de Merkle. Você pode verificar eficientemente se algo deu errado com um pedaço de dados. Como veremos na próxima seção, existem outras aplicações interessantes também.