Drzewo Merkle Patricia

Stan Ethereum (całość wszystkich kont, sald i inteligentnych kontraktów) jest zakodowany w specjalnej wersji struktury danych, znanej w informatyce jako drzewo Merkle. Struktura ta jest przydatna w wielu zastosowaniach w kryptografii, ponieważ tworzy weryfikowalną relację między wszystkimi pojedynczymi fragmentami danych splątanymi w drzewie, co skutkuje pojedynczą wartością korzenia, która może być użyta do udowodnienia różnych kwestii dotyczących danych.

Struktura danych Ethereum to „zmodyfikowane drzewo Merkle-Patricia”, nazwane tak, ponieważ czerpie niektóre cechy z PATRICIA (ang. Practical Algorithm To Retrieve Information Coded in Alphanumeric) i ponieważ jest zaprojektowana do wydajnego odzyskiwania (ang. retrieval) danych, które składają się na stan Ethereum.

Drzewo Merkle-Patricia jest deterministyczne i weryfikowalne kryptograficznie: jedynym sposobem na wygenerowanie korzenia stanu jest obliczenie go z każdego pojedynczego elementu stanu, a identyczność dwóch stanów można łatwo udowodnić, porównując hasz korzenia i hasze, które do niego doprowadziły (dowód Merklego). I odwrotnie, nie ma sposobu na stworzenie dwóch różnych stanów o tym samym haszu korzenia, a każda próba modyfikacji stanu za pomocą różnych wartości spowoduje powstanie innego haszu korzenia stanu. Teoretycznie struktura ta zapewnia „święty Graal” wydajności O(log(n)) dla operacji wstawiania, wyszukiwania i usuwania.

W niedalekiej przyszłości Ethereum planuje migrację do struktury drzewa Verkle, co otworzy wiele nowych możliwości przyszłych ulepszeń protokołu.

Wymagania wstępne

Aby lepiej zrozumieć tę stronę, pomocna będzie podstawowa znajomość haszy (opens in a new tab), drzew Merklego (opens in a new tab), drzew prefiksowych (tries) (opens in a new tab) i serializacji (opens in a new tab). Ten artykuł rozpoczyna się od opisu podstawowego drzewa pozycyjnego (radix) (opens in a new tab), a następnie stopniowo wprowadza modyfikacje niezbędne dla bardziej zoptymalizowanej struktury danych Ethereum.

Podstawowe drzewa pozycyjne

W podstawowym drzewie pozycyjnym każdy węzeł wygląda następująco:

1    [i_0, i_1 ... i_n, wartość]

Gdzie i_0 ... i_n reprezentują symbole alfabetu (często binarnego lub szesnastkowego), wartość jest wartością końcową w węźle, a wartości w i_0, i_1 ... i_n slotach są albo NULL, albo wskaźnikami (w naszym przypadku haszami) do innych węzłów. Tworzy to podstawowy magazyn (klucz, wartość).

Załóżmy, że chcesz użyć struktury danych drzewa pozycyjnego do utrwalenia porządku w zbiorze par klucz-wartość. Aby znaleźć wartość aktualnie przypisaną do klucza dog w drzewie, należy najpierw przekonwertować dog na litery alfabetu (co daje 64 6f 67), a następnie zejść w dół drzewa, podążając tą ścieżką, aż do znalezienia wartości. Oznacza to, że zaczynasz od wyszukania haszu korzenia w płaskiej bazie danych klucz/wartość, aby znaleźć węzeł główny drzewa. Jest on reprezentowany jako tablica kluczy wskazujących na inne węzły. Użyjesz wartości o indeksie 6 jako klucza i wyszukasz ją w płaskiej bazie danych klucz/wartość, aby uzyskać węzeł o jeden poziom niżej. Następnie wybierz indeks 4, aby wyszukać następną wartość, potem indeks 6 i tak dalej, aż po przejściu ścieżki: korzeń -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, odszukasz wartość węzła i zwrócisz wynik.

Istnieje różnica między wyszukiwaniem czegoś w „drzewie” a podstawową płaską „bazą danych” klucz/wartość. Oba definiują układy klucz/wartość, ale podstawowa baza danych może wykonać tradycyjne 1-etapowe wyszukiwanie klucza. Wyszukanie klucza w drzewie wymaga wielokrotnego wyszukiwania w podstawowej bazie danych, aby dotrzeć do ostatecznej wartości opisanej powyżej. Aby wyeliminować niejednoznaczność, będziemy nazywać to drugie ścieżką.

Operacje aktualizacji i usuwania dla drzew pozycyjnych można zdefiniować w następujący sposób:

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)
Pokaż wszystko

