sommaire · 10 sections
Ton portefeuille sur téléphone affiche ton solde en quelques secondes. Il te dit qu’un paiement reçu est confirmé, et combien de blocs l’ont recouvert depuis. Pourtant il n’a jamais téléchargé la blockchain : plusieurs centaines de gigaoctets, qu’aucun téléphone ne garde. Alors sur quoi s’appuie-t-il ?
Sur deux briques. La première est une structure de données vieille de 1979, l’arbre de Merkle, qui permet de prouver qu’une transaction est dans un bloc avec quelques centaines d’octets. La seconde est une façon de trouver ses propres transactions dans la masse sans dire à personne ce qu’on cherche — un problème que Bitcoin a mis cinq ans à bien résoudre. On va voir les deux, sur de vrais blocs, en recalculant tout ce qu’on affirme.
6 017 transactions, 32 octets
Le header d’un bloc fait 80 octets, et la preuve de travail ne porte que sur eux. Or un bloc contient des milliers de transactions. Il faut donc que ces 80 octets engagent toutes les transactions, de sorte qu’en modifier une seule — un montant, un destinataire, l’ordre — rende le header faux. C’est le rôle du champ de 32 octets qu’on avait laissé de côté : la racine de Merkle.
La solution la plus simple serait de hacher la liste entière des transactions d’un seul coup. Ça marcherait pour l’intégrité, mais pas pour la suite : pour vérifier qu’une transaction est dans le bloc, il faudrait alors fournir toutes les autres. L’arbre de Merkle, décrit par Ralph Merkle en 1979 et repris par Satoshi Nakamoto dans le livre blanc, fait mieux.
Construire l’arbre
La construction tient en trois règles :
- Les feuilles sont les identifiants des transactions, les txid — eux-mêmes des doubles SHA-256, dans l’ordre du bloc, la coinbase en premier.
- On remonte deux par deux : chaque nœud du niveau supérieur est le double SHA-256 de la concaténation de ses deux enfants (64 octets hachés en 32).
- On recommence jusqu’à ce qu’il ne reste qu’un seul hash : la racine.
Il reste un cas à régler : un niveau qui compte un nombre impair d’éléments. Bitcoin a choisi une règle simple, et un peu étrange : on duplique le dernier, qui se retrouve apparié avec lui-même.
Appliquons-le au bloc 973 976, celui de l’article précédent. Il contient 6 017 transactions. On a récupéré ses 6 017 txid sur mempool.space et reconstruit l’arbre nous-mêmes :
| Niveau | Éléments | Impair → duplication ? |
|---|---|---|
| feuilles | 6 017 | oui |
| 1 | 3 009 | oui |
| 2 | 1 505 | oui |
| 3 | 753 | oui |
| 4 | 377 | oui |
| 5 | 189 | oui |
| 6 | 95 | oui |
| 7 → 10 | 48, 24, 12, 6 | non |
| 11 | 3 | oui |
| 12 | 2 | non |
| racine | 1 | — |
Treize étages de hachage, huit duplications, et au sommet :
ae6d9ce24ddda2b5ba23f97d20b9423a01e7abc2118aeaba52c1861532a57751
C’est exactement la racine inscrite dans le header du bloc. Le recalcul confirme ce qu’on attendait : ces 32 octets résument les 6 017 transactions, dans leur ordre exact. Changer un seul octet d’une seule d’entre elles change son txid, donc le nœud au-dessus, et ainsi de suite jusqu’à la racine. Le header ne correspond plus, et la preuve de travail est à refaire.
La preuve de Merkle
Voici où l’arbre devient intéressant. Pour prouver qu’une transaction est dans un bloc, il n’est pas nécessaire de fournir le bloc. Il suffit de fournir un hash par niveau : le « frère » de chaque nœud sur le chemin qui mène de la transaction à la racine. Le vérifieur refait les hachages, niveau par niveau, et compare le résultat à la racine du header. Si elles sont égales, la transaction est dans le bloc. Sinon, la preuve est fausse.
C’est la preuve de Merkle. Pour la vérifier, il faut trois choses : la transaction (ou son txid), sa position dans le bloc, et la liste des frères.
La position fait un travail discret mais indispensable. Lue en binaire, de droite à gauche, elle dit à chaque étage si notre nœud est l’enfant de gauche (bit 0, le frère est à droite) ou de droite (bit 1, le frère est à gauche). Or l’ordre compte : hacher A‖B ne donne pas le même résultat que B‖A.
Sur un vrai bloc
Reprenons la transaction de 222 octets de L’anatomie d’une transaction
, de txid b0d246e7…5353c72f. Elle a été confirmée dans le bloc 963 721, qui compte 5 064 transactions. Elle y occupe la position 35 — en binaire, 100011.
mempool.space fournit sa preuve : 13 hashs. On les a recombinés nous-mêmes. Aux deux premiers niveaux, notre nœud est à droite (les bits 1 et 1 de 100011) ; aux trois suivants, à gauche ; puis à droite ; puis, en haut de l’arbre, toujours à gauche. Après le treizième hachage, on obtient :
d537bdf1988743b6e9932919a73a5f0ba2d046c6c521ae156671a4775f8a7b24
C’est la racine de Merkle du header du bloc 963 721. La transaction y est, prouvée avec 13 × 32 = 416 octets, quand le bloc entier en pèse 1 633 037. Près de 4 000 fois moins.
Pourquoi ça passe à l’échelle
Le nombre de hashs dans une preuve est le nombre d’étages de l’arbre, c’est-à-dire le logarithme en base 2 du nombre de transactions, arrondi au-dessus. Le logarithme grandit très lentement :
| Transactions dans le bloc | Hashs dans la preuve | Taille de la preuve |
|---|---|---|
| 8 | 3 | 96 octets |
| 1 000 | 10 | 320 octets |
| 5 064 (bloc 963 721) | 13 | 416 octets |
| 1 000 000 | 20 | 640 octets |
Multiplier le bloc par mille n’ajoute que dix hashs à la preuve. C’est cette propriété qui rend possibles les portefeuilles légers.
Un second arbre, pour les témoins
Un détail que les plus attentifs auront relevé : l’arbre est construit sur les txid, et depuis SegWit, le txid ne couvre plus les signatures. On l’avait vu dans l’article sur les transactions : les signatures vivent dans le témoin, exclu du txid pour corriger la malléabilité. La racine de Merkle du header n’engage donc pas les témoins.
SegWit a réglé ça sans toucher au header, ce qui aurait exigé un hard-fork. On construit un second arbre, cette fois sur les wtxid (les identifiants qui incluent le témoin), et on inscrit sa racine dans une sortie OP_RETURN de la coinbase : c’est l’engagement du témoin, qu’on avait aperçu dans l’article sur le minage. Comme la coinbase est elle-même la première feuille du premier arbre, les témoins se retrouvent engagés par le header, à un étage d’indirection près.
Dans ce second arbre, une seule entorse : le wtxid de la coinbase est remplacé par 32 octets nuls, puisque la coinbase ne peut pas contenir l’empreinte d’un arbre qui la contiendrait elle-même. Pour le bloc 973 976, on a recalculé les 6 017 wtxid, reconstruit ce second arbre, et retrouvé l’engagement inscrit dans la coinbase, 09014480…68246559.
Les angles morts de l’arbre de Bitcoin
La règle de duplication a un coût. Si le dernier élément d’un niveau impair est apparié avec lui-même, alors deux listes de transactions différentes peuvent produire la même racine. Le code de Bitcoin Core en donne l’exemple : les listes [1,2,3,4,5,6] et [1,2,3,4,5,6,5,6] aboutissent au même hash.
En 2012, cette ambiguïté a été identifiée comme une faille, enregistrée sous le nom CVE-2012-2459. Un attaquant pouvait diffuser une version « gonflée » d’un bloc valide, avec des transactions dupliquées : même racine, même header, même preuve de travail, mais contenu invalide. Un nœud qui marquait ce bloc comme invalide refusait ensuite la version légitime — portant le même hash — et se retrouvait coupé du reste du réseau. La parade, toujours en place : un nœud vérifie qu’aucun niveau de l’arbre ne contient deux hashs identiques côte à côte, et traite un bloc « muté » comme un bloc dont la racine serait fausse, sans le blacklister.
Le portefeuille léger de Satoshi
Revenons au téléphone. Le livre blanc de Bitcoin consacre sa section 8 à ce qu’il appelle la Simplified Payment Verification, le SPV. L’idée : un utilisateur n’a pas besoin de tous les blocs, seulement de leurs headers. Il garde la chaîne des headers ayant le plus de travail cumulé, demande la preuve de Merkle de la transaction qui l’intéresse, et vérifie qu’elle mène à la racine d’un header de cette chaîne. Les blocs empilés au-dessus lui disent combien de travail recouvre son paiement.
Les headers sont légers : 80 octets par bloc. Jusqu’au bloc 973 976, cela fait 77,9 millions d’octets, environ 78 Mo — tenable sur un téléphone, et qui ne grossit que de 4 Mo par an.
Le livre blanc est honnête sur la limite : un client SPV ne vérifie pas lui-même les transactions. Il fait confiance au fait que la chaîne la plus travaillée ne contient que des transactions valides, ce qui suppose que la majorité de la puissance de calcul est honnête. Un nœud complet n’a pas besoin de cette hypothèse.
Reste un problème que le livre blanc ne traite pas : comment le portefeuille sait-il quelles transactions le concernent ? Pour demander une preuve, il faut savoir quoi demander. Et pour savoir quoi demander, il faut parcourir les blocs.
BIP37, ou demander au nœud de chercher pour soi
La première réponse date de 2012 : BIP37 , écrit par Mike Hearn et Matt Corallo, intégré à Bitcoin Core 0.8.0 en 2013. Le principe : le portefeuille envoie à un nœud complet un filtre de Bloom construit à partir de ses adresses, et le nœud lui renvoie, bloc après bloc, les transactions qui correspondent, avec leur preuve de Merkle.
Un filtre de Bloom est une structure probabiliste : un tableau de bits, où chaque élément ajouté allume quelques cases. Pour savoir si un élément « est dedans », on regarde ses cases. Si l’une est éteinte, il n’y est sûrement pas ; si toutes sont allumées, il y est probablement — avec un taux de faux positifs qu’on règle. BIP37 comptait sur ces faux positifs pour brouiller les pistes : le nœud recevrait les transactions du portefeuille noyées parmi d’autres, sans pouvoir les distinguer.
Le modèle a vieilli, pour trois raisons.
La confidentialité ne tient pas. En 2014, Arthur Gervais, Ghassan Karame, Damian Gruber et Srdjan Capkun ont montré qu’un nœud qui reçoit le filtre d’un portefeuille utilisant une poignée d’adresses peut en retrouver la quasi-totalité, et que la fuite s’aggrave quand le portefeuille redémarre et renvoie un nouveau filtre. Le brouillage était bien plus faible que prévu.
La charge repose sur le nœud. Pour chaque client connecté, le nœud doit repasser chaque bloc demandé au crible de son filtre. Des clients malveillants pouvaient s’en servir pour l’épuiser.
Le nœud peut se taire. Il peut omettre une transaction qui correspond au filtre, et le portefeuille n’a aucun moyen de le savoir : on peut prouver qu’une transaction est dans un bloc, pas qu’elle n’y est pas.
Depuis Bitcoin Core 0.19.0 (novembre 2019), un nœud ne sert plus les filtres de Bloom par défaut, pour fermer ces vecteurs de déni de service. L’option existe toujours, mais il faut l’activer.
BIP157/158, ou inverser les rôles
La réponse moderne a été proposée en 2017 par Olaoluwa Osuntokun, Alex Akselrod et Jim Posen : les filtres de blocs compacts, décrits dans BIP157 (le protocole) et BIP158 (le filtre). L’idée est d’inverser les rôles : ce n’est plus le portefeuille qui envoie un filtre au nœud, c’est le nœud qui publie un filtre par bloc, le même pour tout le monde. Le portefeuille télécharge ces filtres, les teste chez lui contre ses propres adresses, et ne demande que les blocs qui correspondent — en entier.
Le filtre d’un bloc contient tous les scripts de verrouillage qui y apparaissent : ceux des sorties créées, et ceux des sorties dépensées. Il est encodé de façon très compacte, en Golomb-Rice : chaque script est réduit à un nombre, les nombres sont triés, et on ne stocke que les écarts entre eux. Les paramètres de BIP158 fixent le taux de faux positifs à 1 sur 784 931 par élément cherché.
Le filtre du bloc 973 976, recalculé
Les tailles de filtres citées en ligne varient du simple au quadruple. Plutôt que de choisir une source, on a calculé le filtre du bloc 973 976 nous-mêmes. On a d’abord écrit l’algorithme de BIP158 et vérifié qu’il reproduisait les dix vecteurs de test officiels de la spécification — dix sur dix. Puis on l’a appliqué au bloc :
- 4 611 scripts distincts : 2 505 scripts de sorties créées et 2 592 scripts dépensés par les entrées, dont 486 apparaissent des deux côtés. Les 4 794 sorties
OP_RETURNdu bloc sont exclues, comme le veut la spécification : elles ne peuvent jamais être dépensées, donc aucun portefeuille ne les cherche ; - un filtre de 12 136 octets, soit 21 bits par script ;
- 0,71 % de la taille du bloc (1 714 534 octets), soit 141 fois moins.
Pour un portefeuille, l’ordre de grandeur est donc d’une douzaine de kilo-octets par bloc. Si tous les blocs ressemblaient à celui-ci, suivre une année de chaîne (environ 52 500 blocs) coûterait de l’ordre de 640 Mo de filtres : bien moins que les blocs eux-mêmes, mais nettement plus que les 4 Mo de headers, et plus que BIP37, où le nœud ne renvoyait que les quelques transactions utiles.
Ce que ça change
Le nœud n’apprend rien de la recherche. Il sert le même filtre à tout le monde. Quand un portefeuille demande un bloc entier, le nœud sait que ce bloc l’intéresse, mais pas pour quelle transaction — et le portefeuille peut répartir ces demandes entre plusieurs nœuds.
Le mensonge devient détectable. Les filtres sont déterministes : n’importe quel nœud honnête calcule exactement le même pour un bloc donné. BIP157 les enchaîne par des en-têtes de filtre, chacun engageant le filtre et l’en-tête précédent, comme les headers de blocs. Un portefeuille qui interroge plusieurs nœuds voit tout de suite s’ils divergent, et peut alors télécharger le bloc pour trancher. La limite : ces filtres ne sont pas inscrits dans les blocs eux-mêmes, la confiance repose donc sur le fait qu’au moins un des nœuds interrogés soit honnête.
La charge passe du nœud au client. Le nœud calcule chaque filtre une fois, au lieu de trier pour chaque client. Bitcoin Core sait construire cet index depuis la version 0.19.0 et le servir aux autres nœuds depuis la 0.21.0 (janvier 2021), mais seulement si l’opérateur l’active.
Qui s’en sert en 2026
L’adoption reste minoritaire. Les principaux utilisateurs de BIP157/158 sont :
- Neutrino , le client léger en Go de Lightning Labs, qui a fini par prêter son nom au protocole entier. Il permet à LND, l’implémentation Lightning de Lightning Labs, de fonctionner sans nœud Bitcoin complet, ce qu’utilisent des portefeuilles Lightning mobiles embarquant LND ;
- Wasabi Wallet, dont le mode léger repose sur les filtres BIP158, et qui sait depuis sa version 2.6 se synchroniser directement sur le nœud de l’utilisateur, sans serveur intermédiaire ;
- les bibliothèques de développement : BDK avec le client Kyoto en Rust, et LDK côté Lightning.
La plupart des portefeuilles légers grand public ont fait un autre choix : interroger un serveur Electrum ou Esplora, qui indexe la blockchain par adresse et répond directement « voici les transactions de cette adresse ». C’est rapide et simple à opérer, mais le serveur voit toutes les adresses qu’on lui demande. Ce n’est pas un défaut si le serveur est le tien, branché sur ton propre nœud ; ça en devient un quand c’est celui d’un tiers.
Ce qu’il faut retenir
- La racine de Merkle résume tout un bloc en 32 octets : les txid sont hachés deux par deux jusqu’au sommet. Recalculée sur le bloc 973 976, elle tombe juste.
- Une preuve d’inclusion coûte un hash par étage : 13 hashs, 416 octets, pour prouver qu’une transaction est dans un bloc de 5 064. Multiplier le bloc par mille n’ajoute que dix hashs.
- L’arbre de Bitcoin a des angles morts : la duplication du dernier élément (CVE-2012-2459, corrigée) et les transactions de 64 octets (la cible de BIP54, pas encore activé).
- Un client léger garde les headers (78 Mo pour toute l’histoire) et fait confiance à la majorité de la puissance de calcul pour la validité des transactions.
- BIP37 faisait trier le nœud à partir des adresses du portefeuille : mauvaise confidentialité, charge serveur, mensonge par omission. Désactivé par défaut depuis 2019.
- BIP157/158 fait trier le portefeuille à partir d’un filtre public par bloc : le nœud n’apprend rien, mais le client télécharge davantage. Techniquement supérieur, encore peu adopté face aux serveurs Electrum.
Et après
On a jusqu’ici parlé de « la » chaîne, celle qui a le plus de travail cumulé, comme si elle allait de soi. Mais que se passe-t-il quand deux mineurs trouvent un bloc presque en même temps, ou quand une partie du réseau suit des règles différentes ? Comment des milliers de nœuds qui ne se connaissent pas tombent-ils d’accord sur une seule histoire ? C’est l’objet de Le consensus Nakamoto (BTC-A-05, à venir).