Uma introdução à árvore Merkel: o que é e como funciona?

Uma Merkle Tree é uma árvore binária de valores de hash, onde cada nó folha representa um único pedaço de dados ou um hash de um pedaço de dados. Ele é usado para verificar a integridade de grandes quantidades de dados de forma eficiente. Foi inventado por Ralph Merkle em 1979 e é amplamente utilizado em criptomoedas como Bitcoin e Ethereum.

Uma função hash é como uma máquina de impressão digital. Ele pega qualquer entrada, como um arquivo, um texto ou um número, e produz uma saída única, chamada de hash, que é muito mais curta que a entrada. O hash é como uma impressão digital da entrada. É difícil encontrar duas entradas diferentes que tenham o mesmo hash. E é impossível obter a entrada original do hash.

Por exemplo, se você tiver um arquivo chamado " kishan.jpg " com 1 MB de tamanho, poderá usar uma função hash para obter um hash com apenas 64 caracteres, como 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F .

Se você alterar até mesmo um pixel no arquivo, o hash será completamente diferente, como C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF .

Então você pode usar o hash para verificar se o arquivo é o mesmo de antes.

Mas e se você tiver muitos arquivos? Calcular e armazenar o hash para cada arquivo separadamente seria tedioso. É aí que as árvores Merkle são úteis.

Uma árvore Merkle é como uma árvore genealógica de hashes. Você começa com os hashes de cada arquivo como as folhas da árvore . Então você emparelha os hashes e os combina para obter novos hashes. Você repete esse processo até chegar ao topo da árvore, onde resta apenas um hash. Esse hash é chamado de raiz Merkle .

A raiz Merkle é como uma impressão digital de todos os arquivos na árvore. Se algum arquivo for alterado, seu hash será alterado, assim como todos os hashes acima dele até que a raiz do Merkle seja alterada . Portanto, você pode usar a raiz do Merkle para verificar se todos os arquivos são os mesmos de antes.

Mas como você verifica um arquivo específico? Você não precisa baixar e verificar todos os arquivos na árvore. Você só precisa baixar e verificar alguns hashes ao longo do caminho do arquivo para a raiz do Merkle. Este caminho é chamado de prova de Merkle .

Por exemplo, suponha que você queira verificar se o arquivo "cat.jpg" está correto. Você só precisa baixar seu hash HA que é 0a6df4 , o hash de seu irmão HB (ea12e7) , o hash H CD (b582ae) e a raiz Merkle H ABCD (7bd24f) .

Então você pode calcular H AB combinando HA e HB e calcular H ABCD combinando H AB e H CD . Se H ABCD corresponder à raiz Merkle, você pode ter certeza de que " cat.jpg " está correto.

Você pode usar a mesma analogia para verificar se a transação presente no bloco é moderada, verificando a raiz Merkle em vez de cat.jpg ou dog.txt. Haverá um monte de transações nos nós de folha.

Observação: trunquei o valor do hash para 6 caracteres no exemplo acima para fazer o diagrama parecer limpo.

E se eu tiver apenas três nós de folha? Como vou criar uma Merkle Tree?

Esse cenário pode ser resolvido rapidamente duplicando um nó, tornando o número total de nós quatro.

Por exemplo, suponha que você tenha transações. TA , TB e TC . Você pode calcular seus hashes. HA , HB e HC . Então você pode duplicar HC para obter H C' . Depois; você pode emparelhar e combinar os hashes para obter H AB , H CC' e H ABCC' . A raiz Merkle é H ABCC' .

Resumindo, as árvores Merkle beneficiam o blockchain e outros sistemas distribuídos, onde muitos computadores devem compartilhar e verificar grandes quantidades de dados. Ao usar árvores Merkle, eles podem economizar largura de banda, armazenamento e tempo de computação.

Aqui está um exemplo Java rápido para mostrar como você pode criar sua própria árvore Merkle:

 import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; class MerkleTree{ static class Node { String content; public Node(String content) { this.content = content; } public String getHash() throws NoSuchAlgorithmException { MessageDigest md = MessageDigest.getInstance("SHA-256"); byte[] hash = md.digest(content.getBytes(StandardCharsets.UTF_8)); StringBuilder buffer = new StringBuilder(); for (byte b : hash) { buffer.append(String.format("%02x", b)); } return buffer.toString(); } } public static void main(String[] args) throws NoSuchAlgorithmException{ Node cat = new Node("I am a cat, this is a cat file called cat.jpg"); Node dog = new Node("I am a dog, this is a dog file called dog.txt"); // we have two leaf nodes, in order to create a merkle root, // we simple need to get their individual hashes // and then combine those hashes and hash them again String HA = cat.getHash(); String HB = dog.getHash(); Node merkleRoot = new Node(HA + HB); String HAB = merkleRoot.getHash(); System.out.println("Merkle Root: " + merkleRoot.getHash()); // let's say we altered the cat file cat = new Node("I am a cat, this is a cat file called dog.jpg"); // notice we have changed the cat.jpg to dog.jpg String HA_MODIFIED = cat.getHash(); Node modifiedMerkleRoot = new Node(HA_MODIFIED + HB); String HAB_MODIFIED = modifiedMerkleRoot.getHash(); System.out.println("Merkle Root: " + HAB_MODIFIED); } }

Saída:

 Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e

Agradeço por ter tempo para ler o meu artigo. Apoie-me seguindo-me no Hackernoon para ser notificado sempre que eu publicar um artigo.

Muito obrigado.

Mergulhe em artigos perspicazes sobre sistemas descentralizados, tecnologia e tendências de IA: https://www.0xkishan.com . Faça uma visita para mostrar seu apoio.

Também publicado aqui.