Arbres de Merkle

Curiosité

1. Comment une seule valeur de hachage peut-elle certifier l’inclusion de quatre mille transactions distinctes ?
2. Pourquoi Satoshi a-t-il choisi d’apparier une dernière entrée isolée avec elle-même, et quel a été le prix de ce choix ?
3. Quelle vulnérabilité précise la règle d’appariement par duplication a-t-elle introduite dans la première implémentation de Bitcoin ?

Explorer

1. Ralph Merkle a déposé en 1979 un brevet sur l’arbre de hachage binaire (accordé en 1982), une structure de données conçue pour résumer efficacement de grands ensembles de données. Dans Bitcoin, cette architecture réduit des milliers d’identifiants de transaction à une seule valeur de 32 octets appelée racine de Merkle. Cette racine est intégrée directement dans l’en-tête de bloc de 80 octets, ce qui crée un engagement cryptographique immuable envers chaque transaction de ce bloc précis.
2. La construction se fait de manière récursive, de bas en haut. Les identifiants de transaction sont concaténés par paires puis soumis à un double hachage SHA-256 pour produire les nœuds parents. Cet appariement se poursuit niveau par niveau jusqu’à ce qu’il ne reste qu’un seul hash racine. Si un niveau contient un nombre impair d’entrées, la dernière entrée est appariée avec elle-même pour préserver la structure binaire, ce qui garantit que l’arbre s’équilibre correctement à chaque étape.
3. La nature logarithmique de cette structure permet la vérification simplifiée des paiements (SPV). Un client léger ne télécharge pas les blocs complets ; il demande plutôt une branche de Merkle à un nœud complet. Cette branche ne contient que les hashes frères situés le long du chemin qui mène d’une transaction donnée à la racine. Pour un bloc de 4 000 transactions, cette preuve nécessite environ douze valeurs de hash, soit une fraction de la taille totale des données.
4. En combinant le hash de sa propre transaction avec ces hashes frères fournis, un client léger recalcule la racine de Merkle et la compare à la valeur présente dans l’en-tête de bloc téléchargé. Si elles correspondent, l’inclusion est vérifiée cryptographiquement sans qu’il soit nécessaire de stocker toute la chaîne. Ce mécanisme permet aux portefeuilles mobiles de fonctionner en toute sécurité sur des appareils aux capacités de stockage et de calcul limitées.
5. Segregated Witness (SegWit), activé en août 2017, a introduit une deuxième structure d’arbre de Merkle. Alors que l’arbre d’origine s’engage sur les identifiants de transaction, l’arbre witness s’engage sur les identifiants de transaction witness. La racine de ce second arbre n’est pas stockée dans l’en-tête ; elle est inscrite dans une sortie OP_RETURN de la transaction coinbase, que les anciens nœuds traitent comme de simples données, ce qui préserve la compatibilité.
6. La règle d’auto-appariement cachait une faille (CVE-2012-2459). Comme une dernière entrée isolée est appariée avec elle-même, une liste de transactions se terminant par une paire dupliquée produit la même racine de Merkle que la liste sans le doublon. Un attaquant pouvait diffuser cette variante malformée d’un bloc valide ; les nœuds qui la rejetaient pouvaient alors marquer le hash du bloc authentique comme invalide et se désynchroniser du réseau. Le correctif de 2012 permet aux nœuds de reconnaître ce schéma au lieu de mettre le bloc en cache comme invalide.

Faits clés

Exercice neuf, six, trois, un

Vérification des faits

Les dates, les chiffres et les affirmations ont été vérifiés à l’aide des sources publiées listées ci-dessous.

• R. Merkle, US Patent 4,309,569 (1982)
• Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System (2008), sections 7-8
• BIP 141: Segregated Witness (Consensus layer)
• A. M. Antonopoulos & D. A. Harding, Mastering Bitcoin, 3rd ed. (2023), ch. 11