Drzewo pozycyjne „Merkle” jest zbudowane przez łączenie węzłów przy użyciu deterministycznie generowanych kryptograficznych skrótów haszujących. To adresowanie treści (w bazie danych klucz/wartość klucz == keccak256(rlp(wartość))) zapewnia kryptograficzną gwarancję integralności przechowywanych danych. Jeśli hasz korzenia danego drzewa jest publicznie znany, każdy, kto ma dostęp do danych bazowych liści, może skonstruować dowód, że drzewo zawiera daną wartość w określonej ścieżce, podając hasze każdego węzła łączącego określoną wartość z korzeniem drzewa.

Atakujący nie może przedstawić dowodu na parę (ścieżka, wartość), która nie istnieje, ponieważ hasz korzenia jest ostatecznie oparty na wszystkich haszach znajdujących się pod nim. Każda modyfikacja bazowa zmieniłaby hasz korzenia. Można myśleć o haszu jako o skompresowanej reprezentacji informacji strukturalnych o danych, zabezpieczonej przez ochronę przeciwobrazu funkcji haszującej.

Będziemy odnosić się do jednostki atomowej drzewa pozycyjnego (np. pojedynczego znaku szesnastkowego lub 4-bitowej liczby binarnej) jako „półbajtu”. Podczas przechodzenia ścieżki po jednym półbajcie na raz, jak opisano powyżej, węzły mogą odnosić się maksymalnie do 16 potomków, ale zawierają element wartość. Dlatego reprezentujemy je jako tablicę o długości 17. Nazywamy te 17-elementowe tablice „węzłami gałęzi”.

Drzewa pozycyjne mają jedno poważne ograniczenie: są nieefektywne. Jeśli chcesz przechować jedno powiązanie (ścieżka, wartość), gdzie ścieżka, podobnie jak w Ethereum, ma 64 znaki długości (liczba półbajtów w bytes32), będziemy potrzebować ponad kilobajt dodatkowej przestrzeni na przechowanie jednego poziomu na znak, a każde wyszukiwanie lub usuwanie zajmie pełne 64 kroki. Drzewo Patricia wprowadzone w dalszej części rozwiązuje ten problem.

Optymalizacja

Węzeł w drzewie Merkle Patricia jest jednym z następujących:

NULL (reprezentowany jako pusty ciąg znaków)
gałąź 17-elementowy węzeł [ v0 ... v15, vt ]
liść 2-elementowy węzeł [ zakodowanaŚcieżka, wartość ]
rozszerzenie 2-elementowy węzeł [ zakodowanaŚcieżka, klucz ]

Przy ścieżkach o długości 64 znaków nieuniknione jest, że po przejściu przez kilka pierwszych warstw drzewa dotrzemy do węzła, w którym przez przynajmniej część drogi w dół nie istnieje żadna rozbieżna ścieżka. Aby uniknąć konieczności tworzenia do 15 rzadkich węzłów NULL wzdłuż ścieżki, skracamy drogę, tworząc węzeł rozszerzenia w formie [ zakodowanaŚcieżka, klucz ], gdzie zakodowanaŚcieżka zawiera „częściową ścieżkę” do pominięcia (używając kompaktowego kodowania opisanego poniżej), a klucz służy do następnego wyszukiwania w bazie danych.

W przypadku węzła liścia, który może być oznaczony flagą w pierwszym półbajcie zakodowanejŚcieżki, ścieżka koduje wszystkie fragmenty ścieżek poprzednich węzłów i możemy bezpośrednio wyszukać wartość.

Powyższa optymalizacja wprowadza jednak niejednoznaczność.

Podczas przechodzenia ścieżek w półbajtach możemy skończyć z nieparzystą liczbą półbajtów do przejścia, ale ponieważ wszystkie dane są przechowywane w formacie bajtów. Nie jest możliwe rozróżnienie, na przykład, półbajtu 1 od półbajtów 01 (oba muszą być przechowywane jako <01>). Aby określić nieparzystą długość, częściowa ścieżka jest poprzedzona flagą.

Specyfikacja: Kompaktowe kodowanie sekwencji szesnastkowej z opcjonalnym terminatorem

Oznaczanie zarówno nieparzystej vs. parzystej pozostałej długości częściowej ścieżki, jak i węzła liścia vs. rozszerzenia, jak opisano powyżej, znajduje się w pierwszym półbajcie częściowej ścieżki dowolnego 2-elementowego węzła. Skutkują one następującymi:

znak hex	bity	częściowy typ węzła	długość ścieżki
0	0000	rozszerzenie	parzysta
1	0001	rozszerzenie	nieparzysta
2	0010	kończący (liść)	parzysta
3	0011	kończący (liść)	nieparzysta

Dla parzystej pozostałej długości ścieżki (0 lub 2) zawsze następuje kolejny 0 „dopełniający” półbajt.

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
Pokaż wszystko

Przykłady:

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'

Oto rozszerzony kod do pobierania węzła w drzewie Merkle Patricia:

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)
Pokaż wszystko

