Qu’est-ce qu’un arbre de Merkle ?

Oui, avant de vous sauver, vous êtes actuellement sur un blog blockchain. Nous savons que le sujet de cette discussion peut nous faire perdre la tête pour toutes nos connaissances en botanique ; cependant, un arbre de Merkle est loin de tout ce que vous pourriez trouver dans la nature.

Dans ce billet, nous parlerons de l’utilisation des arbres de Merkle dans le contexte des chaînes de blocs et des réseaux cryptographiques. Nous examinerons également pourquoi l’arbre de Merkle joue un rôle si important pour garantir l’efficacité et la fiabilité de ces réseaux.

La blockchain reconstituée

Comme vous vous en souvenez peut-être, une chaîne de blos est un réseau de paiement décentralisé avec un grand livre (base de données) partagé des transactions. Plusieurs ordinateurs de ce réseau doivent conserver des copies de ce grand livre. Comme vous pouvez l’imaginer, des milliers de transactions sont effectuées sur une courte période de temps.

C’est beaucoup de transactions, c’est le moins qu’on puisse dire ! Ce n’est pas tout non plus. N’oubliez pas que chacune de ces transactions doit ensuite être vérifiée par tous les autres ordinateurs du réseau. Vous vous demandez donc peut-être maintenant comment un réseau en chaîne peut traiter un si grand volume de données et vérifier chaque transaction ? Plus encore, comment la blockchain peut-elle le faire tout en préservant l’intégrité des données sans disposer d’un espace de stockage important sur un réseau ou d’une puissance de calcul considérable ?

L’arbre de Merkle sort de terre

C’est là que l’arbre de Merkle entre en jeu. En termes simples, la beauté de l’arbre de Merkle est sa capacité à prendre de grandes quantités de données d’entrée et à les comprimer en une sortie de longueur fixe. Cette sortie ne consiste qu’en une seule chaîne de caractères appelée racine de Merkle. La racine de Merkle peut facilement servir de preuve de la validité des données qu’elle représente. Elle peut également être facilement partagée avec d’autres personnes sur le réseau. Cela signifie qu’il n’est pas nécessaire que chaque utilisateur conserve une copie de l’ensemble de la base de données. En cas d’erreur, nous n’avons pas besoin de faire une recherche ligne par ligne dans la base de données entière.

Cependant, avant de pouvoir comprendre le fonctionnement d’un arbre de Merkle, nous devons comprendre les bases des fonctions de hachage. En effet, les fonctions de hachage sont la technologie clé qui sous-tend un arbre de Merkle.

Explication des fonctions de hachage

Remarquez ce qui se passe si nous ne modifions qu’un détail mineur de la transaction et appliquons la même fonction de hachage. Notre résultat est complètement différent.

Exemple de hachage
Cryptage par md5decrypt.net

La valeur de hachage résultante est unique aux données d’entrée et est comme une empreinte digitale des données. Vous avez sans doute remarqué que les deux chaînes de sortie sont très différentes malgré une légère modification des données d’entrée. Par conséquent, il est assez facile de déterminer quand un fichier est corrompu.

Différence avec le hachage précédent
Cryptage par md5decrypt.net

Pour illustrer le fonctionnement d’une fonction de hachage, nous pouvons utiliser une analogie simple. Veuillez garder à l’esprit qu’il s’agit d’une vision très simpliste des fonctions de hachage. En réalité, les fonctions de hachage sont juste un peu plus compliquées.

Les fonctions de hachage sont du gâteau

Supposons que vous vouliez faire un gâteau. Vous prenez un certain nombre d’ingrédients (l’entrée), vous suivez la liste des instructions de la recette (l’algorithme mathématique de la fonction de hachage) et le résultat est un gâteau (la sortie ou valeur de hachage). Si vous utilisez toujours les mêmes ingrédients et suivez la même recette, vous obtiendrez toujours le même gâteau. Peu importe le nombre de fois que vous faites cela, le résultat est toujours le même. De même, avec la fonction de hachage, les mêmes données d’entrée généreront toujours la même chaîne de caractères de sortie (la valeur de hachage), quel que soit le nombre de fois qu’elle est répétée.

Cependant, comme pour la cuisson d’un gâteau, vous pouvez varier les ingrédients, suivre la même recette et obtenir un gâteau différent. De même, avec une fonction de hachage, la modification des données d’entrée produira une valeur de sortie très différente.

