Définition

Merkle-Patricia Trie : définition

Aussi appelé : MPT

Le Merkle-Patricia Trie (MPT) est la structure de données utilisée par Ethereum pour stocker sous forme clé-valeur l'état des comptes, le stockage des contrats, les transactions et les reçus, tout en produisant une empreinte unique de l'ensemble, la racine.

Thème : Ethereum et smart contracts

Merkle-Patricia Trie : comment ça marche ?

Le MPT combine deux idées. D'un côté, l'arbre de Merkle : chaque nœud contient le hachage de ses enfants, de sorte que la racine résume l'intégralité des données et que la moindre modification change cette racine. De l'autre, l'arbre Patricia, ou trie compressé : les clés sont découpées caractère par caractère et les chemins sans embranchement sont raccourcis, ce qui permet de retrouver rapidement une valeur à partir de sa clé et de la mettre à jour efficacement.

Dans Ethereum, l'en-tête de chaque bloc contient plusieurs racines de ce type : la racine d'état (tous les comptes avec leur solde, leur nonce, leur code et leur stockage), la racine des transactions et celle des reçus. Grâce à cette structure, un client léger peut vérifier qu'un compte possède bien un certain solde à partir d'une preuve de Merkle, sans télécharger tout l'état. Le revers est un coût de stockage et de calcul important, ce qui motive des recherches sur des structures plus compactes, comme les arbres Verkle.

Un exemple concret

Un portefeuille léger veut afficher le solde de l'adresse de Marc sans faire entièrement confiance au serveur qu'il interroge. Il demande une preuve : la liste des nœuds qui relient le compte de Marc à la racine d'état du dernier bloc. En recalculant les hachages, le portefeuille vérifie que le solde fourni est cohérent avec la racine publiée dans l'en-tête du bloc.

À ne pas confondre avec

Arbre de Merkle : L'arbre de Merkle classique, utilisé par exemple pour les transactions d'un bloc Bitcoin, sert surtout à prouver l'appartenance à une liste, alors que le MPT est une structure clé-valeur modifiable conçue pour stocker un état.

Questions fréquentes sur Merkle-Patricia Trie

À quoi sert la racine d'état dans Ethereum ?

C'est une empreinte cryptographique de l'état complet du réseau à un bloc donné. Toute différence de solde ou de stockage produirait une racine différente, ce qui permet aux nœuds de vérifier qu'ils sont d'accord.

Pourquoi parle-t-on de remplacer le Merkle-Patricia Trie ?

Ses preuves sont volumineuses, ce qui complique l'exécution de nœuds légers. Des structures comme les arbres Verkle sont étudiées pour produire des preuves beaucoup plus petites.