paint-brush
Uma introdução à árvore Merkel: o que é e como funciona?por@0xkishan
1,068 leituras
1,068 leituras

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

por Kishan Kumar5m2023/07/03
Read on Terminal Reader

Muito longo; Para ler

Uma Merkle Tree é uma árvore binária de valores de hash, onde cada nó folha representa um único dado. Ele é usado para verificar a integridade de grandes quantidades de dados de forma eficiente. Uma função hash é como uma máquina de impressão digital. Ele pega qualquer entrada e produz uma saída única, chamada de hash, que é muito mais curta que a entrada.
featured image - Uma introdução à árvore Merkel: o que é e como funciona?
Kishan Kumar HackerNoon profile picture
0-item
1-item
2-item

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 .

Ilustração da Árvore Merkle por Kishan Kumar

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.