Verkko-osuuden sivuuttaen voisimme sanoa, että Ethereum on tilakone, jossa transaktiot muuttavat tiloja Ethereum-verkossa. Tila voidaan ilmaista avain-arvoparina. Vaikka avain-arvoparin esittämiseen on useita tapoja, Ethereumin spesifikaatio määrittelee tilojen tallennusmenetelmäksi Modified Merkle Patricia Trie:n (eli MPT:n).
Periaatteessa MPT on yhdistelmä Patricia trie:stä ja Merkle-puusta, ja siihen on tehty muutamia lisäoptimointeja, jotka sopivat Ethereumin ominaisuuksiin. Näin ollen Patricia trie:n ja Merkle-puun ymmärtämisen tulisi edeltää MPT:n ymmärtämistä.
Patricia trie on tietorakenne, jota kutsutaan myös nimellä Prefix tree, radix tree tai trie. Trie käyttää avainta polkuna, joten solmut, joilla on sama etuliite, voivat myös jakaa saman polun. Tämä rakenne on nopein yhteisten etuliitteiden löytämisessä, yksinkertainen toteuttaa ja vaatii vähän muistia. Näin ollen sitä käytetään yleisesti reititystaulukoiden toteuttamiseen, järjestelmiin, joita käytetään matalan spesifikaation koneissa, kuten reitittimissä.
Merkle-puu
Merkle-puu on hashien puu. Lehtisolmut tallentavat tietoja. Vanhemmat solmut sisältävät lastensa hash-arvon sekä lastensa hashien summan hash-arvon. Koska lehtisolmuja lukuun ottamatta kaikki solmut sisältävät hashin, Merkle-puu tunnetaan myös hash-puuna.
Esimerkki Merkle-puusta
Merkle-puulla saadaan tehokkaasti selville se, onko kahdessa erilaisessa solmupisteessä samaa dataa. Ensin on verrattava kahden solmun Top Hash -arvoa. Jos ne ovat samat, kahdella solmulla on samat tiedot. Jos esimerkiksi yllä olevassa kuvassa on neljä solmua (L1, L2, L3, L4), sinun tarvitsee vain tarkistaa, onko niillä sama Top Hash -arvo vai ei. Jos Top Hash on erilainen ja haluat tietää, mitkä tiedot ovat erilaiset, vertaa Hash 0:ta Hash1:een ja tarkista, mikä haara on erilainen. Näin tekemällä saat lopulta selville, mikä data on erilainen.
Merkle Patricia Trie
MPT:ssä, samoin kuin Merkle-puussa, jokaisella solmulla on hash-arvo. Kunkin solmun hash-arvo määräytyy sen sisällön sha3-hash-arvon perusteella. Tätä hash-arvoa käytetään myös solmuun viittaavana avaimena. Go-ethereum käyttää levelDB:tä ja parity rocksDB:tä tilojen tallentamiseen. Ne ovat avainarvotallennuksia. Varastoon tallennetut avaimet ja arvot eivät ole Ethereumin tilan avainarvoja. Varastoon tallennettu arvo on MPT-solmun sisältö, kun taas avain on tämän solmun hash.
Ethereumin tilan avain-arvoja käytetään MPT:n polkuina. Nibble on yksikkö, jota käytetään avainarvojen erottamiseen MPT:ssä, joten kussakin solmussa voi olla enintään 16 haaraa. Lisäksi, koska solmulla on oma arvonsa, haarasolmu on 17 elementin joukko, joka koostuu yhdestä solmun arvosta ja 16 haarasta.
Solmua, jolla ei ole lapsisolmua, kutsutaan lehtisolmuksi. Lehtisolmu koostuu kahdesta elementistä: sen polusta ja arvosta. Sanotaan esimerkiksi, että avain ”0xBEA” sisältää 1000 ja avain ”0xBEE” sisältää 2000. Silloin pitäisi olla haarasolmu, jossa on polku ”0xBE”, ja tämän solmun alle liitetään kaksi lehtisolmua, joissa on kaksi polkua (”0xA” ja ”0xE”).
MPT:ssä on haarasolmujen ja lehtisolmujen lisäksi vielä yksi muu solmutyyppi. Ne ovat jatkosolmuja. Laajennussolmu on haarasolmun optimoitu solmu. Ethereumin tilassa on melko usein haarasolmuja, joilla on vain yksi lapsisolmu. Tästä syystä MPT pakkaa haarasolmut, joissa on vain yksi lapsi, laajennussolmuiksi, joissa on polku ja lapsen hash.
Koska sekä lehtisolmu että laajennussolmu ovat kahden kohteen joukko, pitäisi olla tapa erottaa nämä kaksi eri solmua toisistaan. Tällaisen erottelun tekemiseksi MPT lisää polkuun etuliitteen. Jos solmu on lehti ja polku koostuu parillisesta määrästä nibblejä, etuliitteeksi lisätään 0x20. Jos polku koostuu parittomasta määrästä nibblejä, etuliitteeksi lisätään 0x3. Jos solmu on jatkosolmu ja polku koostuu parillisesta määrästä nibblejä, etuliitteeksi lisätään 0x00. Jos se koostuu parittomasta määrästä nibblejä, etuliitteeksi on lisättävä 0x1. Koska polku, joka koostuu parittomasta määrästä nibblejä, saa etuliitteeksi yhden nibblen ja polku, joka koostuu parillisesta määrästä nibblejä, saa etuliitteeksi kaksi nibbleä, polku ilmaistaan aina tavuina.
(Alkuperäisen koreankielisen version saat klikkaamalla tästä)