Laissant de côté la partie réseau, on pourrait dire qu’Ethereum est une machine à états où les transactions modifient les états sur le réseau Ethereum. Un état peut être exprimé comme une paire clé-valeur. Bien qu’il existe plusieurs façons de représenter une paire clé-valeur, la spécification d’Ethereum définit le Trie de Patricia Merkle modifié (alias MPT) comme la méthode d’enregistrement des états.
Basiquement, MPT est une combinaison du trie de Patricia et de l’arbre de Merkle, avec quelques optimisations supplémentaires qui correspondent aux caractéristiques d’Ethereum. Ainsi, une compréhension du trie de Patricia et de l’arbre de Merkle devrait précéder la compréhension de MPT.
Le trie de Patricia est une structure de données qui est également appelée arbre de préfixe, arbre de radixe ou trie. Trie utilise une clé comme chemin d’accès afin que les nœuds qui partagent le même préfixe puissent également partager le même chemin. Cette structure est la plus rapide pour trouver des préfixes communs, elle est simple à mettre en œuvre et nécessite peu de mémoire. Par conséquent, elle est couramment utilisée pour mettre en œuvre des tables de routage, des systèmes qui sont utilisés dans des machines à faible spécification comme le routeur.
Arbre de Merkle
L’arbre de Merkle est un arbre de hachages. Les nœuds feuilles stockent les données. Les nœuds parents contiennent le hachage de leurs enfants ainsi que la valeur hachée de la somme des hachages de leurs enfants. Puisque tous les nœuds, à l’exception des nœuds feuilles, contiennent un hachage, l’arbre de Merkle est également connu comme un arbre de hachage.
Découvrir si deux nœuds différents ont les mêmes données ou non peut être fait efficacement avec l’arbre de Merkle. Vous devez d’abord comparer la valeur du hachage supérieur des deux nœuds. Si elles sont identiques, cela signifie que les deux nœuds ont les mêmes données. Par exemple, si vous regardez l’image ci-dessus, lorsqu’il y a quatre noeuds (L1, L2, L3, L4), vous devez seulement vérifier s’ils ont le même Top Hash ou non. Si le Top Hash est différent et que vous voulez savoir quelles données sont différentes, vous devez comparer Hash 0 et Hash1 et vérifier quelle branche est différente. En faisant cela, vous finirez par trouver quelles données sont différentes.
Trie de Merkle Patricia
Dans le MPT, ainsi que dans l’arbre de Merkle, chaque nœud a une valeur de hachage. Le hachage de chaque nœud est déterminé par la valeur de hachage sha3 de son contenu. Ce hachage est également utilisé comme la clé qui fait référence au nœud. Go-ethereum utilise levelDB, et parity utilise rocksDB pour stocker les états. Ce sont des stockages de type clé-valeur. Les clés et les valeurs enregistrées dans le stockage ne sont pas les clés-valeurs de l’état Ethereum. La valeur qui est enregistrée dans le stockage est le contenu du nœud MPT tandis que la clé est le hash de ce nœud.
Les valeurs-clés de l’état Ethereum sont utilisées comme chemins sur le MPT. Le Nibble est l’unité utilisée pour distinguer les valeurs clés dans la MPT, ainsi chaque nœud peut avoir jusqu’à 16 branches. De plus, comme un nœud a sa propre valeur, un nœud de branche est un tableau de 17 éléments composé d’une valeur de nœud et de 16 branches.
Un nœud qui n’a pas de nœud enfant est appelé nœud feuille. Un nœud feuille est composé de deux éléments : son chemin et sa valeur. Par exemple, disons que la clé « 0xBEA » contient 1000 et que la clé « 0xBEE » contient 2000. Alors, il devrait y avoir un nœud de branche avec le chemin « 0xBE », et, sous ce nœud, deux nœuds feuilles avec deux chemins (« 0xA » et « 0xE ») seront attachés.
Dans la TMP, il y a un autre type de nœuds en plus des nœuds de branche et des nœuds feuilles. Il s’agit des nœuds d’extension. Un nœud d’extension est un nœud optimisé du nœud de branche. Dans l’état d’Ethereum, il y a souvent des nœuds de branche qui n’ont qu’un seul nœud enfant. C’est la raison pour laquelle la MPT compresse les nœuds de branche qui ne contiennent qu’un enfant en nœuds d’extension qui ont un chemin et le hash de l’enfant.
Puisque le nœud de feuille et le nœud d’extension sont tous deux un tableau de deux éléments, il devrait y avoir un moyen de distinguer ces deux nœuds différents. Afin de faire une telle distinction, le MPT ajoute un préfixe au chemin. Si le noeud est une feuille et que le chemin consiste en un nombre pair de nibbles, vous ajoutez 0x20 comme préfixe. Si le chemin consiste en un nombre impair de nibbles, vous devez ajouter 0x3 comme préfixe. Si le nœud est un nœud d’extension et que le chemin est constitué d’un nombre pair de fragments, vous ajoutez 0x00 comme préfixe. S’il est constitué d’un nombre impair de nibbles, vous devez ajouter 0x1 comme préfixe. Parce que le chemin qui consiste en un nombre impair de nibbles obtient un nibble comme préfixe et le chemin qui consiste en un nombre pair de nibbles obtient deux nibbles comme préfixe, un chemin est toujours exprimé comme un octet.
(Pour la version originale coréenne, cliquez ici)
.