L'arbre de Merkel, comment ça marche ?

Prenez vos chaussures à crampons, aujourd’hui, nous allons grimper dans un arbre. Et pas n’importe lequel !
Nous avons vu dans l’article sur le SHA-256 que les transactions d’un bloc étaient liées les unes aux autres, par un procédé que l’on appelle l’arbre de Merkle. Regardons son fonctionnement et pourquoi il porte ce nom.

Si ce n’est pas un végétal, c’est peut-être un animal ?

L’arbre de Merkle n’a rien à voir avec un végétal sur lequel poussent des chanceliers allemands. C’est une structure très utilisée en informatique, qui permet de vérifier l’intégrité des données de manière très simple et très rapide.

Inventé par un certain Ralph Merkle en 1979, l’arbre doit son nom à la forme que le graphique prend lorsqu’on l’utilise. Ses feuilles sont composées des différents hash, que l’on va combiner par paire, jusqu’à arriver à la racine.

C’est le même fonctionnement qu’un arbre généalogique. Vous êtes la racine, et chacun de vos ancêtres est une feuille qui va se combiner avec une autre, pour arriver jusqu’à vous.

Dit comme ça, ça peut sembler difficile à comprendre, mais vous allez voir que, dans la pratique, c’est très simple. Par contre, si vous n’êtes pas à l’aise avec le concept de hash, prenez le temps de lire cet article auparavant, cela vous facilitera grandement la lecture.

Un arbre pour les relier toutes

Imaginons que notre bloc Bitcoin est composé de 4 transactions que nous appellerons transaction A, B, C et D.

Pour démarrer notre arbre de Merkle, nous allons hacher chacune de ces transactions.
La transaction A deviendra alors H(A), la transaction B devient H(B), et, comme vous l’avez deviné, nous obtenons également H(C) et H(D).

Ce petit travail de hachage va créer la cime de l’arbre. Car oui, un arbre de Merkle est représenté à l’envers. Vous allez comprendre pourquoi avec la suite !

Nous avons maintenant 4 feuilles dans notre arbre. H(A), H(B), H(C) et H(D). Nous allons continuer la construction de l’arbre, et pour ça, nous allons tout simplement hacher la combinaison des différentes feuilles, deux par deux.

Nous allons donc obtenir H(H(A) + H(B)) et H(H(C) + (H(D)).

Rien de très compliqué jusque-là. Et maintenant, vous l’avez compris, je pense, nous allons hacher une nouvelle fois nos deux résultats, pour obtenir un hash final. Nous obtiendrons donc H(H(H(A) + H(B)) + H(H(C) + H(D)))

Ce hash le plus haut dans l’arbre est appelé la racine de Merkle, ou Merkle root en anglais.
Comme vous nous l’expliquions précédemment, l’arbre est représenté à l’envers. Les racines se trouvent en haut, et les feuilles toutes en bas. C’est une manière plus pratique pour représenter les choses et faire comprendre que la racine découle de toutes les opérations précédentes. Et surtout que la racine est l’élément principal de notre arbre !

Comment utiliser l’arbre de Merkel ?

Maintenant que nous avons compris le fonctionnement de l’arbre, nous allons voir à quoi il sert. Car dessiner des arbres c’est chouette, tout le monde aime les arbres, mais quel est l’intérêt dans le cas de Bitcoin ?

Et bien ça va nous servir à organiser les transactions, et surtout à vérifier qu’elles ne sont pas altérées, que ce soit de manière volontaire ou non.

En effet, lorsqu’un nœud reçoit un nouveau bloc, il doit s’assurer que les transactions à l’intérieur sont valides. Il pourrait le faire de manière individuelle, en allant décortiquer chaque transaction, mais ça prendrait du temps et des ressources pour quelque chose qui est totalement évitable.
Car grâce à la racine de Merkle, il sait immédiatement si les données correspondent à celle que le mineur a annoncée, ou non.

Et oui ! De par son fonctionnement en entonnoir, la racine est le hash de chaque feuille (les transactions) de l’arbre. Donc, si un petit malin essaye de modifier la transaction A, alors la valeur de H(A), ne sera plus du tout la même.
Et donc, la valeur de H(H(A) + H(B)) va changer également, et, par définition, celle de la racine H(H(H(A) + H(B)) + H(H(C) + H(D))) ne sera plus du tout celle annoncée auparavant.

La moindre petite modification, même d’un seul caractère dans une transaction, fera son effet boule de neige, qu’il sera impossible à camoufler.

De plus ce fonctionnement avec la racine permet d’économiser de l’espace. Un client Bitcoin léger n’aura pas besoin de détenir toutes les informations sur toutes les transactions pour s’assurer qu’elles sont valides.
En ne conservant que la racine de l’arbre, il est capable de s’assurer que les blocs sont valides et que les transactions le sont également. Pas besoin de télécharger la blockchain au complet !

Merkle et Bitcoin, les deux amis indissociables

L’arbre de Merkle est donc un composant essentiel au fonctionnement de la blockchain. Grâce à lui on peut s’assurer que les données (transactions) sont valides, que les blocs sont ceux attendus et que leur intégrité n’a pas été compromise.

L’espace de stockage est réduit, et la robustesse de l’arbre assure une fiabilité totale des informations. De plus tout est disponible et consultable par tous, ce qui contribue à la transparence offerte par la blockchain Bitcoin.

Comprendre le fonctionnement des arbres de Merkel, combiné à tous les éléments que nous avons vus auparavant (le hash 256, l’ajustement de la difficulté de minage, BIP39) permet de mieux saisir l’ingéniosité de Satoshi Nakamoto, et par définition, celle de notre blockchain préférée !