Une introduction à l'arbre de Merkel : qu'est-ce que c'est et comment ça marche ?

Un arbre de Merkle est un arbre binaire de valeurs de hachage, où chaque nœud feuille représente un seul élément de données ou un hachage d'un élément de données. Il est utilisé pour vérifier efficacement l'intégrité de grandes quantités de données. Il a été inventé par Ralph Merkle en 1979 et est largement utilisé dans les crypto-monnaies comme Bitcoin et Ethereum.

Une fonction de hachage est comme une machine à empreintes digitales. Il prend n'importe quelle entrée, telle qu'un fichier, un texte ou un nombre, et produit une sortie unique, appelée hachage, qui est beaucoup plus courte que l'entrée. Le hachage est comme une empreinte digitale de l'entrée. Il est difficile de trouver deux entrées différentes qui ont le même hachage. Et il est impossible d'obtenir l'entrée d'origine du hachage.

Par exemple, si vous avez un fichier appelé " kishan.jpg " d'une taille de 1 Mo, vous pouvez utiliser une fonction de hachage pour obtenir un hachage de seulement 64 caractères, tel que 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F .

Si vous modifiez même un pixel dans le fichier, le hachage sera complètement différent, tel que C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF .

Vous pouvez donc utiliser le hachage pour vérifier que le fichier est le même qu'avant.

Mais que se passe-t-il si vous avez de nombreux fichiers ? Le calcul et le stockage du hachage pour chaque fichier séparément seraient fastidieux. C'est là que les arbres Merkle sont utiles.

Un arbre Merkle est comme un arbre généalogique de hachages. Vous commencez avec les hachages de chaque fichier comme les feuilles de l'arbre . Ensuite, vous associez les hachages et les combinez pour obtenir de nouveaux hachages. Vous répétez ce processus jusqu'à ce que vous atteigniez le sommet de l'arbre, où il ne vous reste qu'un seul hachage. Ce hachage s'appelle la racine de Merkle .

La racine Merkle est comme une empreinte digitale de tous les fichiers de l'arborescence. Si un fichier change, son hachage changera, ainsi que tous les hachages au-dessus jusqu'à ce que la racine Merkle change . Vous pouvez donc utiliser la racine Merkle pour vérifier que tous les fichiers sont les mêmes qu'avant.

Mais comment vérifier un fichier spécifique ? Vous n'avez pas besoin de télécharger et de vérifier tous les fichiers de l'arborescence. Il vous suffit de télécharger et de vérifier quelques hachages le long du chemin du fichier à la racine Merkle. Ce chemin s'appelle une preuve de Merkle .

Par exemple, supposons que vous vouliez vérifier si le fichier "cat.jpg" est correct. Il vous suffit de télécharger son hachage HA qui est 0a6df4 , le hachage HB (ea12e7) , le hachage H CD (b582ae) et la racine Merkle H ABCD (7bd24f) .

Ensuite, vous pouvez calculer H AB en combinant HA et HB et calculer H ABCD en combinant H AB et H CD . Si H ABCD correspond à la racine Merkle, vous pouvez être sûr que " cat.jpg " est correct.

Vous pouvez utiliser la même analogie pour vérifier si la transaction présente dans le bloc est tempérée en vérifiant la racine Merkle au lieu de cat.jpg ou dog.txt. Ce sera un tas de transactions aux nœuds feuilles.

Remarque : j'ai tronqué la valeur de hachage à 6 caractères dans l'exemple ci-dessus pour que le diagramme ait l'air propre.

Que se passe-t-il si je n'ai que trois nœuds feuilles ? Comment vais-je créer un arbre Merkle ?

Ce scénario peut être rapidement résolu en dupliquant un nœud, ce qui porte le nombre total de nœuds à quatre.

Par exemple, supposons que vous ayez des transactions. TA , TB et TC . Vous pouvez calculer leurs hachages. HA , HB et HC . Ensuite, vous pouvez dupliquer HC pour obtenir H C' . Après; vous pouvez associer et combiner les hachages pour obtenir H AB , H CC' et H ABCC' . La racine de Merkle est H ABCC' .

En résumé, les arbres de Merkle profitent à la blockchain et à d'autres systèmes distribués, où de nombreux ordinateurs doivent partager et vérifier de grandes quantités de données. En utilisant les arbres Merkle, ils peuvent économiser de la bande passante, du stockage et du temps de calcul.

Voici un exemple Java rapide pour montrer comment vous pouvez créer votre propre arbre 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); } }

Sortir:

 Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e

Je vous remercie d'avoir pris le temps de lire mon article. Soutenez-moi en me suivant sur Hackernoon afin d'être averti chaque fois que je publie un article.

Merci beaucoup.

Plongez dans des articles perspicaces sur les tendances des systèmes décentralisés, de la technologie et de l'IA : https://www.0xkishan.com . Visitez pour montrer votre soutien.

Également publié ici.