Pomijając część sieciową, można powiedzieć, że Ethereum to maszyna stanowa, w której transakcje modyfikują stany w sieci Ethereum. Stan może być wyrażony jako para klucz-wartość. Chociaż istnieje kilka sposobów reprezentowania pary klucz-wartość, specyfikacja Ethereum definiuje Zmodyfikowane Merkle Patricia Trie (a.k.a MPT) jako metodę zapisywania stanów.
Podstawowo MPT jest połączeniem Patricia trie i Merkle tree, z kilkoma dodatkowymi optymalizacjami, które pasują do charakterystyki Ethereum. Tak więc zrozumienie trie Patricia i drzewa Merkle powinno poprzedzać zrozumienie MPT.
Patricia trie jest strukturą danych, która jest również nazywana drzewem prefiksowym, drzewem radix lub trie. Trie używa klucza jako ścieżki, więc węzły, które mają ten sam prefiks, mogą również dzielić tę samą ścieżkę. Struktura ta jest najszybsza w znajdowaniu wspólnych prefiksów, prosta w implementacji i wymaga niewielkiej pamięci. Dlatego jest powszechnie używana do implementacji tablic routingu, systemów, które są używane w maszynach o niskiej specyfikacji, takich jak router.
Drzewo Merkle
Drzewo Merkle jest drzewem haszów. Węzły liści przechowują dane. Węzły nadrzędne zawierają hasz swoich dzieci oraz wartość sumy haszów swoich dzieci. Ponieważ wszystkie węzły oprócz węzłów liści zawierają hash, drzewo Merkle’a jest również znane jako drzewo haszujące.
Znalezienie, czy dwa różne węzły mają te same dane, czy nie, może być skutecznie wykonane za pomocą drzewa Merkle’a. Najpierw trzeba porównać wartość Top Hash dwóch węzłów. Jeśli są one takie same, to te dwa węzły mają te same dane. Na przykład, jeśli spojrzeć na powyższy rysunek, gdy istnieją cztery węzły (L1, L2, L3, L4), wystarczy sprawdzić, czy mają one ten sam Top Hash, czy nie. Jeśli Top Hash jest inny i chcesz wiedzieć, które dane są różne, powinieneś porównać Hash 0 z Hash1 i sprawdzić, która gałąź jest inna. Postępując w ten sposób, ostatecznie dowiesz się, które dane są różne.
Merkle Patricia Trie
W MPT, podobnie jak w drzewie Merkle’a, każdy węzeł ma wartość hash. O hashu każdego węzła decyduje wartość sha3 hash jego zawartości. Ten hash jest również używany jako klucz, który odnosi się do węzła. Go-ethereum używa levelDB, a parity używa rocksDB do przechowywania stanów. Są to magazyny klucz-wartość. Klucze i wartości zapisane w magazynie nie są kluczami-wartościami stanu Ethereum. Wartość, która jest przechowywana w magazynie, jest zawartością węzła MPT, podczas gdy klucz jest hashem tego węzła.
Key-wartości stanu Ethereum są używane jako ścieżki na MPT. Nibble jest jednostką używaną do rozróżniania wartości kluczy w MPT, więc każdy węzeł może mieć do 16 gałęzi. Dodatkowo, ponieważ węzeł ma swoją własną wartość, węzeł gałęzi jest tablicą 17 elementów składających się z 1 wartości węzła i 16 gałęzi.
Węzeł, który nie ma węzła dziecka, jest nazywany węzłem liści. Węzeł liściowy składa się z dwóch elementów: jego ścieżki i wartości. Na przykład, powiedzmy, że klucz „0xBEA” zawiera 1000, a klucz „0xBEE” zawiera 2000. Wówczas powinien powstać węzeł gałęzi ze ścieżką „0xBE”, a pod tym węzłem będą dołączone dwa węzły liści z dwiema ścieżkami („0xA” i „0xE”).
W MPT oprócz węzłów gałęzi i węzłów liści istnieje jeszcze jeden rodzaj węzłów. Są to węzły rozszerzające. Węzeł rozszerzenia jest zoptymalizowanym węzłem węzła gałęzi. W stanie Ethereum dość często zdarzają się węzły rozgałęzione, które mają tylko jeden węzeł potomny. Jest to powód, dla którego MPT kompresuje węzły gałęzi, które zawierają tylko jedno dziecko, do węzłów rozszerzenia, które mają ścieżkę i hash dziecka.
Ponieważ zarówno węzeł liści, jak i węzeł rozszerzenia są tablicą dwóch elementów, powinien istnieć sposób na rozróżnienie tych dwóch różnych węzłów. Aby dokonać takiego rozróżnienia, MPT dodaje prefiks do ścieżki. Jeśli węzeł jest liściem i ścieżka składa się z parzystej liczby nibbli, dodajemy 0x20 jako prefiks. Jeśli ścieżka składa się z nieparzystej liczby nibbli, powinieneś dodać 0x3 jako prefiks. Jeśli węzeł jest węzłem rozszerzenia i ścieżka składa się z parzystej liczby nibble, dodajesz 0x00 jako prefiks. Jeśli ścieżka składa się z nieparzystej liczby pól, powinieneś dodać 0x1 jako prefiks. Ponieważ ścieżka, która składa się z nieparzystej liczby nibble dostaje nibble jako prefiks, a ścieżka, która składa się z parzystej liczby nibble dostaje dwa nibble jako prefiks, ścieżka jest zawsze wyrażona jako bajt.
(Dla oryginalnej koreańskiej wersji, kliknij tutaj)