Merkle Patricia Trie

Status Ethereum (keseluruhan dari semua akun, saldo, dan kontrak pintar), dienkode ke dalam versi khusus dari struktur data yang secara umum dikenal dalam ilmu komputer sebagai Merkle Tree. Struktur ini berguna untuk banyak aplikasi dalam kriptografi karena menciptakan hubungan yang dapat diverifikasi antara semua potongan data individu yang terjalin di dalam pohon, menghasilkan nilai akar (root) tunggal yang dapat digunakan untuk membuktikan hal-hal tentang data tersebut.

Struktur data Ethereum adalah 'Merkle-Patricia Trie yang dimodifikasi', dinamakan demikian karena meminjam beberapa fitur dari PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric), dan karena dirancang untuk pengambilan (retrieval) data yang efisien dari item-item yang membentuk status Ethereum.

Merkle-Patricia trie bersifat deterministik dan dapat diverifikasi secara kriptografi: Satu-satunya cara untuk menghasilkan akar status adalah dengan menghitungnya dari setiap potongan individu dari status tersebut, dan dua status yang identik dapat dengan mudah dibuktikan dengan membandingkan hash akar dan hash yang mengarah kepadanya (bukti Merkle). Sebaliknya, tidak ada cara untuk membuat dua status yang berbeda dengan hash akar yang sama, dan setiap upaya untuk memodifikasi status dengan nilai yang berbeda akan menghasilkan hash akar status yang berbeda. Secara teoritis, struktur ini memberikan 'cawan suci' efisiensi O(log(n)) untuk penyisipan, pencarian, dan penghapusan.

Dalam waktu dekat, Ethereum berencana untuk bermigrasi ke struktur Verkle Tree, yang akan membuka banyak kemungkinan baru untuk peningkatan protokol di masa depan.

Prasyarat

Untuk lebih memahami halaman ini, akan sangat membantu jika Anda memiliki pengetahuan dasar tentang hash (opens in a new tab), Merkle tree (opens in a new tab), trie (opens in a new tab), dan serialisasi (opens in a new tab). Artikel ini dimulai dengan deskripsi tentang radix tree (opens in a new tab) dasar, kemudian secara bertahap memperkenalkan modifikasi yang diperlukan untuk struktur data Ethereum yang lebih dioptimalkan.

Radix trie dasar

Dalam radix trie dasar, setiap node terlihat sebagai berikut:

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

Di mana i_0 ... i_n mewakili simbol-simbol alfabet (sering kali biner atau hex), value adalah nilai terminal pada node, dan nilai-nilai di slot i_0, i_1 ... i_n adalah NULL atau penunjuk ke (dalam kasus kita, hash dari) node lain. Ini membentuk penyimpanan (key, value) dasar.

Katakanlah Anda ingin menggunakan struktur data radix tree untuk mempertahankan urutan atas sekumpulan pasangan nilai kunci (key-value). Untuk menemukan nilai yang saat ini dipetakan ke kunci dog di dalam trie, Anda pertama-tama akan mengonversi dog menjadi huruf-huruf alfabet (menghasilkan 64 6f 67), dan kemudian menuruni trie mengikuti jalur tersebut hingga Anda menemukan nilainya. Yaitu, Anda mulai dengan mencari hash akar di DB key/value datar untuk menemukan node akar dari trie. Ini direpresentasikan sebagai array kunci yang menunjuk ke node lain. Anda akan menggunakan nilai pada indeks 6 sebagai kunci dan mencarinya di DB key/value datar untuk mendapatkan node satu tingkat di bawahnya. Kemudian pilih indeks 4 untuk mencari nilai berikutnya, lalu pilih indeks 6, dan seterusnya, hingga, setelah Anda mengikuti jalur: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, Anda akan mencari nilai node tersebut dan mengembalikan hasilnya.

Ada perbedaan antara mencari sesuatu di 'trie' dan 'DB' key/value datar yang mendasarinya. Keduanya mendefinisikan susunan key/value, tetapi DB yang mendasarinya dapat melakukan pencarian kunci 1 langkah tradisional. Mencari kunci di dalam trie memerlukan beberapa pencarian DB yang mendasarinya untuk mencapai nilai akhir yang dijelaskan di atas. Mari kita sebut yang terakhir sebagai path (jalur) untuk menghilangkan ambiguitas.

Operasi pembaruan dan penghapusan untuk radix trie dapat didefinisikan sebagai berikut:

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)
Tampilkan semua

