-
Notifications
You must be signed in to change notification settings - Fork 1
/
tag-bnb.html
359 lines (349 loc) · 15.6 KB
/
tag-bnb.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
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
<!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 "bnb":</h1>
<div class="post-date">14 Jul 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-07-14-parallel-evm:-bep-130.html">Parallel EVM: BEP-130</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="#orge2771bc">1. Blockchain fundamentals</a>
<ul>
<li><a href="#org69c633d">1.1. System contract</a></li>
<li><a href="#org9e40074">1.2. Transaction execution phases</a></li>
</ul>
</li>
<li><a href="#org87059dc">2. Design principle</a></li>
<li><a href="#org3917a6e">3. Workflow</a>
<ul>
<li><a href="#orgc2b83c6">3.1. Dispatch factors</a></li>
<li><a href="#orge09585a">3.2. Slot execution stages</a></li>
<li><a href="#org01ea43d">3.3. Conflict detection</a></li>
</ul>
</li>
</ul>
</div>
</nav>
<p>
This is a personal note for <a href="https://github.com/bnb-chain/BEPs/blob/master/BEPs/BEP130.md">BEP-130</a>.
BEP-130 is a proposal that introduces a parallel transaction execution mechanism on the BNB Smart Chain (BSC).
</p>
<div id="outline-container-orge2771bc" class="outline-2">
<h2 id="orge2771bc"><span class="section-number-2">1.</span> Blockchain fundamentals</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-org69c633d" class="outline-3">
<h3 id="org69c633d"><span class="section-number-3">1.1.</span> System contract</h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>Built-in contracts to perform system level operations, e,g., gas fee reward, cross chain communication.</li>
<li>Cannot be executed concurrently since they depend on the execution results of other transactions, e.g., a number of transaction made by an account at some timestamp.</li>
</ul>
</div>
</div>
<div id="outline-container-org9e40074" class="outline-3">
<h3 id="org9e40074"><span class="section-number-3">1.2.</span> Transaction execution phases</h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>Block mining phase: received from the P2P transaction pool, could contain invalid transactions.</li>
<li>Block sync phase: the block is confirmed.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org87059dc" class="outline-2">
<h2 id="org87059dc"><span class="section-number-2">2.</span> Design principle</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Should always produce the same result as the current sequential execution.</li>
<li>Should be decoupled into existing or new modules with no circular dependency.</li>
<li>Should be configurable based on node hardware resources.</li>
<li>Keep it simple and smart.</li>
</ul>
</div>
</div>
<div id="outline-container-org3917a6e" class="outline-2">
<h2 id="org3917a6e"><span class="section-number-2">3.</span> Workflow</h2>
<div class="outline-text-2" id="text-3">
</div>
<div id="outline-container-orgc2b83c6" class="outline-3">
<h3 id="orgc2b83c6"><span class="section-number-3">3.1.</span> Dispatch factors</h3>
<div class="outline-text-3" id="text-3-1">
<ul class="org-ul">
<li>Is the slot idle or occupied?</li>
<li>Is there a same address contract running or pending in this slot?</li>
<li>Has the slot’s pending transactions size reached the max transactions queue size limitation?</li>
<li>Is there a big transaction index gap between the slot’s head transaction and the dispatched transaction?</li>
<li>Is the transaction contract likely to have high gas cost or a conflict rate?</li>
</ul>
</div>
</div>
<div id="outline-container-orge09585a" class="outline-3">
<h3 id="orge09585a"><span class="section-number-3">3.2.</span> Slot execution stages</h3>
<div class="outline-text-3" id="text-3-2">
<ol class="org-ol">
<li>Execute the transaction \(Tx_i\)based on a specific worldstate, e.g., the state when the execution starts.</li>
<li>Wait for the finalization of the previous transaction \(Tx_{i-1}\).</li>
<li>Detect if there is any conflict between the state read by \(Tx_i\) and the state change after the execution of \(Tx_i\) starts.</li>
<li>If a conflict is detected, re-execute \(Tx_{i}\) again based on the latest finalized worldstate.</li>
<li>Finalize the state changed by \(Tx_i\) to the latest worldstate.</li>
<li>The state changes are kept within each slot, and are merged to the main StateDB once the execution is done.</li>
<li>The first transaction in a block can be immediately finalized.</li>
<li>If \(Tx_i\) and \(Tx_{i-1}\) are in the same slot, \(Tx_i\) can immediately start conflict detection.</li>
<li>Re-executed transaction can be immediately finalized as it reads the latest worldstate.</li>
</ol>
</div>
</div>
<div id="outline-container-org01ea43d" class="outline-3">
<h3 id="org01ea43d"><span class="section-number-3">3.3.</span> Conflict detection</h3>
<div class="outline-text-3" id="text-3-3">
<ul class="org-ul">
<li>Detection items: storage key/value pair; account balance; contract content and status.</li>
<li>Overlap reads without write, or hardcode writes without read are not conflicts.</li>
</ul>
</div>
</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-parallel-evm.html">parallel-evm</a> <a href="https://chenyo.me/tag-bnb.html">bnb</a> </div>
<div class="post-date">07 Jul 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-07-07-parallel-evm:-bnb-chain.html">Parallel EVM: BNB chain</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="#org3cfd85a">1. Blockchain fundamentals</a>
<ul>
<li><a href="#org9489617">1.1. Why is parallel EVM not easy</a></li>
<li><a href="#org91459cc">1.2. A Parallel EVM ideas</a></li>
<li><a href="#orgac74760">1.3. Block STM algorithm</a></li>
</ul>
</li>
<li><a href="#org89b3b0e">2. BNB Parallel EVM 1.0: Infrastructure</a></li>
<li><a href="#orgc6e3320">3. BNB Parallel EVM 2.0: Performance enhancement</a></li>
<li><a href="#org3031326">4. BNB Parallel EVM 3.0: Production</a>
<ul>
<li><a href="#org41dcabc">4.1. Hint-based dispatcher</a></li>
<li><a href="#orgbf38fde">4.2. Seamless BNB chain ecosystem integration</a></li>
</ul>
</li>
<li><a href="#org0a50e59">5. Comparison with other solutions</a></li>
<li><a href="#org48a8333">6. Other optimizations</a></li>
</ul>
</div>
</nav>
<p>
This is a personal note for <a href="https://www.bnbchain.org/zh-CN/blog/road-to-high-performance-parallel-evm-for-bnb-chain">BNB chain-blog</a>.
</p>
<div id="outline-container-org3cfd85a" class="outline-2">
<h2 id="org3cfd85a"><span class="section-number-2">1.</span> Blockchain fundamentals</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-org9489617" class="outline-3">
<h3 id="org9489617"><span class="section-number-3">1.1.</span> Why is parallel EVM not easy</h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>Lack of visibility of potential transaction conflict.</li>
<li>Blockchains experience transaction bursts, e.g., >70M transactions per day.</li>
</ul>
</div>
</div>
<div id="outline-container-org91459cc" class="outline-3">
<h3 id="org91459cc"><span class="section-number-3">1.2.</span> A Parallel EVM ideas</h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>Run multiple EVM instances concurrently on different threads.</li>
<li>Execute transactions independently on each thread and later merge a finial state update.</li>
<li><a href="https://lh7-us.googleusercontent.com/Dh1GAMYlMkiRI0xWQ0ByYOxq_GNtA9h1PP1OF7FP9b8O3VRxVtlh1eq991OlNa4rNX_ZXH8tVPRBeN58_0dBF1jPUVRuuJMl4JqmBchhCTZp_vF-W003l77KajIjIMCHfapjsBH--0EpMi0FT2iNPlw">Parallel EVM scheme</a></li>
</ul>
</div>
</div>
<div id="outline-container-orgac74760" class="outline-3">
<h3 id="orgac74760"><span class="section-number-3">1.3.</span> Block STM algorithm</h3>
<div class="outline-text-3" id="text-1-3">
<ul class="org-ul">
<li>Optimistic parallelism: assigns transactions to various threads.</li>
<li>Software transaction memory (STM): detect conflicts when transactions try to modify the same shared state simultaneously.</li>
<li>Conflict resolution: when conflicts are detected, the offending transactions are discarded without affecting the blockchain state and are re-executed.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org89b3b0e" class="outline-2">
<h2 id="org89b3b0e"><span class="section-number-2">2.</span> BNB Parallel EVM 1.0: Infrastructure</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Proposal: <a href="https://github.com/bnb-chain/BEPs/pull/130?ref=bnbchain.ghost.io">BEP-130 (2022)</a></li>
<li>Dispatcher: distributes transactions across threads to optimize throughput.</li>
<li>Parallel execution engine: execute transactions independently on each thread.</li>
<li>Local stateDB: each thread maintains a local stateDB to record state access.</li>
<li>Conflict detection: detect conflicts and re-execute conflicting transactions.</li>
<li>State commit: the finalized results are committed to the global state DB.</li>
</ul>
</div>
</div>
<div id="outline-container-orgc6e3320" class="outline-2">
<h2 id="orgc6e3320"><span class="section-number-2">3.</span> BNB Parallel EVM 2.0: Performance enhancement</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li>Dispatcher: combine both static and dynamic dispatch strategies.</li>
<li>Execution engine: streaming pipeline to enable smooth transaction processing.</li>
<li>Conflict detection: ensure data integrity while minimizing unnecessary re-execution.</li>
<li>Memory: shared memory pools and light copying techniques to reduce memory footprint.</li>
<li>The overall performance ranges from 20% to 50%.</li>
</ul>
</div>
</div>
<div id="outline-container-org3031326" class="outline-2">
<h2 id="org3031326"><span class="section-number-2">4.</span> BNB Parallel EVM 3.0: Production</h2>
<div class="outline-text-2" id="text-4">
</div>
<div id="outline-container-org41dcabc" class="outline-3">
<h3 id="org41dcabc"><span class="section-number-3">4.1.</span> Hint-based dispatcher</h3>
<div class="outline-text-3" id="text-4-1">
<ul class="org-ul">
<li>leverages external hint providers to analyze transactions and generate predictions about potential state access conflicts.</li>
<li>Simple hints include read/write state sets; advanced hints incorporate weak/strong ordering for optimal parallelism.</li>
<li>Conflicting transactions are assigned to the same slot.</li>
<li>Transactions with no conflicts are distributed across different slots.</li>
<li>Conflict detector remains as a backup for handling unforeseen conflicts.</li>
</ul>
</div>
</div>
<div id="outline-container-orgbf38fde" class="outline-3">
<h3 id="orgbf38fde"><span class="section-number-3">4.2.</span> Seamless BNB chain ecosystem integration</h3>
<div class="outline-text-3" id="text-4-2">
<ul class="org-ul">
<li>Modularization and reconstructing.</li>
<li>Thorough testing and validation.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org0a50e59" class="outline-2">
<h2 id="org0a50e59"><span class="section-number-2">5.</span> Comparison with other solutions</h2>
<div class="outline-text-2" id="text-5">
<table>
<colgroup>
<col class="org-left">
<col class="org-left">
<col class="org-left">
<col class="org-left">
</colgroup>
<thead>
<tr>
<th scope="col" class="org-left">Solutions</th>
<th scope="col" class="org-left">TX dependency check</th>
<th scope="col" class="org-left">Conflict resolution</th>
<th scope="col" class="org-left">StateDB optimization</th>
</tr>
</thead>
<tbody>
<tr>
<td class="org-left">BlockSTM</td>
<td class="org-left">tracks at execution</td>
<td class="org-left">re-execution</td>
<td class="org-left">N/A</td>
</tr>
<tr>
<td class="org-left">Polygon</td>
<td class="org-left">minimal metadata solution</td>
<td class="org-left">reduced re-execution</td>
<td class="org-left">N/A</td>
</tr>
<tr>
<td class="org-left">Monad</td>
<td class="org-left">static analysis</td>
<td class="org-left">reduced re-execution</td>
<td class="org-left">Monad DB</td>
</tr>
<tr>
<td class="org-left">Sei</td>
<td class="org-left">tracks at execution</td>
<td class="org-left">re-execution</td>
<td class="org-left">SeiDB</td>
</tr>
<tr>
<td class="org-left">Neon EVM and Solana Sealevel</td>
<td class="org-left">contract provided</td>
<td class="org-left">reduced re-execution</td>
<td class="org-left">depends on Solana</td>
</tr>
<tr>
<td class="org-left">BNBChain</td>
<td class="org-left">hint info</td>
<td class="org-left">reduced or eliminated re-execution</td>
<td class="org-left">Thread local DB</td>
</tr>
</tbody>
</table>
</div>
</div>
<div id="outline-container-org48a8333" class="outline-2">
<h2 id="org48a8333"><span class="section-number-2">6.</span> Other optimizations</h2>
<div class="outline-text-2" id="text-6">
<ul class="org-ul">
<li>Opcode-level optimization: fine-tuning individual EVM instructions for maximum efficiency.</li>
<li>Compilation optimization: JIT/AOT compilation paradigms; instruction-level parallelism (SIMD).</li>
<li>Database sharding: distribute data across multiple databases.</li>
<li>Concurrent node execution.</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-parallel-evm.html">parallel-evm</a> <a href="https://chenyo.me/tag-bnb.html">bnb</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/chenyo17" 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>