O que é uma árvore Merkle

De Área31 Hackerspace

As árvores Merkle são uma estrutura de dados criada com o objetivo de facilitar a verificação de grandes quantidades de dados organizados, relacionando-os usando várias técnicas de gerenciamento de informações e criptografia.

Eu entro qualquer bloque da rede Bitcoin, encontramos uma estrutura chamada "Árvore Merkle".

Uma árvore Merkle é uma estrutura de dados dividida em várias camadas cujo objetivo é relacionar cada nó com uma única raiz associada a eles. Para conseguir isso, cada nó deve ser identificado com um identificador exclusivo (de hash) Esses nós iniciais, chamados nós filhos (folhas), são então associados a um nó pai (ramo) não superior. O nó pai terá um identificador exclusivo resultante do hash de seus nós filhos. Essa estrutura é repetida até que o nó raiz ou raiz Merkle (raiz Merkle), cuja impressão está associada a todos os nós da árvore.

Graças a esta estrutura única, as árvores Merkle possibilitam relacionar uma grande quantidade de dados em um único ponto (Raiz Merkle). Desta forma, a verificação e validação desses dados podem se tornar muito eficientes, tendo que verificar apenas a Raiz Merkle em vez de toda a estrutura.

Este design foi criado por Ralph Merkle, em 1979, a fim de otimizar o processo de verificação de grandes quantidades de dados.

Como funciona uma árvore Merkle? Uma árvore Merkle é uma estrutura que relaciona todas as transações e as agrupa entre pares para obter um Hash de raiz o "endereço raiz ". Esse hash raiz está relacionado a todos os hashes da árvore. Verificar todos relações de uma rede seria extremamente lento e ineficiente. Por este motivo, este sistema foi implementado. Uma vez que, se um hash for alterado, todos os outros serão alterados até chegar à raiz (hash raiz). Isso invalidará a autenticidade das informações para toda a árvore. É precisamente esta função que permite às árvores Merkels fornecer o alto nível de segurança que as caracteriza.

Para entender como uma árvore Merkle funciona com mais detalhes, examine o seguinte exemplo:

Imagine um bloco de dados com uma impressão ou hash único e irrepetível. Cada um desses blocos está organizado em camadas no que veríamos como uma estrutura de pirâmide. Esses blocos são vinculados a uma camada superior por meio desses hashes. Dessa forma, os blocos superiores sempre apontam para os blocos inferiores, mas, mais importante, o hash desses blocos superiores é o resultado da soma das informações contidas no novo bloco com o hash do bloco anterior. Dessa forma, à medida que você continua a escalar, a mesma estrutura se repete, pois todos os blocos estão conectados a um grande bloco de dados.

O fato de funcionar desta forma faz com que se altere o hash de um bloco, invalidando os hashes dos demais blocos. Desta forma, o sistema facilita duas coisas. Primeiro, torna mais fácil verificar os blocos de dados. Em segundo lugar, ele serve como um mecanismo para evitar adulteração. Isso se deve ao fato de que este mecanismo permite detectar mudanças de hashes em cada bloco de dados. Se uma alteração for detectada, toda a árvore será invalidada, pois foi alterada e seus dados não são válidos.

Características das árvores Merkle Algumas das características mais marcantes das árvores Merkle são:

Eles são um meio eficiente de gerar uma estrutura de dados distribuídos. Eles oferecem grande segurança e resistência a alterações de dados. Eles permitem um alto nível de desempenho na transmissão de dados em redes distribuídas. Graças a isso, eles reduzem a quantidade de dados necessários para o correto funcionamento. Eles são computacionalmente baratos e eficientes na criação, processamento e verificação de informações. Eles permitem que a "dissecção" torne as verificações mais rápidas. Tudo isso, sem comprometer a segurança e a rastreabilidade das transações realizadas. Graças ao recurso "dissecação", eles também podem economizar recursos de armazenamento. Eles oferecem grande adaptabilidade a diferentes problemas de computador. Graças a isso, as árvores Merkle têm sido amplamente utilizadas em diferentes sistemas. Por exemplo, softwares de banco de dados, sistemas de arquivos, estruturas de chave pública, sistemas de versionamento, redes distribuídas (P2P), entre outros.

Usa hoje Árvores Merkle têm um grande número de usos em sistemas de computador hoje, e vamos falar sobre alguns deles aqui.