Tout comme une recette peut être appliquée à une liste différente d’ingrédients, une fonction de hachage (ou algorithme) peut être appliquée à plusieurs reprises à différentes entrées. Chacune d’entre elles génère une sortie différente. Ces sorties auront alors chacune leur propre jeu de caractères ou d’empreintes digitales. Dans Bitcoin, l’algorithme utilisé est l’algorithme SHA256, qui génère une chaîne de sortie d’une longueur de 256 bits.

Détecter la corruption

Ce qui est intéressant avec une fonction de hachage, c’est que si je varie l’entrée, même légèrement, la sortie peut être une chaîne de caractères radicalement différente. Il est donc très facile de détecter la corruption des données d’entrée, ce qui permet de vérifier l’intégrité des données. De même, avec un gâteau, si l’on changeait un seul ingrédient, le résultat serait facilement détecté. Par exemple, si j’ajoute des pépites de chocolat à mon gâteau au lieu de noix, la différence est assez évidente.

Gagner de la place

Le hachage permet également d’économiser du stockage. Au lieu de stocker d’énormes quantités de données d’entrée, il suffit de stocker la valeur de hachage. Comme pour la comparaison de gâteaux, au lieu de stocker une quantité infinie d’ingrédients, vous n’avez qu’à stocker le gâteau. De plus, comme j’ai la recette, je peux reproduire le gâteau. Cela permet également de gagner de la place dans le garde-manger. Pourquoi pouvons-nous dire cela ?

Il est toujours possible de reproduire le gâteau en rassemblant les ingrédients et en suivant la même recette avec les mêmes ingrédients. Les ingrédients eux-mêmes peuvent être stockés dans de nombreux endroits différents, comme chez un voisin, un ami ou même chez grand-mère, et nous ne pouvons récupérer ces ingrédients que lorsque nous en avons besoin. De même, avec un réseau distribué, nous pouvons utiliser différentes sources pour stocker de plus petits sous-ensembles de données et nous passer d’un stockage central. Et si nous détectons un problème ou devons vérifier certaines données, nous n’avons qu’à récupérer les parties dont nous avons besoin. Cela contribue à l’efficacité d’une chaîne de blocs.

Les 4 avantages d’une fonction de hachage

Ok, nous avons compris qu’il y a tellement de choses intéressantes à propos des fonctions de hachage, comment sommes-nous censés nous en souvenir ? Un résumé pratique, bien sûr ! Les fonctions de hachage sont utiles pour ces quatre raisons principales :

  1. En appliquant une fonction de hachage, vous pouvez prendre un énorme ensemble de données et le compresser en une seule sortie de longueur fixe (valeur de hachage). Cela permet d’économiser de l’espace de stockage sur l’ordinateur, car il suffit de stocker la valeur de hachage, au lieu de l’ensemble des données.
  2. La valeur de hachage est unique pour les données d’entrée et est donc comme une empreinte digitale. Même une modification mineure de l’entrée se traduira par une sortie très différente. Cela permet de détecter facilement toute corruption de l’ensemble des données et de vérifier l’intégrité des données.
  3. Elle est déterministe, c’est-à-dire que peu importe le nombre de fois que vous exécutez la fonction de hachage avec les mêmes données d’entrée, elle générera toujours la même valeur de hachage.
  4. Il s’agit d’une fonction à sens unique, ce qui signifie qu’il est impossible de prendre la valeur de hachage et d’en extraire les données d’entrée ; elle est donc sécurisée.

Voici le moment que vous attendez tous. Parlons de l’arbre de Merkle.

Le concept de l’arbre de Merkle

Le concept de l’arbre de Merkle remonte à 1979, avant l’existence de la chaîne de blocs, et a été nommé d’après Ralph Merkle, l’informaticien qui a breveté l’idée. Il a imaginé l’arbre de Merkle comme un moyen de stocker et de vérifier de grandes quantités de données de manière efficace et sûre.

La technologie clé qui sous-tend l’arbre de Merkle est la fonction de hachage, qui sert à la fois à crypter les données et à les comprimer en une taille gérable. La structure de base d’un arbre de Merkle est semblable à celle d’un arbre inversé, comme le montre le schéma suivant :

Concept simplifié d'un arbre de Merkle

