Merkle Patricia Trie

Stav Etherea (tj. souhrn všech účtů, zůstatků a smart kontraktů) je zakódován do speciální verze datové struktury, která je obecně v informatice známá jako Merkle tree. Tato struktura je užitečná pro mnoho aplikací v kryptografii, protože vytváří ověřitelný vztah mezi všemi jednotlivými datovými prvky propletenými ve stromu, což vede k jediné kořenové hodnotě, kterou lze použít k prokazování různých skutečností o datech.

Datová struktura Etherea je „modifikovaný Merkle-Patricia Trie“, pojmenovaný tak proto, že si půjčuje některé vlastnosti z PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric) a protože je navržen pro efektivní retrieval (vyhledávání) položek, které tvoří stav Etherea.

Datová struktura Merkle-Patricia trie je deterministická a kryptograficky ověřitelná: Jediný způsob, jak vygenerovat kořen stavu, je jeho výpočet z každé jednotlivé části stavu, a dva identické stavy lze snadno prokázat porovnáním kořenového haše a hašů, které k němu vedly (Merkleho důkaz). Naopak není možné vytvořit dva různé stavy se stejným kořenovým hashem a jakýkoli pokus o modifikaci stavu s jinými hodnotami povede k odlišnému kořenovému hashi stavu. Teoreticky tato struktura poskytuje „svatý grál“ efektivity O(log(n)) pro vkládání, vyhledávání a mazání.

V blízké budoucnosti Ethereum plánuje přejít na strukturu stromu Verkle, což otevře mnoho nových možností pro budoucí vylepšení protokolu.

Předpoklady

Pro lepší pochopení této stránky je užitečné mít základní znalosti o haších (opens in a new tab), Merkleho stromech (opens in a new tab), trie (opens in a new tab) a serializaci (opens in a new tab). Tento článek začíná popisem základního radixového stromu (opens in a new tab) a postupně zavádí úpravy nezbytné pro optimalizovanější datovou strukturu Etherea.

Základní radixové trie

V základním radixovém trie vypadá každý síťový uzel následovně:

1    [i_0, i_1 ... i_n, value]

Kde i_0 ... i_npředstavují symboly abecedy (často binární nebo hexadecimální),valueje konečná hodnota v uzlu a hodnoty vi_0, i_1 ... i_n slotech jsou buď NULL, nebo ukazatele na (v našem případě haše) jiné uzly. To tvoří základní úložiště (key, value).

Řekněme, že chcete použít strukturu radixového stromu pro uchování uspořádání nad sadou párů key-value. Chcete-li najít hodnotu aktuálně namapovanou na klíč dog v trie, nejprve byste dog převedli na písmena abecedy (což dá 64 6f 67) a poté sestupovali v trie po této cestě, dokud nenajdete hodnotu. To znamená, že začnete vyhledáním kořenového hashe v ploché databázi key-value, abyste našli kořenový uzel trie. Ten je reprezentován jako pole klíčů ukazujících na jiné uzly. Použili byste hodnotu na indexu 6 jako klíč a vyhledali ji v ploché databázi klíč/hodnota, abyste získali uzel o jednu úroveň níže. Poté zvolíte index 4 pro vyhledání další hodnoty, pak index 6 a tak dále, dokud po sledování cesty: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7 nevyhledáte hodnotu uzlu a nevrátíte výsledek.

Existuje rozdíl mezi vyhledáváním něčeho v „trie“ a v podkladové ploché databázi key-value. Obě definují uspořádání key-value, ale podkladová databáze může provést tradiční jednorázové vyhledání klíče. Vyhledávání klíče v trie vyžaduje několik podkladových vyhledávání v databázi, aby se dospělo k finální hodnotě popsané výše. Nazvěme to druhé jako path, abychom eliminovali nejednoznačnost.

Operace aktualizace a mazání pro radixové trie mohou být definovány následovně:

1    def update(node_hash, path, value):
2        curnode = db.get(node_hash) if node_hash else [NULL] * 17
3        newnode = curnode.copy()
4        if path == "":
5            newnode[-1] = value
6        else:
7            newindex = update(curnode[path[0]], path[1:], value)
8            newnode[path[0]] = newindex
9        db.put(hash(newnode), newnode)
10        return hash(newnode)
11
12    def delete(node_hash, path):
13        if node_hash is NULL:
14            return NULL
15        else:
16            curnode = db.get(node_hash)
17            newnode = curnode.copy()
18            if path == "":
19                newnode[-1] = NULL
20            else:
21                newindex = delete(curnode[path[0]], path[1:])
22                newnode[path[0]] = newindex
23
24            if all(x is NULL for x in newnode):
25                return NULL
26            else:
27                db.put(hash(newnode), newnode)
28                return hash(newnode)
Zobrazit vše
Kopírovat

