Prova de Árvore de Merkle

O que é uma prova de Árvore de Merkle?

Uma prova de Árvore de Merkle é uma prova criptográfica que mostra que um dado específico pertence a um conjunto maior de dados, sem revelar nem exigir o download do conjunto inteiro.

No universo cripto, uma prova de Árvore de Merkle costuma ser usada para provar que uma transação, conta, saldo, valor de armazenamento, reivindicação de NFT ou endereço de carteira está incluído em um conjunto de dados verificado.

Ela funciona com hashes de uma Árvore de Merkle, também chamada de árvore de hashes.

Uma Árvore de Merkle recebe vários dados, transforma-os em folhas por meio de hashes, combina esses hashes em pares e continua aplicando hashes nos níveis superiores até restar um único hash final.

Esse hash final é chamado de raiz de Merkle.

Se a raiz de Merkle for confiável, o usuário poderá verificar um item usando apenas uma pequena prova, em vez de conferir todo o conjunto de dados.

O guia de desenvolvimento do Bitcoin explica que as Árvores de Merkle permitem que os clientes verifiquem se uma transação foi incluída em um bloco usando a raiz de Merkle do cabeçalho do bloco e hashes intermediários fornecidos por um peer.

Por isso, as provas de Árvore de Merkle são importantes para a eficiência da blockchain, light clients, airdrops de tokens, whitelists de NFTs, bridges, provas de estado e verificação de dados.

Como funciona uma Árvore de Merkle

Uma Árvore de Merkle começa com itens de dados individuais na parte inferior da árvore.

Esses itens inferiores são chamados de folhas.

Em uma blockchain, cada folha pode representar um hash de transação, registro de conta, valor de armazenamento, endereço de carteira ou registro de reivindicação.

Cada folha é processada por uma função hash criptográfica.

Em seguida, os hashes são agrupados em pares e processados novamente.

Esse processo continua nível por nível até que a árvore produza um único hash no topo.

Esse hash é a raiz de Merkle.

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

Essa alteração se propaga pela árvore e modifica a raiz de Merkle.

Por isso, a raiz de Merkle pode funcionar como uma impressão digital compacta de um grande conjunto de dados.

Como funciona uma prova de Árvore de Merkle

Uma prova de Árvore de Merkle demonstra que uma folha específica pertence a uma árvore com uma raiz conhecida.

Em geral, a prova contém os hashes irmãos necessários para reconstruir o caminho da folha até a raiz.

O verificador começa pelo hash da folha.

Em seguida, combina esse hash com o primeiro hash irmão e processa o par.

O resultado é combinado com o próximo hash irmão e processado novamente.

Esse processo continua até que o verificador calcule uma raiz final.

Se a raiz calculada corresponder à raiz de Merkle confiável, a prova será válida.

Se a raiz calculada não corresponder, a prova será inválida.

Assim, é possível verificar os dados sem expor todas as folhas da árvore.

Exemplo simples de uma prova de Árvore de Merkle

Imagine uma whitelist de NFT com quatro endereços de carteira.

Cada endereço é transformado em uma folha por meio de um hash.

As folhas A e B são combinadas e processadas para criar um hash pai.

As folhas C e D são combinadas e processadas para criar outro hash pai.

Esses dois hashes pais são então combinados para criar a raiz de Merkle.

Se a Carteira A quiser provar que está na whitelist, não precisará revelar a lista inteira.

Ela precisará apenas de sua própria folha e dos hashes irmãos necessários para reconstruir a raiz de Merkle.

O contrato inteligente pode verificar a prova e permitir que a carteira reivindique ou faça mint se a prova corresponder à raiz armazenada.

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

As provas de Árvore de Merkle são importantes porque as blockchains precisam de formas eficientes de verificar grandes quantidades de dados.

Sem provas de Merkle, usuários e aplicativos talvez precisassem baixar ou confiar em muito mais informações.

Uma prova de Merkle torna a verificação mais compacta, rápida e prática.

Isso é especialmente útil quando há limitações de armazenamento, largura de banda, taxas de gas ou recursos do dispositivo.

Carteiras leves podem usar provas para verificar dados sem executar um full node.

Contratos inteligentes podem usar provas para verificar whitelists sem armazenar milhares de endereços on-chain.

Bridges e sistemas cross-chain podem usar provas para verificar eventos ou estados de outra chain.

Sistemas de disponibilidade de dados e rollups também podem usar compromissos baseados em Merkle para ajudar a provar que os dados pertencem a uma estrutura maior comprometida.