Comme pour tout arbre, il y a des feuilles, des branches et une racine. Les feuilles sont les transactions (ou blocs de transactions) qui constituent les données d’entrée. Une fonction de hachage est appliquée à chaque bloc d’opérations (E1, E2, E3, E4) pour créer ce que l’on appelle des nœuds de feuilles (I, II, III, IV). Les nœuds de feuille constituent le début de l’arbre de Merkle.

Dans cet exemple, nous pouvons concaténer (joindre ensemble) deux nœuds feuilles (I+II) pour créer un nœud parent (A) en appliquant à nouveau la fonction de hachage. Nous pouvons faire de même avec les nœuds feuilles (III+IV) pour créer un nœud parent (B). Nous pouvons ensuite hacher les nœuds parents A+B ensemble pour obtenir ce que l’on appelle la racine de Merkle. Le résultat est une sortie composée d’une chaîne de caractères de longueur fixe. Maintenant, au lieu de stocker un grand ensemble de données, nous pouvons représenter l’ensemble de ces données avec seulement la racine de Merkle.

Une arborescence plus complexe

L’arbre de Merkle représenté ci-dessus est un exemple simple. En réalité, un arbre de Merkle peut être beaucoup plus grand, ayant plus de niveaux, et beaucoup plus large, incorporant plus de séries de données. Le processus est le même. La fonction de hachage est appliquée à plusieurs reprises jusqu’à ce qu’il ne reste que la racine de Merkle.

Sur un réseau en chaîne, nous pouvons stocker la racine de Merkle dans un endroit sûr à une source fiable, et répartir la responsabilité du stockage du reste des informations à d’autres sources sur le réseau. Sans révéler de données réelles ni exiger le contenu de la base de données entière, nous pouvons vérifier très rapidement des sous-ensembles de données en faisant simplement correspondre chaque hachage avec la racine de Merkle. Toute erreur peut être détectée rapidement en demandant le hachage d’un sous-ensemble plus petit jusqu’à ce que le bloc corrompu soit trouvé. Cela permet d’accroître l’efficacité en n’exigeant pas qu’une base de données entière soit recherchée pour une seule erreur.

Qu’est-ce que la racine de Merkle ?

Pour illustrer comment un arbre de Merkel peut simplifier le processus de vérification des données dans un réseau distribué, nous avons pensé qu’un exemple s’imposait. Examinons à nouveau le même tableau ci-dessus pour cet exemple. Supposons que je détienne une copie d’un sous-ensemble de données, T1, et que je veuille confirmer que les données sont correctes. Sans connaître le contenu de toute la base de données, je peux demander la valeur de X et B à d’autres sources sur le réseau. Avec cela, je peux calculer la racine de Merkle.

Ayant T1, je peux donc prendre son hash, et obtenir W. Ensuite, je peux prendre le hash de W et X pour obtenir A. Ayant A et connaissant la valeur de B, je peux prendre le hash de A et B pour générer la racine de Merkle, que je peux ensuite comparer à l’original, vérifiant ainsi l’intégrité de l’ensemble de données T1, sans connaître réellement le contenu du reste de la base de données.

Le DAG expliqué

Tout d’abord, qu’est-ce qu’un DAG ? L’acronyme DAG signifie « directed acyclic graph » (graphique acyclique dirigé). Sans trop entrer dans les détails, un DAG décrit essentiellement comment les informations d’un réseau de nœuds connectés sont transmises d’un nœud à l’autre. Les graphes acycliques sont des graphes qui ne contiennent aucun cycle. En d’autres termes, il n’y a pas de chemin pour que l’information retourne à un nœud qui a déjà été rencontré. La partie dirigée du graphe indique que l’information n’est dirigée que dans une seule direction. Cela signifie que la séquence va de plus en plus loin. On pourrait également appeler ce type d’ordonnancement un ordre topographique.

On peut dire qu’une chaîne de blocs est un exemple de simple graphe acyclique dirigé. Dans une blockchain, il y a une seule chaîne de blocs, chaque bloc faisant référence au précédent.

Représentation du concept de DAG

Notez que dans ce diagramme, l’information n’est dirigée que dans une seule direction.

Le DAG de Merkle