"Merkle" radixový strom je vytvořen propojením uzlů pomocí deterministicky generovaných kryptografických hash digestů. Toto adresování obsahu (v databázi klíč/hodnota key == keccak256(rlp(value))) poskytuje kryptografickou záruku integrity uložených dat. Pokud je kořenový hash daného trie veřejně známý, pak kdokoli s přístupem k podkladovým datům listů může vytvořit důkaz, že trie obsahuje danou hodnotu na konkrétní cestě tím, že poskytne hashe každého uzlu spojujícího danou hodnotu s kořenem stromu.

Je nemožné, aby útočník poskytl důkaz o páru (path, value), který neexistuje, protože kořenový haš je nakonec založen na všech haších pod ním. Jakákoli podkladová modifikace by změnila kořenový haš. Můžete si představit haš jako komprimované zobrazení strukturálních informací o datech, zajištěné ochranou před obrazy hašovací funkce.

Atomickou jednotku radixového stromu (např. jeden hexadecimální znak nebo 4bitové binární číslo) budeme nazývat „nibble“. Při procházení cesty po jednom nibble, jak je popsáno výše, mohou uzly odkazovat na maximálně 16 potomků, ale obsahují prvek value. Proto je reprezentujeme jako pole o délce 17. Těmto 17prvkovým polím říkáme "větvové uzly".

Merkle Patricia Trie

Radixové trie mají jednu zásadní nevýhodu: jsou neefektivní. Pokud chcete uložit jednu vazbu (path, value), kde cesta, stejně jako na Ethereu, má délku 64 znaků (počet nibblů v bytes32), budete potřebovat více než kilobajt dalšího prostoru pro uložení jedné úrovně na znak a každé vyhledání nebo smazání bude trvat celých 64 kroků. Patricia trie, představené níže, tento problém řeší.

Optimalizace

Uzel v Merkle Patricia trie je jedním z následujících:

