O que é uma árvore Merkle? Um Guia Simples para Árvores Merkle

A Merkle Tree é um método de estruturação de dados que permite que um grande corpo de informações seja verificado quanto à precisão de forma extremamente rápida e eficiente. Cada árvore Merkle resulta numa única cadeia de dados, conhecida como raiz de Merkle. Com a raiz Merkle, mais alguns outros dados, qualquer computador pode validar eficientemente todas as outras entradas na árvore Merkle. Na tecnologia blockchain, estas entradas são números de identificação de transação.

Se está envolvido no mundo da blockchain, pode ter se deparado com a frase “merkle tree” antes. Embora as árvores Merkle não sejam um conceito amplamente compreendido, também não são terrivelmente complicadas. Este post vai explicar as árvores Merkle em inglês simples e ajudá-lo a entender como elas tornam a tecnologia blockchain possível.

Tudo sobre Merkle Trees

A história de Merkle Trees começa em 1979 com um tipo chamado Ralph Merkle. Enquanto cursava a graduação na Universidade de Stanford, Merkle escreveu um artigo académico chamado “A Certified Digital Signature”. Neste ensaio, Merkle descreveu um método para criar assinaturas digitais e estabeleceu um método novo e extremamente eficiente de criação de provas criptográficas. Por outras palavras, desenhou um processo de verificação de dados que permitiria aos computadores fazerem o seu trabalho muito, muito mais rápido do que nunca.

Merkle chamou-lhe a ideia de “Assinaturas de Árvore” ou “Autenticação em Árvore. Hoje em dia, esta ideia é mais conhecida como Árvore Merkle, em homenagem ao inventor.

Não é exagero dizer que as Merkle Trees revolucionaram o mundo da criptografia e, por extensão, a forma como funcionam os protocolos informáticos encriptados. Na verdade, as Merkle Trees são mencionadas repetidamente no ensaio de 2008 de Satoshi Nakamoto que introduziu o Bitcoin ao mundo. São utilizados extensivamente no protocolo Bitcoin.

Então, o que é exatamente uma Merkle Tree? Vamos descobrir.

Primeiro, é importante compreender o conceito de uma função hash criptográfica. Dito de forma simples, as funções hash são funções matemáticas irreversíveis que levam uma entrada de qualquer comprimento — de um caractere ao texto de um conjunto inteiro de enciclopédias — e produzem uma saída aleatória de um comprimento fixo. Como a saída parece aleatória e tem comprimento fixo, um invasor não tem pistas sobre qual entrada criou uma saída específica. As funções de hash também são determinísticas, pelo que a mesma entrada produzirá sempre a mesma saída. Por último, as funções hash são irreversíveis, por isso não há absolutamente nenhuma maneira de determinar uma entrada apenas com o conhecimento da saída.

Todas estas propriedades permitem funções de hash para criar impressões digitais eletrónicas de uma entrada específica. Usando funções hash, as redes blockchain criam um hash criptográfico — uma impressão digital eletrónica — de cada transação. O hash criptográfico de uma transação chama-se simplesmente o ID da transação. Para quase todos os protocolos blockchain, cada ID de transação é uma cadeia de dados alfanuméricos de 64 caracteres (256 bits).

Quando considera que as blockchains são normalmente constituídas por centenas de milhares de blocos, com cada bloco contendo até vários milhares de transações, pode imaginar a rapidez com que a verificação das transações pode tornar-se computacionalmente difícil. Como tal, é ideal usar o mínimo de dados possível ao processar e verificar transações. Isto minimiza os tempos de processamento da CPU ao mesmo tempo que garante o mais alto nível de segurança.

Bem, é exatamente isso que as Merkle Trees fazem. Simplificando, as Merkle Trees pegam um grande número de IDs de transação, estruturam-nos de uma maneira específica e usam funções hash criptográficas para derivar uma única cadeia alfanumérica de 64 caracteres que atua como uma impressão digital eletrónica para todo o corpo de dados.

