Árvore de Merkle

O que é uma Árvore de Merkle?

Uma Árvore de Merkle é uma estrutura de dados criptográfica que organiza muitos dados em uma árvore de hashes.

No universo cripto, as Árvores de Merkle ajudam as blockchains a verificar transações, saldos, contas, valores de armazenamento, reivindicações de airdrop, whitelists de NFT e outros grandes conjuntos de dados com eficiência.

Uma Árvore de Merkle também é chamada de árvore de hashes, pois cada nível da árvore é formado por valores de hash criptográficos.

O nível inferior contém itens de dados individuais chamados folhas.

O hash de cada folha é combinado com outro hash e processado novamente para criar o próximo nível.

Esse processo continua até restar um único hash no topo.

Esse hash final é chamado de raiz de Merkle.

O guia de desenvolvimento do Bitcoin explica que os hashes das transações são agrupados em pares e processados repetidamente até restar uma única raiz de Merkle no cabeçalho do bloco.

A ideia principal é simples: uma única raiz pequena pode representar um grande conjunto de dados.

Se algum item do conjunto mudar, os hashes acima dele também mudarão, modificando a raiz de Merkle.

Como funciona uma Árvore de Merkle

Uma Árvore de Merkle começa com dados brutos, como transações, endereços de carteira, registros de contas ou entradas de reivindicações.

Cada item é processado por uma função hash criptográfica para criar o hash de uma folha.

Dois hashes de folhas são combinados e processados para criar um hash pai.

Os hashes pais são então agrupados em pares e processados novamente para criar hashes de níveis superiores.

O processo continua até restar apenas um hash.

Esse hash final é a raiz de Merkle.

A raiz de Merkle funciona como uma impressão digital compacta de todo o conjunto de dados.

Se os dados não mudarem, o mesmo método de construção da árvore deverá produzir a mesma raiz.

Se uma transação, endereço, saldo ou valor de reivindicação mudar, a raiz final também deverá mudar.

Por que as Árvores de Merkle são importantes no universo cripto

As Árvores de Merkle são importantes porque as blockchains precisam verificar grandes quantidades de dados sem exigir que todos os usuários processem tudo o tempo todo.

Um bloco de blockchain pode conter muitas transações.

Um airdrop de tokens pode incluir milhares ou milhões de carteiras elegíveis.

Um banco de dados do estado da blockchain pode incluir contas, saldos, armazenamento de contratos e código.

As Árvores de Merkle permitem que os sistemas se comprometam com grandes conjuntos de dados por meio de uma única raiz, mantendo a possibilidade de verificar itens individuais posteriormente.

Isso melhora a eficiência, a escalabilidade e a integridade dos dados.

Também reduz os requisitos de armazenamento e largura de banda de muitos aplicativos cripto.

Sem Árvores de Merkle ou estruturas de dados autenticadas semelhantes, muitas tarefas de verificação em blockchain seriam mais lentas, pesadas e caras.

Raiz de Merkle

A raiz de Merkle é o hash final no topo de uma Árvore de Merkle.

Ela representa todos os dados abaixo dela.

Em um bloco de blockchain, a raiz de Merkle pode resumir todas as transações incluídas naquele bloco.

Em um contrato de airdrop, a raiz de Merkle pode resumir todos os endereços de carteira elegíveis e os valores de suas reivindicações.

Em uma árvore de estado, a raiz pode resumir várias contas ou valores de armazenamento.

A raiz, por si só, não revela o conjunto de dados completo.

Ela funciona apenas como um compromisso criptográfico com esse conjunto de dados.

O usuário ainda precisa da prova e das regras de verificação corretas para confirmar que um item pertence à árvore.

Folhas e ramos de Merkle

As folhas são os hashes do nível inferior de uma Árvore de Merkle.

Cada folha geralmente representa um item de dados.

