Arbres de Merkle : intégrité des transactions à grande échelle

Un bloc Bitcoin contient environ 2 000 transactions. Pour prouver que la transaction T est incluse sans télécharger les 2 000 transactions, nous avons besoin d’une preuve compacte. Les arbres de Merkle résolvent ce problème : la taille de la preuve est de O(log n) hachages au lieu de O(n) transactions.

Feuilles : SHA256d (double-SHA256) de chaque transaction. Parent : SHA256d(left_child_hash || right_child_hash). Répétez l’opération jusqu’à obtenir un seul hachage racine. Si le nombre de nœuds est impair, dupliquez le dernier nœud. La racine est la racine de Merkle stockée dans l’en-tête du bloc (32 octets).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Pour prouver que la transaction T se trouve à la position i, fournissez les hachages des nœuds frères à chaque niveau, de la feuille de T jusqu’à la racine (O(log n) hachages). Le vérificateur recalcule la racine à partir de T et du chemin des nœuds frères. Si la racine calculée correspond à la racine de Merkle de l’en-tête du bloc, l’inclusion de T est prouvée.

1 024 transactions → une preuve de Merkle = 10 hachages = 320 octets. Un bloc complet = environ 1 MB. Les clients SPV téléchargent uniquement l’en-tête de 80 octets et la preuve de Merkle de 320 octets pour chaque transaction qui les intéresse, soit une économie de bande passante de 99,97 % par rapport au téléchargement du bloc complet.

Si une transaction quelconque de l’arbre est modifiée, son hachage de feuille change et cette modification se propage jusqu’à la racine de Merkle. La racine modifiée ne correspond plus à celle de l’en-tête du bloc, qui est scellé par le PoW. Toute modification peut être détectée en calculant la racine à partir des transactions.

Ethereum étend les arbres de Merkle avec des tries (trie de Merkle Patricia) : un arbre radix à préfixe hexadécimal dont chaque nœud est haché selon Merkle. Il est utilisé pour le trie d’état (soldes des comptes), le trie des transactions et le trie des reçus. Il permet de prouver efficacement l’état d’un compte sans disposer des données d’un nœud complet.

Une structure de Merkle en montagnes (MMR) est une structure de Merkle en ajout uniquement destinée aux données de type journal. Les nouveaux éléments sont ajoutés à la suite et les sommets, c’est-à-dire les racines des sous-arbres de taille puissance de 2, sont conservés. Elle est utilisée dans Grin/MimbleWimble et ZCash pour produire efficacement des preuves compactes sur un journal en ajout uniquement.

Les arbres de Verkle remplaceront les arbres de Merkle dans la feuille de route d’Ethereum (EIP-6800) : ils utilisent des engagements vectoriels (engagements polynomiaux KZG) plutôt que des hachages. Taille de la preuve : O(1), contre O(log n) pour Merkle. Les clients sans état peuvent ainsi vérifier l’état sans stocker l’intégralité du trie.

Certificate Transparency (RFC 6962) utilise un journal de Merkle en ajout uniquement : chaque certificat émis par une CA en est une feuille. Les preuves d’inclusion vérifient qu’un certificat a bien été enregistré. Les preuves de cohérence vérifient que le journal est resté en ajout uniquement, sans suppression ni insertion. Les fournisseurs de navigateurs vérifient les SCT au moyen de ce journal.

Les arbres Git (instantanés de répertoires) sont des arbres de Merkle : chaque nœud d’arbre hache ses objets blob de fichiers et ses sous-arbres. Le hachage d’une validation identifie de manière unique l’état complet de la base de code. C’est pourquoi git checkout restitue toujours exactement les mêmes fichiers.

Combien de hachages une preuve de Merkle nécessite-t-elle pour prouver l’inclusion dans un arbre de 1 024 feuilles ?

Les arbres de Merkle permettent des preuves d’inclusion en O(log n). Bitcoin stocke la racine de Merkle dans les en-têtes de blocs ; les clients SPV utilisent ces preuves. Ethereum étend ce concept aux tries de Merkle Patricia. Les arbres de Verkle remplaceront les arbres de Merkle pour fournir des preuves en O(1). Ensuite : le minage par preuve de travail et la difficulté.