O que é uma Árvore de Merkle e qual é seu papel na Blockchain?

Árvores de Merkle são usadas em aplicações de ciência da computação como uma estrutura de dados para verificação e sincronização de dados. Árvores de Merkle também são usadas para criptografar dados de blockchain de forma mais segura e eficiente em Bitcoin e outras criptomoedas. 

Com criptomoedas, um banco de dados de árvore de Merkle é usado para dividir com segurança os dados do bloco e garantir que não sejam perdidos, danificados ou alterados. Este método de gestão de dados torna possível validar transações específicas sem baixar todo o blockchain, que tem tamanho de terabytes. É um método confiável, seguro e criptográfico de executar o blockchain.

Como resultado da queda do gigante da Exchange Centralizada (CEX), FTX, muitas CEXs construíram e implementaram a Árvore de Merkle como uma forma de Prova de Reservas (PoR) para assegurar aos usuários que seus fundos estão seguros. Neste artigo, discutiremos o que são as Árvores de Merkle, seu papel no blockchain e como um usuário pode validar seus fundos usando a Árvore de Merkle.

Quem é o fundador da Árvore de Merkle?

Ralph Merkle, um cientista da computação renomado por seu trabalho em criptografia de chave pública, propôs as árvores de Merkle no artigo de 1987 "A Digital Signature Based on a Conventional Encryption Function". A hash criptográfica também foi inventada por Merkle.

O que é uma Árvore de Merkle?

A árvore de Merkle é uma estrutura de dados matemáticos baseada em hash que compila os resumos de todas as transações em um bloco. É um método para verificar rapidamente a precisão dos dados de maneira descentralizada. Como resultado de suas funcionalidades, as árvores de Merkle são utilizadas de forma mais eficaz e segura para criptografar dados de blockchain. 

As árvores de Merkle são frequentemente usadas com redes peer-to-peer (P2P) devido à necessidade de ter informações compartilhadas e validadas de forma independente. Vamos entender mais sobre árvores de Merkle e como elas funcionam.

Estrutura da Árvore de Merkle

A árvore de Merkle, também conhecida como árvore de hash, tem uma estrutura de árvore binária, com os hashes dos dados transacionais na linha inferior sendo chamados de "Nós Folha", os hashes intermediários sendo chamados de "Nós Não-Folha", e o hash no topo sendo chamado de "Raiz". Embora a maioria das implementações de árvore de hash sejam binárias (cada nó tem dois nós filhos), elas também podem ter muito mais nós filhos.

Ao olhar para a estrutura de uma árvore de Merkle, todas as transações são agrupadas em pares. Cada par tem um hash calculado que é armazenado diretamente no nó pai. Esses nós também são agrupados em pares, após o que seu hash é armazenado no nível seguinte. Este processo continua até atingir a raiz da árvore de Merkle.

Vamos dar uma olhada em cada um dos nós:

Nós Folha

Estes são os hashes de cada transação de criptomoeda em um bloco, também conhecidos como IDs de transação (TXIDs). Você visualiza o hash da transação quando procura por uma transação em um explorador de blocos.

Nós Não-Folha

Então, para criar uma camada de nós não-folha acima dos nós folha, esses nós folha são combinados em pares e seus hashes calculados. Eles são conhecidos como nós não-folha porque, ao contrário dos nós folha, eles simplesmente armazenam o hash dos dois nós folha que representam e não contêm IDs de transação (ou hashes). Como resultado, haverá metade dos hashes (ou nós) na camada de nós não-folha acima dos nós folha, em comparação à camada de nós folha. À medida que a árvore se estreita conforme sobe, essas camadas de nós não-folha continuam a ser combinadas em pares, resultando em metade dos nós por camada. Dois nós estarão presentes na camada final de nós não-folha. Isso cria a raiz de Merkle e é o local da última combinação de hashes em uma árvore de Merkle.

Raiz de Merkle

Com o Bitcoin, os hashes de todas as transações são combinados em um único hash e armazenados no cabeçalho do bloco. A raiz de Merkle, também conhecida como hash raiz, é este hash específico. Os nós folha (IDs/hashes de transação) na base da árvore de Merkle podem ser verificados usando esta raiz de Merkle. Quando usada para criptomoedas, a raiz de Merkle garante que os blocos de dados estejam inalterados, intactos e completos.

Uma árvore de Merkle é binária, o que significa que o número total de diferentes nós folha deve ser par para que a árvore seja corretamente construída. Quando existe um número ímpar de nós folha, o hash anterior será duplicado para fornecer um número par de nós.