Por exemplo, uma folha pode representar um hash de transação, endereço de carteira, registro de reivindicação, permissão para fazer mint de NFT ou valor de conta.

Os ramos são os hashes intermediários entre as folhas e a raiz.

Os ramos conectam as folhas individuais à raiz de Merkle final.

Uma prova de Merkle usa esses hashes dos ramos para provar que uma folha pertence à árvore.

Esse modelo permite verificar os dados sem mostrar nem baixar todas as outras folhas.

Provas de Árvore de Merkle

Uma prova de Árvore de Merkle é o conjunto de hashes irmãos necessário para provar que uma folha pertence a uma árvore com uma raiz conhecida.

O verificador começa pela folha em questão e a combina com os hashes da prova na ordem correta.

Se o hash final calculado corresponder à raiz confiável, a prova será válida.

Se o hash final calculado não corresponder à raiz confiável, a prova será inválida.

A documentação MerkleProof da OpenZeppelin descreve ferramentas para contratos inteligentes verificarem se uma folha pode ser comprovada como parte de uma Árvore de Merkle definida por uma raiz.

Por isso, as Árvores de Merkle são úteis para whitelists, reivindicações, recompensas e verificações de acesso on-chain.

Árvores de Merkle no Bitcoin

O Bitcoin usa Árvores de Merkle para organizar as transações dentro dos blocos.

Cada transação é processada por um hash. Em seguida, os hashes das transações são agrupados em pares e processados em níveis sucessivos até gerar uma única raiz de Merkle.

A raiz de Merkle é armazenada no cabeçalho do bloco.

Isso ajuda os nós do Bitcoin a detectar se os dados de uma transação foram alterados.

Também viabiliza a verificação leve de transações.

Um cliente leve pode usar uma prova de Merkle para verificar se uma transação foi incluída em um bloco sem baixar todas as transações desse bloco.

Isso viabiliza a verificação simplificada de pagamentos, geralmente chamada de SPV.

A SPV é menos abrangente do que a validação de um full node, mas é mais eficiente para carteiras e dispositivos com recursos limitados.

Árvores de Merkle no Ethereum

O Ethereum usa uma estrutura de dados autenticada relacionada, chamada Merkle Patricia Trie.

A documentação do Ethereum sobre Merkle Patricia Trie explica que a estrutura do Ethereum é determinística e pode ser verificada criptograficamente.

Essa estrutura ajuda o Ethereum a representar o estado das contas, o armazenamento e outros dados de chave e valor.

Se o estado mudar, a raiz de estado também mudará.

Isso permite que clientes e aplicativos do Ethereum verifiquem dados de estado em relação a uma raiz conhecida.

O padrão EIP-1186 eth_getProof descreve um método RPC para obter provas de Merkle de contas e valores de armazenamento do Ethereum.

A estrutura do Ethereum não é igual a uma Árvore de Merkle binária simples, mas usa a mesma ideia central de verificação por meio de hashes encadeados.

Árvores de Merkle em airdrops

Airdrops de cripto costumam usar Árvores de Merkle para gerenciar grandes listas de reivindicações.

Um projeto pode criar uma lista de endereços de carteira elegíveis e valores em tokens.

Cada par de endereço e valor se torna uma folha na Árvore de Merkle.

O projeto armazena apenas a raiz de Merkle no contrato inteligente.

Quando um usuário reivindica o airdrop, envia uma prova de Merkle.

O contrato verifica se a carteira e o valor pertencem à árvore representada pela raiz armazenada.

Isso economiza taxas de gas, pois o contrato não precisa armazenar cada carteira elegível diretamente on-chain.

Também torna mais prático realizar campanhas de reivindicação em grande escala.

Árvores de Merkle em whitelists de NFT

Projetos de NFT costumam usar Árvores de Merkle para whitelists, vendas antecipadas e acesso antecipado ao mint.

Em vez de armazenar cada endereço de carteira aprovado em um contrato, o projeto armazena uma única raiz de Merkle.

