Bitcoin et les arbres de Merkle : comment vérifier les transactions ?

Comment prouver qu’une transaction Bitcoin figure dans un bloc sans devoir examiner toutes les transactions de ce bloc ? La réponse repose sur une structure cryptographique inventée plusieurs décennies avant Bitcoin : l’arbre de Merkle. Derrière ce nom se cache une méthode de regroupement des empreintes numériques qui permet de résumer un grand ensemble de données et de vérifier efficacement qu’un élément en fait partie.

Cette technique intervient au cœur de chaque bloc Bitcoin. Elle relie les transactions à une empreinte unique, appelée racine de Merkle, enregistrée dans l’en-tête du bloc. Elle joue aussi un rôle dans certaines méthodes de vérification légère. Pourtant, il serait trompeur d’affirmer qu’une preuve de Merkle suffit à garantir qu’une transaction est valide ou définitivement irréversible. Pour comprendre son intérêt, il faut distinguer l’intégrité des données, la preuve d’inclusion et la validation du consensus.

Une invention antérieure à Bitcoin : l’héritage de Ralph Merkle

L’histoire commence bien avant la publication du livre blanc de Satoshi Nakamoto en 2008. À la fin des années 1970, le cryptographe Ralph Merkle travaille sur des méthodes permettant de vérifier efficacement de grandes quantités d’informations. Ses recherches sur les structures de hachage et les signatures fondées sur des fonctions cryptographiques contribueront à établir les bases de ce que l’on appelle aujourd’hui les arbres de Merkle.

Le site History of Bitcoin situe cette étape historique au 4 juin 1979. Cette date correspond à son entrée chronologique et ne doit pas être interprétée, sans source complémentaire, comme la preuve que l’invention aurait eu lieu précisément ce jour-là. L’essentiel est que les principes étaient étudiés près de trente ans avant la naissance de Bitcoin. Satoshi a ensuite intégré cette famille de techniques à son système de monnaie électronique.

L’intérêt de cette histoire dépasse l’anecdote. Bitcoin ne résulte pas d’une invention cryptographique isolée : il associe des idées antérieures, dont les signatures numériques, les fonctions de hachage, la preuve de travail et les arbres de Merkle, dans une architecture nouvelle. Cette combinaison permet à des participants indépendants de contrôler les mêmes données sans confier la tenue du registre à une autorité unique.

Comment fonctionne un arbre de Merkle ?

Des empreintes numériques organisées par paires

Une fonction de hachage transforme une donnée en une empreinte de longueur fixe. Dans Bitcoin, chaque transaction possède un identifiant appelé TXID, obtenu à partir de sa sérialisation selon les règles applicables. Pour construire l’arbre de Merkle d’un bloc, les TXID sont pris dans leur ordre et regroupés deux par deux. Chaque paire est concaténée, puis soumise à un double SHA-256 pour obtenir une nouvelle empreinte.

Le processus recommence avec les empreintes nouvellement calculées. Deux résultats donnent un parent, deux parents donnent un niveau supérieur, et ainsi de suite jusqu’à ne conserver qu’une seule valeur : la racine de Merkle. Cette valeur de 32 octets résume cryptographiquement l’ensemble ordonné des identifiants de transactions du bloc.

Si un niveau comporte un nombre impair d’éléments, Bitcoin duplique le dernier hash pour former la dernière paire. Si le bloc ne contient que la transaction coinbase, son TXID constitue directement la racine. Ces détails font partie de la construction utilisée par Bitcoin et expliquent pourquoi l’ordre des transactions et les règles de calcul doivent être respectés.

Un exemple avec quatre transactions

Imaginons un bloc contenant quatre transactions A, B, C et D. Leurs identifiants sont notés respectivement H(A), H(B), H(C) et H(D). Le protocole calcule une empreinte commune pour les deux premières et une autre pour les deux dernières. Il combine ensuite ces deux résultats pour obtenir la racine. Dans cet exemple, H désigne schématiquement l’opération de hachage ; dans Bitcoin, les calculs des nœuds internes utilisent le double SHA-256 sur les octets concaténés.