Provas de Árvore de Merkle no Bitcoin

O Bitcoin usa Árvores de Merkle para resumir as transações de um bloco.

A raiz de Merkle é incluída no cabeçalho do bloco.

Um cliente leve pode verificar se uma transação foi incluída em um bloco conferindo uma prova de Merkle em relação à raiz de Merkle do bloco.

Isso viabiliza a Verificação Simplificada de Pagamentos, geralmente chamada de SPV.

A SPV permite que uma carteira ou cliente verifique a inclusão de uma transação sem baixar todos os blocos completos.

Isso não significa que o cliente verifica tudo o que um full node verifica.

Significa que o cliente pode verificar a inclusão com mais eficiência, usando cabeçalhos de blocos e dados da prova.

Provas de Árvore de Merkle no Ethereum

O Ethereum usa estruturas de dados autenticadas baseadas em Merkle para verificar contas e dados de armazenamento.

A documentação do Ethereum sobre Merkle Patricia Tries explica que o Ethereum usa estruturas de árvores vinculadas por hashes criptográficos para garantir a integridade dos dados armazenados.

As provas do Ethereum podem mostrar que uma conta ou um valor de armazenamento faz parte de uma raiz de estado específica.

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

Esse tipo de prova é útil quando um aplicativo quer verificar o estado de uma conta sem confiar cegamente em um provedor de dados.

Os sistemas de prova do Ethereum são mais complexos do que uma árvore binária de Merkle simples, porque o estado do Ethereum é armazenado em estruturas baseadas em tries.

No entanto, a ideia central é semelhante: uma pequena prova pode verificar um dado em relação a uma raiz confiável.

Provas de Árvore de Merkle em whitelists de NFT

Projetos de NFT costumam usar provas de Árvore de Merkle para whitelists e vendas antecipadas.

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

Cada usuário aprovado recebe uma prova que mostra que seu endereço de carteira faz parte da árvore da whitelist.

Quando o usuário reivindica ou faz mint, o contrato inteligente verifica a prova em relação à raiz armazenada.

Isso pode reduzir os custos de armazenamento on-chain, pois armazenar uma única raiz é muito mais barato do que armazenar milhares de endereços.

Também pode melhorar a privacidade, pois não é necessário inserir a whitelist completa diretamente no contrato.

No entanto, os usuários ainda devem verificar se a raiz foi criada pelo projeto oficial e se a página de reivindicação não é um site de phishing.

Provas de Árvore de Merkle em airdrops

Os airdrops costumam usar provas de Árvore de Merkle para verificar quem pode reivindicar tokens.

O projeto cria um conjunto de dados com os endereços de carteira elegíveis e os valores das reivindicações.

Cada registro de reivindicação se torna uma folha na Árvore de Merkle.

O contrato inteligente armazena a raiz de Merkle.

Quando o usuário faz uma reivindicação, envia seu endereço, o valor da reivindicação e a prova.

O contrato verifica se a prova corresponde à raiz armazenada.

Se a prova for válida e a carteira ainda não tiver feito a reivindicação, o contrato poderá liberar os tokens.

Esse modelo ajuda os projetos a administrar grandes airdrops sem armazenar cada registro de reivindicação diretamente on-chain.

Provas de Árvore de Merkle em light clients

Um light client é uma carteira ou um nó que verifica dados da blockchain sem baixar e processar todos os dados da blockchain completa.

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

A documentação do Ethereum sobre light clients explica que eles permitem verificar dados recebidos usando apenas uma pequena fração dos recursos exigidos por full nodes.

Isso é importante para dispositivos móveis, navegadores, sistemas embarcados e usuários com largura de banda limitada.

Light clients não são iguais a full nodes.

Eles verificam menos dados, mas ainda podem aumentar a confiança em comparação com a dependência total de um provedor de dados centralizado.

Provas de Árvore de Merkle em contratos inteligentes

Os contratos inteligentes podem verificar provas de Árvore de Merkle diretamente on-chain.

Isso é útil quando um contrato precisa verificar a inclusão de um item em um conjunto de dados grande.

A documentação MerkleProof da OpenZeppelin oferece ferramentas para verificar provas de Merkle em contratos inteligentes.

Um padrão comum de contrato armazena uma raiz de Merkle e verifica as provas enviadas pelos usuários durante reivindicações, mints, recompensas ou verificações de acesso.

Isso evita a necessidade de armazenar todos os endereços ou registros elegíveis no contrato.

A principal desvantagem é que a prova precisa ser gerada corretamente off-chain.

