L'arbre de Merkle expliqué simplement

L’idée en une phrase

Un arbre de Merkle résume une longue liste en une seule empreinte, de sorte qu'on peut prouver qu'un élément y figure sans montrer tous les autres.

On hache chaque élément, puis on hache les empreintes deux par deux, puis les résultats deux par deux, jusqu'à n'en garder qu'une : la racine. Ralph Merkle a décrit cette structure à la fin des années 1970, bien avant Bitcoin.

La démo

Sans JavaScript, voici l'exemple à huit transactions : la première, « Alice paie 2 à Bob », a pour feuille 688af399…, sa voisine « Bob paie 3 à Emma » a pour feuille 886f5fed…, et l'arbre complet donne la racine 2ff418b1…. Trois étages, donc trois empreintes de preuve, soit 96 octets au lieu de 256.

Pourquoi ça compte

Ton téléphone fait tourner un wallet léger. Il veut savoir si ton paiement figure dans un bloc, sans télécharger tous les blocs de la chaîne. Le nœud complet qu'il interroge pourrait mentir. Comment vérifier sa réponse avec très peu de données ?

L'en-tête d'un bloc Bitcoin fait 80 octets et contient la racine de Merkle de toutes ses transactions. Il suffit donc au téléphone de stocker les en-têtes. Pour un bloc de 4 000 transactions, la preuve tient en 12 empreintes, soit 384 octets, contre 128 000 octets pour la seule liste des identifiants.

Le code

La construction tient en quelques lignes. Change une lettre de la liste txs ou le numéro de la transaction prouvée, et regarde la racine et la preuve réagir.

Clique sur Lancer pour exécuter ce code dans ton navigateur.

Ce qui se passe vraiment

La démo dessine l'arbre, racine en haut. Chaque case montre les quatre premiers caractères d'un hash. La ligne du bas contient les feuilles, c'est-à-dire le double SHA-256 de chaque transaction. Au-dessus, chaque case est le double SHA-256 de ses deux enfants mis bout à bout.

Clique sur « Falsifier le montant ». La case de la feuille change, puis tout le chemin jusqu'à la racine, car chaque parent dépend de son enfant par le jeu de l'effet avalanche. Les autres branches ne bougent pas. Cela permet de localiser une différence en descendant l'arbre, sans tout comparer.

La racine recalculée vire au rouge, car elle ne correspond plus à celle de l'en-tête. La preuve échoue pour la même raison. Pour la faire passer, il faudrait trouver des frères qui ramènent à la même racine, ce qui revient à casser la résistance à la seconde préimage de SHA-256.

Observe aussi les cases en tirets : ce sont les seules données que le nœud complet doit fournir. Pour remonter de la feuille à la racine, le vérificateur calcule lui-même le chemin en trait plein et ne reçoit que les frères. À chaque étage, le nombre de nœuds est divisé par deux, donc la preuve croît comme le logarithme en base 2 du nombre de feuilles.

Pousse le curseur sur une valeur impaire. Un étage impair n'a pas de partenaire pour son dernier nœud : Bitcoin le duplique et le hache avec lui-même. C'est la case en pointillés.

La démo simplifie : elle hache un texte au lieu d'une transaction sérialisée, et affiche les hash dans l'ordre naturel, alors que Bitcoin inverse souvent l'ordre des octets à l'affichage.

Dans la vraie vie

La racine de Merkle relie les transactions au reste de la blockchain : elle entre dans l'en-tête du bloc, et cet en-tête est ce que le minage scelle. Toucher à une transaction ancienne change sa feuille, sa racine, puis le hash du bloc.

La vérification simplifiée de paiement, décrite dans le livre blanc de Bitcoin, repose sur cette propriété. Le wallet léger suit les en-têtes, puis demande une preuve de Merkle pour ses transactions.

Ethereum utilise une variante, l'arbre de Merkle-Patricia, pour résumer l'état de tous les comptes. Les layer 2 s'en servent pour publier un engagement compact sur la chaîne principale. On retrouve la même idée dans Git, dans les journaux de transparence des certificats HTTPS, et dans certaines preuves de réserves publiées par des plateformes. Les distributions de tokens stockent souvent une seule racine dans un contrat, chaque bénéficiaire apportant sa propre preuve : cela évite d'écrire des milliers d'adresses sur la chaîne.

Ce qui peut mal tourner

• La duplication du dernier nœud. Une liste de transactions dont les deux dernières sont identiques a la même racine que la liste sans doublon. Ce défaut de Bitcoin, répertorié CVE-2012-2459, a permis de fabriquer des blocs invalides de même hash. Les nœuds le détectent désormais.
• La confusion feuille et nœud interne. Si feuilles et nœuds sont hachés de la même façon, une valeur de 64 octets peut passer pour la concaténation de deux enfants. La RFC 6962 sépare les deux avec un préfixe distinct. Si tu conçois un arbre, fais de même.
• Une preuve d'inclusion n'est pas une preuve de validité. Elle dit que la donnée figure sous cette racine, pas que la transaction respecte les règles. Le wallet léger se repose sur le travail accumulé des mineurs.
• Une racine de source douteuse. La preuve ne vaut que si la racine vient d'une source fiable. Le nœud menteur peut fabriquer un arbre cohérent à partir de sa propre racine.
• Un arbre ne prouve pas l'absence. Une preuve de Merkle ordinaire ne montre pas qu'un élément manque. Il faut pour cela un arbre trié ou une structure dédiée.
• L'ordre gauche-droite. Hacher a + b n'est pas hacher b + a. Une preuve sans indication de côté, ou un code qui trie mal les paires, produit de faux échecs ou de fausses validations.

Teste-toi