A hálózati részt félretéve azt mondhatjuk, hogy az Ethereum egy állapotgép, ahol a tranzakciók módosítják az Ethereum hálózat állapotát. Egy állapotot kulcs-érték párosként lehet kifejezni. Bár egy kulcs-érték pár ábrázolásának több módja is létezik, az Ethereum specifikációja az állapotok mentésének módszereként a Modified Merkle Patricia Trie-t (más néven MPT) határozza meg.
Az MPT lényegében a Patricia trie és a Merkle-fa kombinációja, néhány további, az Ethereum jellemzőihez illeszkedő optimalizálással. Ezért a Patricia trie és a Merkle-fa megértésének meg kell előznie az MPT megértését.
A Patricia trie egy adatszerkezet, amelyet Prefix-fának, radix-fának vagy trie-nek is neveznek. A trie egy kulcsot használ útvonalként, így az azonos előtaggal rendelkező csomópontok ugyanazt az útvonalat is használhatják. Ez a struktúra a leggyorsabb a közös előtagok megtalálásában, egyszerűen implementálható, és kis memóriát igényel. Ezáltal gyakran használják útválasztó táblák, rendszerek megvalósítására, amelyeket alacsony specifikációjú gépekben, például a routerekben használnak.
Merkle fa
A Merkle fa egy hashákból álló fa. A levélcsomópontok adatokat tárolnak. A szülő csomópontok tartalmazzák gyermekeik hash-értékét, valamint gyermekeik hash-értékeinek összegének hash-értékét. Mivel a levélcsomópontok kivételével minden csomópont tartalmaz hash-t, a Merkle-fát hash-fának is nevezik.
A Merkle-fa segítségével hatékonyan megállapítható, hogy két különböző csomópontban ugyanaz az adat van-e vagy sem. Először össze kell hasonlítanunk a két csomópont Top Hash értékét. Ha ezek megegyeznek, akkor a két csomópontnak ugyanazok az adatai. Ha például megnézzük a fenti képet, amikor négy csomópont van (L1, L2, L3, L4), akkor csak azt kell ellenőriznünk, hogy ugyanaz-e a Top Hash értékük vagy sem. Ha a Top Hash különbözik, és tudni szeretné, hogy melyik adat különbözik, akkor a Hash 0-t kell összehasonlítania a Hash1-gyel, és meg kell vizsgálnia, hogy melyik ág különbözik. Így végül megtudjuk, hogy melyik adat különbözik.
Merkle Patricia Trie
Az MPT-ben, akárcsak a Merkle-fában, minden csomópontnak van egy hash-értéke. Minden csomópont hash-értékét a tartalmának sha3 hash-értéke határozza meg. Ez a hash-érték egyben a csomópontra utaló kulcsként is szolgál. A Go-ethereum a levelDB-t, a parity pedig a rocksDB-t használja az állapotok tárolására. Ezek kulcsérték-tárolók. A tárolókban tárolt kulcsok és értékek nem az Ethereum állapotának kulcsértékei. A tárolóban tárolt érték az MPT csomópont tartalma, míg a kulcs ennek a csomópontnak a hash-ja.
Az Ethereum-állapot kulcs-értékeit az MPT-n útvonalként használják. A nibble a kulcsértékek megkülönböztetésére használt egység az MPT-ben, így minden csomópontnak legfeljebb 16 elágazása lehet. Továbbá, mivel egy csomópontnak saját értéke van, egy elágazó csomópont egy 17 elemű tömb, amely 1 csomópontértékből és 16 elágazásból áll.
Az olyan csomópontot, amelynek nincs gyermekcsomópontja, levélcsomópontnak nevezzük. Egy levélcsomópont két elemből áll: az útvonalából és az értékéből. Tegyük fel például, hogy a “0xBEA” kulcs 1000-et, a “0xBEE” kulcs pedig 2000-et tartalmaz. Ekkor létre kell jönnie egy ágcsomópontnak a “0xBE” útvonallal, és e csomópont alá két levélcsomópont fog kapcsolódni két útvonallal (“0xA” és “0xE”).
Az MPT-ben az ágcsomópontokon és a levélcsomópontokon kívül van még egy csomóponttípus. Ezek a kiterjesztési csomópontok. A kiterjesztési csomópont az ágcsomópont optimalizált csomópontja. Az Ethereum állapotában elég gyakran vannak olyan ágcsomópontok, amelyeknek csak egy gyermekcsomópontjuk van. Ez az oka annak, hogy az MPT a csak egy gyermeket tartalmazó ágcsomópontokat kiterjesztési csomópontokká tömöríti, amelyeknek van egy útvonala és a gyermek hash-ja.
Mivel mind a levélcsomópont, mind a kiterjesztési csomópont egy két elemből álló tömb, valamilyen módon meg kell különböztetni ezt a két különböző csomópontot. Az ilyen megkülönböztetés érdekében az MPT egy előtagot ad az útvonalhoz. Ha a csomópont levél, és az útvonal páros számú nibble-ből áll, akkor 0x20 előtagot ad hozzá. Ha az útvonal páratlan számú nibble-ből áll, akkor 0x3 előtagot kell hozzáadni. Ha a csomópont egy kiterjesztő csomópont, és az útvonal páros számú nibble-ből áll, 0x00 előtagot kell hozzáadni. Ha a csomópont páratlan számú nibble-ből áll, akkor 0x1 előtagot kell hozzáadni. Mivel a páratlan számú nibble-ből álló útvonal egy nibble-t kap előtagként, a páros számú nibble-ből álló útvonal pedig két nibble-t kap előtagként, az útvonal mindig bájtként van kifejezve.
(Az eredeti koreai változatért kattintson ide)