Hvis vi ser bort fra netværksdelen, kan vi sige, at Ethereum er en tilstandsmaskine, hvor transaktioner ændrer tilstande på Ethereum-netværket. En tilstand kan udtrykkes som et nøgle-værdipar. Selv om der er flere måder at repræsentere et nøgle-værdipar på, definerer Ethereum-specifikationen Modified Merkle Patricia Trie (alias MPT) som metoden til at gemme tilstande.
Grundlæggende er MPT en kombination af Patricia trie og Merkle tree med få ekstra optimeringer, der passer til Ethereums karakteristika. Derfor bør en forståelse af Patricia trie og Merkle tree gå forud for forståelsen af MPT.
Patricia trie er en datastruktur, som også kaldes Prefix tree, radix tree eller trie. Trie bruger en nøgle som en sti, så de knuder, der deler det samme præfiks, kan også dele den samme sti. Denne struktur er hurtigst til at finde fælles præfikser, er enkel at implementere og kræver lidt hukommelse. Dermed bruges den ofte til at implementere routingtabeller, systemer, der bruges i maskiner med lav specifikation som routeren.
Merkle Tree
Merkle Tree er et træ af hashes. Bladknuder gemmer data. Forældreknuder indeholder deres børns hash samt den hashede værdi af summen af deres børns hash’er. Da alle knuder undtagen bladknuder indeholder en hash, er Merkle-træet også kendt som et hash-træ.
Det kan gøres effektivt med Merkle-træet at finde ud af, om to forskellige knuder har de samme data eller ej. Du skal først sammenligne Top Hash-værdien for de to knuder. Hvis de er de samme, har de to knuder de samme data. Hvis man f.eks. ser på billedet ovenfor, hvor der er fire knuder (L1, L2, L3, L4), skal man kun kontrollere, om de har den samme Top Hash-værdi eller ej. Hvis Top Hash er forskellig, og du ønsker at vide, hvilke data der er forskellige, skal du sammenligne Hash 0 med Hash1 og kontrollere, hvilken gren der er forskellig. Ved at gøre dette vil du i sidste ende finde ud af, hvilke data der er forskellige.
Merkle Patricia Trie
I MPT, såvel som i Merkle-træet, har hver knude en hash-værdi. Hver knudes hashværdi bestemmes af sha3-hashværdien af dens indhold. Denne hash bruges også som den nøgle, der henviser til knuden. Go-ethereum bruger levelDB, og parity bruger rocksDB til at gemme tilstande. De er nøgleværdiopbevaringslagre. Nøgler og værdier, der er gemt i lageret, er ikke nøgleværdierne i Ethereum-tilstanden. Den værdi, der gemmes i lageret, er indholdet af MPT-knuden, mens nøglen er hash-koden for denne knude.
Nøgleværdierne i Ethereum-tilstanden bruges som stier på MPT’en. Nibble er den enhed, der bruges til at skelne nøgleværdier i MPT’en, så hver knude kan have op til 16 grene. Da en node desuden har sin egen værdi, er en grennode et array af 17 elementer, der består af 1 nodeværdi og 16 grene.
En node, der ikke har en barnnode, kaldes en bladnode. En bladknude består af to elementer: dens sti og værdi. Lad os f.eks. sige, at nøglen “0xBEA” indeholder 1000, og at nøglen “0xBEE” indeholder 2000. Så skal der være en grenknude med stien “0xBE”, og under denne knude vil der være knyttet to bladknuder med to stier (“0xA” og “0xE”).
I MPT er der endnu en type knuder ud over grenknuderne og bladknuderne. De er udvidelsesknuder. En udvidelsesknude er en optimeret knude af en grenknude. I Ethereums tilstand er der ret ofte grenknuder, der kun har én barnknude. Det er grunden til, at MPT komprimerer grenknuder, der kun indeholder ét barn, til udvidelsesknuder, der har en sti og barnets hash.
Da både bladknuden og udvidelsesknuden er et array af to elementer, bør der være en måde at skelne disse to forskellige knuder fra hinanden på. For at kunne foretage en sådan skelnen tilføjer MPT et præfiks til stien. Hvis knuden er et blad, og stien består af et lige antal nibbles, tilføjes 0x20 som præfiks. Hvis stien består af et ulige antal nibbles, skal man tilføje 0x3 som præfiks. Hvis knuden er en udvidelsesknude, og stien består af et lige antal nibbles, skal du tilføje 0x00 som præfiks. Hvis den består af et ulige antal nibbles, skal du tilføje 0x1 som et præfiks. Da stien, der består af et ulige antal nibbles, får en nibble som præfiks, og stien, der består af et lige antal nibbles, får to nibbles som præfiks, udtrykkes en sti altid som en byte.
(For den originale koreanske version, klik her)