W Ethereum konta są mapowane na odpowiadające im stany. Mapowanie między wszystkimi kontami Ethereum, w tym EOA i Konta kontraktowe z ich stanami są wspólnie nazywane stanami światowymi. Aby przechowywać te dane mapowania, strukturą danych stosowaną w Ethereum jest MPT. Tak więc MPT jest główną strukturą danych stosowaną w Ethereum, znanym również jako Merkle Patricia trie. Dowiedzieliśmy się o drzewkach Merkle w rozdziale Bitcoin, który już teraz zajmuje nam połowę zrozumienia MPT. MPT jest w rzeczywistości uzyskiwany przez pobieranie elementów zarówno z drzewa Merkle, jak i drzewa Patricia. Przypomnij sobie z rozdziału Bitcoin, że drzewa Merkle są binarne drzewa skrótów, w których węzły liścia zawierają skrót bloków danych, a każdy nieleafowy węzeł zawiera skróty ich węzłów potomnych. Po zaimplementowaniu takiej struktury danych łatwo jest sprawdzić, czy określona transakcja była częścią bloku. Tylko przy użyciu bardzo małej ilości informacji z całego bloku, to znaczy przy użyciu tylko gałęzi Merkle zamiast całego drzewa, dostarczenie dowodu członkostwa było dość łatwe. Drzewa merkle ułatwiają sprawną i bezpieczną weryfikację zawartości w zdecentralizowanych systemach. Zamiast pobierać każdą transakcję i każdy blok, klienci light mogą pobierać tylko łańcuch nagłówków bloków, to znaczy 80-bajtowe fragmenty danych dla każdego bloku, które zawierają tylko pięć rzeczy: skrót poprzedniego nagłówka bloku, znacznik czasu, trudność wyszukiwania , wartość nonce, która spełniała wartość PoW, a skrót główny drzewa Merkle zawierający wszystkie transakcje dla tego bloku. Chociaż jest to dość użyteczne i interesujące, zauważ tutaj, że oprócz sprawdzania dowodu członkostwa dla transakcji w bloku, nic nie możesz zrobić. Jednym szczególnym ograniczeniem jest to, że nie można udowodnić żadnych informacji o bieżącym stanie (np. Całkowite zasoby aktywów cyfrowych, rejestracja nazw, status umów finansowych). Nawet w celu sprawdzenia, ile Bitcoinów posiadasz, wiąże się to z dużą ilością zapytań i weryfikacji. Z drugiej strony drzewa Patricia są formą drzew Radix. Nazwa PATRICIA oznacza „Praktyczny algorytm odzyskiwania informacji zakodowanych alfanumerycznie”. Drzewo Patricia ułatwia wydajne operacje wstawiania / usuwania. Wyszukiwanie klucz-wartość w drzewie Patricia jest bardzo wydajne. Klucze są zawsze zakodowane na ścieżce. Zatem „klucz” to ścieżka, którą pobierasz od korzenia do węzła liścia, w którym przechowywana jest „wartość”. Klucze to zwykle ciągi znaków, które pomagają zejść w dół ścieżki, gdzie każdy znak wskazuje, który węzeł potomny ma podążać, aby dotrzeć do węzła liścia i znaleźć w nim zapisaną wartość. Tak więc MPT zapewniają kryptograficznie uwierzytelnioną strukturę danych używaną do przechowywania wszystkich powiązań (klucz, wartość) w Ethereum. Są w pełni deterministyczne, co oznacza, że drzewo Patricia z tymi samymi powiązaniami (klucz, wartość) z pewnością będzie takie samo aż do ostatniego bajtu. Operacje wstawiania, wyszukiwania i usuwania są dość wydajne przy złożoności O (log (n)). Ze względu na część Merkle w MPT, skrót węzła jest używany jako wskaźnik do węzła, a MPT jest odpowiednio skonstruowany, gdzie Key == SHA3 (RLP (wartość)) Podczas gdy część Merkle zapewnia odporną na manipulacje i deterministyczną strukturę drzewa, część Patricia zapewnia wydajną funkcję wyszukiwania informacji. Więc jeśli zauważysz uważnie, węzeł główny w MPT staje się kryptograficznym odciskiem palca całej struktury danych. W sieci Ethereum P2P, gdy transakcje są transmitowane przewodowo, są one montowane przez każdy węzeł wydobywczy, który je otrzymał. Węzły następnie tworzą Drzewo (a.k.a. trie) i obliczają wartość skrótu głównego, aby uwzględnić ją w nagłówku bloku. Chociaż transakcje są przechowywane lokalnie w drzewie, są one wysyłane do innych węzłów lub klientów po ich serializacji na listy. Strony odbierające muszą je przekształcić z postaci szeregowej z powrotem w celu utworzenia drzewa transakcji w celu weryfikacji względem wartości skrótu głównego. Zauważ też, że w Ethereum, MPT są nieco zmodyfikowane, aby lepiej pasowały do implementacji Ethereum. Zamiast binarnego używany jest szesnastkowy – znaki X z 16-znakowego „alfabetu”. Dlatego węzły w drzewie lub trie mają 16 węzłów potomnych (16-znakowy alfabet szesnastkowy) i maksymalną głębokość X. Aby dać znać, a W wielu miejscach znak szesnastkowy nazywany jest „skubkiem”. Podstawową ideą MPT w Ethereum jest to, że dla pojedynczej operacji zmodyfikuje tylko minimalną liczbę węzłów, aby ponownie obliczyć skrót główny. W ten sposób pamięć i złożoność są minimalne.