Tecnologia Blockchain O uso de árvores Merkle na tecnologia blockchain É vital. Graças ao seu uso, o software cliente pode baixar todo o histórico do blockchain e verificá-lo a quente. Na verdade, seu uso facilita o processo ao permitir “ameixa seca”(Pegue apenas parte do histórico) o histórico e reduza o tamanho do download.

Por exemplo, um usuário que deseja instalar um cliente Bitcoin não precisa baixar todo o histórico do blockchain. Em vez disso, você pode reduzir seu download para apenas algumas centenas ou milhares de blocos atrás. Dessa forma, você tem acesso a uma versão mais clara do histórico que melhor atende aos seus requisitos.

Ao contrário do que você possa pensar, isso não prejudica a segurança do cliente. Bem, graças à árvore Merkle, é possível baixar um "hash raiz" específico e a partir daí começar a criar um histórico. Uma vez que esse "hash raiz" está relacionado aos blocos anteriores, tudo o que você precisa fazer é verificá-lo. Para fazer isso, você pode ir a uma série de nós Bitcoin completos (com todo o histórico) e verificar se o "hash raiz" corresponde. Tendo consenso absoluto neste ponto, o "hash raiz" é dado como válido. E a partir desse ponto, o usuário pode usar perfeitamente seu novo nó de cliente Bitcoin.

Sistemas de arquivos Outro utilitário que podemos ver nas árvores Merkle se reflete nos sistemas de arquivos. Um sistema de arquivos é uma estrutura de dados que um sistema operacional usa para acompanhar os arquivos que ele armazena. Normalmente, essa estrutura é aplicada em um disco rígido e até dentro dos cartões de memória que nossos smartphones usam.

Algumas dessas criações peculiares fazem uso de árvores Merkle para gerenciar e garantir o uso correto dos dados armazenados. Casos especiais de menção neste grupo são os sistemas de arquivos ZFS y btrfs.

ZFS conhecido como Sistema de arquivos Zettabyte, é considerado no mundo dos computadores o melhor sistema de arquivamento. Suas habilidades excedem em muito seus oponentes mais conhecidos como NTFS, GORDO, exFAT o ext3 / 4. Possui resistência a falhas, recuperação e correção de erros, desduplicação de dados, replicação, cópia na gravação (CoW) e alta escalabilidade. Tudo isso faz com que seja uma opção perfeita para ser implantada em ambientes críticos. Desenhado por Sun Microsystems e introduzido em 2004, atualmente é o líder em sistemas de arquivos de computador.

Mas para conseguir isso, o ZFS tem uma ferramenta secreta no meio de todo o seu código: o uso extensivo e intensivo de árvores Merkle. Tudo isso para ter um sistema que permita a verificação rápida dos dados armazenados em suas estruturas. Suas propriedades de recuperação de erros, deduplicação, CoW (Copy-On-Write) e replicação dependem fortemente desta técnica, caso contrário, acarretaria um alto custo computacional que prejudicaria suas vantagens.

Sistemas de controle de versão Outro uso de árvores Merkle pode ser visto em sistemas de controle de versão de software, casos bem conhecidos de Git y mercurial. Dos dois, os mais conhecidos no Git, o mesmo que permite a operação de plataformas como Gitlab y Github, ou o desenvolvimento do kernel Linux, este foi o primeiro projeto a usá-lo na produção, já que o criador do Git é Linus Torvalds.

O uso de árvores Merkle neste tipo de software está relacionado ao sistema de controle de alterações dentro do repositório ou área de trabalho onde os arquivos são armazenados. Desta forma, cada alteração realizada (novos blocos de dados) passa por um processo de hashing que, ao percorrer todo o conteúdo do repositório, gera um hash único do referido espaço de trabalho, que se denomina commit.

Este sistema de marcação permite, por exemplo, ir a um commit específico para ver qual era o status do código do projeto em um determinado momento, enquanto o status geral do projeto permanece intacto. Vendo de uma forma mais simples, as árvores Merkle no Git nos permitem criar uma espécie de máquina do tempo, que nos permite navegar pelos diferentes commits do projeto, mantendo os arquivos e suas alterações como estavam naquele momento específico.

Um utilitário que é muito útil ao projetar software em ambientes de alto tráfego e trabalho distribuído, como Linus Torvalds não demonstrou em seu grande projeto de kernel Linux. [1]


Referências:

Cookies nos ajudam a entregar nossos serviços. Ao usar nossos serviços, você concorda com o uso de cookies.