Przykładowe drzewo

Załóżmy, że chcemy mieć drzewo zawierające cztery pary ścieżka/wartość ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

Najpierw konwertujemy zarówno ścieżki, jak i wartości na bajty. Poniżej, rzeczywiste reprezentacje bajtowe dla ścieżek są oznaczone przez <>, chociaż wartości są nadal pokazane jako ciągi znaków, oznaczone przez '', dla łatwiejszego zrozumienia (one również w rzeczywistości byłyby bajtami):

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

Teraz budujemy takie drzewo z następującymi parami klucz/wartość w podstawowej bazie danych:

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' ] ]

Gdy jeden węzeł jest przywoływany wewnątrz innego węzła, to, co jest dołączane, to keccak256(rlp.encode(node)), jeśli len(rlp.encode(node)) >= 32, w przeciwnym razie node, gdzie rlp.encode to funkcja kodowania RLP.

Należy pamiętać, że podczas aktualizacji drzewa należy zapisać parę klucz/wartość (keccak256(x), x) w trwałej tabeli przeglądowej, jeśli nowo utworzony węzeł ma długość >= 32. Jeśli jednak węzeł jest krótszy, nie trzeba niczego przechowywać, ponieważ funkcja f(x) = x jest odwracalna.

Drzewa w Ethereum

Wszystkie drzewa Merklego w warstwie wykonawczej Ethereum wykorzystują drzewo Merkle Patricia.

Z nagłówka bloku pochodzą 3 korzenie z 3 takich drzew.

stateRoot
transactionsRoot
receiptsRoot

Drzewo stanu

Istnieje jedno globalne drzewo stanu, które jest aktualizowane za każdym razem, gdy klient przetwarza blok. W nim ścieżka to zawsze: keccak256(adresEthereum), a wartość to zawsze: rlp(kontoEthereum). Dokładniej, konto Ethereum to 4-elementowa tablica [nonce,balance,storageRoot,codeHash]. W tym momencie warto zauważyć, że ten storageRoot jest korzeniem innego drzewa Patricia:

Drzewo przechowywania

Drzewo przechowywania to miejsce, w którym znajdują się wszystkie dane kontraktu. Dla każdego konta istnieje oddzielne drzewo przechowywania. Aby pobrać wartości na określonych pozycjach przechowywania pod danym adresem, wymagany jest adres przechowywania, pozycja całkowita przechowywanych danych w magazynie oraz identyfikator bloku. Można je następnie przekazać jako argumenty do eth_getStorageAt zdefiniowanego w API JSON-RPC, np. aby pobrać dane ze slotu 0 przechowywania dla 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"}

Pobieranie innych elementów z magazynu jest nieco bardziej skomplikowane, ponieważ najpierw należy obliczyć pozycję w drzewie przechowywania. Pozycja jest obliczana jako hasz keccak256 adresu i pozycji w magazynie, oba dopełnione z lewej strony zerami do długości 32 bajtów. Na przykład pozycja danych w slocie 1 przechowywania dla adresu 0x391694e7e0b0cce554cb130d723a9d27458f9298 to:

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

W konsoli Geth można to obliczyć w następujący sposób:

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

Ścieżka jest zatem keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Można to teraz wykorzystać do pobrania danych z drzewa przechowywania, tak jak poprzednio:

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"}

Uwaga: storageRoot dla konta Ethereum jest domyślnie pusty, jeśli nie jest to konto kontraktu.

Drzewo transakcji

Dla każdego bloku istnieje osobne drzewo transakcji, przechowujące pary (klucz, wartość). Ścieżka tutaj to: rlp(indeksTransakcji), która reprezentuje klucz odpowiadający wartości określonej przez:

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

Więcej informacji na ten temat można znaleźć w dokumentacji EIP 2718 (opens in a new tab).

Drzewo potwierdzeń

Każdy blok ma własne drzewo potwierdzeń. Ścieżka tutaj to: rlp(indeksTransakcji). indeksTransakcji to jego indeks w bloku, w którym został zawarty. Drzewo potwierdzeń nigdy nie jest aktualizowane. Podobnie jak w drzewie transakcji, istnieją bieżące i starsze potwierdzenia. Aby wyszukać określone potwierdzenie w drzewie potwierdzeń, wymagany jest indeks transakcji w jej bloku, ładunek potwierdzenia oraz typ transakcji. Zwrócone potwierdzenie może być typu Receipt, który jest zdefiniowany jako konkatenacja TransactionType i ReceiptPayload lub może być typu LegacyReceipt, który jest zdefiniowany jako rlp([status, cumulativeGasUsed, logsBloom, logs]).

Więcej informacji na ten temat można znaleźć w dokumentacji EIP 2718 (opens in a new tab).

Drzewo Merkle Patricia

Wymagania wstępne

Podstawowe drzewa pozycyjne