Glossaire / Minage et consensus
Arbre de Merkle
- Qu'est-ce qu'un arbre de Merkle ?
- Un arbre de Merkle est la pyramide de hachages qui compresse toutes les transactions d'un bloc en une seule valeur de 32 octets, ce qui permet de prouver qu'un paiement donné appartient au bloc sans avoir le reste.
Appariez les hachages des transactions, hachez chaque paire, puis répétez jusqu'à ce qu'il ne reste qu'un hachage. Cette valeur unique figure dans l'en-tête de bloc, et prouver qu'une transaction en fait partie ne demande que les hachages d'un seul chemin : onze d'entre eux, soit 352 octets, pour un bloc contenant 2 000 paiements. C'est pourquoi un portefeuille sur téléphone peut vérifier que vos bitcoins sont bien arrivés sans télécharger le bloc.
Comment cela fonctionne
Un arbre de Merkle transforme une liste en pyramide en hachant les voisins ensemble, niveau par niveau, jusqu'à ce qu'il ne reste qu'un hachage.
Les feuilles sont les identifiants de transaction dans l'ordre où le mineur les a placés. Bitcoin combine chaque paire en concaténant les deux valeurs de 32 octets et en appliquant SHA-256 au résultat deux fois. Lorsqu'un niveau contient un nombre impair d'entrées, la dernière est appariée avec une copie d'elle-même, ce qui garde l'algorithme simple et a causé une fois de vrais problèmes : la vulnérabilité cataloguée sous CVE-2012-2459, divulguée en mai 2012 et corrigée le même mois, exploitait cette duplication pour construire un bloc qui semblait invalide aux nœuds alors que les transactions sous-jacentes étaient correctes.
Le gain est logarithmique. Doubler le nombre de transactions ajoute un niveau, et non un hachage par transaction. Un bloc de 1 024 paiements demande dix hachages pour prouver l'appartenance, soit 320 octets. Quatre mille quatre-vingt-seize en demandent douze, soit 384 octets. Celui qui vérifie la preuve recalcule le chemin vers le haut et compare le résultat à la racine à laquelle il se fie déjà depuis l'en-tête, et il est impossible de falsifier un chemin sans casser SHA-256.
Rien de tout cela ne vient de bitcoin. Ralph Merkle a décrit cette construction dans la demande de brevet devenue US 4 309 569, déposée en 1979 et accordée en janvier 1982. Le livre blanc cite ses travaux et fait deux usages de l'arbre : élaguer les transactions dépensées des anciens blocs pour économiser de l'espace disque, à la section 7, et permettre à un client de vérifier un paiement en ne détenant que les en-têtes, à la section 8.
Où le voir
Les arbres de Merkle apparaissent partout où un système doit prouver qu'un élément appartient à un vaste ensemble sans transmettre l'ensemble.
Dans bitcoin, chaque en-tête de bloc porte le sommet d'un tel arbre. Un nœud reconstruit l'arbre à partir des transactions qu'il a reçues et rejette le bloc si le résultat ne correspond pas. Bitcoin Core expose directement ce mécanisme : gettxoutproof produit une preuve sérialisée qu'une transaction a été incluse dans un bloc, et verifytxoutproof en vérifie une, ce qui est un moyen pratique de fournir à quelqu'un la preuve d'un paiement sans lui donner un portefeuille.
Ailleurs dans bitcoin, Taproot en construit un second : les conditions de dépense alternatives d'une sortie Taproot sont disposées en arbre, si bien que révéler la branche utilisée ne divulgue rien sur les branches non utilisées. Hors de bitcoin, la même forme sous-tend l'historique des commits de Git, les journaux de Certificate Transparency qui détectent les certificats web mal délivrés, et les contrôles d'intégrité des données du système de fichiers ZFS.
Pour un utilisateur de portefeuille, la conséquence visible est modeste et utile. Un client léger qui détient quelques dizaines de mégaoctets d'en-têtes peut confirmer que votre transaction figure dans un bloc précis, à une profondeur précise, et n'obtenir une réponse fausse que si quelqu'un a produit une preuve de travail valide sur une chaîne factice, ce qui coûte de l'argent réel.
Arbre de Merkle vs racine de Merkle
L'arbre de Merkle est la structure de travail ; la racine de Merkle est la seule valeur conservée ensuite. Un nœud construit toute la pyramide en mémoire pendant la validation d'un bloc puis la jette, ne conservant que les 32 octets du sommet, car tout ce qui se trouve en dessous peut être régénéré à partir des transactions. Quand un explorateur vous montre un champ appelé racine de Merkle, c'est ce survivant. Personne ne stocke l'arbre, et personne n'en a besoin.