-
Notifications
You must be signed in to change notification settings - Fork 1
/
tag-trie.html
304 lines (292 loc) · 14.8 KB
/
tag-trie.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<link rel="alternate"
type="application/rss+xml"
href="https://chenyo.me/rss.xml"
title="RSS feed for https://chenyo.me">
<title>Chenyo's Blog</title>
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'],['\\(','\\)']]}});
</script>
<meta name="author" content="chenyo">
<meta name="referrer" content="no-referrer">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="assets/style.css" type="text/css"/>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css"/>
<link rel="favicon" type="image/x-icon" href="favicon.ico">
<script src="assets/search.js"></script></head>
<body>
<div id="preamble" class="status">
<header>
<h1><a href="https://chenyo.me">Chenyo's org-static-blog</a></h1>
<nav>
<a href="https://chenyo.me">Home</a>
<a href="archive.html">Archive</a>
<a href="tags.html">Tags</a>
<div id="search-container">
<input type="text" id="search-input" placeholder="Search anywhere...">
<i class="fas fa-search search-icon"></i>
</div>
</nav>
</header></div>
<div id="content">
<h1 class="title">Posts tagged "trie":</h1>
<div class="post-date">28 Jul 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-07-28-ethereum-merkle-patricia-trie.html">Ethereum Merkle Patricia Trie</a></h1>
<nav id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#orgf7b6299">1. Blockchain fundamentals</a>
<ul>
<li><a href="#org3573270">1.1. RLP (Recursive Length Prefix)</a></li>
<li><a href="#orgfd89f34">1.2. Merkle tree</a>
<ul>
<li><a href="#org542effc">1.2.1. Complexity for \(N\) items.</a></li>
</ul>
</li>
<li><a href="#org86ff4d1">1.3. Patricia tree</a></li>
<li><a href="#orgbec115c">1.4. Merkle Patricia Tree (MPT)</a>
<ul>
<li><a href="#org65736cd">1.4.1. Prefix byte</a></li>
<li><a href="#orgee98561">1.4.2. Complexity for \(N\) items and key length \(K\)</a></li>
</ul>
</li>
<li><a href="#org8911502">1.5. Rollup state tree</a></li>
<li><a href="#org1d61d64">1.6. PoI for Verkle tree (see MegaETH post for details)</a></li>
<li><a href="#orge92ca5d">1.7. Polynomial/KZG commitment</a></li>
</ul>
</li>
<li><a href="#org13490d9">2. Ethereum MPT data structure</a></li>
<li><a href="#orgacd8268">3. Ethereum MPT Functionality</a></li>
<li><a href="#orge26ea95">4. Proof of inclusion</a></li>
</ul>
</div>
</nav>
<p>
This is a personal note of Ethereum Merkle Patricia Trie (MPT), resources are from:
</p>
<ul class="org-ul">
<li><a href="https://github.com/zhangchiqing/merkle-patricia-trie?tab=readme-ov-file">Simplified Go implementation of Ethereum MPT (2022)</a></li>
<li><a href="https://www.youtube.com/watch?v=Qn6sFmo8xGo">Blockchain trees Youtube (2022)</a></li>
<li><a href="https://claude.ai/chat/a3ee5b1f-4d83-46c1-b681-d2d7b170c7e1">Claude.ai</a></li>
</ul>
<div id="outline-container-orgf7b6299" class="outline-2">
<h2 id="orgf7b6299"><span class="section-number-2">1.</span> Blockchain fundamentals</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-org3573270" class="outline-3">
<h3 id="org3573270"><span class="section-number-3">1.1.</span> RLP (Recursive Length Prefix)</h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>A serialization method to encode arbitrarily nested arrays of binary data.</li>
<li>RLP provides a simple (e.g., no type), space-efficient and deterministic encoding.</li>
</ul>
</div>
</div>
<div id="outline-container-orgfd89f34" class="outline-3">
<h3 id="orgfd89f34"><span class="section-number-3">1.2.</span> Merkle tree</h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>Used in Bitcoin to simplify proof of inclusion (PoI) of a transaction.</li>
<li>If one computes the hash of an array of \(N\):
<ul class="org-ul">
<li>Construction complexity: \(O(n)\) time and space.</li>
<li>PoI complexity: \(O(n)\) time and space (needs all other items).</li>
</ul></li>
</ul>
</div>
<div id="outline-container-org542effc" class="outline-4">
<h4 id="org542effc"><span class="section-number-4">1.2.1.</span> Complexity for \(N\) items.</h4>
<div class="outline-text-4" id="text-1-2-1">
<ul class="org-ul">
<li>Construction: \(O(2n)\) time and space.</li>
<li>PoI complexity:
<ul class="org-ul">
<li>\(O(logN)\) space: PoI requires one hash from each level from the leaf to the root (the Merkle tree is binary).</li>
<li>\(O(logN)\) time: \(O(logN)\) to collect all hashes, and \(O(logN)\) to generate the proof.</li>
</ul></li>
</ul>
<figure id="orgaa09efe">
<img src="https://blockonomi.com/wp-content/uploads/2018/06/merkle-tree.jpg" alt="merkle-tree.jpg" align="center" width="500px">
<figcaption><span class="figure-number">Figure 1: </span>Bitcoin Merkle Tree (<a href="https://blockonomi.com/wp-content/uploads/2018/06/merkle-tree.jpg">source</a>)</figcaption>
</figure>
</div>
</div>
</div>
<div id="outline-container-org86ff4d1" class="outline-3">
<h3 id="org86ff4d1"><span class="section-number-3">1.3.</span> Patricia tree</h3>
<div class="outline-text-3" id="text-1-3">
<ul class="org-ul">
<li>Trie: a data structure that stores key-value pair in a key’s prefix tree.</li>
<li>Patricia tree: compress trie by merging nodes on the same path.</li>
<li>The structure the Patricia tree is independent of the item insertion order.</li>
<li>The time complexity for add, query and deletion is \(O(K)\), where \(K\) is the key length.</li>
</ul>
<figure id="org6547c20">
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/ae/Patricia_trie.svg/525px-Patricia_trie.svg.png" alt="525px-Patricia_trie.svg.png" align="center" width="400px">
<figcaption><span class="figure-number">Figure 2: </span>Patricia Tree (<a href="https://upload.wikimedia.org/wikipedia/commons/thumb/a/ae/Patricia_trie.svg/525px-Patricia_trie.svg.png">source</a>)</figcaption>
</figure>
</div>
</div>
<div id="outline-container-orgbec115c" class="outline-3">
<h3 id="orgbec115c"><span class="section-number-3">1.4.</span> Merkle Patricia Tree (MPT)</h3>
<div class="outline-text-3" id="text-1-4">
<ul class="org-ul">
<li>MPT is a hex-ary Merkle tree with an additional DB for hash lookup.</li>
<li>There are 4 types of nodes:
<ul class="org-ul">
<li>Empty node: the null node the root points to when first creating the tree.</li>
<li>Leaf node: stores the real data, e.g., account balance.</li>
<li>Branch node: stores the pointers to at most 16 other nodes, e.g., they have the common prefix (nibbles) before and differ at the current <b><b>nibble</b></b> (4 bit,0-f).</li>
<li>Extension node: record the compressed common prefix for a branch node.</li>
</ul></li>
<li>Each <b><b>pointer</b></b> in the tree is the <b><b>hash value</b></b> of the child node; the real node data is stored in a separate DB that maps from a node hash to its data.</li>
<li>If the child node is small, the parent node could also directly store the node data rather than the hash pointer.</li>
<li>In practical implementation, the <b><b>entire tree</b></b> is typically stored in a KV DB, and each node is stored with its hash as the key.</li>
</ul>
<figure id="org66b7a36">
<img src="https://github.com/zhangchiqing/merkle-patricia-trie/raw/master/diagrams/4_add_4th_tx_kv.png" alt="4_add_4th_tx_kv.png" align="center" width="400px">
<figcaption><span class="figure-number">Figure 3: </span>MPT DB storage (<a href="https://github.com/zhangchiqing/merkle-patricia-trie/raw/master/diagrams/4_add_4th_tx_kv.png">source</a>)</figcaption>
</figure>
</div>
<div id="outline-container-org65736cd" class="outline-4">
<h4 id="org65736cd"><span class="section-number-4">1.4.1.</span> Prefix byte</h4>
<div class="outline-text-4" id="text-1-4-1">
<ul class="org-ul">
<li>Identify both the node type and the parity of the stored nibbles.</li>
<li>Leaf node: 2 if the <code>key-end</code> has even number of nibbles, e.g., the compressed ending of an account; 3X if the number is odd (so the last 4-bit is stored as X in the prefix).</li>
<li>Extension: 0 if the <code>shared nibbles</code> has even number; 1X if has odd number.</li>
</ul>
</div>
</div>
<div id="outline-container-orgee98561" class="outline-4">
<h4 id="orgee98561"><span class="section-number-4">1.4.2.</span> Complexity for \(N\) items and key length \(K\)</h4>
<div class="outline-text-4" id="text-1-4-2">
<ul class="org-ul">
<li>Construction:
<ul class="org-ul">
<li>Time: worst \(O(NK)\); average: \(O(Nlog_{16}N)\).</li>
<li>Space: \(O(N)\).</li>
</ul></li>
<li>Indexing (e.g., query an account balance):
<ul class="org-ul">
<li>Time: tree traversal worst \(O(K)\), average \(O(log_{16}N)\); <b><b>each traversal equals a DB query</b></b>.</li>
</ul></li>
<li>PoI: \(O(16log_{16}N)\) time and space.
<ul class="org-ul">
<li>Calculating the hash of a branch node requires the hash of all 16 child nodes.</li>
</ul></li>
</ul>
<figure id="org3a2eae6">
<img src="https://i.sstatic.net/YZGxe.png" alt="YZGxe.png" align="center" width="600px">
<figcaption><span class="figure-number">Figure 4: </span>Merkle Patricia Tree (<a href="https://i.sstatic.net/YZGxe.png">source</a>)</figcaption>
</figure>
</div>
</div>
</div>
<div id="outline-container-org8911502" class="outline-3">
<h3 id="org8911502"><span class="section-number-3">1.5.</span> Rollup state tree</h3>
<div class="outline-text-3" id="text-1-5">
<ul class="org-ul">
<li>Rollup has a higher performance requirement for PoI.</li>
<li><b><b>Separate</b></b> the indexing and PoI with a sorted key-value arrays and a (binary) Merkle tree.
<ul class="org-ul">
<li>MPT: <code>{Addr0: State0, Addr1: State1,...}</code>.</li>
<li>Rollup: map: <code>{Addr0: Id0, Addr1: Id1,...}</code> + array: <code>[(Addr0, State0), (Addr1, State1),...]</code>.</li>
</ul></li>
<li>When a client wants to query an account, it first gets the key id from the map, then get the state from the array.</li>
<li>When a node wants to generate PoI, it follows the merkle path and collect hashes (more hashes than MPT).</li>
</ul>
</div>
</div>
<div id="outline-container-org1d61d64" class="outline-3">
<h3 id="org1d61d64"><span class="section-number-3">1.6.</span> PoI for Verkle tree (see <a href="https://chenyo-17.github.io/org-static-blog/2024-07-04-parallel-evm:-megaeth.html">MegaETH post</a> for details)</h3>
<div class="outline-text-3" id="text-1-6">
<ul class="org-ul">
<li>Stateless light nodes get a witness along with the new block, the witness is a PoI for the state change in the block.</li>
<li>Light nodes download related state information, e.g., changed account from other full nodes, or from the portal network.</li>
</ul>
</div>
</div>
<div id="outline-container-orge92ca5d" class="outline-3">
<h3 id="orge92ca5d"><span class="section-number-3">1.7.</span> Polynomial/KZG commitment</h3>
<div class="outline-text-3" id="text-1-7">
<ul class="org-ul">
<li>In MPT, PoI for a branch node requires the hash values of all branches.</li>
<li>KZG commitment reduce the proof size by adding a polynomial formula \(f(x)\) in the branch node, and each branch has a point \((x, y)\) such that \(y = f(x)\).</li>
<li>In this way, the proof no longer requires hashes of other branches, the proof space complexity \(O(log_{16}N)\) (no 16 coefficient).</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org13490d9" class="outline-2">
<h2 id="org13490d9"><span class="section-number-2">2.</span> Ethereum MPT data structure</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Essentially is a key-value mapping; it provides <code>Get</code>, <code>Put</code> and <code>Del</code> functions.</li>
<li>Ethereum has 3 MPTs: transaction trie; receipt trie and state trie, each trie root hash is included in the block header.
<ul class="org-ul">
<li><code>transactionTrie</code>: all transactions included in the block.
<ul class="org-ul">
<li>The keys are the RLP encodings of an unsigned integer starting from 0.</li>
<li>The values are the RLP encodings of the transaction.</li>
</ul></li>
<li><code>stateTrie</code>: all account states in the network.</li>
<li><code>receiptTrie</code>: the outcomes of all transaction executions in the block, e.g., gas used, transaction status.</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-orgacd8268" class="outline-2">
<h2 id="orgacd8268"><span class="section-number-2">3.</span> Ethereum MPT Functionality</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li>Allows to verify <b><b>data integrity</b></b> with the <code>Hash</code> function to compute the Merkle root hash.</li>
<li>Allows to verify the <b><b>inclusion</b></b> of a key-value pair without the access to the entire key-value pairs.
<ul class="org-ul">
<li>A full node provide a merkle proof <code>Proof</code> for a key-value pair (e.g., an account and its balance).</li>
<li>A light node can verify a proof only against the root hash with <code>VerifyProf(rootHash, key, proof)</code>; if the proof does not match the hash (e.g., the balance mismatches), an error is thrown.</li>
</ul></li>
<li>Why would a light node trust the root hash: it trusts the consensus mechanism, e.g., other benign full nodes verify the hash, act honestly is more profitable.</li>
</ul>
</div>
</div>
<div id="outline-container-orge26ea95" class="outline-2">
<h2 id="orge26ea95"><span class="section-number-2">4.</span> Proof of inclusion</h2>
<div class="outline-text-2" id="text-4">
<ul class="org-ul">
<li>Proof: the path from the root to the leaf node.</li>
<li>Verification: start from the root, decode the node to match the nibbles until find the node that matches all the remaining nibbles; if not found, the proof is invalid.</li>
</ul>
</div>
</div>
<div class="taglist"><a href="https://chenyo.me/tags.html">Tags</a>: <a href="https://chenyo.me/tag-evm.html">evm</a> <a href="https://chenyo.me/tag-trie.html">trie</a> </div><div id="archive">
<a href="https://chenyo.me/archive.html">Other posts</a>
</div>
</div>
<div id="postamble" class="status"><div id="search-results"></div>
<footer>
<div class="footer-content">
<div class="footer-left">
<p>© 2024 chenyo. Some rights reserved.</p>
<a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width: 0"
src="https://i.creativecommons.org/l/by-nc/4.0/88x31.png"/>
</a>
</div>
<div class="social-links">
<a href="https://t.me/feihuadawangjiushiwo" target="_blank" rel="noopener noreferrer">
<i class="fab fa-telegram"></i>
</a>
<a href="https://github.com/chenyo-17" target="_blank" rel="noopener noreferrer">
<i class="fab fa-github"></i>
</a>
</div>
</footer></div>
</body>
</html>