Pomineme-li síťovou část, můžeme říci, že Ethereum je stavový stroj, kde transakce modifikují stavy v síti Ethereum. Stav lze vyjádřit jako dvojici klíč-hodnota. Ačkoli existuje několik způsobů, jak reprezentovat dvojici klíč-hodnota, specifikace Etherea definuje jako metodu ukládání stavů Modifikovaný Merkleův trie Patricia (neboli MPT).
V podstatě je MPT kombinací Patricia trie a Merkleova stromu s několika dalšími optimalizacemi, které odpovídají charakteristikám Etherea. Pochopení Patricia trie a Merkleho stromu by tedy mělo předcházet pochopení MPT.
Patricia trie je datová struktura, která se také nazývá prefixový strom, radixový strom nebo trie. Trie používá klíč jako cestu, takže uzly, které mají stejný prefix, mohou mít také stejnou cestu. Tato struktura je nejrychlejší při hledání společných prefixů, je jednoduchá na implementaci a vyžaduje malou paměť. Proto se běžně používá pro implementaci směrovacích tabulek, systémů, které se používají ve strojích s nízkou specifikací, jako je směrovač.
Merkleho strom
Merkleho strom je strom hashů. V listových uzlech jsou uložena data. Nadřazené uzly obsahují hash svých dětí a také hashovanou hodnotu součtu hashů svých dětí. Protože všechny uzly kromě listových obsahují hash, je Merklův strom známý také jako hashovací strom.
Zjistit, zda dva různé uzly mají stejná data nebo ne, lze efektivně pomocí Merklova stromu. Nejprve je třeba porovnat hodnotu Top Hash obou uzlů. Pokud jsou stejné, pak mají oba uzly stejná data. Pokud se například podíváte na obrázek výše, kdy jsou čtyři uzly (L1, L2, L3, L4), stačí zkontrolovat, zda mají stejnou hodnotu Top Hash, nebo ne. Pokud se Top Hash liší a vy chcete vědět, která data se liší, měli byste porovnat Hash 0 s Hash1 a zkontrolovat, která větev se liší. Tímto postupem nakonec zjistíte, která data se liší.
Merkleho patricijský strom
V MPT, stejně jako v Merklově stromu, má každý uzel hodnotu hash. O hashi každého uzlu rozhoduje hodnota hashe sha3 jeho obsahu. Tento hash se také používá jako klíč, který odkazuje na daný uzel. Go-ethereum používá levelDB a parita používá k ukládání stavů rocksDB. Jedná se o úložiště typu klíč-hodnota. Klíče a hodnoty uložené v úložišti nejsou klíčovými hodnotami stavu Ethereum. Hodnota, která je uložena v úložišti, je obsahem uzlu MPT, zatímco klíč je hash tohoto uzlu.
Klíčové hodnoty stavu Ethereum se používají jako cesty na MPT. Nibble je jednotka používaná k rozlišení hodnot klíčů v MPT, takže každý uzel může mít až 16 větví. Navíc vzhledem k tomu, že uzel má svou vlastní hodnotu, je větev uzlu polem 17 položek složeným z 1 hodnoty uzlu a 16 větví.
Uzel, který nemá podřízený uzel, se nazývá listový uzel. Listový uzel se skládá ze dvou položek: své cesty a hodnoty. Řekněme například, že klíč „0xBEA“ obsahuje 1000 a klíč „0xBEE“ obsahuje 2000. Pak by měl existovat větvový uzel s cestou „0xBE“ a pod tímto uzlem budou připojeny dva listové uzly se dvěma cestami („0xA“ a „0xE“).
V MPT existuje kromě větvových a listových uzlů ještě jeden typ uzlů. Jsou to rozšiřující uzly. Rozšiřující uzel je optimalizovaný uzel větvového uzlu. Ve stavu Ethereum se poměrně často vyskytují větvové uzly, které mají pouze jeden podřízený uzel. To je důvod, proč MPT komprimuje uzly větví, které obsahují pouze jednoho potomka, do uzlů rozšíření, které mají cestu a hash potomka.
Protože jak uzel listu, tak uzel rozšíření jsou pole dvou položek, měl by existovat způsob, jak tyto dva různé uzly rozlišit. Aby bylo možné takové rozlišení provést, přidává MPT k cestě prefix. Pokud je uzel list a cesta se skládá ze sudého počtu nibblů, přidá se jako prefix 0x20. Pokud se cesta skládá z lichého počtu nibbles, je třeba jako prefix přidat 0x3. Pokud je uzel rozšiřujícím uzlem a cesta se skládá ze sudého počtu vsuvek, přidejte jako prefix 0x00. Pokud se skládá z lichého počtu nibbles, měli byste jako prefix přidat 0x1. Protože cesta, která se skládá z lichého počtu nibblů, dostane jako prefix jeden nibbl a cesta, která se skládá ze sudého počtu nibblů, dostane jako prefix dva nibbly, cesta se vždy vyjadřuje jako bajt.
(Pro původní korejskou verzi klikněte zde)