Contente
O que é uma árvore Merkle?
Como as árvores Merkle são construídas?
Por que as raízes Merkle são usadas no Bitcoin?
Mineração
Verificação
Retomar
O que é uma árvore Merkle?
O conceito de árvore Merkle foi proposto no início da década de 1980 por Ralph Merkle, um cientista da computação conhecido por seu trabalho em criptografia de chave pública.
Uma árvore Merkle é uma estrutura para verificar dados em um conjunto. É amplamente utilizado no campo das redes peer-to-peer, onde os participantes precisam trocar informações e submetê-las a uma verificação independente.
A estrutura da árvore Merkle é baseada em funções hash, por isso recomendamos que você primeiro leia o artigo “O que é hashing” e depois retorne a este tópico.
Como as árvores Merkle são construídas?
Digamos que você baixe um arquivo grande. Ao usar um programa de código aberto, você precisa verificar se o hash do arquivo baixado corresponde ao hash publicado pelos desenvolvedores. Se corresponder, o arquivo no seu computador é exatamente igual ao arquivo deles.
Se os hashes forem diferentes, você baixou um arquivo malicioso disfarçado de programa ou ele foi baixado incorretamente e não funcionará. Problemas de carregamento também podem ser um incômodo, especialmente se demorar muito. Nesse caso, você precisará baixar o arquivo novamente e torcer para que desta vez tudo corra bem.
Você provavelmente está pensando: “É realmente tão complicado?” Felizmente, é aqui que as árvores Merkle são úteis, permitindo-nos dividir o arquivo em partes. Por exemplo, um arquivo de 50 GB pode ser dividido em 100 pedaços de 0,5 GB. Nesse caso, ele será baixado em partes, da mesma forma que os arquivos são baixados por meio de um torrent.
O objetivo principal do processo é obter um único hash chamado raiz Merkle que representa cada dado em um arquivo. Usando a raiz Merkle, podemos simplificar bastante a validação de dados.
Como exemplo, vamos pegar um arquivo de 8 GB dividido em 8 partes. Cada fragmento recebe um nome de A a H e depois passa por uma função hash para produzir 8 hashes diferentes.
Cada um dos oito fragmentos passa por uma função hash para gerar seu hash.
Então, tiramos isso do caminho. Recebemos um hash de todos os fragmentos, o que significa que podemos compará-lo com o original e descobrir qual está com defeito, certo? É possível, mas seria extremamente ineficaz. Existem apenas oito fragmentos em nosso arquivo, mas se houver milhares deles, você faria o hash de todos eles e compararia os resultados?
Dificilmente. Em vez disso, você precisa pegar cada par de hashes, concatená-los e misturá-los. Então, fazemos hash de hA + hB, hC + hD, hE + hF e hG + hH e obtemos quatro hashes. Em seguida, realizamos outra rodada de hashing para que haja dois hashes. Finalmente, fazemos o hash do par restante e obtemos o hash principal - a raiz Merkle (ou hash raiz).
A estrutura lembra uma árvore invertida. Na linha inferior há “folhas” que vão para os nós, que vão para a raiz.
Portanto, temos uma raiz Merkle representando o arquivo baixado. Agora podemos comparar o hash raiz com o hash do criador original. Se combinarem, então está tudo ótimo! Se os hashes forem diferentes, significa que os dados foram alterados, ou seja, um ou mais fragmentos criaram um hash diferente. Assim, qualquer modificação dos dados produzirá uma raiz Merkle completamente diferente.
Felizmente, podemos encontrar facilmente o fragmento incorreto. Digamos que este seja ele. Primeiro, consulte os dois últimos hashes que criaram a raiz Merkle (hABCD e hEFGH). Seu hABCD será igual ao original porque não há erros nesse segmento, mas seu hEFGH será diferente e deverá ser verificado. A seguir, solicitamos hEF e hGH e comparamos com os nossos. Como o hGH será compatível, precisamos do hEF. Finalmente, comparamos os hashes hE e hF. Então descobrimos que o fragmento incorreto é hE, o que significa que precisamos baixá-lo novamente.
Para resumir, uma árvore Merkle é criada dividindo os dados em muitas partes, que são então hash repetidamente para formar uma raiz Merkle. Este sistema torna mais fácil verificar se todos os dados estão corretos. Na próxima seção veremos outros usos possíveis.
Você está se perguntando como começar com criptomoedas? Compre Bitcoin na Binance!
Por que as raízes Merkle são usadas no Bitcoin?
As árvores Merkle têm muitos usos, mas por enquanto estamos interessados em sua aplicação em blockchain. As árvores Merkle são necessárias para trabalhar com Bitcoin e muitas outras criptomoedas; elas são parte integrante de cada bloco e estão localizadas nos cabeçalhos dos blocos; Para obter as folhas da árvore, utilizamos o hash de cada transação (TXID) incluída no bloco.
Neste caso, a raiz Merkle executa diversas tarefas. A seguir, veremos seu uso na mineração de criptomoedas e na verificação de transações.
Mineração
Um bloco Bitcoin consiste em duas partes. A primeira parte é o cabeçalho do bloco, um segmento de tamanho fixo que contém metadados do bloco. A segunda parte é uma lista de transações, cujo tamanho geralmente é muito maior que o cabeçalho, mas pode variar.
Os mineiros precisam fazer hash dos dados várias vezes para obter um resultado que atenda a certas condições e extrair um bloco válido. Encontrá-lo pode exigir trilhões de tentativas porque os mineradores precisam alterar o número aleatório no cabeçalho do bloco (nonce) para obter um novo resultado, mas a maior parte do bloco permanecerá a mesma. Pode haver milhares de transações em um bloco e todas elas terão que ser hash a cada vez.
A raiz Merkle simplifica muito esse processo. Durante a mineração, todas as transações necessárias são alinhadas em uma árvore Merkle. O hash raiz (32 bytes) é colocado no cabeçalho do bloco, após o qual apenas o cabeçalho do bloco é hash, não o bloco inteiro.
Este método é à prova de falsificação e resume efetivamente todas as transações em um bloco em um formato compacto. No entanto, é impossível encontrar um cabeçalho de bloco válido e depois alterar a lista de transações, pois isso alterará a raiz Merkle. Quando um bloco é enviado para outros nós, eles calculam a raiz da lista de transações. Se não corresponder à raiz no cabeçalho, o bloco será rejeitado.
Verificação
Vejamos outra propriedade útil das raízes Merkle, que diz respeito aos nós simplificados (que não contêm uma cópia completa do blockchain). Se você estiver executando um nó em um dispositivo com recursos limitados, não precisará necessariamente baixar e fazer hash de todas as transações de um bloco. Em vez disso, você pode simplesmente solicitar ao nó completo uma prova Merkle – prova de que sua transação está em um bloco específico. Esse método foi descrito em detalhes por Satoshi Nakamoto no white paper Bitcoin e costuma ser chamado de verificação de pagamento simplificada (SPV).
Para verificar o HD, apenas hashes vermelhos são necessários.
Digamos que precisamos de informações sobre uma transação cujo TXID seja hD. Dado hC, podemos calcular hCD. Precisamos então de hAB para calcular hABCD. Finalmente, hEFGH pode ser usado para verificar se a raiz Merkle resultante corresponde à raiz no cabeçalho do bloco. Se sim, isso prova que a transação foi incluída no bloco, pois é quase impossível criar o mesmo hash com dados diferentes.
No exemplo acima, fizemos hash apenas três vezes, enquanto sem a prova de Merkle isso teria que ser feito sete vezes. Como os blocos podem conter milhares de transações, o uso de provas Merkle pode economizar muito tempo e recursos computacionais.
Retomar
As árvores Merkle provaram sua eficácia na tecnologia de computadores. Eles são incrivelmente úteis em blockchains e permitem que as informações sejam facilmente verificadas em sistemas distribuídos sem sobrecarregar a rede com dados desnecessários.
Sem as árvores Merkle (e as raízes Merkle), os blocos de Bitcoin e outras criptomoedas seriam muito volumosos. Embora os nós leves possam ter preocupações de privacidade e segurança, as provas Merkle podem dizer de forma econômica se as transações foram incluídas em um bloco.