Guia Sobre Merkle Trees e Merkle Roots
P√°gina Inicial
Artigos
Guia Sobre Merkle Trees e Merkle Roots

Guia Sobre Merkle Trees e Merkle Roots

Avançado
Publicado em Jul 6, 2020Atualizado em Dec 27, 2022
7m

O que é uma Merkle Tree?

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.


Como funcionam as Merkle Trees?

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!



Por que Merkle Roots s√£o usadas para Bitcoin?

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.


Considera√ß√Ķes finais

As Merkle Trees se provaram extremamente √ļteis em diversas aplica√ß√Ķes da ci√™ncia da computa√ß√£o ‚Ästcomo 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.
Compartilhar publica√ß√Ķes
Registre uma conta
Coloque seus conhecimentos em pr√°tica. Abra uma conta na Binance hoje mesmo.