Se a construção da árvore, o método de hash, a regra de ordenação ou a codificação das folhas estiverem incorretos, usuários elegíveis poderão não passar na verificação ou usuários não elegíveis poderão ser aceitos em sistemas mal projetados.

Prova de Árvore de Merkle vs. raiz de Merkle

A raiz de Merkle é o hash final que representa a árvore inteira.

Uma prova de Árvore de Merkle é o conjunto de hashes e dados relacionados usados para provar que uma folha pertence à árvore.

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

A prova é a evidência que conecta um item a essa impressão digital.

Sozinha, a raiz não revela todos os dados da árvore.

Sozinha, a prova não é útil se o verificador não tiver uma raiz confiável para comparar.

As duas são necessárias para a verificação.

Prova de Árvore de Merkle vs. prova de conhecimento zero

Uma prova de Árvore de Merkle e uma prova de conhecimento zero são ferramentas criptográficas diferentes.

Uma prova de Árvore de Merkle demonstra que um item específico está incluído em um conjunto de dados comprometido.

Uma prova de conhecimento zero pode demonstrar que uma afirmação é verdadeira sem revelar as informações privadas subjacentes.

Em geral, as provas de Merkle são mais simples, baratas e fáceis de verificar do que muitas provas de conhecimento zero.

As provas de conhecimento zero podem viabilizar casos de uso mais complexos relacionados à privacidade e à computação.

Em alguns sistemas, as provas de Merkle e de conhecimento zero são usadas em conjunto.

Por exemplo, um circuito de conhecimento zero pode verificar de forma privada uma prova de inclusão de Merkle.

Prova de Árvore de Merkle vs. prova de armazenamento

Uma prova de armazenamento costuma ser um tipo de prova baseada em Merkle que verifica um valor armazenado no estado da blockchain.

Por exemplo, uma prova de armazenamento do Ethereum pode mostrar que um slot de armazenamento de um contrato inteligente tinha determinado valor em uma raiz de estado específica de um bloco.

Prova de Árvore de Merkle é o conceito mais abrangente.

Uma prova de armazenamento é um caso de uso específico para provar dados de estado ou armazenamento.

Essa distinção é importante porque diferentes chains usam estruturas de dados, formatos de prova e regras de hash diferentes.

Os usuários não devem presumir que uma prova de uma blockchain funciona da mesma forma em outra blockchain.

Benefícios das provas de Árvore de Merkle

O primeiro benefício é a eficiência.

Uma prova permite verificar um item sem exigir o conjunto de dados inteiro.

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

Os contratos inteligentes podem armazenar uma única raiz em vez de milhares ou milhões de registros.

O terceiro benefício é uma escalabilidade maior.

É possível comprometer grandes conjuntos de dados com uma raiz pequena e verificá-los por meio de provas compactas.

O quarto benefício é a integridade dos dados.

Se uma folha ou um hash da prova for alterado, a raiz calculada não corresponderá à original.

O quinto benefício é a privacidade parcial.

Os usuários podem provar que um item está incluído sem revelar todos os outros itens do conjunto de dados.

Riscos e limitações

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

Se um projeto construir a árvore incorretamente, as provas poderão falhar ou produzir resultados inesperados.

O segundo risco é a codificação inadequada das folhas.

Se as folhas não forem codificadas com cuidado, entradas diferentes poderão gerar comportamentos de prova confusos ou inseguros.

O terceiro risco são as suposições incorretas sobre a ordenação.

Alguns sistemas de prova de Merkle exigem pares ordenados, enquanto outros dependem da ordem esquerda-direita.

O quarto risco são raízes não confiáveis.

Uma prova válida apenas demonstra a inclusão no conjunto de dados representado por aquela raiz. Por isso, a própria raiz precisa vir de uma fonte confiável ou verificada.

O quinto risco são problemas de repetição ou reivindicação duplicada.

Contratos de airdrop e de reivindicação precisam registrar se uma prova já foi usada quando cada reivindicação deve ocorrer apenas uma vez.

O sexto risco é o phishing.

Golpistas podem criar páginas falsas de reivindicação que pedem aos usuários que enviem provas ou assinem transações perigosas.

Como verificar uma prova de Árvore de Merkle

Comece pelos dados da folha que precisam ser verificados.

Processe a folha com o mesmo método de hash usado para construir a árvore original.

Combine o hash da folha com o primeiro hash irmão da prova.

Processe o valor combinado.

Repita o processo com cada hash irmão restante.

