O que é uma árvore Merkle?
O conceito de árvore Merkle foi proposto no início dos anos 80 por Ralph Merkle – um cientista da computação conhecido por seu trabalho em criptografia de chave pública.
Uma árvore Merkle é uma estrutura usada para verificar com eficiência a integridade dos dados em um conjunto. Eles são particularmente interessantes no contexto de redes peer-to-peer, onde os participantes precisam compartilhar e validar informações de forma independente.
As funções hash estão no centro das estruturas da árvore Merkle, por isso recomendamos que você verifique O que é Hashing? antes de proceder.
Como funcionam as árvores Merkle?
Suponha que você queira baixar um arquivo grande. Com software de código aberto, normalmente você deseja verificar se o hash do arquivo baixado corresponde ao tornado público pelos desenvolvedores. Se isso acontecer, você sabe que o arquivo que tem no seu computador é exatamente igual ao deles.
Se os hashes não corresponderem, você tem um problema. 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 se tiver que esperar algum tempo para o download do arquivo. Agora, você precisa reiniciar o processo e torcer para que ele não seja corrompido novamente.
Se ao menos houvesse uma maneira mais fácil de fazer isso, você pensa. Felizmente, é aí que entram as árvores Merkle. Com uma delas, você teria seu arquivo dividido em pedaços. Se fosse um arquivo de 50 GB, você poderia dividi-lo em cem partes, de modo que cada uma tivesse 0,5 GB de tamanho. Em seguida, ele seria baixado peça por peça. Isso é essencialmente o que você faz quando baixa arquivos torrent.
Nesse caso, sua fonte fornecerá um hash conhecido como raiz Merkle. Esse hash único é uma representação de cada pedaço de dados que compõe seu arquivo. Mas a raiz Merkle torna muito mais fácil a verificação dos dados.
Para simplificar, vamos dar um exemplo em que usamos um arquivo de 8 GB dividido em oito partes. Chame os diferentes fragmentos de A a H. Cada fragmento é então passado por uma função hash, dando-nos oito hashes diferentes.
Passamos cada um dos nossos oito fragmentos por uma função hash para obter seus hashes.
Ok, então temos algo que faz um pouco mais de sentido. Temos o hash de todos os fragmentos, então se algum estiver com defeito saberemos comparando com o da fonte, certo? Possivelmente, mas isso também é incrivelmente ineficiente. Se o seu arquivo tiver milhares de fragmentos, você realmente vai fazer o hash de todos eles e comparar meticulosamente os resultados?
Em vez disso, pegaremos cada par de hashes, combiná-los e, em seguida, misturá-los. Então, misturamos hA + hB, hC + hD, hE + hF e hG + hH. Acabamos com quatro hashes. Então fazemos outra rodada de hashing com estes para terminar com dois. Finalmente, fazemos o hash dos dois restantes para chegar ao nosso hash mestre – a raiz Merkle (ou hash raiz).
A estrutura parece uma árvore invertida. Na linha inferior, temos as folhas, que se combinam para produzir os nós e, por fim, a raiz.
Agora temos a raiz Merkle que representa o arquivo que baixamos. Podemos comparar esse hash raiz com aquele fornecido pela fonte. Se combinar, 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 pequena modificação nos dados nos dará uma raiz Merkle totalmente diferente.
Felizmente, existe uma maneira prática de verificar qual fragmento está com defeito. No nosso caso, digamos que seja ele. Você começaria pedindo a um par os dois hashes que produziram a raiz Merkle (hABCD e hEFGH). Seu valor hABCD deve corresponder ao deles, pois não há erros nessa subárvore. Mas o hEFGH não o fará, então você deve verificar lá. Você então solicita hEF e hGH e os compara com os seus. O hGH ficará bem, então você sabe que o hEF é o nosso culpado. Por último, você compara os hashes de hE e hF. Agora você sabe que hE está incorreto, então você pode baixar novamente esse pedaço.
Resumindo tudo, uma árvore Merkle é criada dividindo os dados em vários pedaços, que são então hash repetidamente para formar a raiz Merkle. Você pode então verificar com eficiência se algo deu errado com um dado. Como veremos na próxima seção, também existem outras aplicações interessantes.
Quer começar com criptomoeda? Compre Bitcoin na Binance!
Por que as raízes Merkle são usadas no Bitcoin?
Existem alguns casos de uso para árvores Merkle, mas aqui vamos nos concentrar em sua importância em blockchains. As árvores Merkle são essenciais no Bitcoin e em muitas outras criptomoedas. Eles são um componente integral de cada bloco, onde podem ser encontrados nos cabeçalhos dos blocos. Para obter as folhas da nossa árvore, usamos o hash da transação (o TXID) de cada transação incluída no bloco.
A raiz Merkle serve a alguns propósitos neste caso. Vamos dar uma olhada em suas aplicações em mineração de criptomoedas e verificação de transações.
Mineração
Um bloco Bitcoin é composto de duas peças. A primeira parte é o cabeçalho 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 muito maior que o cabeçalho.
Os mineradores precisam fazer hash repetidamente dos dados para produzir uma saída que atenda a certas condições para extrair um bloco válido. Eles podem fazer trilhões de tentativas antes de encontrar um. A cada tentativa, eles alteram um número aleatório no cabeçalho do bloco (o nonce) para produzir uma saída diferente. Mas grande parte do bloco permanece o mesmo. Pode haver milhares de transações e você ainda precisará fazer hash delas todas as vezes.
Uma raiz Merkle agiliza consideravelmente o processo. Ao iniciar a mineração, você alinha todas as transações que deseja incluir e constrói uma árvore Merkle. Você coloca o hash raiz resultante (32 bytes) no cabeçalho do bloco. Então, quando você estiver minerando, você só precisará fazer o hash do cabeçalho do bloco, em vez de todo o bloco.
Isso funciona porque é à prova de adulteração. Você resume efetivamente todas as transações do bloco em um formato compacto. Você não pode encontrar um cabeçalho de bloco válido e posteriormente alterar a lista de transações, porque isso alteraria a raiz Merkle. Quando o bloco é enviado para outros nós, eles calculam a raiz da lista de transações. Se não corresponder ao do cabeçalho, eles rejeitam o bloco.
Verificação
Há outra propriedade interessante das raízes Merkle que podemos aproveitar. Este diz respeito aos clientes leves (nós que não possuem uma cópia completa do blockchain). Se você estiver executando um nó em um dispositivo com recursos limitados, você não deseja baixar e fazer hash de todas as transações de um bloco. Em vez disso, o que você pode fazer é simplesmente solicitar uma prova Merkle – evidência fornecida pelo nó completo que prova que sua transação está em um bloco específico. Isso é mais comumente referido como Verificação de Pagamento Simplificada, ou SPV, e foi detalhado por Satoshi Nakamoto no white paper Bitcoin.
Para verificar o HD, precisamos apenas dos hashes mostrados em vermelho.
Considere o cenário onde queremos saber informações sobre a transação cujo TXID é hD. Se hC nos for fornecido, podemos calcular o hCD. Então, precisamos de hAB para calcular hABCD. Por último, com hEFGH, podemos verificar se a raiz Merkle resultante corresponde àquela do cabeçalho do bloco. Se isso acontecer, é uma prova de que a transação foi incluída no bloco – seria quase impossível criar o mesmo hash com dados diferentes.
No exemplo acima, só tivemos que fazer hash três vezes. Sem uma prova de Merkle, teríamos precisado de o fazer sete vezes. Como os blocos hoje em dia contêm milhares de transações, o uso das provas Merkle economiza muito tempo e recursos computacionais.
Pensamentos finais
As árvores Merkle provaram ser altamente úteis em uma variedade de aplicações de ciência da computação – como vimos, elas são incrivelmente valiosas em blockchains. Em sistemas distribuídos, as árvores Merkle permitem fácil verificação de informações sem inundar a rede com dados desnecessários.
Sem as árvores Merkle (e as raízes Merkle), os blocos de Bitcoin e outras criptomoedas não seriam tão compactos como são hoje. E embora faltem clientes leves nas frentes de privacidade e segurança, as provas Merkle permitem que os usuários verifiquem se suas transações foram incluídas em um bloco com sobrecarga mínima.