Premier niveau : les identifiants des quatre transactions A, B, C et D.
Deuxième niveau : une empreinte pour la paire A–B et une autre pour C–D.
Dernier niveau : une empreinte commune des deux branches, appelée racine de Merkle.

L’illustration de cette page représente précisément ce principe simplifié. Une modification du contenu d’une transaction change normalement son identifiant, puis les empreintes des branches concernées et enfin la racine. Une racine attendue qui ne correspond plus à la racine recalculée signale donc une incohérence des données, sous les hypothèses de sécurité de la fonction de hachage.

La racine de Merkle : un engagement cryptographique inscrit dans chaque bloc

L’en-tête d’un bloc Bitcoin occupe 80 octets. Il contient notamment la version, le hash de l’en-tête précédent, la racine de Merkle, un horodatage, une représentation compacte de la cible de difficulté et un nonce. La racine y occupe 32 octets. Comme l’en-tête intervient dans la preuve de travail, modifier les transactions du bloc entraîne normalement une nouvelle racine, donc un en-tête différent et la nécessité de refaire le travail correspondant.

La racine ne contient pas les transactions elles-mêmes et ne permet pas de les reconstruire. Elle agit comme un engagement cryptographique envers un ensemble ordonné d’identifiants. C’est cette propriété qui permet de détecter une modification sans conserver, dans l’en-tête, une copie de toutes les données engagées. Elle n’est toutefois pas une signature numérique et ne prouve pas, à elle seule, qu’un bloc respecte toutes les règles du protocole.

La preuve de Merkle : vérifier une inclusion avec peu de données

Pourquoi quelques empreintes peuvent suffire

Pour démontrer qu’une transaction particulière figure dans un arbre dont la racine est connue, il n’est pas nécessaire de transmettre toutes les transactions du bloc. Il suffit de fournir son identifiant, les empreintes des branches voisines nécessaires au calcul et leur position relative. Le vérificateur peut alors reconstruire le chemin jusqu’à la racine et comparer le résultat à la valeur attendue.

Dans un arbre équilibré de 1 024 feuilles, le chemin comporte environ dix niveaux, puisque 1 024 correspond à 2 puissance 10. Il faut donc environ dix empreintes voisines, soit 320 octets d’empreintes de 32 octets, auxquels s’ajoutent les informations nécessaires à leur interprétation. Ce calcul illustre l’efficacité de la méthode : la taille de la preuve augmente approximativement avec le logarithme du nombre de feuilles, et non proportionnellement à leur nombre.

Une preuve valide démontre que l’identifiant de la transaction participe à la construction de la racine annoncée. Elle ne démontre pas automatiquement que la transaction est autorisée, qu’elle ne dépense pas des fonds déjà dépensés ou que le bloc appartient à la chaîne ayant le plus de travail cumulé. Ces propriétés exigent d’autres vérifications.

La différence entre preuve d’inclusion et validation complète

Un nœud complet vérifie les transactions, les scripts, les conditions de dépense et les règles de consensus applicables. Une preuve de Merkle se limite à relier cryptographiquement un identifiant de transaction à une racine donnée. Elle peut donc constituer une pièce d’un contrôle plus large, mais pas remplacer toutes les opérations nécessaires pour établir la validité d’un bloc.

Cette distinction est importante pour les utilisateurs qui souhaitent conserver une indépendance maximale. La preuve de Merkle réduit les données nécessaires pour vérifier une inclusion, tandis que la validation complète permet de contrôler soi-même les règles du réseau. Les deux méthodes répondent à des besoins différents et ne doivent pas être présentées comme équivalentes.

Le rôle historique des preuves de Merkle dans les clients légers

Dans la huitième section de son livre blanc, Satoshi Nakamoto décrit une méthode de vérification simplifiée des paiements, généralement appelée SPV, pour Simplified Payment Verification. Le principe consiste notamment à utiliser les en-têtes de blocs et une branche de Merkle afin d’établir qu’une transaction figure dans un bloc, sans télécharger systématiquement l’intégralité de ses transactions.