Como Funciona uma Árvore de Merkle?

Uma árvore de Merkle é essencialmente projetada para dividir grandes pedaços de dados em pedaços consideravelmente menores, o que garante que todas as transações possam ser verificadas prontamente. A árvore resume cada transação criando uma pequena impressão digital de um conjunto específico de transações, o que facilita para os usuários verificarem a disponibilidade das transações em um bloco. 

As árvores de Merkle são formadas pela hash de diferentes pares de nós até que apenas uma hash permaneça, que é referida como a raiz de Merkle. Essas árvores são construídas de baixo para cima, com cada transação consistindo de hashes. Cada nó folha é uma única hash de dados. Quanto aos nós não-folha, estes são hashes de hashes anteriores.

Vamos supor que uma árvore de Merkle consista em quatro transações que são rotuladas como D0, D1, D2 e D3. Cada transação é hasheada antes da hash ser armazenada diretamente no nó folha. Quando isso ocorre, as hashes N0, N1, N2 e N3 são criadas. Qualquer par consecutivo de nós folha será então resumido em um nó pai através da hash da hash N0 e da hash N1, resultando na hash N4. Se a hash N2 e a hash N3 são hasheadas juntas, a hash N5 é criada. Ambas essas hashes, N4 e N5, são hasheadas mais uma vez para criar a raiz de Merkle.

Este processo pode ser usado com conjuntos de dados extensos. A raiz de Merkle é responsável por resumir os dados presentes em transações específicas, todas armazenadas diretamente no cabeçalho do bloco. Esta técnica resulta na integridade dos dados sendo devidamente mantida. No caso de algum detalhe dentro da transação ser alterado em algum momento, a raiz de Merkle mudará automaticamente junto com ele.

Benefícios de uma Árvore de Merkle

Há muitos benefícios para a tecnologia blockchain e plataformas de criptomoedas ao usar uma árvore de Merkle para verificar transações, o que inclui desde verificação eficiente até fácil detecção de adulteração.

Processo Eficiente de Verificação de Dados

É fácil garantir a integridade da transação em praticamente nenhum tempo. Devido à forma como os dados são estruturados, muito pouca memória precisa ser usada durante o processo de verificação e o poder computacional necessário é significativamente reduzido. 

Como os blockchains geralmente consistem em centenas de milhares de blocos, cada um dos quais pode conter até vários milhares de transações, validar os dados apresenta dois grandes desafios: espaço de memória e poder computacional. Cada nó na rede teria sido obrigado a manter uma cópia completa de cada transação que já ocorreu no blockchain se as árvores de Merkle não fossem um conceito no blockchain. Um nó teria que comparar cada entrada linha por linha ao verificar uma transação para garantir que seus registros correspondem exatamente aos registros da rede. A segurança da rede poderia ser comprometida se houvesse qualquer discrepância entre os registros. Como resultado, para comparar os registros e garantir que não houve alterações, o computador usado para validar os dados precisaria de muito mais poder de processamento. 

As árvores de Merkle, por outro lado, oferecem uma solução para esse problema ao reduzir drasticamente a quantidade de dados que devem ser mantidos à mão para necessidades de verificação. Elas fazem hash de cada entrada no livro-razão, separando efetivamente os dados em si das provas que os sustentam. Sem saber cada TXID em um bloco, você pode verificar um TXID usando a raiz de Merkle com uma árvore de Merkle. Uma árvore de Merkle é essencialmente uma ótima maneira de demonstrar que algo está presente em um conjunto de dados sem precisar baixar o conjunto inteiro. Consequentemente, menos poder computacional é necessário para validar as transações.

Velocidade de Processamento Mais Rápida

Como resultado da distribuição das transações no bloco entre os validadores, cada validador está trabalhando em uma transação diferente ao mesmo tempo. Comparado a um método onde cada transação é validada sequencialmente após outra, isso é muito mais eficaz.

Uso de Carteira Cripto

A Verificação de Pagamento Simples (SPV), que permite confirmar uma transação sem baixar um bloco ou blockchain inteiro, é possibilitada pela árvore de Merkle. Isso permite o uso de um nó leve, mais formalmente conhecido como carteira cripto, para enviar e receber transações.

Detecção de Qualquer Manipulação

A estrutura de hash facilita para os mineradores identificar se houve manipulação nas transações. 

