Arbres de Merkle et preuves d'inclusion

La question de départ

Un commerçant reçoit un lot de quatre paiements. Il veut une seule valeur courte qui change si n'importe lequel des quatre est modifié, et qui permette ensuite de prouver qu'un paiement précis en fait partie. Hacher la concaténation de tout le lot donne la première propriété, mais pas la seconde : pour prouver un paiement, il faudrait rendre les trois autres. L'arbre de Merkle donne les deux.

Le concept (convention jouet de cet atelier)

Règles, que tous les outils du cours appliquent :

1. Feuille = SHA-256 du texte de la donnée (par exemple une transaction).
2. Nœud parent = SHA-256 de la concaténation des deux empreintes enfants, en octets bruts, gauche puis droite.
3. Si un niveau compte un nombre impair de nœuds, le dernier est dupliqué.
4. On répète jusqu'à un seul nœud : la racine de Merkle.

Exemple détaillé : quatre transactions

Textes : tx0:Amina->Bello:20, tx1:Bello->Chantal:5, tx2:Chantal->Didier:12, tx3:Didier->Amina:7. Empreintes calculées avec SHA-256, tronquées à 8 caractères hexadécimaux pour la lecture :

Le symbole ‖ désigne la concaténation. Vous pouvez recalculer chaque ligne avec les outils : sha256 pour les feuilles, hexhash pour les nœuds (en entrant les deux empreintes complètes l'une après l'autre).

Ce que la racine garantit