Cette approche réduit les besoins de stockage et de transmission, mais introduit des hypothèses de sécurité différentes de celles d’un nœud complet. Un client qui ne vérifie pas lui-même toutes les règles dépend davantage des informations reçues de ses pairs et de la chaîne d’en-têtes qu’il considère pertinente. Les portefeuilles légers modernes n’emploient pas tous exactement la méthode SPV historique : leurs architectures et leurs garanties doivent être examinées séparément.

Il faut donc éviter une formule trop séduisante : « vérifier une transaction sans rien télécharger ». Une preuve d’inclusion demande bien certaines données, et son interprétation dépend de la confiance accordée à l’en-tête et à la chaîne concernés. L’avantage est une réduction considérable du volume nécessaire pour une question précise, non une validation complète gratuite.

Les limites techniques et les précautions de sécurité

La sécurité d’un arbre de Merkle repose sur les propriétés des fonctions de hachage et sur une construction rigoureuse. Il faut notamment éviter les ambiguïtés entre différentes représentations de données et traiter correctement les arbres comportant un nombre impair de feuilles. L’histoire de Bitcoin a montré l’importance de ces détails, notamment autour des cas de mutation liés à la duplication de certains identifiants dans l’arbre.

Un autre point mérite d’être compris : les transactions Bitcoin ont plusieurs identifiants selon les données considérées. Depuis SegWit, la structure des blocs comprend également un engagement distinct lié aux données de témoin, utilisant une racine construite à partir des WTXID. Cette structure ne remplace pas la racine traditionnelle des TXID inscrite dans l’en-tête ; elle complète les engagements nécessaires au contrôle des données de témoin.

Enfin, les arbres de Merkle ne garantissent ni la confidentialité des transactions ni leur irréversibilité. Ils ne cachent pas les montants, n’empêchent pas un portefeuille compromis de signer une dépense et ne suppriment pas les possibilités de réorganisation de la blockchain. Leur rôle est plus précis : permettre un engagement compact envers des données et fournir des preuves d’inclusion efficaces.

Pourquoi cette invention compte autant dans l’architecture de Bitcoin

L’arbre de Merkle répond à une difficulté fondamentale des systèmes distribués : comment contrôler efficacement une information appartenant à un ensemble très vaste ? En regroupant les empreintes dans une structure hiérarchique, il rend possible une vérification ciblée sans devoir transporter tout l’ensemble. Son intégration dans les blocs Bitcoin relie cette propriété aux mécanismes de consensus et de preuve de travail.

Cette idée rejoint notre dossier sur l’asymétrie technique de Bitcoin. Dans les deux cas, une opération de vérification peut demander bien moins de ressources que la production ou le traitement initial des données. La comparaison a toutefois ses limites : une preuve de Merkle démontre une inclusion, tandis que la preuve de travail répond à une condition de difficulté. Les deux mécanismes se complètent sans remplir la même fonction.

En bref

Un arbre de Merkle regroupe les identifiants des transactions d’un bloc en une racine cryptographique de 32 octets. Grâce aux preuves d’inclusion, un vérificateur peut établir qu’une transaction participe à cette racine à partir d’un nombre limité d’empreintes. Cette méthode contribue à l’efficacité de Bitcoin, mais ne remplace pas la validation des règles de consensus par un nœud complet.

🔍 Avis de DUC

Ce qui m’intéresse particulièrement dans les arbres de Merkle, c’est leur capacité à rendre compréhensible une idée qui paraît presque contradictoire : contrôler une information précise sans devoir examiner à nouveau tout ce qui l’entoure. Derrière une structure mathématique assez simple à représenter se trouve un mécanisme essentiel à l’efficacité des vérifications cryptographiques.

Je pense aussi qu’il faut éviter de transformer cette propriété en argument publicitaire. Une preuve d’inclusion n’est pas une garantie absolue de validité et encore moins une promesse de sécurité pour tous les portefeuilles. Bitcoin fonctionne parce que plusieurs mécanismes se complètent. Les arbres de Merkle en sont une pièce importante, mais ils prennent leur véritable sens lorsqu’on les replace aux côtés des signatures, des nœuds et de la preuve de travail.