Esta cadeia de dados, chamada Merkle Root, é extremamente importante porque permite que qualquer computador verifique rapidamente se uma transação específica ocorreu num determinado bloco da forma mais eficiente possível.

O que é uma raiz de Merkle?

A única corda de 256 bits que uma Merkle Tree produz chama-se Raiz de Merkle. Cada bloco numa cadeia de blocos tem exatamente um. E, como acabamos de mencionar, o Merkle Root é um dado crucial porque permite que os computadores verifiquem informações com uma velocidade e eficiência incríveis.

Vamos mergulhar um pouco mais fundo. Como é produzida uma raiz de Merkle? O primeiro passo é organizar todas as entradas de dados que, neste caso, são IDs de transação. Merkle Trees, por design, agrupam sempre todas as entradas em pares. Se houver um número ímpar de entradas, a última entrada é copiada e emparelhada consigo mesma. Isto é válido para todos os IDs de transação gravados num bloco de uma cadeia de blocos.

Por exemplo, suponhamos que um único bloco contenha um total de 512 transações. A Merkle Tree começaria por agrupar esses 512 IDs de transações em 256 pares. Então, esses 256 pares de IDs de transação passariam por um processo matemático — a função de hash ou o algoritmo de hash, como às vezes é chamado — e teríamos 256 novos hashes criptográficos de 64 caracteres.

O mesmo processo ocorre de novo. Esses 256 novos hashes seriam emparelhados e transformados em 128 hashes. O processo é repetido, cortando o número de hashes pela metade de cada vez, até restar apenas um hash. Esse hash único é a nossa raiz de Merkle.

Um exemplo simples de uma árvore Merkle

Para deixar este conceito claro, vejamos um exemplo muito simples de uma árvore Merkle. Imagine que houve 8 transações realizadas num determinado bloco. Na realidade, os IDs de transação têm 64 caracteres, mas por uma questão de simplicidade, vamos fingir que têm apenas 8 caracteres. Para tornar as coisas ainda mais fáceis, vamos usar apenas números (e ignorar as letras completamente).

Portanto, neste exemplo, os nossos oito IDs de transações serão:

• 11111111
• 22222222
• 33333333
• 44444444
• 55555555
• 66666666
• 77777777
• 88888888

Agora vamos supor que o método para fazer o hash dos IDs de transação juntos é pegar o primeiro, o terceiro, o quinto e o sétimo dígitos de cada um dos dois IDs que estão a ser combinados e, em seguida, simplesmente juntar esses números para formar um novo código de 8 dígitos.

Claro que, na realidade, a matemática por trás dos algoritmos de hashing é muito mais complicada do que isso. Mas para esta demonstração simples, este sistema elementar será suficiente.

Isto é o que a nossa árvore Merkle ficaria:

Repare que o número de códigos é cortado ao meio a cada passo abaixo da Árvore Merkle. Começamos com 8 IDs de transação e, depois de apenas 3 passos, acabamos com um único código — o Merkle Root. Neste exemplo, a nossa raiz de Merkle é o código na caixa inferior: 12345678.

O principal benefício das Merkle Trees é que permitem uma verificação extremamente rápida dos dados. Se quisermos validar um único ID de transação, não precisaríamos de verificar novamente todas as transações no bloco. Em vez disso, só precisaríamos verificar esse “ramo” específico da nossa Árvore Merkle.

Eficiência e Velocidade: Os Benefícios das Árvores Merkle

Vamos supor que queremos validar um ID de transação no nosso exemplo atual. Bob diz que pagou a Alice uma certa quantia de Bitcoin e diz-nos que o ID da transação é 88888888. Ele também nos envia 3 hashes: 77777777, 55556666 e 11223344. Isso é toda a informação que precisa de ser enviada ou recebida para verificar o pagamento do Bob à Alice.