Cada carteira aprovada recebe uma prova que mostra que ela pertence à whitelist.

Durante o mint, o contrato inteligente confere a prova em relação à raiz armazenada.

Se a prova for válida, a carteira poderá fazer mint de acordo com as regras da whitelist.

Isso pode reduzir os custos de armazenamento on-chain e tornar a verificação da whitelist mais eficiente.

Mesmo assim, os usuários devem verificar se a página de mint, o endereço do contrato e a raiz de Merkle vêm de fontes oficiais.

Árvores de Merkle em light clients

Os light clients usam métodos compactos de verificação para reduzir a quantidade de dados da blockchain que precisam baixar.

As Árvores de Merkle ajudam os light clients a verificar transações ou dados de estado específicos em relação a cabeçalhos de bloco ou raízes confiáveis.

Isso é útil para carteiras móveis, navegadores e dispositivos com armazenamento ou largura de banda limitados.

Um light client não oferece o mesmo modelo de segurança que um nó com validação completa.

No entanto, a verificação baseada em Merkle pode oferecer mais confiança do que confiar cegamente em um único provedor de dados.

Isso faz das Árvores de Merkle um componente importante para uma infraestrutura cripto mais acessível.

Árvores de Merkle em jogos blockchain e aplicativos de metaverso

Jogos blockchain e aplicativos de metaverso podem usar Árvores de Merkle para verificar grandes listas de ativos, recompensas, jogadores ou permissões.

Um jogo pode usar uma raiz de Merkle para registrar a elegibilidade a recompensas de uma temporada.

Um aplicativo de metaverso pode usar uma raiz de Merkle para verificar reivindicações de distintivos de eventos ou permissões de terrenos virtuais.

Um projeto de NFT pode usar uma Árvore de Merkle para gerenciar revelações de atributos ou acesso por whitelist.

Isso permite que os aplicativos mantenham grandes conjuntos de dados off-chain e ainda verifiquem entradas específicas on-chain.

O resultado pode ser um custo menor e maior escalabilidade.

A desvantagem é que o processo off-chain de construção da árvore precisa ser transparente e correto.

Árvores de Merkle e integridade dos dados

As Árvores de Merkle protegem a integridade dos dados ao facilitar a detecção de alterações.

Se uma folha mudar, seu hash também muda.

Essa mudança afeta o hash pai, depois o hash do próximo nível e, por fim, a raiz de Merkle.

Assim, um verificador pode comparar raízes para detectar se o conjunto de dados continua igual.

As Árvores de Merkle não impedem que alguém crie um conjunto de dados falso.

Elas ajudam a provar se os dados correspondem a uma raiz específica com a qual houve um compromisso.

Por isso, a raiz precisa vir de uma fonte confiável ou verificada por consenso.

Árvore de Merkle vs. lista de hashes

Uma lista de hashes é simplesmente uma lista de hashes.

Uma Árvore de Merkle é uma estrutura organizada de hashes que permite criar provas compactas.

Com uma lista de hashes, a verificação de um item pode exigir mais dados da lista completa.

Com uma Árvore de Merkle, o verificador geralmente precisa apenas da folha em questão e de uma pequena quantidade de hashes irmãos.

Isso torna as Árvores de Merkle mais eficientes para grandes conjuntos de dados.

A vantagem de eficiência se torna mais importante à medida que o conjunto de dados cresce.

Árvore de Merkle vs. Merkle Patricia Trie

Uma Árvore de Merkle é uma estrutura geral de dados baseada em árvore de hashes.

Uma Merkle Patricia Trie é uma estrutura mais especializada, usada para dados de chave e valor.

O Ethereum usa uma Merkle Patricia Trie modificada para armazenar e verificar o estado com eficiência.

Uma Árvore de Merkle simples costuma ser usada para verificar a inclusão de transações, whitelists de NFT e reivindicações de airdrop.

