Un arbre de Merkle est une méthode de structuration des données qui permet de vérifier l'exactitude d'un grand nombre d'informations de manière extrêmement rapide et efficace. Chaque arbre de Merkle aboutit à une seule chaîne de données, appelée racine de Merkle. Avec la racine de Merkle et quelques autres données, n'importe quel ordinateur peut valider efficacement toutes les autres entrées de l'arbre de Merkle. Dans la technologie blockchain, ces entrées sont des numéros d'identification de transaction.

Si vous êtes impliqué dans le monde de la blockchain, vous avez peut-être déjà rencontré l'expression "arbre de merkle". Si les arbres de Merkle ne sont pas un concept très répandu, ils ne sont pas non plus très compliqués. Ce billet explique les arbres Merkle en termes simples et vous aide à comprendre comment ils rendent possible la technologie de la blockchain.

Tout savoir sur les arbres de Merkle

L'histoire de Merkle Trees commence en 1979 avec un certain Ralph Merkle. Pendant ses études supérieures à l'université de Stanford, Merkle a rédigé un article intitulé "A Certified Digital Signature" (Une signature numérique certifiée). Dans cet essai, Merkle décrit une méthode de création de signatures numériques et établit une nouvelle méthode extrêmement efficace de création de preuves cryptographiques. En d'autres termes, il a conçu un processus de vérification des données qui permettrait aux ordinateurs d'effectuer leur travail beaucoup plus rapidement qu'auparavant.

Merkle a appelé son idée "Tree Signatures" ou "Tree Authentication". Aujourd'hui, cette idée est mieux connue sous le nom d'arbre de Merkle, du nom de son inventeur.

Il n'est pas exagéré de dire que les arbres Merkle ont révolutionné le monde de la cryptographie et, par extension, le fonctionnement des protocoles informatiques cryptés. En fait, les arbres de Merkle sont mentionnés à plusieurs reprises dans l 'essai de Satoshi Nakamoto de 2008 qui a présenté le bitcoin au monde entier. Ils sont largement utilisés dans le protocole Bitcoin.

Qu'est-ce qu'un arbre de Merkle ? Découvrons-le.

Tout d'abord, il est important de comprendre le concept de fonction de hachage cryptographique. En termes simples, les fonctions de hachage sont des fonctions mathématiques irréversibles qui prennent une entrée de n'importe quelle longueur - d'un caractère au texte d'un ensemble complet d'encyclopédies - et produisent une sortie aléatoire d'une longueur fixe. Comme la sortie semble aléatoire et qu'elle est de longueur fixe, un attaquant n'a aucun indice sur l'entrée qui a créé une sortie spécifique. Les fonctions de hachage sont également déterministes, de sorte que la même entrée produira toujours la même sortie. Enfin, les fonctions de hachage sont irréversibles, de sorte qu'il n'existe absolument aucun moyen de vérifier une entrée à partir de la seule connaissance de la sortie.

Toutes ces propriétés permettent aux fonctions de hachage de créer des empreintes électroniques d'une entrée particulière. En utilisant des fonctions de hachage, les réseaux blockchain créent un hachage cryptographique - une empreinte électronique - de chaque transaction. Le hachage cryptographique d'une transaction est simplement appelé l'identifiant de la transaction. Pour presque tous les protocoles de blockchain, chaque identifiant de transaction est une chaîne de données alphanumérique de 64 caractères (256 bits).

Lorsque l'on sait que les blockchains sont généralement constituées de centaines de milliers de blocs, chaque bloc contenant jusqu'à plusieurs milliers de transactions, on peut imaginer à quelle vitesse la vérification des transactions peut devenir difficile sur le plan informatique. Il est donc optimal d'utiliser le moins de données possible lors du traitement et de la vérification des transactions. Cela permet de réduire les temps de traitement de l'unité centrale tout en garantissant le plus haut niveau de sécurité.

C'est exactement ce que font les arbres Merkle. Pour simplifier, les arbres de Merkle prennent un grand nombre d'identifiants de transaction, les structurent d'une manière spécifique et utilisent des fonctions de hachage cryptographique pour obtenir une chaîne alphanumérique unique de 64 caractères qui agit comme une empreinte digitale électronique pour l'ensemble des données.

