Lässt man den Netzwerkteil beiseite, könnte man sagen, dass Ethereum eine Zustandsmaschine ist, bei der Transaktionen Zustände im Ethereum-Netzwerk verändern. Ein Zustand kann als ein Schlüssel-Wert-Paar ausgedrückt werden. Obwohl es mehrere Möglichkeiten gibt, ein Schlüssel-Wert-Paar darzustellen, definiert die Ethereum-Spezifikation den modifizierten Merkle-Patricia-Trie (auch MPT genannt) als Methode zum Speichern von Zuständen.
Grundsätzlich ist MPT eine Kombination aus Patricia-Trie und Merkle-Baum, mit einigen zusätzlichen Optimierungen, die zu den Eigenschaften von Ethereum passen. Daher sollte dem Verständnis von MPT ein Verständnis des Patricia-Tries und des Merkle-Baums vorausgehen.
Der Patricia-Trie ist eine Datenstruktur, die auch Präfixbaum, Radixbaum oder Trie genannt wird. Trie verwendet einen Schlüssel als Pfad, so dass die Knoten, die das gleiche Präfix haben, auch den gleichen Pfad haben können. Diese Struktur findet am schnellsten gemeinsame Präfixe, ist einfach zu implementieren und benötigt wenig Speicherplatz. Daher wird sie häufig für die Implementierung von Routing-Tabellen verwendet, die in Maschinen mit geringer Spezifikation wie dem Router eingesetzt werden.
Merkle Tree
Merkle Tree ist ein Baum aus Hashes. Blattknoten speichern Daten. Elternknoten enthalten den Hashwert ihrer Kinder sowie den Hashwert der Summe der Hashwerte ihrer Kinder. Da alle Knoten mit Ausnahme der Blattknoten einen Hash-Wert enthalten, wird der Merkle-Baum auch als Hash-Baum bezeichnet.
Mit dem Merkle-Baum lässt sich effizient herausfinden, ob zwei verschiedene Knoten die gleichen Daten haben oder nicht. Dazu vergleicht man zunächst den Top-Hash-Wert der beiden Knoten. Wenn sie gleich sind, dann haben die beiden Knoten die gleichen Daten. In der obigen Abbildung beispielsweise müssen Sie bei vier Knoten (L1, L2, L3, L4) nur prüfen, ob sie denselben Top Hash-Wert haben oder nicht. Wenn der Top Hash unterschiedlich ist und Sie wissen wollen, welche Daten unterschiedlich sind, sollten Sie Hash 0 mit Hash1 vergleichen und prüfen, welcher Zweig unterschiedlich ist. Auf diese Weise findet man schließlich heraus, welche Daten unterschiedlich sind.
Merkle Patricia Trie
Im MPT, wie auch im Merkle-Baum, hat jeder Knoten einen Hash-Wert. Der Hashwert eines jeden Knotens wird durch den sha3-Hashwert seines Inhalts bestimmt. Dieser Hashwert wird auch als Schlüssel verwendet, der auf den Knoten verweist. Go-Ethereum verwendet levelDB und Parity verwendet rocksDB, um Zustände zu speichern. Dies sind Schlüssel-Wert-Speicher. Die im Speicher gespeicherten Schlüssel und Werte sind nicht die Schlüsselwerte des Ethereum-Zustands. Der Wert, der im Speicher gespeichert wird, ist der Inhalt des MPT-Knotens, während der Schlüssel der Hash dieses Knotens ist.
Schlüsselwerte des Ethereum-Zustands werden als Pfade auf dem MPT verwendet. Nibble ist die Einheit, die verwendet wird, um Schlüsselwerte im MPT zu unterscheiden, so dass jeder Knoten bis zu 16 Zweige haben kann. Da ein Knoten außerdem seinen eigenen Wert hat, ist ein Zweigknoten ein Array aus 17 Elementen, das aus einem Knotenwert und 16 Zweigen besteht.
Ein Knoten, der keinen Kindknoten hat, wird als Blattknoten bezeichnet. Ein Blattknoten besteht aus zwei Elementen: seinem Pfad und seinem Wert. Nehmen wir zum Beispiel an, der Schlüssel „0xBEA“ enthält 1000 und der Schlüssel „0xBEE“ enthält 2000. Dann sollte es einen Verzweigungsknoten mit dem Pfad „0xBE“ geben, und unter diesem Knoten werden zwei Blattknoten mit zwei Pfaden („0xA“ und „0xE“) angehängt.
In der MPT gibt es neben den Verzweigungsknoten und den Blattknoten eine weitere Art von Knoten. Sie sind Erweiterungsknoten. Ein Erweiterungsknoten ist ein optimierter Knoten des Zweigknotens. Im Ethereum-Zustand gibt es recht häufig Branch Nodes, die nur einen Child Node haben. Das ist der Grund, warum die MPT Zweigknoten, die nur ein Kind enthalten, in Erweiterungsknoten komprimiert, die einen Pfad und den Hash des Kindes haben.
Da sowohl der Blattknoten als auch der Erweiterungsknoten ein Array aus zwei Elementen sind, sollte es eine Möglichkeit geben, diese beiden unterschiedlichen Knoten zu unterscheiden. Um eine solche Unterscheidung zu treffen, fügt die MPT dem Pfad ein Präfix hinzu. Wenn der Knoten ein Blatt ist und der Pfad aus einer geraden Anzahl von Nibbles besteht, wird 0x20 als Präfix hinzugefügt. Besteht der Pfad aus einer ungeraden Anzahl von Nibbles, sollte man 0x3 als Präfix hinzufügen. Wenn der Knoten ein Erweiterungsknoten ist und der Pfad aus einer geraden Anzahl von Nibbles besteht, fügen Sie 0x00 als Präfix hinzu. Wenn er aus einer ungeraden Anzahl von Nibbles besteht, sollten Sie 0x1 als Präfix hinzufügen. Da der Pfad, der aus einer ungeraden Anzahl von Nibbles besteht, ein Nibble als Präfix erhält und der Pfad, der aus einer geraden Anzahl von Nibbles besteht, zwei Nibbles als Präfix erhält, wird ein Pfad immer als Byte ausgedrückt.
(Für die ursprüngliche koreanische Version, hier klicken)