Tout d’abord, un DAG de Merkle est un graphique acyclique dirigé par Merkle. Il a une structure similaire à celle d’un arbre de Merkle mais n’est pas aussi strict. Il n’y a pas d’exigences d’équilibre. Chaque nœud peut contenir des données, et comme plusieurs branches peuvent se reconvertir, un nœud peut avoir plusieurs parents. Ceci est différent d’un arbre de Merkle qui est généralement de nature binaire. Où chaque parent est le hachage de deux enfants.

Ce qui rend le DAG intéressant dans le monde des chaînes de blocs, c’est que sa structure ouvre la possibilité de délais de traitement des transactions beaucoup plus rapides. Dans une blockchain standard, telle que Bitcoin, il n’y a qu’une seule chaîne de blocs. Toutes les transactions qui se produisent en même temps sont regroupées dans un bloc. Les mineurs se font ensuite concurrence pour la validation de ce bloc et une fois validé, le bloc est lié au bloc précédent. La durée moyenne d’extraction d’un bloc est d’environ 10 minutes. Comme vous pouvez l’imaginer, si ce système devait être adopté par une large communauté d’utilisateurs, cela pourrait entraîner de longs temps de transaction et des inefficacités dans le système, ainsi qu’un coût élevé pour chaque transaction.

Pourquoi avons-nous besoin du DAG ?

Le DAG permet l’existence de plusieurs chaînes latérales, qui se ramifient à partir d’un seul bloc. Les chaînes ramifiées sont créées lorsque deux mineurs produisent un bloc en même temps. Lorsque cela se produit dans une chaîne de blocs, une période de temps arbitraire, appelée temps de bloc, est appliquée pour donner au réseau le temps de se consolider et de vérifier quel bloc est correct. Si une branche malveillante est détectée, elle devient orpheline ou est interrompue.

Dans un DAG, étant donné que plusieurs chaînes peuvent être créées en même temps, nous pouvons avoir différentes transactions fonctionnant simultanément sur différentes chaînes. Elles peuvent coexister en parallèle, à condition que les informations soient dirigées dans le même sens. Il n’est donc pas nécessaire de prévoir un temps de blocage pour valider quel bloc est correct. Cela réduit également le temps perdu pour les succursales orphelines.

Alors que la chaîne de blocs repose sur les confirmations de toutes les transactions par les pairs, les confirmations au sein de la chaîne de DAG se font par les transactions elles-mêmes. Par conséquent, plus il y a d’utilisateurs, plus les délais de confirmation sont rapides.

Une leçon sur la vérification

La vérification ne doit provenir que des deux nœuds les plus proches. Cela réduit le besoin d’algorithmes complexes et permet d’éliminer le processus d’extraction externe. Il en résulte une vitesse de transaction presque instantanée et des coûts réduits pour tous les utilisateurs du réseau.

Le DAG ouvre la voie à l’adoption massive de la cryptographie. En effet, il offre la possibilité de vérifier des milliers de transactions chaque seconde. Le processus est également beaucoup moins coûteux pour l’utilisateur. À titre de comparaison, le temps moyen d’extraction d’un bloc est de 10 minutes, le temps moyen de transaction pour un réseau DAG est presque instantané. Ceci est particulièrement important si l’on veut que les cryptomonnaies soient plus attrayantes pour les masses et les institutions financières.

Alors que Bitcoin est considéré comme Blockchain 1.0, et Ethereum : Blockchain 2.0, beaucoup pensent que DAG n’est peut-être que Blockchain 3.0.

Conclusion

Et voilà, vous l’avez. Une leçon, non pas de botanique, mais d’un outil très important dans le monde de la technologie blockchain. Si vous devez retenir quelque chose, rappelez-vous qu’un arbre de Merkle est particulièrement utile pour gérer de grandes quantités de données. Il permet également de s’assurer que les données peuvent être récupérées et vérifiées efficacement dans un réseau distribué.

Enfin, il peut y avoir des variantes du concept d’arbre de Merkle, comme le Merkle DAG, qui pourrait permettre des formes plus rapides et encore plus complexes de réseaux cryptographiques. Cela signifie une adoption à grande échelle par les masses et une réduction considérable des coûts de transaction. Oui, l’avenir est brillant quand vous avez des arbres, des arbres de Merkle.

Comments (No)

Leave a Reply

odio accumsan quis at facilisis dictum risus ipsum Lorem venenatis,