• Si une seule feuille change d'un bit, sa feuille change, puis chaque nœud sur le chemin jusqu'à la racine : la racine change (effet d'avalanche, atelier 104).
• La racine dépend aussi de l'ordre des feuilles : échanger tx0 et tx1 donne une autre racine, car L0 ‖ L1 ≠ L1 ‖ L0.
• Cela suppose que SHA-256 est résistant aux collisions : on ne sait pas, aujourd'hui, produire deux entrées différentes de même empreinte.

Un cas à nombre impair de feuilles

Avec trois feuilles a, b, c : on calcule N1 = H(La ‖ Lb), puis N2 = H(Lc ‖ Lc) (c est dupliquée), puis la racine H(N1 ‖ N2). Pour cinq feuilles, la duplication intervient à deux niveaux. L'outil merkle-explorer le montre : saisissez 5 feuilles et regardez les nœuds copiés.

Ce que cela ne garantit pas

La racine ne dit rien de la validité des données (une transaction peut être frauduleuse et figurer joliment dans l'arbre), ni de leur origine : c'est une empreinte, pas une signature. Et la règle de duplication a un revers, vu en leçon 3.

En bref

• Racine = résumé de 32 octets de tout l'ensemble, sensible à chaque bit et à l'ordre.
• Feuille = H(donnée) ; nœud = H(gauche ‖ droite) ; niveau impair : dupliquer le dernier.
• La racine prouve la cohérence d'un ensemble, pas sa validité.

La question de départ

Didier affirme : « mon paiement tx2 est dans ce lot dont la racine est 803bff37… ». Vous ne voulez pas télécharger les quatre transactions. De quoi avez-vous strictement besoin pour vous en convaincre ?

Le concept

Une preuve d'inclusion pour une feuille liste, de la feuille vers la racine, le frère de chaque nœud du chemin : l'empreinte avec laquelle il est combiné à ce niveau. Le vérificateur reçoit la donnée et cette liste, et il recalcule la racine.

Règle de côté, utilisée par l'outil et par les épreuves : à chaque niveau, si l'indice courant est pair, le frère est à droite ; s'il est impair, il est à gauche. Puis l'indice est divisé par deux (arrondi vers le bas).

Exemple détaillé : prouver tx2 (indice 2)

Arbre de la leçon 1. La feuille tx2 a l'indice 2, donc pair.

1. Niveau 0 : indice 2 pair → le frère est à droite : L3 (f62a1b13…). On calcule N2 = SHA-256(L2 ‖ L3). Nouvel indice : 1.
2. Niveau 1 : indice 1 impair → le frère est à gauche : N1 (82bcaf46…). On calcule SHA-256(N1 ‖ N2). C'est la racine candidate.

La preuve ne contient donc que deux empreintes : L3 et N1, soit 64 octets, et non les trois autres transactions. Si le résultat vaut la racine annoncée (803bff37…), la preuve est acceptée.

Pourquoi la preuve « lie » la feuille

Pour fabriquer une fausse preuve pour une autre donnée X', il faudrait trouver des frères tels que le recalcul donne la même racine. Si la structure de l'arbre est fixée sans ambiguïté, cela revient à trouver une collision ou une préimage de SHA-256, ce que l'on ne sait pas faire. La preuve est alors liante pour cette racine, à cette position.

À vous

Dans merkle-explorer, entrez quatre feuilles, cliquez sur la troisième : l'outil affiche sa preuve et la vérifie. Modifiez ensuite un caractère de la feuille dans la preuve (sans toucher à la racine annoncée) : la vérification échoue. Puis modifiez un des frères : elle échoue aussi.

Ce que la preuve ne garantit pas

• La racine elle-même. Si un attaquant vous fournit une fausse racine avec de fausses preuves cohérentes, tout paraît correct. La racine doit venir d'une source de confiance. Dans Bitcoin, elle est dans l'en-tête de bloc de 80 octets, et un client léger suit la chaîne d'en-têtes dont le travail cumulé est le plus grand (voir la section 8 du papier de Bitcoin).
• La validité de la transaction. La preuve dit « incluse », pas « conforme aux règles » : un client léger se fie au fait qu'un bloc accepté par le réseau a été validé.
• L'absence. L'absence de preuve n'est pas une preuve d'absence (voir leçon 4 pour les arbres triés).

En bref

• Une preuve = les frères le long du chemin ; le vérificateur recalcule la racine.
• Indice pair → frère à droite ; impair → à gauche ; indice ÷ 2 à chaque niveau.
• La preuve lie la donnée à une racine, mais la racine doit déjà être digne de confiance.

La question de départ

Un bloc contient 1 000 000 de transactions (hypothèse de cours). Combien d'octets faut-il pour prouver l'inclusion d'une transaction ? Un million ? Mille ? Moins ?

Le concept

À chaque niveau de l'arbre, le nombre de nœuds est à peu près divisé par deux. Le chemin d'une feuille à la racine traverse donc autant de niveaux qu'il faut de divisions par deux pour passer de n à 1. Pour n feuilles (n ≥ 2), la preuve contient

⌈log₂ n⌉ empreintes

où ⌈ ⌉ est l'arrondi vers le haut. Chaque empreinte SHA-256 fait 32 octets.

Exemples détaillés

Doubler le nombre de feuilles n'ajoute qu'une empreinte à la preuve. Le million de feuilles se prouve avec 640 octets ; pour comparer, tout le million d'empreintes pèse 32 Mo. Cette propriété est ce qui rend les clients légers possibles sur un téléphone à forfait limité.

Vérifiez avec 5 feuilles : les niveaux ont 5, 3, 2, puis 1 nœuds : trois étapes, et ⌈log₂ 5⌉ = 3. ✔ La duplication ne change pas la formule : elle fournit un frère (une copie) là où il en manque un.

À vous

Dans l'outil, saisissez 8 feuilles : vous verrez des preuves de 3 empreintes. Avec 5 feuilles (niveaux de 5, 3, 2, puis 1 nœuds), les preuves en ont 3 aussi ; pour la dernière feuille, l'un des frères est une copie d'elle-même. L'outil s'arrête à 8 feuilles : pour 9 feuilles (niveaux de 9, 5, 3, 2, puis 1 nœuds), comptez à la main : chaque preuve a 4 empreintes, ce que le laboratoire autonome vérifiera en code.

Un revers de la règle de duplication

Prenons trois feuilles [a, b, c] et quatre feuilles [a, b, c, c]. Dans le premier cas, c est dupliquée pour former N2 = H(Lc ‖ Lc) ; dans le second, c et sa copie forment la même paire. Les deux listes donnent la même racine (dans la convention jouet, d31a37ef… avec des feuilles de texte « a », « b », « c »). Deux ensembles différents, une racine : la racine seule ne distingue pas « 3 transactions » de « 3 transactions dont la dernière est répétée ». Bitcoin applique cette même règle de duplication du dernier hachage, et ce défaut y a donné lieu à une vulnérabilité connue (de malléabilité des blocs, non un vol de fonds) que les implémentations ont dû traiter ; il faut pour cela que le doublon passe les autres règles de validation. Les protocoles qui s'en soucient détectent ces doublons ou changent de convention.

Ce que cela ne garantit pas

« Petite » ne veut pas dire « gratuite » : le vérificateur doit aussi connaître la position (ou les côtés) et la donnée de la feuille. Et prouver une seule transaction ne dit rien des autres. Des idées voisines (arbres de Merkle sur des données redondantes) servent aussi à l'échantillonnage de disponibilité des données dans certaines conceptions de chaînes ; ce sujet est hors programme ici.

En bref

• Une preuve compte ⌈log₂ n⌉ empreintes de 32 octets : 20 pour un million de feuilles, soit 640 octets.
• Doubler l'ensemble ajoute une empreinte, pas le double.
• Avec la duplication du dernier nœud, deux listes différentes peuvent avoir la même racine.

La question de départ

Dans notre convention, une feuille est SHA-256(donnée) et un nœud est SHA-256(gauche ‖ droite). Les deux sont donc « SHA-256 de quelque chose ». Un vérificateur peut-il confondre une feuille et un nœud interne ? Si oui, que peut en faire un attaquant ?

L'attaque, pas à pas

Reprenons l'arbre de quatre transactions (leçon 1) et sa racine R = 803bff37…

Un nœud interne N1 vaut SHA-256(L0 ‖ L1). Les octets L0 ‖ L1 font 64 octets. Un attaquant dit : « voici une donnée de 64 octets, égale à L0 ‖ L1, c'est ma feuille ; voici ma preuve : un seul frère, N2, à droite ». Le vérificateur applique la règle :

1. feuille = SHA-256(donnée) = SHA-256(L0 ‖ L1) = N1 ;
2. racine candidate = SHA-256(N1 ‖ N2) = R ✔.

La preuve est acceptée parce que le vérificateur ne contrôle pas la longueur de la preuve (un vérificateur qui fixerait la profondeur attendue, deux niveaux pour quatre feuilles, refuserait une preuve à un seul niveau), et pourtant la « feuille » n'est pas une transaction : c'est un nœud interne déguisé, et la preuve n'a qu'un niveau au lieu de deux. C'est une attaque par seconde préimage sur l'arbre (plus exactement, une confusion entre niveaux) : l'attaquant n'a cassé aucune fonction de hachage ; il a profité d'une ambiguïté de structure.

La parade : séparation des domaines

On préfixe les deux types de hachage par un octet différent :

• feuille = SHA-256(0x00 ‖ donnée)
• nœud = SHA-256(0x01 ‖ gauche ‖ droite)

Ainsi une valeur calculée comme feuille ne peut pas être prise pour un nœud, ni inversement, car les entrées diffèrent dès le premier octet. C'est la solution retenue par le protocole de transparence des certificats (RFC 6962). Autres parades possibles : fixer la profondeur attendue de l'arbre, ou exiger des feuilles d'une longueur différente de 64 octets. L'arbre des transactions de Bitcoin n'emploie pas ces préfixes ; le sujet est connu des chercheurs et dépasse cet atelier.

Ce que la preuve ne garantit toujours pas

• Même avec séparation des domaines, une preuve établit l'inclusion, pas l'absence : pour prouver qu'une donnée n'est pas dans un ensemble, on peut utiliser un arbre dont les feuilles sont triées : on prouve alors l'inclusion de deux voisins consécutifs a < x < b, entre lesquels x devrait se trouver. C'est le sujet du laboratoire autonome.
• Une preuve ne vaut que pour la racine donnée. Une racine qui change (un nouveau bloc) demande de nouvelles preuves.

À vous

Faites l'exercice de sécurité : vous allez exécuter l'attaque avec hexhash sur de vraies empreintes.

En bref

• Sans séparation, une feuille et un nœud interne sont indiscernables : un nœud peut se faire passer pour une feuille.
• Un préfixe distinct (0x00 / 0x01) supprime cette ambiguïté.
• Une preuve d'inclusion ne prouve jamais l'absence.