Um valor hash distinto é gerado para cada bloco usando a raiz de Merkle. O bloco liga um bloco ao outro na blockchain ao incluir o hash do bloco anterior. O hash de qualquer transação muda sempre que essa transação é modificada. O bloco torna-se inválido como resultado dessa mudança porque ela se propaga até a Raiz de Merkle e altera seu valor. Isso então causa uma mudança no hash do bloco seguinte, tornando o restante da Blockchain inválido. Como resultado, a árvore de Merkle cria um registro imutável das transações do bloco.

A dupla utilização também pode ser evitada como resultado. Se um indivíduo tentar gastar duas vezes sua moeda digital, um hash será gerado para essa transação. Se esse hash corresponder aos registros existentes presentes na Blockchain, essa transação é rejeitada.

Por que as Árvores de Merkle são Importantes em Blockchains?

As árvores de Merkle têm se mostrado essenciais para a tecnologia blockchain porque facilitam a verificação rápida e fácil de uma maneira que não é possível com outras técnicas. Essas árvores de Merkle fornecem aos desenvolvedores a capacidade de comprimir conjuntos de dados extremamente grandes, eliminando todos os dados desnecessários e transformando os dados que permanecem em hashes. As várias características fornecidas pelas árvores de Merkle incluem:

• Estrutura muito leve
• Escalabilidade eficaz
• Eficiência de combustível
• Verificação de que transações estão incluídas em um bloco específico
• Autenticação básica de pagamento

Prova de Reservas (PoR) da Árvore de Merkle

Como mencionado no início, após a queda da FTX, os usuários têm estado preocupados se seus fundos estão realmente seguros nas CEXs. Como resultado, várias CEXs se apresentaram para desenvolver um mecanismo de prova de reserva de árvore de Merkle. Nesta seção, vamos analisar as provas de Merkle e como nossos usuários podem validar seus fundos.

Provas de Merkle

Uma prova de árvore de Merkle é um recorte de uma árvore de Merkle, não a árvore real. E pode ser representada como uma matriz ou sequência (mostrada pela parte laranja no diagrama abaixo).

Todos os nós folha e as informações de saldo para um usuário específico da nossa empresa são representados pelos nós do último nível da figura. Assumindo que as pessoas em rosa na figura representam os destinatários pretendidos das provas, extraímos as partes laranja da figura nível por nível e apresentamos os documentos de prova aos usuários na ordem de altura. É significativo lembrar que a prova de Merkle tem dois componentes principais

1. Os nós pais diretos (i.e., B e D) deste usuário não são extraídos.
2. Fornecer o nó raiz, ou seja, a raiz de Merkle.

Tomando como exemplo um volume de 10 milhões de usuários, a altura da árvore pode ser calculada como Log2(10.000.000) = 23,2534966642 com base na fórmula matemática, que dá à árvore uma altura de 24 níveis. Portanto, os nós no gráfico que não são intencionalmente fornecidos aos usuários serão 24 - 2 = 22.

A árvore de Merkle é uma árvore binária completa, que nos permite calcular todas as informações sobre seu nó pai simplesmente conhecendo os nós esquerdo e direito. Duas partes compõem esta informação completa: os dados de saldo e os dados de hash.

1. Dados de Saldo: Os dados do nó pai podem e só podem ser divididos para seus nós inferiores à esquerda e à direita.
2. Dados de Hash: Apenas dados de saldo, dados de hierarquia de árvore, e dados de hash dos nós filhos estarão presentes para cada nó (cada nó mantém dados resumidos dos nós à esquerda e à direita abaixo dele).

A validação da Merkle tree é calculada derivando o B e D e verificando que

1. o saldo está em conformidade com o princípio de divisão; e
2. o hash é legal.

Ao utilizar uma função de resumo de hash, a Merkle tree permite que os usuários determinem se eles fazem parte de toda a árvore sem precisar estar cientes de cada nó púrpura no gráfico. A prova Merkle é exclusiva para esse usuário. Por exemplo, uma Merkle tree de 24 níveis requer um array de 23 elementos para verificar a informação de saldo do usuário, e este array só pode confirmar que a prova de saldo do usuário é precisa.

O usuário não pode reconstruir toda a árvore com base em sua informação fragmentada enquanto não obtiver mais da metade do número total de usuários. Como resultado, a Merkle tree protege tanto a privacidade do usuário quanto a capacidade da empresa de prevenir o vazamento de informações sobre os ativos gerais da empresa.

Validando Sua Conta Bybit

Existem 2 métodos disponíveis para você validar sua conta Bybit e verificar a validade dos fundos.

Ferramenta de Validação da Plataforma

