Les arbres de Merkle

Un bloc de Bitcoin peut contenir plusieurs milliers de transactions. Comment les résumer en une seule petite empreinte, tout en gardant la possibilité de prouver qu'une transaction précise s'y trouve, sans télécharger le bloc entier ? La réponse est une structure élégante : l'arbre de Merkle.

L'idée : hacher par paires

On part des transactions (les feuilles de l'arbre). On calcule l'empreinte de chacune, puis on regroupe ces empreintes deux par deux et on hache chaque paire. On obtient deux fois moins d'empreintes. On recommence, niveau après niveau, jusqu'à n'en avoir plus qu'une seule : la racine de Merkle (en anglais Merkle root).

                    Racine
                 H(H12 + H34)
                /            \
          H12                    H34
       H(H1+H2)               H(H3+H4)
        /     \                /     \
     H1        H2           H3        H4
     |         |            |         |
    Tx1       Tx2          Tx3       Tx4

Ici H1 = H(Tx1), puis H12 = H(H1 + H2), et enfin Racine = H(H12 + H34). La racine est un condensé de toutes les transactions : changer n'importe quelle transaction change son empreinte de feuille, ce qui remonte jusqu'à modifier la racine.

Cette racine est stockée dans l'en-tête du bloc (le petit résumé qui est effectivement haché pour chaîner les blocs). L'en-tête reste minuscule, quel que soit le nombre de transactions.

L'avantage décisif : la preuve d'inclusion

Le vrai pouvoir de l'arbre de Merkle est la preuve d'inclusion (Merkle proof). Pour convaincre quelqu'un que Tx3 est bien dans le bloc, on n'a pas besoin de lui fournir toutes les transactions : il suffit de lui donner les quelques empreintes situées sur le chemin de Tx3 vers la racine.

Pour prouver que Tx3 est incluse, il faut fournir :
  - H4   (le frère de H3)
  - H12  (le frère de H34)
Le vérificateur calcule alors :
  H3   = H(Tx3)              (il a Tx3)
  H34  = H(H3 + H4)
  Rac. = H(H12 + H34)
puis compare Rac. à la racine de Merkle de l'en-tête.
Si elles coïncident : Tx3 est prouvée incluse.

Le vérificateur n'a eu besoin que de 2 empreintes au lieu des 4 transactions.

Pourquoi log(n)

Le nombre d'empreintes à fournir est la hauteur de l'arbre. Comme on divise le nombre de nœuds par deux à chaque niveau, cette hauteur vaut environ log₂(n).

Nombre de transactions	Empreintes dans la preuve
4	2
1 024	10
1 000 000	~20

Pour un million de transactions, une vingtaine d'empreintes suffisent à prouver l'inclusion. C'est ce qui permet aux clients « légers » (SPV) de vérifier une transaction sans stocker toute la blockchain.

En résumé

• Un arbre de Merkle résume des milliers de transactions en hachant par paires jusqu'à une unique empreinte : la racine de Merkle.
• Cette racine est stockée dans l'en-tête du bloc ; modifier une transaction change la racine.
• La preuve d'inclusion démontre qu'une transaction est présente en ne fournissant qu'environ log₂(n) empreintes, sans télécharger tout le bloc.
• C'est ce qui rend possibles les portefeuilles légers, capables de vérifier sans tout stocker.