Estes três hashes, juntamente com o ID da transação em questão e o Merkle Root deste bloco em particular, são os únicos dados necessários para verificar o pagamento do Bob a Alice. Isto são muito menos dados do que seriam necessários para verificar toda a Árvore Merkle. Como resultado, o processo de verificação é muito mais rápido e muito mais eficiente para todos.

É assim que funciona. Já temos o Merkle Root do bloco, então o Bob não precisa de nos enviar isso. Ele envia-nos o ID da transação e os 3 hashes adicionais que listamos acima. Ele também envia um pouquinho de informação sobre o pedido e o posicionamento para usar os hashes. Agora, tudo o que temos de fazer é executar o algoritmo de hash no conjunto de dados que o Bob forneceu.

Começamos por fazer o hashing do primeiro código 77777777 com o ID da transação 88888888, o que nos dá o resultado 77778888. Bob não nos enviou este código mas não precisou porque estamos a usar o mesmo algoritmo de hash que ele. Portanto, recebemos exatamente os mesmos resultados.

Em seguida, pegamos o segundo código que Bob nos enviou, 55556666, e o hash com o novo código 77778888 que acabamos de derivar. Isto, é claro, produz o número 55667788.

Finalmente, hash o terceiro código que Bob nos deu, 11223344, com o outro novo código que recebemos, 55667788, e acabamos com a raiz de Merkle correta: 12345678.

Repare que só precisamos de 3 códigos do Bob e só tivemos de executar o algoritmo de hash três vezes para ver se a transação do Bob é válida. Isso significa que o nosso computador fez menos da metade do trabalho que teria sido necessário para verificar toda a Merkle Tree. O diagrama original da Merkle Tree tem 15 números e o algoritmo de hash precisa de ser executado 7 vezes. Mas mais da metade dessa árvore não é necessária para verificar a transação do Bob!

Procedimentos de validação simplificados com Merkle Tree

Este procedimento é suficiente para verificar se o Bob pagou, de facto, a Alice aquela certa soma de Bitcoin porque derivamos números que, quando misturados com os outros códigos que Bob nos enviou, produziram a mesma Raiz Merkle que já sabíamos ser verdadeiros para este bloco em particular.

Bob não pode falsificar uma transação porque isso exigiria encontrar um ID de transação falso e um conjunto adicional de códigos falsos que, quando colocados através da função de hash, produziriam a verdadeira raiz Merkle. As hipóteses de isto acontecer são tão astronomicamente pequenas que podemos dizer com confiança que é impossível.

Neste exemplo simples, a poupança de poder computacional pode não parecer substancial. No entanto, quando considera que os blocos numa cadeia de blocos podem conter vários milhares de transações, é fácil ver como as Merkle Trees aumentam a eficiência de forma tão dramática.

Resumindo, esse é o principal benefício de uma Merkle Tree. Permite que os computadores verifiquem informações de forma extremamente eficiente e com muito menos dados do que seria necessário sem a Árvore Merkle.

Merkle Trees são também o conceito fundamental na solução da Plataforma Komodo para o problema de escalabilidade da blockchain. A solução de escalonamento da Komodo permite uma interoperabilidade completa da cadeia de blocos e permitirá à Komodo processar transações mais rapidamente do que qualquer outro serviço de processamento de pagamentos no planeta. Atualmente, a nova tecnologia de escalonamento da Komodo está a processar mais de 20.000 transações por segundo num ambiente de testes.

Isenção de responsabilidade：

1. Este artigo foi reimpresso de [komodo]. Todos os direitos de autor pertencem ao autor original [Delton Rhodes]. Se houver objeções a esta reimpressão, contacte a equipa do Gate Learn, e eles tratarão disso imediatamente.
2. Isenção de responsabilidade: As opiniões e opiniões expressas neste artigo são exclusivamente do autor e não constituem nenhum conselho de investimento.
3. As traduções do artigo para outras línguas são feitas pela equipa do Gate Learn. A menos que mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.