Este método é o primeiro e único em toda a rede, e mostrará o processo de derivação de nó da validação da Árvore de Merkle de maneira gráfica e intuitiva na plataforma da empresa.

Ferramenta de Auto Validação

O código-fonte de geração da árvore de Merkle da empresa e o código de validação estão abertamente disponíveis no github para auxiliar os usuários a programarem sua própria validação. O processo de cálculo da árvore de Merkle envolve uma grande quantidade de cálculos de usuário, que são geralmente implementados por big data e Java. 

*Um código Java aberto significa que está disponível para os usuários sem reter qualquer informação.

A Bybit disponibilizou o seguinte código em código aberto para que usuários profissionais validem seu próprio arquivo de prova da Árvore de Merkle, copiando-o da página de prova de reservas para sua própria versão "fixa" do sistema através do botão Copiar Dados e armazenando-o como um arquivo chamado myProof.json no disco local.

Aplicações de Árvores de Merkle no Blockchain

Estruturas de árvore de Merkle e raiz de Merkle já foram amplamente adotadas em muitas plataformas de blockchain e criptomoedas diferentes. A seguir, são detalhadas três dessas aplicações.

Bitcoin

Bitcoin usa árvores de Merkle de várias formas, o que torna essas árvores parte integrante de toda a plataforma Bitcoin. Na verdade, essas árvores estão presentes em todos os cabeçalhos de bloco do Bitcoin. O hash de cada transação disponível dentro do bloco é colocado no cabeçalho. Quando se trata de Bitcoin, a raiz de Merkle é importante tanto para a mineração quanto para a verificação.

Mineração

Os blocos de Bitcoin consistem em cabeçalhos que contêm metadados, assim como uma extensa lista de transações. Esta lista é geralmente maior do que o cabeçalho do bloco. Os mineradores fazem hash dos dados para criar uma saída que adere a condições específicas, o que é necessário ao validar um bloco. Os mineradores podem fazer trilhões de tentativas separadas antes de encontrarem um bloco válido. Cada tentativa requer que um número no cabeçalho do bloco seja alterado. Mesmo que milhares de transações separadas possam existir em um bloco, cada uma deve ser hasheada.

As raízes de Merkle permitem que os mineradores tornem este processo muito mais eficiente. Quando o processo de mineração começa, tudo o que é necessário é que as transações sejam transformadas em uma árvore de Merkle, após o qual o hash da raiz pode ser colocado dentro do cabeçalho do bloco. Neste ponto, o minerador só precisa fazer hash do cabeçalho do bloco, em vez do bloco inteiro.

Verificação

Outro aspecto da raiz de Merkle usada com o Bitcoin envolve a alavancagem, que se concentra em clientes leves. Quando um nó está sendo operado em um dispositivo relativamente fraco que tem recursos limitados, os usuários não poderão baixar e hashear todas as transações em um único bloco. Em vez disso, pode ser solicitado um comprovante de Merkle, que é a confirmação de que uma transação está presente em um bloco. Ao reduzir o número de hashes que precisam ser realizados durante o processo de verificação, a verificação pode ocorrer sem usar tantos recursos computacionais.

Ethereum

Ethereum é baseado em uma versão ligeiramente modificada da árvore de Merkle, por isso é referida como a árvore de Merkle Patricia. Cada bloco dentro da blockchain Ethereum consiste em três árvores de Merkle, em vez de uma árvore binária — o que acontece nos blocos de Bitcoin. Cada uma das três raízes tem seu próprio propósito.

A raiz inicial é considerada a raiz de cada transação. Quanto à segunda raiz, ela mostra o estado da transação. A raiz final é o recibo da transação. Um usuário pode olhar para uma raiz de Merkle para determinar se uma transação é encontrada em um bloco específico, assim como determinar qual é o saldo de sua conta.

Hyperledger Fabric

Ao olhar especificamente para Hyperledger Fabric, esta plataforma blockchain usa uma árvore de Merkle para computar dados de bloco como um hash. O valor do hash identifica a largura da árvore de Merkle. As árvores de Merkle na plataforma Hyperledger Fabric funcionam da mesma forma que as da plataforma Bitcoin.

Conclusão

As árvores de Merkle provaram ser extremamente úteis para plataformas de criptomoeda que querem garantir que seu processo de verificação de transação seja o mais fácil e eficiente possível. Sem essa estrutura em vigor, a verificação seria um processo demorado porque os dados precisariam ser transferidos por toda a rede para verificação. As plataformas que usam árvores de Merkle beneficiam de menos requisitos de largura de banda e potência computacional.