Radix tree "Merkle" dibangun dengan menautkan node menggunakan intisari hash kriptografi yang dihasilkan secara deterministik. Pengalamatan konten ini (dalam DB key/value key == keccak256(rlp(value))) memberikan jaminan integritas kriptografi dari data yang disimpan. Jika hash akar dari trie tertentu diketahui publik, maka siapa pun yang memiliki akses ke data daun (leaf) yang mendasarinya dapat menyusun bukti bahwa trie tersebut menyertakan nilai tertentu pada jalur tertentu dengan memberikan hash dari setiap node yang menggabungkan nilai tertentu ke akar pohon.

Mustahil bagi penyerang untuk memberikan bukti pasangan (path, value) yang tidak ada karena hash akar pada akhirnya didasarkan pada semua hash di bawahnya. Modifikasi apa pun yang mendasarinya akan mengubah hash akar. Anda dapat menganggap hash sebagai representasi terkompresi dari informasi struktural tentang data, yang diamankan oleh perlindungan pra-citra (pre-image) dari fungsi hashing.

Kita akan menyebut unit atomik dari radix tree (misalnya, karakter hex tunggal, atau angka biner 4 bit) sebagai "nibble". Saat melintasi jalur satu nibble pada satu waktu, seperti yang dijelaskan di atas, node dapat secara maksimal merujuk ke 16 anak tetapi menyertakan elemen value. Oleh karena itu, kita merepresentasikannya sebagai array dengan panjang 17. Kita menyebut array 17 elemen ini sebagai "node cabang" (branch nodes).

Radix trie memiliki satu batasan utama: mereka tidak efisien. Jika Anda ingin menyimpan satu ikatan (path, value) di mana jalurnya, seperti di Ethereum, memiliki panjang 64 karakter (jumlah nibble dalam bytes32), kita akan membutuhkan lebih dari satu kilobyte ruang ekstra untuk menyimpan satu tingkat per karakter, dan setiap pencarian atau penghapusan akan memakan waktu 64 langkah penuh. Patricia trie yang diperkenalkan berikut ini memecahkan masalah ini.

Optimasi

Sebuah node dalam Merkle Patricia trie adalah salah satu dari berikut ini:

NULL (direpresentasikan sebagai string kosong)
branch Node 17 item [ v0 ... v15, vt ]
leaf Node 2 item [ encodedPath, value ]
extension Node 2 item [ encodedPath, key ]

Dengan jalur 64 karakter, tidak dapat dihindari bahwa setelah melintasi beberapa lapisan pertama dari trie, Anda akan mencapai node di mana tidak ada jalur divergen yang ada untuk setidaknya sebagian jalan ke bawah. Untuk menghindari keharusan membuat hingga 15 node NULL yang jarang di sepanjang jalur, kita mempersingkat penurunan dengan menyiapkan node extension dalam bentuk [ encodedPath, key ], di mana encodedPath berisi "jalur parsial" untuk melompat ke depan (menggunakan pengkodean ringkas yang dijelaskan di bawah), dan key adalah untuk pencarian DB berikutnya.

Untuk node leaf, yang dapat ditandai dengan bendera (flag) di nibble pertama dari encodedPath, jalur tersebut mengkodekan semua fragmen jalur node sebelumnya dan kita dapat mencari value secara langsung.

Namun, optimasi di atas memperkenalkan ambiguitas.

Saat melintasi jalur dalam nibble, kita mungkin berakhir dengan jumlah nibble ganjil untuk dilintasi, tetapi karena semua data disimpan dalam format bytes. Tidak mungkin untuk membedakan antara, misalnya, nibble 1, dan nibble 01 (keduanya harus disimpan sebagai <01>). Untuk menentukan panjang ganjil, jalur parsial diawali dengan sebuah bendera.

Spesifikasi: Pengkodean ringkas urutan hex dengan terminator opsional

Penandaan baik panjang jalur parsial tersisa ganjil vs. genap maupun node leaf vs. extension seperti yang dijelaskan di atas berada di nibble pertama dari jalur parsial dari setiap node 2 item. Mereka menghasilkan hal berikut:

karakter hex	bit	tipe node parsial	panjang jalur
0	0000	extension	genap
1	0001	extension	ganjil
2	0010	terminating (leaf)	genap
3	0011	terminating (leaf)	ganjil

Untuk panjang jalur tersisa yang genap (0 atau 2), nibble "padding" 0 lainnya akan selalu mengikuti.

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. # hexarray sekarang memiliki panjang genap di mana nibble pertamanya adalah flag.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        return o
Tampilkan semua

Contoh:

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'

Berikut adalah kode yang diperluas untuk mendapatkan node di 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)
Tampilkan semua

Contoh Trie