Cette chaîne de données, appelée racine de Merkle, est extrêmement importante car elle permet à n'importe quel ordinateur de vérifier rapidement qu'une transaction spécifique a eu lieu sur un bloc particulier, de la manière la plus efficace possible.

Qu'est-ce qu'une racine Merkle ?

La chaîne unique de 256 bits produite par un arbre de Merkle est appelée racine de Merkle. Chaque bloc d'une blockchain en compte exactement un. Et, comme nous venons de le mentionner, la racine de Merkle est une donnée cruciale car elle permet aux ordinateurs de vérifier des informations avec une rapidité et une efficacité incroyables.

Approfondissons un peu la question. Comment une racine Merkle est-elle produite ? La première étape consiste à organiser toutes les données d'entrée qui, dans le cas présent, sont des identifiants de transaction. Les arbres de Merkle, de par leur conception, regroupent toujours toutes les entrées par paires. Si le nombre d'entrées est impair, la dernière entrée est copiée puis appariée avec elle-même. Cela vaut pour tous les identifiants de transaction inscrits sur un bloc de la blockchain.

Supposons par exemple qu'un seul bloc contienne un total de 512 transactions. L'arbre de Merkle commence par regrouper les 512 identifiants de transaction en 256 paires. Ensuite, ces 256 paires d'identifiants de transaction sont soumises à un processus mathématique - la fonction de hachage ou l'algorithme de hachage, comme on l'appelle parfois - et nous obtenons 256 nouveaux hachages cryptographiques de 64 caractères.

Le même processus exact se reproduit. Ces 256 nouveaux hashs seraient appariés et transformés en 128 hashs. Le processus est répété, en réduisant le nombre de hachages de moitié à chaque fois, jusqu'à ce qu'il ne reste plus qu'un seul hachage. Ce hachage unique est notre racine Merkle.

Un exemple simple d'arbre de Merkle

Pour clarifier ce concept, examinons un exemple très simple d'arbre de Merkle. Imaginez que 8 transactions aient été effectuées sur un bloc particulier. En réalité, les identifiants de transaction ont une longueur de 64 caractères, mais par souci de simplicité, supposons qu'ils ne comportent que 8 caractères. Pour faciliter les choses, nous n'utiliserons que des chiffres (et nous ne tiendrons pas compte des lettres).

Ainsi, dans cet exemple, les identifiants de nos huit transactions seront les suivants :

• 11111111
• 22222222
• 33333333
• 44444444
• 55555555
• 66666666
• 77777777
• 88888888

Supposons maintenant que la méthode de hachage des identifiants de transaction consiste à prendre les premier, troisième, cinquième et septième chiffres de chacun des deux identifiants à combiner, puis à simplement pousser ces chiffres ensemble pour former un nouveau code à 8 chiffres.

Bien sûr, en réalité, les mathématiques qui sous-tendent les algorithmes de hachage sont bien plus compliquées que cela. Mais pour cette simple démonstration, ce système élémentaire suffira.

Voici à quoi ressemblerait notre arbre de Merkle :

Remarquez que le nombre de codes est réduit de moitié à chaque étape de l'arbre de Merkle. Nous partons de 8 identifiants de transaction et, après seulement trois étapes, nous obtenons un seul code, la racine de Merkle. Dans cet exemple, notre racine Merkle est le code dans la case du bas : 12345678.

Le principal avantage des arbres Merkle est qu'ils permettent une vérification extrêmement rapide des données. Si nous voulons valider l'identifiant d'une seule transaction, nous n'avons pas besoin de revérifier toutes les transactions du bloc. Au lieu de cela, nous ne devrions vérifier que cette "branche" particulière de notre arbre de Merkle.

Efficacité et rapidité : les avantages des arbres Merkle

Supposons que nous voulions valider l'identifiant d'une transaction dans notre exemple actuel. Bob dit qu'il a payé à Alice une certaine somme en bitcoins et nous indique que l'identifiant de la transaction est 88888888. Il nous envoie également trois hachages : 77777777, 55556666 et 11223344. C'est toute l'information qui doit être envoyée ou reçue pour vérifier le paiement de Bob à Alice.

Ces trois hachages, ainsi que l'identifiant de la transaction en question et la racine Merkle de ce bloc particulier, sont les seules données nécessaires pour vérifier le paiement de Bob à Alice. Cela représente beaucoup moins de données que ce qui serait nécessaire pour vérifier l'ensemble de l'arbre de Merkle. Le processus de vérification est donc beaucoup plus rapide et efficace pour tout le monde.