Uma trie é mais adequada quando os dados precisam ser consultados por chaves, como endereços de contas ou slots de armazenamento.

As duas estruturas usam hashes criptográficos para permitir a detecção de adulteração dos dados.

Árvore de Merkle vs. Árvore de Verkle

Uma Árvore de Verkle é uma estrutura de dados autenticada mais recente, que usa compromissos vetoriais em vez de apenas pares de hashes.

As Árvores de Verkle costumam ser mencionadas como uma possível melhoria futura para os sistemas de estado de blockchain, pois podem reduzir o tamanho de algumas provas.

A documentação do Ethereum observa que o projeto planeja migrar, no futuro, da atual estrutura Merkle Patricia Trie para uma estrutura de Árvore de Verkle.

Isso não torna as Árvores de Merkle obsoletas.

Elas continuam amplamente usadas porque são simples, confiáveis e bem compreendidas.

Em muitos casos de uso, como airdrops e whitelists, as Árvores de Merkle continuam sendo práticas e eficientes.

Benefícios das Árvores de Merkle

O primeiro benefício é a eficiência da verificação.

Os usuários podem verificar um item sem baixar o conjunto de dados completo.

O segundo benefício é a integridade dos dados.

Qualquer alteração nos dados subjacentes modifica os hashes dos níveis superiores.

O terceiro benefício é o menor custo de armazenamento on-chain.

Os contratos inteligentes podem armazenar uma única raiz em vez de muitos registros individuais.

O quarto benefício é a escalabilidade.

Grandes conjuntos de dados podem ser representados por uma única raiz compacta.

O quinto benefício é a privacidade parcial.

Um usuário pode provar que um item está incluído sem revelar todos os outros itens do conjunto de dados.

Riscos e limitações das Árvores de Merkle

O primeiro risco é uma raiz incorreta.

Uma prova de Merkle apenas demonstra a inclusão no conjunto de dados representado por aquela raiz, que precisa ser confiável ou verificada.

O segundo risco é a construção incorreta da árvore.

Se um projeto usar um método de hash, uma codificação, uma ordenação ou um formato de folha incorretos, as provas poderão falhar ou se tornar inseguras.

O terceiro risco são erros de repetição ou reivindicação duplicada.

Os contratos de reivindicação precisam registrar se uma carteira já usou sua prova quando as reivindicações devem ocorrer apenas uma vez.

O quarto risco é o phishing.

Golpistas podem criar sites falsos de reivindicação que alegam usar provas de Merkle, mas pedem aos usuários que assinem transações prejudiciais.

O quinto risco é a interpretação equivocada.

Uma Árvore de Merkle prova a inclusão dos dados, mas não prova que um projeto é honesto, valioso ou seguro.

Como avaliar um sistema de Árvore de Merkle

Comece verificando se a raiz de Merkle vem de uma fonte oficial ou verificada por consenso.

Analise como as folhas são codificadas.

Confira qual função hash é usada.

Confirme se a árvore usa pares ordenados ou uma ordem fixa da esquerda para a direita.

Verifique se as provas são geradas por ferramentas oficiais ou por código open source.

Em contratos inteligentes, analise a função de verificação da prova e a lógica de controle das reivindicações.

Em airdrops e whitelists de NFT, verifique o endereço oficial do contrato antes de enviar uma prova ou assinar uma transação.

Um sistema de Árvore de Merkle bem projetado deve deixar claros a raiz, as regras e o processo de verificação.

Equívocos comuns sobre Árvores de Merkle

Um equívoco comum é pensar que uma Árvore de Merkle armazena todos os dados on-chain.

Em muitos aplicativos cripto, apenas a raiz de Merkle é armazenada on-chain, enquanto o conjunto de dados completo é criado e armazenado off-chain.

Outro equívoco é pensar que uma raiz de Merkle revela o conjunto de dados completo.

Uma raiz é apenas um compromisso por meio de hash e não mostra todas as folhas por si só.