1. NULL (reprezentován jako prázdný řetězec)
2. branch 17položkový uzel [ v0 ... v15, vt ]`
3. leaf 2položkový uzel [ encodedPath, value ]
4. extension 2položkový uzel [ encodedPath, key ]

S cestami 64 znaků je nevyhnutelné, že po projití několika prvních vrstev trie se dostanete do uzlu, kde alespoň část cesty dolů neexistuje žádná divergentní cesta. Abychom se vyhnuli vytváření až 15 řídkých uzlů NULL podél cesty, zkrátíme sestup nastavením uzlu extension ve tvaru [ encodedPath, key ], kde encodedPath obsahuje „částečnou cestu“ pro přeskočení (pomocí kompaktního kódování popsaného níže) a key je pro další vyhledávání v DB.

U uzlu leaf, který může být označen příznakem v prvním nibble encodedPath, cesta kóduje všechny fragmenty cesty předchozích uzlů a hodnotu value můžeme vyhledat přímo.

Tato výše uvedená optimalizace však zavádí nejednoznačnost.

Při procházení cest po nibblech můžeme skončit s lichým počtem nibblů k procházení, ale protože všechna data jsou uložena ve formátu bytes. Není možné rozlišit například mezi nibblem 1 a nibbly 01 (obojí musí být uloženo jako <01>). Abychom specifikovali lichou délku, je částečná cesta předznačena příznakem.

Specifikace: Kompaktní kódování hexadecimální sekvence s volitelným terminátorem

Příznaky pro lichou vs. sudou zbývající délku částečné cesty i pro uzel list vs. uzel rozšíření, jak je popsáno výše, se nacházejí v prvním nibblu částečné cesty jakéhokoli 2položkového uzlu. Výsledkem je následující:

Pro sudou zbývající délku cesty (0 nebo 2) bude vždy následovat další „vycpávkový“ nibble 0.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # hexarray now has an even length whose first nibble is the flags.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        return o
Zobrazit vše
Kopírovat

Příklady:

1    > [1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [f, 1, c, b, 8, 10]
8    '3f 1c b8'
Kopírovat

Zde je rozšířený kód pro získání uzlu v Merkle Patricia trie:

1    def get_helper(node_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
Zobrazit vše
Kopírovat

Příklad Trie

Předpokládejme, že chceme trie obsahující čtyři páry cesta/hodnota ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

Nejprve převedeme cesty i hodnoty na bytes. Níže jsou skutečné bajtové reprezentace cest označeny <>, ačkoli hodnoty jsou pro snazší pochopení stále zobrazeny jako řetězce označené '' (i ony by ve skutečnosti byly bytes):

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coins'
4    <68 6f 72 73 65> : 'stallion'

Nyní vytvoříme takový trie s následujícími páry klíč/hodnota v podkladové DB:

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashC ]
4    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Pokud jeden uzel odkazuje na jiný uzel, je zahrnuto keccak256(rlp.encode(node)), pokud len(rlp.encode(node)) >= 32, jinak node, kde rlp.encode je kódovací funkce RLP.

Všimněte si, že při aktualizaci trie je třeba uložit pár klíč/hodnota (keccak256(x), x) do perzistentní vyhledávací tabulky, pokud má nově vytvořený uzel délku >= 32. Pokud je však uzel kratší, není třeba nic ukládat, protože funkce f(x) = x je reverzibilní.

Trie v Ethereu

Všechny merkle trie v exekuční vrstvě Etherea používají Merkle Patricia Trie.

V hlavičce bloku jsou 3 kořeny z 3 těchto trie.

1. stateRoot
2. transactionsRoot
3. receiptsRoot

Stavová trie

Existuje jedna globální stavová trie, která se aktualizuje pokaždé, když klient zpracuje blok. V ní je path vždy: keccak256(ethereumAddress) a value je vždy: rlp(ethereumAccount). Konkrétně je ethereový účet 4položkové pole [nonce,balance,storageRoot,codeHash]. V tomto bodě stojí za zmínku, že tento storageRoot je kořenem další patricia trie:

Úložná trie

V úložné trie jsou uložena všechna data kontraktu. Pro každý účet existuje samostatná úložná trie. K načtení hodnot na konkrétních pozicích úložiště na dané adrese je nutná adresa úložiště, celočíselná pozice uložených dat v úložišti a ID bloku. Ty pak mohou být předány jako argumenty do eth_getStorageAt definovaného v JSON-RPC API, např. pro načtení dat v úložném slotu 0 pro adresu 0x295a70b2de5e3953354a6a8344e616ed314d7251:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}

Načítání dalších prvků v úložišti je o něco složitější, protože se nejprve musí vypočítat pozice v úložné trie. Pozice se vypočítá jako haš keccak256 adresy a pozice v úložišti, obě doplněné zleva nulami na délku 32 bajtů. Například pozice pro data v úložném slotu 1 pro adresu 0x391694e7e0b0cce554cb130d723a9d27458f9298 je:

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))
Kopírovat

V konzoli Geth to lze vypočítat následovně:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

path je tedy keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). To lze nyní použít k načtení dat z úložné trie jako předtím:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Poznámka: storageRoot pro ethereový účet je ve výchozím nastavení prázdný, pokud se nejedná o účet kontraktu.

Transakční trie

Pro každý blok existuje samostatná transakční trie, která opět ukládá páry (klíč, hodnota). Cesta je zde: rlp(transactionIndex), která představuje klíč odpovídající hodnotě určené:

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)
Kopírovat

Více informací o tomto naleznete v dokumentaci k EIP 2718 (opens in a new tab).

Trie účtenek

Každý blok má svou vlastní trie účtenek. path zde je: rlp(transactionIndex). transactionIndex je jeho index v bloku, ve kterém byl zahrnut. Trie účtenek se nikdy neaktualizuje. Podobně jako transakční trie, existují aktuální a starší účtenky. Pro dotaz na konkrétní účtenku v trie účtenek je nutný index transakce v jejím bloku, datová část účtenky a typ transakce. Vrácená účtenka může být typu Receipt, který je definován jako zřetězení TransactionType a ReceiptPayload, nebo může být typu LegacyReceipt, který je definován jako rlp([status, cumulativeGasUsed, logsBloom, logs]).

Více informací o tomto naleznete v dokumentaci k EIP 2718 (opens in a new tab).

Další čtení

• Modifikovaný Merkle Patricia Trie – jak Ethereum ukládá stav (opens in a new tab)
• Merkling v Ethereu (opens in a new tab)
• Pochopení Ethereum trie (opens in a new tab)