Voici comment cela fonctionne. Nous disposons déjà de la racine Merkle du bloc, Bob n'a donc pas besoin de nous l'envoyer. Il nous envoie son identifiant de transaction et les 3 hachages supplémentaires que nous avons énumérés ci-dessus. Il envoie également quelques informations sur l'ordre et l'emplacement dans lesquels les hachages doivent être utilisés. Il ne nous reste plus qu'à exécuter l'algorithme de hachage sur l'ensemble des données fournies par Bob.

Nous commençons par hacher le premier code 77777777 avec l'identifiant de transaction 88888888, ce qui nous donne le résultat 77778888. Bob ne nous a pas envoyé ce code, mais il n'en a pas eu besoin car nous utilisons le même algorithme de hachage que lui. Nous obtenons donc exactement les mêmes résultats.

Nous prenons ensuite le deuxième code que Bob nous a envoyé, 55556666, et nous le hachons avec le nouveau code 77778888 que nous venons de dériver. Cela donne bien sûr le nombre 55667788.

Enfin, nous hachons le troisième code que Bob nous a donné, 11223344, avec l'autre nouveau code que nous avons reçu, 55667788, et nous obtenons la racine de Merkle correcte : 12345678.

Remarquez que nous n'avons besoin que de trois codes de la part de Bob et qu'il a suffi d'exécuter l'algorithme de hachage trois fois pour vérifier que la transaction de Bob est valide. Cela signifie que notre ordinateur a effectué moins de la moitié du travail qui aurait été nécessaire pour vérifier l'ensemble de l'arbre de Merkle. Le diagramme de Merkle original comporte 15 nombres et l'algorithme de hachage doit être exécuté 7 fois. Mais plus de la moitié de cet arbre n'est pas nécessaire pour vérifier la transaction de Bob !

Procédures de validation simplifiées avec l'arbre de Merkle

Cette procédure est suffisante pour vérifier que Bob a effectivement payé à Alice cette certaine somme de bitcoins, car nous avons obtenu des nombres qui, une fois hachés avec les autres codes que Bob nous a envoyés, ont produit la même racine de Merkle que nous savions déjà être vraie pour ce bloc particulier.

Bob ne peut pas falsifier une transaction, car cela nécessiterait de trouver un faux identifiant de transaction et un ensemble supplémentaire de faux codes qui, lorsqu'ils sont soumis à la fonction de hachage, produiraient la véritable racine de Merkle. Les chances que cela se produise sont si faibles que nous pouvons affirmer avec certitude que c'est impossible.

Dans cet exemple simple, les économies de puissance de calcul peuvent ne pas sembler substantielles. Toutefois, si l'on considère que les blocs d'une blockchain peuvent contenir plusieurs milliers de transactions, il est facile de comprendre comment les Merkle Trees augmentent l'efficacité de manière aussi spectaculaire.

En bref, c'est le principal avantage d'un arbre Merkle. Il permet aux ordinateurs de vérifier des informations de manière extrêmement efficace et avec beaucoup moins de données que ce qui serait nécessaire sans l'arbre de Merkle.

Les Merkle Trees sont également le concept fondamental de la solution apportée par Komodo Platform au problème de l'extensibilité de la blockchain. La solution de mise à l'échelle de Komodo permet une interopérabilité complète de la blockchain et permettra à Komodo de traiter les transactions plus rapidement que tout autre service de traitement des paiements sur la planète. Actuellement, la nouvelle technologie de mise à l'échelle de Komodo traite plus de 20 000 transactions par seconde dans un environnement de test.

Clause de non-responsabilité：

1. Cet article est repris de[komodo]. Tous les droits d'auteur appartiennent à l'auteur original[Delton Rhodes]. Si vous avez des objections à cette réimpression, veuillez contacter l'équipe de Gate Learn, qui s'en chargera rapidement.
2. Clause de non-responsabilité : Les points de vue et les opinions exprimés dans cet article sont uniquement ceux de l'auteur et ne constituent pas un conseil en investissement.
3. Les traductions de l'article dans d'autres langues sont effectuées par l'équipe de Gate Learn. Sauf mention contraire, il est interdit de copier, distribuer ou plagier les articles traduits.