Qu'est-ce qu'un arbre Merkle ?
Le concept d'arbre de Merkle a été proposé au début des années 80 par Ralph Merkle, un informaticien réputé pour ses travaux sur la cryptographie à clé publique.
Un arbre Merkle est une structure utilisée pour vérifier efficacement l'intégrité des données dans un ensemble. Ils sont particulièrement intéressants dans le contexte des réseaux peer-to-peer, où les participants doivent partager et valider des informations de manière indépendante.
Les fonctions de hachage sont au cœur des arborescences Merkle, nous vous recommandons donc de consulter Qu'est-ce que le hachage ? avant de procéder.
Comment fonctionnent les arbres Merkle ?
Supposons que vous souhaitiez télécharger un fichier volumineux. Avec un logiciel open source, vous souhaiterez généralement vérifier que le hachage du fichier que vous avez téléchargé correspond à celui rendu public par les développeurs. Si tel est le cas, vous savez que le fichier que vous avez sur votre ordinateur est exactement le même que le leur.
Si les hachages ne correspondent pas, vous avez un problème. Soit vous avez téléchargé un fichier malveillant se faisant passer pour le logiciel, soit il n’a pas été téléchargé correctement et ne fonctionnera donc pas. Si tel est le cas, vous ne serez probablement pas très heureux si vous devez attendre un certain temps pour que le fichier soit téléchargé. Maintenant, vous devez redémarrer le processus et espérer qu’il ne soit plus corrompu.
Si seulement il y avait un moyen plus simple de procéder, pensez-vous. Heureusement, c'est là qu'interviennent les arbres Merkle. Avec l'un d'eux, votre fichier serait divisé en morceaux. S'il s'agissait d'un fichier de 50 Go, vous pouvez le diviser en cent morceaux, de telle sorte que chacun mesure 0,5 Go. Ensuite, il serait téléchargé morceau par morceau. C’est essentiellement ce que vous faites lorsque vous torrent des fichiers.
Dans ce cas, votre source vous aura fourni un hachage appelé racine Merkle. Ce hachage unique est une représentation de chaque bloc de données qui constitue votre fichier. Mais la racine Merkle facilite grandement la vérification des données.
Pour faire simple, prenons un exemple où nous utilisons un fichier de 8 Go divisé en huit morceaux. Appelez les différents fragments A à H. Chaque fragment passe ensuite par une fonction de hachage, nous donnant huit hachages différents.
Nous faisons passer chacun de nos huit fragments via une fonction de hachage pour obtenir leurs hachages.
D'accord, nous avons donc quelque chose qui a un peu plus de sens. Nous avons le hachage de tous les fragments, donc si l’un d’entre eux est défectueux, nous le saurons en le comparant avec celui de la source, non ? Peut-être, mais c’est aussi incroyablement inefficace. Si votre fichier contient des milliers de fragments, allez-vous vraiment tous les hacher et comparer méticuleusement les résultats ?
Non. Au lieu de cela, nous allons prendre chaque paire de hachages, les combiner, puis les hacher ensemble. Nous hachons donc hA + hB, hC + hD, hE + hF et hG + hH. Nous nous retrouvons avec quatre hachages. Ensuite, nous effectuons un autre tour de hachage avec ceux-ci pour finir avec deux. Enfin, nous hachons les deux autres pour accéder à notre hachage principal – la racine Merkle (ou hachage racine).
La structure ressemble à un arbre renversé. Sur la rangée du bas, nous avons les feuilles, qui sont combinées pour produire les nœuds et enfin la racine.
Nous avons maintenant la racine Merkle qui représente le fichier que nous avons téléchargé. On peut comparer ce hachage racine avec celui fourni par la source. Si ça correspond, parfait ! Mais si les hachages sont différents, on peut être sûr que les données ont été modifiées. En d’autres termes, un ou plusieurs fragments ont produit un hachage différent. Ainsi, toute légère modification des données nous donnera une racine Merkle totalement différente.
Heureusement, il existe un moyen pratique de vérifier quel fragment est défectueux. Dans notre cas, disons que c’est lui. Vous commenceriez par demander à un homologue les deux hachages qui ont produit la racine Merkle (hABCD et hEFGH). Votre valeur hABCD doit correspondre à la leur puisqu'il n'y a aucune erreur dans ce sous-arbre. Mais hEFGH ne le fera pas, alors vous savez vous enregistrer là-bas. Vous demandez ensuite hEF et hGH et les comparez avec les vôtres. hGH aura l’air bien, vous savez donc que hEF est notre coupable. Enfin, vous comparez les hachages de hE et hF. Vous savez maintenant que hE est incorrect, vous pouvez donc retélécharger ce morceau.
En résumé, un arbre Merkle est créé en divisant les données en plusieurs morceaux, qui sont ensuite hachés à plusieurs reprises pour former la racine Merkle. Vous pouvez alors vérifier efficacement si quelque chose ne va pas avec une donnée. Comme nous le verrons dans la section suivante, il existe également d’autres applications intéressantes.
Vous cherchez à vous lancer dans la crypto-monnaie ? Achetez du Bitcoin sur Binance !
Pourquoi les racines Merkle sont-elles utilisées dans Bitcoin ?
Il existe une poignée de cas d’utilisation des arbres Merkle, mais nous nous concentrerons ici sur leur importance dans les blockchains. Les arbres Merkle sont essentiels dans Bitcoin et dans de nombreuses autres crypto-monnaies. Ils font partie intégrante de chaque bloc, où ils peuvent être trouvés dans les en-têtes de bloc. Pour obtenir les feuilles de notre arbre, nous utilisons le hachage de transaction (le TXID) de chaque transaction incluse dans le bloc.
La racine Merkle sert à plusieurs fins dans ce cas. Jetons un coup d'œil à leurs applications dans le domaine de l'extraction de crypto-monnaie et de la vérification des transactions.
Exploitation minière
Un bloc Bitcoin est composé de deux morceaux. La première partie est l'en-tête du bloc, un segment de taille fixe contenant les métadonnées du bloc. La deuxième partie est une liste de transactions dont la taille est variable, mais qui a tendance à être beaucoup plus grande que l'en-tête.
Les mineurs doivent hacher les données à plusieurs reprises pour produire un résultat qui correspond à certaines conditions pour extraire un bloc valide. Ils peuvent faire des milliards de tentatives avant d’en trouver une. À chaque tentative, ils modifient un nombre aléatoire dans l’en-tête du bloc (le nom occasionnel) pour produire une sortie différente. Mais une grande partie du bloc reste la même. Il peut y avoir des milliers de transactions, et vous devrez quand même les hacher à chaque fois.
Une racine Merkle rationalise considérablement le processus. Lorsque vous commencez à exploiter, vous alignez toutes les transactions que vous souhaitez inclure et construisez un arbre Merkle. Vous placez le hachage racine résultant (32 octets) dans l'en-tête du bloc. Ensuite, lorsque vous exploitez, il vous suffit de hacher l’en-tête du bloc, au lieu du bloc entier.
Cela fonctionne parce que c’est inviolable. Vous résumez efficacement toutes les transactions du bloc dans un format compact. Vous ne pouvez pas trouver un en-tête de bloc valide et modifier ultérieurement la liste des transactions, car cela modifierait la racine Merkle. Lorsque le bloc est envoyé à d'autres nœuds, ils calculent la racine à partir de la liste des transactions. S’il ne correspond pas à celui de l’en-tête, ils rejettent le blocage.
Vérification
Il existe une autre propriété intéressante des racines de Merkle que nous pouvons exploiter. Celui-ci concerne les clients légers (nœuds ne détenant pas de copie complète de la blockchain). Si vous exécutez un nœud sur un appareil doté de ressources limitées, vous ne souhaitez pas télécharger et hacher toutes les transactions d'un bloc. Ce que vous pouvez faire à la place, c'est simplement demander une preuve Merkle – une preuve fournie par le nœud complet qui prouve que votre transaction se trouve dans un bloc particulier. Ceci est plus communément appelé vérification de paiement simplifiée, ou SPV, et a été détaillé par Satoshi Nakamoto dans le livre blanc Bitcoin.
Pour vérifier HD, nous n'avons besoin que des hachages affichés en rouge.
Considérons le scénario dans lequel nous souhaitons connaître des informations sur la transaction dont le TXID est hD. Si hC nous est fourni, nous pouvons élaborer hCD. Ensuite, nous avons besoin de hAB pour calculer hABCD. Enfin, avec hEFGH, nous pouvons vérifier que la racine Merkle résultante correspond à celle de l'en-tête du bloc. Si c’est le cas, c’est la preuve que la transaction a été incluse dans le bloc – il serait presque impossible de créer le même hachage avec des données différentes.
Dans l’exemple ci-dessus, nous n’avons dû hacher que trois fois. Sans une preuve Merkle, nous aurions dû le faire sept fois. Étant donné que les blocs contiennent aujourd’hui des milliers de transactions, l’utilisation des preuves Merkle nous fait gagner beaucoup de temps et de ressources informatiques.
Pensées finales
Les arbres Merkle se sont révélés très utiles dans une gamme d'applications informatiques : comme nous l'avons vu, ils sont incroyablement précieux dans les blockchains. Dans les systèmes distribués, les arbres Merkle permettent une vérification facile des informations sans inonder le réseau de données inutiles.
Sans les arbres Merkle (et les racines Merkle), les blocs de Bitcoin et d’autres crypto-monnaies ne seraient pas aussi compacts qu’ils le sont aujourd’hui. Et tandis que les clients légers font défaut en matière de confidentialité et de sécurité, les preuves Merkle permettent aux utilisateurs de vérifier si leurs transactions ont été incluses dans un bloc avec un minimum de frais généraux.
