Un Merkle Tree regroupe progressivement les empreintes cryptographiques de données en un résultat unique. Dans Bitcoin, il produit le Merkle root inscrit dans l’en-tête du bloc. Quelques empreintes supplémentaires permettent de vérifier qu’une transaction correspond à cette racine, sans transmettre toutes les autres.
Votre portefeuille indique que le paiement a été inclus dans un bloc. Comment le vérifier sans télécharger tout son contenu ? C’est là qu’intervient le Merkle Tree. Les transactions sont d’abord représentées par des hash, de courtes empreintes cryptographiques. Elles sont regroupées progressivement en une seule empreinte commune, la racine. L’en-tête contient ce Merkle root et relie ainsi le bloc à ses transactions. La racine n’est pas une archive permettant de relire tous les paiements : elle sert à vérifier les données présentées. [1] [2]
Imaginez quatre transactions A, B, C et D. On prend leurs empreintes, on associe A à B et on calcule un nouveau hash AB. On fait de même avec C et D pour obtenir CD. Enfin, on réunit les empreintes AB et CD et on calcule la racine. Les lettres ne font ici que nommer les transactions et les résultats intermédiaires ; ce ne sont pas de vrais hash. L’ensemble ressemble à un arbre inversé : de nombreuses feuilles convergent par des branches vers une racine. Davantage de transactions ajoutent des étages, sans changer le principe. [3]
Pour vérifier B, vous disposez de ses données et calculez son empreinte. Il suffit d’obtenir celle de A et l’empreinte commune CD, avec leur ordre correct. Vous formez AB à partir de A et B, puis la racine à partir de AB et CD, avant de la comparer à celle de l’en-tête. Ce chemin complémentaire est appelé Merkle proof. Nul besoin du contenu de A, C ou D. Dans un arbre équilibré de 1024 transactions, le chemin comporte 10 hash voisins. La taille de la preuve augmente donc bien plus lentement que celle de la liste complète. [2] [3]
Une preuve correspondant à la racine ne permet pas de faire aveuglément confiance à l’en-tête fourni. Il faut aussi vérifier son Proof of Work : le résultat du calcul de minage respecte-t-il la difficulté exigée ? Il faut également vérifier le rattachement de l’en-tête à la chaîne appropriée. Même alors, un Merkle proof ne vérifie pas toutes les signatures ni toutes les règles des transactions du bloc. C’est le rôle d’un Full Node. La vérification simplifiée des paiements, ou SPV, décrite dans le whitepaper repose donc sur d’autres hypothèses de sécurité que la validation complète. Une réorganisation peut aussi sortir le bloc de la branche active : son contenu reste prouvable, mais la place du paiement dans l’historique courant peut changer. [2]
Dans l’arbre ordinaire de Bitcoin, les feuilles sont les identifiants txid dans l’ordre des transactions du bloc, en commençant par la Coinbase Transaction, la transaction spéciale par laquelle le mineur réclame la récompense du bloc. Les paires sont assemblées sous forme d’octets et hachées deux fois avec SHA-256. Si un étage finit par un hash sans partenaire, il est dupliqué pour ce calcul ; aucun paiement supplémentaire n’est créé. Avec une seule transaction, son txid est directement la racine. Cette duplication exige des contrôles soigneux des doublons dans l’implémentation. L’amélioration du protocole SegWit sépare aussi les données witness, notamment les signatures. Une autre empreinte cryptographique, inscrite dans la Coinbase Transaction, relie ces données au bloc. Cette empreinte est appelée witness commitment. Il ne faut donc pas confondre l’arbre txid ordinaire avec l’arbre witness. [3] [4]
Pour une vision complète, lisez aussi Block, Transaction, Block Header. Cette entrée est également citée par Block Header, Hash, SHA-256, Confirmation.