Het netwerkgedeelte buiten beschouwing latend, zouden we kunnen zeggen dat Ethereum een toestandsmachine is waarbij transacties toestanden op het Ethereum-netwerk wijzigen. Een toestand kan worden uitgedrukt als een sleutel-waarde paar. Hoewel er verschillende manieren zijn om een sleutel-waarde paar te representeren, definieert de Ethereum specificatie de Modified Merkle Patricia Trie (a.k.a MPT) als de methode om toestanden op te slaan.
Basically, MPT is een combinatie van Patricia trie en Merkle tree, met een paar extra optimalisaties die passen bij de kenmerken van Ethereum. Een begrip van de Patricia trie en Merkle tree zou dus vooraf moeten gaan aan het begrip van MPT.
Patricia trie is een datastructuur die ook wel Prefix tree, radix tree of trie wordt genoemd. Trie gebruikt een sleutel als een pad zodat de knooppunten die dezelfde prefix delen ook hetzelfde pad kunnen delen. Deze structuur is het snelst in het vinden van gemeenschappelijke voorvoegsels, eenvoudig te implementeren, en heeft weinig geheugen nodig. Daarom wordt het vaak gebruikt voor het implementeren van routing tabellen, systemen die worden gebruikt in lage specificatie machines zoals de router.
Merkle Tree
Merkle tree is een boom van hashes. Bladknopen slaan gegevens op. Ouder-knopen bevatten de hash van hun kinderen en de hashed-waarde van de som van de hashes van hun kinderen. Aangezien alle knooppunten behalve de bladknooppunten een hash bevatten, wordt de Merkle boom ook wel een hash boom genoemd.
Uitzoeken of twee verschillende knooppunten dezelfde gegevens hebben of niet, kan efficiënt worden gedaan met de Merkle boom. Je moet eerst de Top Hash waarde van de twee nodes vergelijken. Als die gelijk zijn, dan hebben de twee nodes dezelfde data. Als u bijvoorbeeld naar de bovenstaande afbeelding kijkt, wanneer er vier nodes zijn (L1, L2, L3, L4), hoeft u alleen maar te controleren of ze dezelfde Top Hash hebben of niet. Als de Top Hash verschillend is en je wilt weten welke gegevens verschillend zijn, dan moet je Hash 0 vergelijken met Hash1 en kijken welke tak verschillend is. Door dit te doen, zult u uiteindelijk te weten komen welke gegevens verschillend zijn.
Merkle Patricia Trie
In de MPT, evenals in de Merkle boom, heeft elke knoop een hash waarde. De hash van elke knoop wordt bepaald door de sha3 hashwaarde van zijn inhoud. Deze hash wordt ook gebruikt als de sleutel die naar de node verwijst. Go-ethereum gebruikt levelDB, en parity gebruikt rocksDB om staten op te slaan. Het zijn sleutel-waarde opslagplaatsen. Sleutels en waarden die in de opslag worden opgeslagen zijn niet de sleutelwaarden van de Ethereum-toestand. De waarde die in de opslag wordt opgeslagen is de inhoud van MPT node, terwijl de sleutel de hash van deze node is.
Sleutel-waarden van de Ethereum-staat worden gebruikt als paden op de MPT. Nibble is de eenheid die wordt gebruikt om sleutelwaarden in de MPT te onderscheiden, dus elk knooppunt kan maximaal 16 takken hebben. Bovendien, aangezien een node zijn eigen waarde heeft, is een vertakkingsnode een array van 17 items bestaande uit 1 nodewaarde en 16 vertakkingen.
Een node die geen kindnode heeft, wordt een bladnode genoemd. Een bladknoop bestaat uit twee items: zijn pad en zijn waarde. Laten we bijvoorbeeld zeggen dat de sleutel “0xBEA” 1000 bevat en de sleutel “0xBEE” 2000. Dan zou er een vertakkingsknooppunt moeten zijn met het pad “0xBE”, en onder dat knooppunt zouden twee bladknooppunten met twee paden (“0xA” en “0xE”) moeten komen.
In de MPT is er nog een type knooppunten naast de vertakkingsknooppunten en de bladknooppunten. Dit zijn extensieknooppunten. Een extension node is een geoptimaliseerde node van de branch node. In de Ethereum staat zijn er vrij vaak branch nodes die slechts één child node hebben. Dit is de reden waarom de MPT vertakkingsknooppunten die slechts één kind bevatten comprimeert tot extensieknooppunten die een pad en de hash van het kind hebben.
Omdat zowel het bladknooppunt als het extensieknooppunt een array van twee items zijn, moet er een manier zijn om deze twee verschillende knooppunten te onderscheiden. Om dit onderscheid te maken voegt de MPT een prefix toe aan het pad. Indien het knooppunt een blad is en het pad uit een even aantal nibbles bestaat, voegt u 0x20 als prefix toe. Indien het pad uit een oneven aantal nibbles bestaat, moet u 0x3 als voorvoegsel toevoegen. Indien het knooppunt een extensieknooppunt is en het pad uit een even aantal nibbles bestaat, voegt u 0x00 als voorvoegsel toe. Indien het uit oneven aantal nibbles bestaat, moet u 0x1 als voorvoegsel toevoegen. Omdat het pad dat uit een oneven aantal nibbles bestaat een nibble als prefix krijgt en het pad dat uit een even aantal nibbles bestaat twee nibbles als prefix krijgt, wordt een pad altijd uitgedrukt als een byte.
(Voor de originele Koreaanse versie, klik hier)