Misalkan kita menginginkan trie yang berisi empat pasangan path/value ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

Pertama, kita mengonversi path dan value menjadi bytes. Di bawah ini, representasi byte aktual untuk path dilambangkan dengan <>, meskipun value masih ditampilkan sebagai string, dilambangkan dengan '', untuk pemahaman yang lebih mudah (mereka juga sebenarnya akan berupa bytes):

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

Sekarang, kita membangun trie semacam itu dengan pasangan key/value berikut di DB yang mendasarinya:

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

Ketika satu node direferensikan di dalam node lain, apa yang disertakan adalah keccak256(rlp.encode(node)), jika len(rlp.encode(node)) >= 32 jika tidak node di mana rlp.encode adalah fungsi pengkodean RLP.

Perhatikan bahwa saat memperbarui trie, seseorang perlu menyimpan pasangan key/value (keccak256(x), x) dalam tabel pencarian persisten jika node yang baru dibuat memiliki panjang >= 32. Namun, jika node lebih pendek dari itu, seseorang tidak perlu menyimpan apa pun, karena fungsi f(x) = x dapat dibalik (reversible).

Trie di Ethereum

Semua merkle trie di lapisan eksekusi Ethereum menggunakan Merkle Patricia Trie.

Dari header blok terdapat 3 akar dari 3 trie ini.

stateRoot
transactionsRoot
receiptsRoot

State Trie

Terdapat satu state trie global, dan ini diperbarui setiap kali klien memproses sebuah blok. Di dalamnya, sebuah path selalu: keccak256(ethereumAddress) dan sebuah value selalu: rlp(ethereumAccount). Lebih spesifiknya, sebuah akun Ethereum adalah array 4 item dari [nonce,balance,storageRoot,codeHash]. Pada titik ini, perlu dicatat bahwa storageRoot ini adalah akar dari patricia trie lainnya:

Storage Trie

Storage trie adalah tempat semua data kontrak berada. Terdapat storage trie terpisah untuk setiap akun. Untuk mengambil nilai pada posisi penyimpanan tertentu di alamat yang diberikan, alamat penyimpanan, posisi integer dari data yang disimpan di penyimpanan, dan ID blok diperlukan. Ini kemudian dapat diteruskan sebagai argumen ke eth_getStorageAt yang didefinisikan dalam API JSON-RPC, mis., untuk mengambil data di slot penyimpanan 0 untuk alamat 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"}

Mengambil elemen lain dalam penyimpanan sedikit lebih rumit karena posisi di storage trie harus dihitung terlebih dahulu. Posisi dihitung sebagai hash keccak256 dari alamat dan posisi penyimpanan, keduanya diisi dengan nol di sebelah kiri (left-padded) hingga panjang 32 byte. Misalnya, posisi untuk data di slot penyimpanan 1 untuk alamat 0x391694e7e0b0cce554cb130d723a9d27458f9298 adalah:

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

Di konsol Geth, ini dapat dihitung sebagai berikut:

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

Oleh karena itu, path adalah keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Ini sekarang dapat digunakan untuk mengambil data dari storage trie seperti sebelumnya:

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

Catatan: storageRoot untuk akun Ethereum secara default kosong jika itu bukan akun kontrak.

Transactions Trie

Terdapat transactions trie terpisah untuk setiap blok, yang sekali lagi menyimpan pasangan (key, value). Sebuah path di sini adalah: rlp(transactionIndex) yang mewakili kunci yang sesuai dengan nilai yang ditentukan oleh:

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

Informasi lebih lanjut tentang ini dapat ditemukan dalam dokumentasi EIP 2718 (opens in a new tab).

Receipts Trie

Setiap blok memiliki Receipts trie-nya sendiri. Sebuah path di sini adalah: rlp(transactionIndex). transactionIndex adalah indeksnya di dalam blok tempat ia disertakan. Receipts trie tidak pernah diperbarui. Mirip dengan Transactions trie, terdapat tanda terima (receipt) saat ini dan warisan (legacy). Untuk menanyakan tanda terima tertentu di Receipts trie, indeks transaksi di bloknya, payload tanda terima, dan tipe transaksi diperlukan. Tanda terima yang dikembalikan dapat berupa tipe Receipt yang didefinisikan sebagai penggabungan dari TransactionType dan ReceiptPayload atau dapat berupa tipe LegacyReceipt yang didefinisikan sebagai rlp([status, cumulativeGasUsed, logsBloom, logs]).

Informasi lebih lanjut tentang ini dapat ditemukan dalam dokumentasi EIP 2718 (opens in a new tab).

Merkle Patricia Trie

Prasyarat

Radix trie dasar