Om vi bortser från nätverksdelen kan vi säga att Ethereum är en tillståndsmaskin där transaktioner ändrar tillstånden i nätverket Ethereum. Ett tillstånd kan uttryckas som ett nyckel-värdepar. Även om det finns flera sätt att representera ett nyckel-värdepar definierar specifikationen för Ethereum Modified Merkle Patricia Trie (a.k.a MPT) som metod för att spara tillstånd.
I grund och botten är MPT en kombination av Patricia trie och Merkle tree, med några ytterligare optimeringar som passar Ethereums egenskaper. Därför bör en förståelse av Patricia trie och Merkle tree föregå förståelsen av MPT.
Patricia trie är en datastruktur som också kallas Prefix tree, radix tree eller trie. Trie använder en nyckel som en sökväg så att noder som delar samma prefix också kan dela samma sökväg. Denna struktur är snabbast när det gäller att hitta gemensamma prefix, är enkel att implementera och kräver litet minne. Därmed används den ofta för att implementera routingtabeller, system som används i maskiner med låg specifikation som routern.
Merkle Tree
Merkle tree är ett träd av hashes. Bladnoderna lagrar data. Föräldranoder innehåller sina barns hash samt det hashade värdet av summan av deras barns hash. Eftersom alla noder utom bladnoderna innehåller en hash kallas Merkle-trädet också för ett hashträd.
Finnandet av huruvida två olika noder har samma data eller inte kan göras effektivt med Merkle-trädet. Du måste först jämföra Top Hash-värdet för de två noderna. Om de är desamma har de två noderna samma data. Om du till exempel tittar på bilden ovan, när det finns fyra noder (L1, L2, L3, L4), behöver du bara kontrollera om de har samma Top Hash-värde eller inte. Om Top Hash är olika och du vill veta vilka data som är olika, bör du jämföra Hash 0 med Hash1 och kontrollera vilken gren som är olika. Genom att göra så kommer du så småningom att få reda på vilka data som är olika.
Merkle Patricia Trie
I MPT, liksom i Merkle-trädet, har varje nod ett hash-värde. Varje nods hashvärde bestäms av sha3-hashvärdet för dess innehåll. Detta hashvärde används också som nyckel som hänvisar till noden. Go-ethereum använder levelDB och parity använder rocksDB för att lagra tillstånd. De är nyckelvärdeslagringar. Nycklar och värden som sparas i lagret är inte nyckelvärdena i Ethereum-tillståndet. Värdet som lagras i lagret är innehållet i MPT-noden medan nyckeln är hash för denna nod.
Nyckelvärden i Ethereum-tillståndet används som sökvägar på MPT. Nibble är den enhet som används för att särskilja nyckelvärden i MPT, så varje nod kan ha upp till 16 grenar. Eftersom en nod har sitt eget värde är en grennod dessutom en matris med 17 objekt som består av 1 nodvärde och 16 grenar.
En nod som inte har en barnnod kallas för en bladnod. En bladnod består av två objekt: dess sökväg och värde. Låt oss till exempel säga att nyckeln ”0xBEA” innehåller 1000 och nyckeln ”0xBEE” innehåller 2000. Då bör det finnas en grennod med sökvägen ”0xBE”, och under den noden kommer två bladnoder med två sökvägar (”0xA” och ”0xE”) att kopplas till.
I MPT finns det ytterligare en typ av noder förutom gren- och bladnoderna. De är förlängningsnoder. En förlängningsnod är en optimerad nod till grennoden. I Ethereum-tillståndet finns det ganska ofta grennoder som bara har en barnnod. Detta är anledningen till att MPT komprimerar grennoder som endast innehåller ett barn till förlängningsnoder som har en sökväg och barnets hash.
Med tanke på att både bladnoden och förlängningsnoden är en matris med två objekt bör det finnas ett sätt att särskilja dessa två olika noder. För att göra en sådan distinktion lägger MPT till ett prefix till sökvägen. Om noden är ett blad och sökvägen består av ett jämnt antal nibbles, lägger man till 0x20 som prefix. Om banan består av ett udda antal nibbles ska du lägga till 0x3 som prefix. Om noden är en förlängningsnod och sökvägen består av ett jämnt antal nibbles ska du lägga till 0x00 som prefix. Om den består av ett udda antal nibbles ska du lägga till 0x1 som prefix. Eftersom den väg som består av ett udda antal nibbles får en nibble som prefix och den väg som består av ett jämnt antal nibbles får två nibbles som prefix, uttrycks en väg alltid som en byte.
(För den koreanska originalversionen, klicka här)