Les Merkle Trees sont un composant fondamental des blockchains qui soutiennent leur fonctionnalité. Ils permettent une vérification efficace et sécurisée de grandes structures de données et, dans le cas des blockchains, d’ensembles de données potentiellement illimités.
La mise en œuvre des arbres Merkle dans les blockchains a de multiples effets. Il leur permet d'évoluer tout en leur fournissant une architecture basée sur le hachage leur permettant de maintenir l'intégrité des données et un moyen trivial de vérifier l'intégrité des données.
Les fonctions de hachage cryptographique sont la technologie sous-jacente qui permet aux arbres Merkle de fonctionner. Il est donc d'abord important de comprendre ce que sont les fonctions de hachage cryptographique.
Verdict rapide: Les arbres Merkle sont des structures de données composées de hachages cryptographiques qui permettent une vérification efficace de l'intégrité et un mappage de grands ensembles de données, ce qui en fait un composant intégral de systèmes tels que les blockchains et le contrôle de version distribué.
Faits saillants
| Points clés | Description |
|---|---|
| Fonctions de hachage cryptographique | Fonctions de hachage qui prennent une entrée de n'importe quelle taille et génèrent une valeur de hachage de longueur fixe. Utilisé dans les arbres Merkle. |
| Arborescence Merkle | Structure de données arborescente où chaque nœud non-feuille est un hachage de ses nœuds enfants. Permet une cartographie et une vérification efficaces de grands ensembles de données. |
| Hachage racine | Hachage au sommet de l'arbre Merkle qui représente le hachage de l'arbre entier. Agit comme une empreinte digitale pour l’ensemble des données. |
| Preuves Merkle | Autoriser la vérification de l'intégrité des données et de leur position dans l'arborescence sans avoir besoin de l'ensemble de données complet, uniquement du hachage racine. |
| Implémentation dans Bitcoin | Les arbres Merkle stockent les transactions dans des blocs. Le hachage racine stocké dans l'en-tête du bloc permet aux nœuds SPV de vérifier les transactions. |
| Autres implémentations de blockchain | Utilisé dans de nombreuses blockchains comme Ethereum qui utilise des arbres Merkle Patricia plus complexes. |
| Systèmes distribués | Permettez aux systèmes de contrôle de version tels que Git et IPFS de vérifier facilement les données partagées entre pairs. |
Fonctions de hachage cryptographique
En termes simples, une fonction de hachage est toute fonction utilisée pour mapper des données d'une taille arbitraire (entrée) à une sortie de taille fixe. Un algorithme de hachage est appliqué à l'entrée de données et la sortie de longueur fixe résultante est appelée hachage.
De nombreux algorithmes de hachage sont largement accessibles au public et peuvent être sélectionnés en fonction de vos besoins.
Le hachage résultant de l'entrée arbitraire n'est pas seulement de longueur fixe, il est également complètement unique à l'entrée et la fonction elle-même est déterministe. Autrement dit, peu importe le nombre de fois que vous exécutez la fonction sur la même entrée, la sortie sera toujours la même.
Par exemple, si vous disposez des ensembles de données suivants ci-dessous en entrée, les sorties résultantes sont uniques pour chaque entrée. Remarquez comment dans les deuxième et troisième exemples, même si la différence entre les entrées n'est que d'un seul mot, les sorties résultantes sont complètement différentes.
Ceci est très important car cela permet de « prendre des empreintes digitales » des données.
Une fonction de hachage cryptographique, Image de Wikipédia
Étant donné que la longueur de sortie (somme de hachage dans l'exemple) est toujours la même que celle déterminée par l'algorithme de hachage utilisé, d'énormes quantités de données peuvent être identifiées uniquement grâce à leur hachage résultant.
Avec des systèmes contenant d’énormes quantités de données, les avantages de pouvoir stocker et identifier des données avec une sortie de longueur fixe peuvent générer d’importantes économies de stockage et contribuer à accroître l’efficacité.
Au sein des blockchains, des algorithmes de hachage sont utilisés pour déterminer l’état de la blockchain.
Les blockchains sont des listes chaînées qui contiennent des données et un pointeur de hachage qui pointe vers le bloc précédent, créant une chaîne de blocs connectés, d'où le nom « blockchain ».
Chaque bloc est connecté les uns aux autres via un pointeur de hachage, qui est le hachage des données à l'intérieur du bloc précédent ainsi que l'adresse du bloc précédent. En reliant des blocs de données dans ce format, chaque hachage résultant du bloc précédent représente l'état complet de la blockchain puisque toutes les données hachées des blocs précédents sont hachées en un seul hachage.
Ceci est représenté (dans le cas de l'algorithme SHA-256) par une sortie (hachage) telle que celle-ci :
b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7
Le hachage ci-dessus est l’empreinte digitale de tout l’état de la blockchain qui la précède. L'état de la blockchain avant le nouveau bloc (sous forme de données hachées) est l'entrée et le hachage résultant est la sortie.
Bien qu’il soit possible d’utiliser des hachages cryptographiques sans arbres Merkle, cette méthode est extrêmement inefficace et non évolutive. Utiliser des hachages pour stocker des données dans un bloc sous un format de série prend du temps et est fastidieux.
Comme vous le verrez, les arbres Merkle permettent une résolution triviale de l'intégrité des données ainsi que le mappage de ces données dans l'ensemble de l'arborescence à l'aide de preuves Merkle.
Arbres Merkle et preuves Merkle
Nommés d'après Ralph Merkle, qui a breveté le concept en 1979, les arbres Merkle sont fondamentalement des arbres de structure de données dans lesquels chaque nœud non-feuille est un hachage de ses nœuds enfants respectifs.
Les nœuds feuilles constituent le niveau de nœuds le plus bas de l’arborescence. Au début, cela peut sembler difficile à comprendre, mais si vous regardez la figure couramment utilisée ci-dessous, cela deviendra beaucoup plus facile à comprendre.
Un exemple d'arbre de hachage binaire, image de Wikipédia
Il est important de noter que les nœuds non-feuilles ou « branches » (représentés par Hash 0-0 et Hash 0-1) sur le côté gauche sont des hachages de leurs enfants respectifs L1 et L2. De plus, remarquez comment la branche Hash 0 est le hachage de ses enfants concaténés, les branches Hash 0-0 et Hash 0-1.
L'exemple ci-dessus est la forme la plus courante et la plus simple d'un arbre Merkle connu sous le nom d'arbre Merkle binaire. Comme vous pouvez le voir, il existe un hachage supérieur qui est le hachage de l'arbre entier, appelé hachage racine. Essentiellement, les arbres Merkle sont une structure de données qui peut prendre « n » nombre de hachages et la représenter avec un seul hachage.
La structure de l'arborescence permet une cartographie efficace de quantités de données arbitrairement importantes et permet une identification facile de l'endroit où se produisent les modifications de ces données. Ce concept permet des preuves Merkle, avec lesquelles quelqu'un peut vérifier que le hachage des données est cohérent tout au long de l'arborescence et dans la bonne position sans avoir à examiner l'ensemble des hachages.
Au lieu de cela, ils peuvent vérifier qu'un bloc de données est cohérent avec le hachage racine en vérifiant uniquement un petit sous-ensemble de hachages plutôt que l'ensemble des données dans son intégralité.
Tant que le hachage racine est publiquement connu et fiable, il est possible pour toute personne souhaitant effectuer une recherche clé-valeur sur une base de données d'utiliser une preuve Merkle pour vérifier la position et l'intégrité d'une donnée dans une base de données qui a une racine particulière.
Lorsque le hachage racine est disponible, l'arborescence de hachage peut être reçue de n'importe quelle source non fiable et une branche de l'arborescence peut être téléchargée à la fois avec une vérification immédiate de l'intégrité des données, même si l'arborescence entière n'est pas encore disponible.
L'un des avantages les plus importants de la structure arborescente Merkle est la possibilité d'authentifier des ensembles de données arbitrairement volumineux via un mécanisme de hachage similaire à celui utilisé pour vérifier des quantités de données beaucoup plus petites.
L'arborescence est avantageuse pour distribuer de grands ensembles de données en parties plus petites gérables où la barrière pour la vérification de l'intégrité est considérablement réduite malgré la taille globale des données plus grande.
Le hachage racine peut être utilisé comme empreinte digitale pour un ensemble de données complet, y compris une base de données entière ou représentant l’état complet d’une blockchain. Dans les sections suivantes, nous verrons comment Bitcoin et d'autres systèmes implémentent les arbres Merkle.
Arbres Merkle dans Bitcoin
La fonction de hachage cryptographique utilisée par Bitcoin est l'algorithme SHA-256. Cela signifie « Secure Hashing Algorithm », dont la sortie a une longueur fixe de 256 bits. La fonction de base des arbres Merkle dans Bitcoin est de stocker et éventuellement d'élaguer les transactions dans chaque bloc.
Comme mentionné précédemment, les blocs d'une blockchain sont connectés via les hachages du bloc précédent. Dans Bitcoin, chaque bloc contient toutes les transactions au sein de ce bloc ainsi que l'en-tête du bloc qui se compose de :
- Numéro de version du bloc
- Hachage de bloc précédent
- Horodatage
- Cible de difficulté minière
- Nonce
- Hachage de racine de Merkle
L'image ci-dessous provient du livre blanc Bitcoin et illustre comment l'arbre Merkle s'intègre dans chaque bloc.
Les transactions sont incluses dans des blocs par les mineurs et sont hachées dans le cadre d'un arbre Merkle, menant à la racine Merkle stockée dans l'en-tête du bloc. Cette conception présente un certain nombre d’avantages distincts.
Plus particulièrement, comme indiqué dans le livre blanc, cela permet l'existence de nœuds SPV (Simple Payment Verification), également appelés « clients légers ». Ces nœuds n'ont pas besoin de télécharger l'intégralité de la blockchain Bitcoin, uniquement les en-têtes de bloc de la chaîne la plus longue.
Les nœuds SPV peuvent y parvenir en interrogeant leurs nœuds homologues jusqu'à ce qu'ils soient convaincus que les en-têtes de bloc stockés sur lesquels ils opèrent font partie de la chaîne la plus longue. Un nœud SPV est ensuite capable de déterminer l'état d'une transaction en utilisant la preuve Merkle pour mapper la transaction à un arbre Merkle spécifique avec le hachage racine de cet arbre Merkle respectif dans un en-tête de bloc qui fait partie de la chaîne la plus longue.
De plus, la mise en œuvre des arbres Merkle par Bitcoin permet d'élaguer la blockchain afin d'économiser de l'espace. Cela est dû au fait que seul le hachage racine est stocké dans l'en-tête du bloc. Par conséquent, les anciens blocs peuvent être élagués en supprimant les branches inutiles de l'arbre Merkle tout en préservant uniquement celles nécessaires à la preuve Merkle.
Implémentation d'arbres Merkle dans d'autres blockchains et systèmes
Bien que Bitcoin ait été la première blockchain à implémenter des arbres Merkle, de nombreuses autres blockchains implémentent des structures arborescentes Merkle similaires ou des versions encore plus complexes.
De plus, la mise en œuvre de l’arbre Merkle ne se limite pas aux blockchains et s’applique à divers autres systèmes.
Ethereum, étant l’autre crypto-monnaie la plus reconnaissable, est également un excellent exemple d’implémentation différente de l’arbre Merkle. Étant donné qu'Ethereum est une plate-forme complète pour créer des applications beaucoup plus complexes, il utilise une version plus complexe de l'arbre Merkle appelée Merkle Patricia Tree, qui est en fait 3 arbres Merkle distincts utilisés pour trois types d'objets. Vous pouvez en savoir plus sur ces arbres ici.
Enfin, les arborescences Merkle sont un composant important des systèmes de contrôle de version distribués tels que Git et IPFS. Leur capacité à garantir et vérifier facilement l’intégrité des données partagées entre ordinateurs au format P2P les rend inestimables pour ces systèmes.
Conclusion
Les arbres Merkle font partie intégrante des blockchains et leur permettent effectivement de fonctionner avec une immuabilité et une intégrité des transactions prouvables.
Comprendre le rôle qu'elles jouent dans les réseaux distribués et leur technologie sous-jacente de fonctions de hachage cryptographique est crucial pour comprendre les concepts de base des crypto-monnaies à mesure qu'elles continuent de se développer vers des systèmes plus grands et plus complexes.
Source : https://blockonomi.com/merkle-tree/