Compare o hash final calculado com a raiz de Merkle confiável.

Se as duas raízes corresponderem, a prova será válida.

Se não corresponderem, a prova será inválida.

Em contratos inteligentes, o mesmo processo costuma ser executado pelo código de verificação.

Para os usuários, a etapa mais importante é confirmar se a raiz, o contrato, a página de reivindicação e a fonte são oficiais.

Equívocos comuns sobre provas de Árvore de Merkle

Um equívoco comum é pensar que uma prova de Árvore de Merkle demonstra que os dados são verdadeiros em todos os sentidos possíveis.

Ela demonstra apenas que os dados estão incluídos em um conjunto representado por uma raiz específica.

Outro equívoco é pensar que uma prova de Merkle revela o conjunto de dados inteiro.

Em geral, ela revela apenas a folha em questão e os hashes irmãos necessários para a verificação.

Um terceiro equívoco é pensar que todas as provas de Merkle usam o mesmo formato.

Diferentes sistemas podem usar funções hash, regras de ordenação, formatos de árvore e codificações de prova diferentes.

Um quarto equívoco é pensar que as provas de Merkle eliminam toda a necessidade de confiança.

Elas reduzem a confiança necessária na entrega dos dados, mas o usuário ainda precisa de uma raiz confiável e de regras de verificação corretas.

Um quinto equívoco é pensar que as provas de Merkle são usadas apenas para transações.

Elas também podem verificar whitelists, airdrops, estado de contas, valores de armazenamento, dados de rollups, mensagens cross-chain e reivindicações de identidade digital.

Perguntas frequentes

O que é uma prova de Árvore de Merkle?

Uma prova de Árvore de Merkle é uma prova criptográfica que demonstra que um dado pertence a um conjunto maior representado por uma raiz de Merkle.

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.

Como uma prova de Merkle verifica os dados?

O verificador processa a folha em questão junto com os hashes irmãos da prova e confere se o resultado final corresponde à raiz de Merkle confiável.

Por que as blockchains usam provas de Árvore de Merkle?

As blockchains usam provas de Árvore de Merkle para verificar dados com eficiência, sem exigir que cada usuário ou aplicativo baixe o conjunto de dados completo.

Como as provas de Merkle são usadas em airdrops?

Os contratos de airdrop podem armazenar uma única raiz de Merkle e permitir que os usuários enviem provas de que suas carteiras e os valores de suas reivindicações estão incluídos no conjunto de dados elegível.

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

Projetos de NFT podem usar provas de Merkle para verificar se uma carteira está em uma whitelist sem armazenar cada endereço aprovado diretamente on-chain.

As provas de Árvore de Merkle são privadas?

Elas oferecem privacidade parcial porque não é necessário revelar o conjunto de dados inteiro, mas a folha em questão e os dados da prova ainda podem ficar visíveis.

Uma prova de Árvore de Merkle pode ser falsa?

Uma prova falsa falhará se o verificador usar as regras corretas de hash e compará-la com a raiz confiável correta.

O que os usuários devem verificar antes de usar uma página de reivindicação com prova de Merkle?

Os usuários devem conferir o contrato oficial, o site oficial, a raiz de Merkle confiável, a solicitação da carteira, as regras de reivindicação e se a página é segura.

Conclusão

Uma prova de Árvore de Merkle é uma das ferramentas de verificação mais importantes do universo cripto.

Ela permite que usuários, carteiras, contratos inteligentes e aplicativos provem que um item pertence a um conjunto de dados maior, sem baixar nem armazenar o conjunto completo.

Isso torna os sistemas blockchain mais eficientes, escaláveis e práticos.

As provas de Árvore de Merkle são usadas para verificar inclusão de transações, light clients, airdrops, whitelists de NFT, estado de contas, provas de armazenamento, bridges e sistemas de rollup.

A ideia central é simples: uma raiz de Merkle confiável representa o conjunto de dados, e uma prova reconstrói o caminho de uma folha até essa raiz.

Se a raiz calculada corresponder à original, os dados estão incluídos.

Se não corresponder, a prova falha.

As provas de Árvore de Merkle reduzem a necessidade de confiar nos provedores de dados, mas não eliminam todos os riscos.

Usuários e desenvolvedores ainda precisam de regras corretas de hash, contratos inteligentes seguros, raízes confiáveis, geração cuidadosa de provas e proteção contra phishing.

Quando bem projetadas, as provas de Árvore de Merkle tornam os sistemas cripto mais leves, baratos e fáceis de verificar.