Um terceiro equívoco é pensar que uma prova de Merkle válida demonstra, em sentido moral ou jurídico, que o usuário merece uma recompensa.

Ela demonstra apenas que os dados enviados estão incluídos no conjunto representado pela raiz.

Um quarto equívoco é pensar que todas as Árvores de Merkle são construídas da mesma forma.

Diferentes sistemas podem usar funções hash, métodos de codificação, regras de ordenação e estruturas de árvore diferentes.

Perguntas frequentes

O que é uma Árvore de Merkle em termos simples?

Uma Árvore de Merkle é uma árvore de hashes que permite verificar um dado específico dentro de um grande conjunto usando uma pequena prova.

O que é uma raiz de Merkle?

Uma raiz de Merkle é o hash final no topo de uma Árvore de Merkle e funciona como uma impressão digital compacta de todo o conjunto de dados.

Por que as blockchains usam Árvores de Merkle?

As blockchains usam Árvores de Merkle para verificar grandes conjuntos de dados com eficiência, reduzir os requisitos de dados e detectar alterações em dados de transações ou de estado.

Como o Bitcoin usa Árvores de Merkle?

O Bitcoin usa Árvores de Merkle para resumir as transações dos blocos, e a raiz de Merkle é armazenada no cabeçalho do bloco.

Como o Ethereum usa estruturas de Merkle?

O Ethereum usa uma Merkle Patricia Trie modificada para armazenar e verificar o estado das contas e os dados de armazenamento dos contratos.

O que é uma prova de Árvore de Merkle?

Uma prova de Árvore de Merkle é um conjunto de hashes irmãos que demonstra que uma folha específica pertence a uma árvore com uma raiz de Merkle conhecida.

Como as Árvores de Merkle são usadas em airdrops?

Os contratos de airdrop podem armazenar uma única raiz de Merkle e verificar as reivindicações dos usuários com provas de Merkle, em vez de armazenar todas as carteiras elegíveis on-chain.

Como as Árvores de Merkle são usadas em whitelists de NFT?

Projetos de NFT podem usar uma raiz de Merkle para representar as carteiras aprovadas e verificar cada carteira com uma prova durante o mint.

As Árvores de Merkle são privadas?

As Árvores de Merkle podem oferecer privacidade parcial, pois os usuários podem provar que um item está incluído sem revelar todo o conjunto de dados.

Árvores de Merkle são iguais a provas de conhecimento zero?

Não. As Árvores de Merkle comprovam a inclusão de dados em um conjunto comprometido, enquanto as provas de conhecimento zero podem demonstrar afirmações mais abrangentes sem revelar dados privados de entrada.

Conclusão

Uma Árvore de Merkle é uma estrutura de dados essencial do universo cripto que facilita a verificação de grandes conjuntos de dados.

Ela transforma vários itens de dados em uma árvore de hashes e produz uma raiz de Merkle final.

Essa raiz pode representar transações, saldos, endereços, reivindicações, valores de armazenamento ou outros dados de blockchain.

As Árvores de Merkle são importantes porque viabilizam a verificação eficiente, reduzem os custos de armazenamento e preservam a integridade dos dados, além de serem usadas por light clients, airdrops, whitelists de NFT e provas de estado de blockchain.

O Bitcoin usa Árvores de Merkle para resumir as transações dos blocos.

O Ethereum usa uma estrutura relacionada, a Merkle Patricia Trie, para representar o estado das contas e do armazenamento.

Aplicativos cripto usam Árvores de Merkle sempre que precisam provar que um item pertence a um grande conjunto de dados sem colocar o conjunto inteiro on-chain.

As Árvores de Merkle são poderosas, mas dependem de hashes corretos, codificação segura, raízes confiáveis e verificação segura das provas.

Quando bem utilizadas, tornam os sistemas cripto mais leves, baratos e fáceis de verificar.