-
Notifications
You must be signed in to change notification settings - Fork 1
/
tag-evm.html
1763 lines (1726 loc) · 88.7 KB
/
tag-evm.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
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!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 "evm":</h1>
<div class="post-date">08 Aug 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-08-08-parallel-evm:-blockworks-bigger-picture.html">Parallel EVM: Blockworks news (Sei, Monad, Solana)</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="#orga587ecd">1. Terminology</a>
<ul>
<li><a href="#org5f410f3">1.1. Ethereum sharding</a></li>
<li><a href="#org17f2a79">1.2. Blob</a></li>
<li><a href="#org83bbc3a">1.3. Erasure coding</a></li>
<li><a href="#org51c3b10">1.4. Data availability sampling (DAS)</a></li>
<li><a href="#orgcd92788">1.5. Danksharding (L2 optimization)</a></li>
<li><a href="#org3dd14bd">1.6. Relations between L1 and L2 scaling</a></li>
<li><a href="#orgb76173b">1.7. Double spending prevention</a></li>
<li><a href="#org826e3b0">1.8. Sealevel (Solana)</a></li>
</ul>
</li>
<li><a href="#org471cb12">2. Ways to achieve parallel processing</a></li>
<li><a href="#orge5e259b">3. Production-ready parallelized EVM projects (Jan 2024)</a></li>
</ul>
</div>
</nav>
<p>
This is a personal note for <a href="https://blockworks.co/news/parallelized-evms-gaining-popularity">Blockworks news (12.01.2024)</a> as well as some terminology explained online, e.g., <a href="https://www.coindesk.com/learn/what-is-ethereum-sharding-a-beginners-guide/">Coindesk</a> and <a href="https://chatgpt.com/c/824f05c9-dc75-4eb6-aeda-59d057baf83a">GPT-4o</a>.
</p>
<div id="outline-container-orga587ecd" class="outline-2">
<h2 id="orga587ecd"><span class="section-number-2">1.</span> Terminology</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-org5f410f3" class="outline-3">
<h3 id="org5f410f3"><span class="section-number-3">1.1.</span> Ethereum sharding</h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>The Ethereum mainnet is divided into smaller interconnected networks called shards.</li>
<li>Each shard processes and validates its own transactions parallel to others.</li>
<li>Pros: increase scalability and <b><b>participation</b></b>.</li>
<li>Cons: a single unit can be compromised; lead to centralization.</li>
</ul>
</div>
</div>
<div id="outline-container-org17f2a79" class="outline-3">
<h3 id="org17f2a79"><span class="section-number-3">1.2.</span> Blob</h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>Rather than storing each transaction data directly in the blockchain, the data is aggregated into a blob (binary object).</li>
<li>Each blob performs erasure coding to dive the blob into multiple smaller pieces with redundancy.</li>
<li>Encoded pieces are stored separately, the block header contain pointers to the piece locations without storing actual data.</li>
<li>Transactions in a block may be distributed across multiple blobs.</li>
</ul>
</div>
</div>
<div id="outline-container-org83bbc3a" class="outline-3">
<h3 id="org83bbc3a"><span class="section-number-3">1.3.</span> Erasure coding</h3>
<div class="outline-text-3" id="text-1-3">
<ul class="org-ul">
<li>Allows one to encode blobs such that if at least half of the data in the blob is published, anyone in the network can reconstruct and re-publish the rest of the data.</li>
</ul>
</div>
</div>
<div id="outline-container-org51c3b10" class="outline-3">
<h3 id="org51c3b10"><span class="section-number-3">1.4.</span> Data availability sampling (DAS)</h3>
<div class="outline-text-3" id="text-1-4">
<ul class="org-ul">
<li>Validators randomly sample blob pieces to confirm the data can be reconstructed.g</li>
<li>If a client cannot get enough pieces to verify the blob availability, or the blob fails the integrity check, or transactions within the blob are invalid or inconsistent with the blockchain state, the blob is rejected.</li>
</ul>
</div>
</div>
<div id="outline-container-orgcd92788" class="outline-3">
<h3 id="orgcd92788"><span class="section-number-3">1.5.</span> Danksharding (L2 optimization)</h3>
<div class="outline-text-3" id="text-1-5">
<ul class="org-ul">
<li>A specific sharding implementation proposal.</li>
<li>Require data availability sampling and <a href="https://chenyo-17.github.io/org-static-blog/tag-evm.html#orgf2db0ef">proposer-builder separation</a>.</li>
<li>Can support hundreds of individual rollups.</li>
</ul>
</div>
</div>
<div id="outline-container-org3dd14bd" class="outline-3">
<h3 id="org3dd14bd"><span class="section-number-3">1.6.</span> Relations between L1 and L2 scaling</h3>
<div class="outline-text-3" id="text-1-6">
<ul class="org-ul">
<li>L1 scaling: optimizations directly to the Ethereum mainnet and core infrastructure, e.g., parallel EVM.</li>
<li>L2 scaling: building secondary rollup layers, e.g., optimistic rollups and ZK rollups, to offload mainnet computation and storage.</li>
</ul>
</div>
</div>
<div id="outline-container-orgb76173b" class="outline-3">
<h3 id="orgb76173b"><span class="section-number-3">1.7.</span> Double spending prevention</h3>
<div class="outline-text-3" id="text-1-7">
<ul class="org-ul">
<li>Bitcoin: uses UTXOs to track which inputs have been spent (no need to go through the entire chain).</li>
<li>Ethereum: uses a nounce to track the number of transactions sent from an account, the nounce is included in the transaction and is incremented by 1 for every new transaction, and all transactions must be executed in order.</li>
</ul>
</div>
</div>
<div id="outline-container-org826e3b0" class="outline-3">
<h3 id="org826e3b0"><span class="section-number-3">1.8.</span> Sealevel (Solana)</h3>
<div class="outline-text-3" id="text-1-8">
<ul class="org-ul">
<li>Solana’s parallel smart contract runtime to process thousands of contracts in parallel.</li>
<li>Solana transactions describe all states a transaction accesses to efficiently recognize transaction dependency and to schedule parallel execution without accessing full blockchain state.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org471cb12" class="outline-2">
<h2 id="org471cb12"><span class="section-number-2">2.</span> Ways to achieve parallel processing</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Process independent transactions in parallel.</li>
<li>Sharding.</li>
</ul>
</div>
</div>
<div id="outline-container-orge5e259b" class="outline-2">
<h2 id="orge5e259b"><span class="section-number-2">3.</span> Production-ready parallelized EVM projects (Jan 2024)</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li>Sei: optimistic parallel execution.</li>
<li>Monad: custom EVM implementation, optimistic parallel execution, <b><b>custom state database</b></b>.
<ul class="org-ul">
<li>Commodity databases are not optimized for Merkle tree data read/write with SSD.</li>
</ul></li>
<li>Neon (Solana): transactions pre-specify dependencies.</li>
<li>See <a href="https://chenyo-17.github.io/org-static-blog/tag-evm.html#orgcb5510d">BNB chain post</a> for more solutions.</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-blockworks.html">blockworks</a> </div>
<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="#orgb2329cb">1. Blockchain fundamentals</a>
<ul>
<li><a href="#orgf17bc83">1.1. RLP (Recursive Length Prefix)</a></li>
<li><a href="#org27a0a3e">1.2. Merkle tree</a>
<ul>
<li><a href="#orgf850705">1.2.1. Complexity for \(N\) items.</a></li>
</ul>
</li>
<li><a href="#org5e3dd63">1.3. Patricia tree</a></li>
<li><a href="#org9107efb">1.4. Merkle Patricia Tree (MPT)</a>
<ul>
<li><a href="#org5dcd242">1.4.1. Prefix byte</a></li>
<li><a href="#orgca46a9c">1.4.2. Complexity for \(N\) items and key length \(K\)</a></li>
</ul>
</li>
<li><a href="#orgb7d70ab">1.5. Rollup state tree</a></li>
<li><a href="#org0ee0da9">1.6. PoI for Verkle tree (see MegaETH post for details)</a></li>
<li><a href="#orgc18a9a3">1.7. Polynomial/KZG commitment</a></li>
</ul>
</li>
<li><a href="#org1e1c405">2. Ethereum MPT data structure</a></li>
<li><a href="#org5aa1dbc">3. Ethereum MPT Functionality</a></li>
<li><a href="#org9020fde">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-orgb2329cb" class="outline-2">
<h2 id="orgb2329cb"><span class="section-number-2">1.</span> Blockchain fundamentals</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-orgf17bc83" class="outline-3">
<h3 id="orgf17bc83"><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-org27a0a3e" class="outline-3">
<h3 id="org27a0a3e"><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-orgf850705" class="outline-4">
<h4 id="orgf850705"><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="org9c04db4">
<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-org5e3dd63" class="outline-3">
<h3 id="org5e3dd63"><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="orgff0a970">
<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-org9107efb" class="outline-3">
<h3 id="org9107efb"><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="org350f98e">
<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-org5dcd242" class="outline-4">
<h4 id="org5dcd242"><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-orgca46a9c" class="outline-4">
<h4 id="orgca46a9c"><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="org652adc3">
<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-orgb7d70ab" class="outline-3">
<h3 id="orgb7d70ab"><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-org0ee0da9" class="outline-3">
<h3 id="org0ee0da9"><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-orgc18a9a3" class="outline-3">
<h3 id="orgc18a9a3"><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-org1e1c405" class="outline-2">
<h2 id="org1e1c405"><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-org5aa1dbc" class="outline-2">
<h2 id="org5aa1dbc"><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-org9020fde" class="outline-2">
<h2 id="org9020fde"><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 class="post-date">24 Jul 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-07-24-parallel-evm:-reth.html">Parallel EVM: Reth scaling plan</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="#org20950c8">1. Blockchain fundamentals</a>
<ul>
<li><a href="#orgf59b06d">1.1. Ethereum engine API</a></li>
<li><a href="#org6a6169c">1.2. Foundry</a></li>
<li><a href="#org97695c9">1.3. Revm</a></li>
<li><a href="#org97ce1ae">1.4. Alloy</a></li>
<li><a href="#org88dd316">1.5. Erigon & Staged sync</a></li>
<li><a href="#org21fc794">1.6. Storage engines</a>
<ul>
<li><a href="#orgf604566">1.6.1. ACID</a></li>
<li><a href="#org737338e">1.6.2. MVCC (Multi-version concurrency control)</a></li>
<li><a href="#orge0cbff7">1.6.3. Common database models</a></li>
<li><a href="#orgceb3dd0">1.6.4. Common storage engines</a></li>
</ul>
</li>
<li><a href="#org6b0a87a">1.7. Reth</a></li>
<li><a href="#org478ab9b">1.8. Why gas per second as the performance metric</a></li>
<li><a href="#org3e971b2">1.9. EVM cost models</a></li>
<li><a href="#orged77b07">1.10. TPC benchmark</a></li>
<li><a href="#org89f5af9">1.11. State growth</a></li>
<li><a href="#orgdf456e7">1.12. JIT (Just-In-Time) and AOT (Ahead-of-Time) EVM</a></li>
<li><a href="#orgf3797a6">1.13. Actor model</a></li>
<li><a href="#orge6bfe92">1.14. Storage trie</a></li>
<li><a href="#org9662699">1.15. Serverless database</a></li>
</ul>
</li>
<li><a href="#orgb4b09e9">2. Reth scaling plan</a>
<ul>
<li><a href="#org1900484">2.1. Vertical scaling (2024)</a>
<ul>
<li><a href="#org61d0655">2.1.1. JIT/AOT EVM</a></li>
<li><a href="#org05122cc">2.1.2. Parallel EVM</a></li>
<li><a href="#org6bffaf9">2.1.3. Optimized state commitment</a></li>
</ul>
</li>
<li><a href="#org266842c">2.2. Horizontal scaling (2025)</a>
<ul>
<li><a href="#org729b06d">2.2.1. Multi-Rollup (?)</a></li>
<li><a href="#orgb4aacf1">2.2.2. Cloud-Native nodes.</a></li>
</ul>
</li>
<li><a href="#org2b8c868">2.3. Open questions</a></li>
</ul>
</li>
</ul>
</div>
</nav>
<p>
This is a personal note for <a href="https://www.paradigm.xyz/2024/04/reth-perf">Reth-performance-blog</a> as well as some terminology explain online, e.g., <a href="https://github.com/paradigmxyz/reth">Reth-repo</a> and <a href="https://claude.ai/chat/6364436f-d279-4c6b-947e-237bfea26409">Claude.ai</a>.
</p>
<div id="outline-container-org20950c8" class="outline-2">
<h2 id="org20950c8"><span class="section-number-2">1.</span> Blockchain fundamentals</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-orgf59b06d" class="outline-3">
<h3 id="orgf59b06d"><span class="section-number-3">1.1.</span> <a href="https://github.com/ethereum/execution-apis/blob/a0d03086564ab1838b462befbc083f873dcf0c0f/src/engine/paris.md">Ethereum engine API</a></h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>A collection of JSON-RPC methods that all execution clients implement.</li>
<li>Specify the interfaces between consensus and execution layers.</li>
</ul>
</div>
</div>
<div id="outline-container-org6a6169c" class="outline-3">
<h3 id="org6a6169c"><span class="section-number-3">1.2.</span> <a href="https://github.com/foundry-rs/foundry/">Foundry</a></h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>A Rust-written toolkit for Ethereum application development.</li>
<li>Consists of an Ethereum testing framework Forge; a framework to interact with the chain Cast; a local Ethereum node Anvil; and a Solidity REPL (Read-Eval-Print-Loop: an interactive environment) Chisel.</li>
</ul>
</div>
</div>
<div id="outline-container-org97695c9" class="outline-3">
<h3 id="org97695c9"><span class="section-number-3">1.3.</span> <a href="https://github.com/bluealloy/revm/">Revm</a></h3>
<div class="outline-text-3" id="text-1-3">
<ul class="org-ul">
<li>A Rust-written EVM; responsible for executing transactions and contracts.</li>
</ul>
</div>
</div>
<div id="outline-container-org97ce1ae" class="outline-3">
<h3 id="org97ce1ae"><span class="section-number-3">1.4.</span> <a href="https://github.com/alloy-rs">Alloy</a></h3>
<div class="outline-text-3" id="text-1-4">
<ul class="org-ul">
<li>A library to interact with the Ethereum and other EVM-base chains.</li>
</ul>
</div>
</div>
<div id="outline-container-org88dd316" class="outline-3">
<h3 id="org88dd316"><span class="section-number-3">1.5.</span> <a href="https://erigon.tech/">Erigon</a> & Staged sync</h3>
<div class="outline-text-3" id="text-1-5">
<ul class="org-ul">
<li>Erigon: a Go-written Ethereum client implementation (execution layer).</li>
<li>Staged sync: break the chain synchronization process into distinct stages in order to achieve better efficiency.</li>
</ul>
</div>
</div>
<div id="outline-container-org21fc794" class="outline-3">
<h3 id="org21fc794"><span class="section-number-3">1.6.</span> Storage engines</h3>
<div class="outline-text-3" id="text-1-6">
</div>
<div id="outline-container-orgf604566" class="outline-4">
<h4 id="orgf604566"><span class="section-number-4">1.6.1.</span> ACID</h4>
<div class="outline-text-4" id="text-1-6-1">
<ul class="org-ul">
<li>A set of properties for database transactions: atomicity, consistency, isolation, duration.</li>
<li>Atomicity: a transaction is treated as an indivisible unit; if any part of the transaction fails, the entire transaction is rolled back.</li>
<li>Consistency: a transaction brings the database from one valid state to another.</li>
<li>Isolation: concurrent transaction execution leave the database in the same state as if transactions are executed sequentially</li>
<li>Duration: a committed transaction remains committed even when the system fails.</li>
</ul>
</div>
</div>
<div id="outline-container-org737338e" class="outline-4">
<h4 id="org737338e"><span class="section-number-4">1.6.2.</span> MVCC (Multi-version concurrency control)</h4>
<div class="outline-text-4" id="text-1-6-2">
<ul class="org-ul">
<li>A concurrency control model used in DBMS.</li>
<li>MVCC keeps multiple version of data simultaneously, each transaction sees a snapshot of the database.</li>
</ul>
</div>
</div>
<div id="outline-container-orge0cbff7" class="outline-4">
<h4 id="orge0cbff7"><span class="section-number-4">1.6.3.</span> Common database models</h4>
<div class="outline-text-4" id="text-1-6-3">
<ul class="org-ul">
<li>Relational model, e.g., SQL.</li>
<li>Document model.</li>
<li>Network model.</li>
<li>key-value, e.g., NoSQL.</li>
</ul>
</div>
</div>
<div id="outline-container-orgceb3dd0" class="outline-4">
<h4 id="orgceb3dd0"><span class="section-number-4">1.6.4.</span> Common storage engines</h4>
<div class="outline-text-4" id="text-1-6-4">
<ul class="org-ul">
<li>MDBX: Ultra-fate key-value embedded database with ACID and MVCC supported.</li>
<li>LevelDB: Google-developed key-value store using log-structured merge-tree for high write throughput.</li>
<li>RocksDB: Meta’s fork of LevelDB, optimized for fast storage.</li>
<li>LSM-based DBs, e.g., BadgerDB: optimized for write-heavy workloads with log-structured merge-tree.</li>
<li>BoltDB: Go-written key-value database with optimized B+ tree, ACID supported.</li>
<li>LMDB: memory-mapped key-value store with ACID and MVCC supported.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org6b0a87a" class="outline-3">
<h3 id="org6b0a87a"><span class="section-number-3">1.7.</span> Reth</h3>
<div class="outline-text-3" id="text-1-7">
<ul class="org-ul">
<li>A Rust implementation of an Ethereum full node; allows users to interact with the Ethereum blockchain.</li>
<li>An execution layer that implements all Ethereum engine APIs.</li>
<li>Modularity: every component is built as a library.</li>
<li>Performance: uses Erigon staged-sync node architecture and other Rust libraries (e.g., Alloy, revm); tests and optimizes on Foundry.</li>
<li>Database/Storage engine: MDBX.</li>
</ul>
</div>
</div>
<div id="outline-container-org478ab9b" class="outline-3">
<h3 id="org478ab9b"><span class="section-number-3">1.8.</span> Why gas per second as the performance metric</h3>
<div class="outline-text-3" id="text-1-8">
<ul class="org-ul">
<li>More nuanced than TPS.</li>
<li>Allows for a clear understanding for the capacity and efficiency.</li>
<li>Helps assessing the cost implications, e.g., DoS attacks.</li>
</ul>
</div>
</div>
<div id="outline-container-org3e971b2" class="outline-3">
<h3 id="org3e971b2"><span class="section-number-3">1.9.</span> EVM cost models</h3>
<div class="outline-text-3" id="text-1-9">
<ul class="org-ul">
<li>Determines the computational and storage costs for the execution.</li>
<li>Key aspects: gas, gas cost (for each operation), gas price (in Wei), gas limit.</li>
</ul>
</div>
</div>
<div id="outline-container-orged77b07" class="outline-3">
<h3 id="orged77b07"><span class="section-number-3">1.10.</span> TPC benchmark</h3>
<div class="outline-text-3" id="text-1-10">
<ul class="org-ul">
<li>Standardized performance tests for transaction processing and databases, e.g., how many transactions a system can process in a given period.</li>
<li>Offer benchmarks for different scenarios, e.g., TPC-C for online transaction processing.</li>
</ul>
</div>
</div>
<div id="outline-container-org89f5af9" class="outline-3">
<h3 id="org89f5af9"><span class="section-number-3">1.11.</span> State growth</h3>
<div class="outline-text-3" id="text-1-11">
<ul class="org-ul">
<li>State: the set of data for building and validating new Ethereum blocks.</li>
<li>State growth: the accumulation of new account and new contract storage.</li>
</ul>
</div>
</div>
<div id="outline-container-orgdf456e7" class="outline-3">
<h3 id="orgdf456e7"><span class="section-number-3">1.12.</span> JIT (Just-In-Time) and AOT (Ahead-of-Time) EVM</h3>
<div class="outline-text-3" id="text-1-12">
<ul class="org-ul">
<li>JIT: convert bytecode to native machine code just before execution to bypass the VM’s interpretative process.</li>
<li>AOT: compile the highest demand contracts and store them on disk, to avoid untrusted bytecode absuing native-code compilation.</li>
</ul>
</div>
</div>
<div id="outline-container-orgf3797a6" class="outline-3">
<h3 id="orgf3797a6"><span class="section-number-3">1.13.</span> Actor model</h3>
<div class="outline-text-3" id="text-1-13">
<ul class="org-ul">
<li>A paradigm/framework for designing distributed systems.</li>
<li>Actor: each actor is an independent entity to receive, process and send messages; create new actors or modify its state.</li>
</ul>
</div>
</div>
<div id="outline-container-orge6bfe92" class="outline-3">
<h3 id="orge6bfe92"><span class="section-number-3">1.14.</span> Storage trie</h3>
<div class="outline-text-3" id="text-1-14">
<ul class="org-ul">
<li>Each contract account has its own storage trie, which is usually stored in a KV database.</li>
</ul>
</div>
</div>
<div id="outline-container-org9662699" class="outline-3">
<h3 id="org9662699"><span class="section-number-3">1.15.</span> Serverless database</h3>
<div class="outline-text-3" id="text-1-15">
<ul class="org-ul">
<li>Allow developers to focus on writing queries without managing database servers.</li>
<li>Automatically scales up or down base on the workload.</li>
<li>Pay-per-use pricing.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-orgb4b09e9" class="outline-2">
<h2 id="orgb4b09e9"><span class="section-number-2">2.</span> Reth scaling plan</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Current status (April 2024): achieves 100-200 mg/s during live sync, including sender recovery, transaction execution and block trie calculation.</li>
<li>The scaling plan does not involve solving state growth.</li>
</ul>
</div>
<div id="outline-container-org1900484" class="outline-3">
<h3 id="org1900484"><span class="section-number-3">2.1.</span> Vertical scaling (2024)</h3>
<div class="outline-text-3" id="text-2-1">
<ul class="org-ul">
<li>Optimize how each system handle transactions and data.</li>
</ul>
</div>
<div id="outline-container-org61d0655" class="outline-4">
<h4 id="org61d0655"><span class="section-number-4">2.1.1.</span> JIT/AOT EVM</h4>
<div class="outline-text-4" id="text-2-1-1">
<ul class="org-ul">
<li>Reduce EVM interpreter overhead to speed up single-threaded transaction processing.</li>
<li>The processing costs \(\approx\) 50% EVM time</li>
<li>Released on <a href="https://www.paradigm.xyz/2024/06/revmc">June 2024</a>.</li>
</ul>
<figure id="org2993c7d">
<img src="https://www.paradigm.xyz/static/reth-perf/3.png" alt="3.png" align="center" width="500px">
<figcaption><span class="figure-number">Figure 1: </span>The JIT/AOT compiler (<a href="https://www.paradigm.xyz/static/reth-perf/3.png">source</a>)</figcaption>
</figure>
</div>
</div>
<div id="outline-container-org05122cc" class="outline-4">
<h4 id="org05122cc"><span class="section-number-4">2.1.2.</span> Parallel EVM</h4>
<div class="outline-text-4" id="text-2-1-2">
<ul class="org-ul">
<li>Utilize multiple cores during EVM execution.</li>
<li><80% of historical transactions have non-conflicting dependencies.</li>
<li>Historical sync: can calculate the best parallelization schedule offline; an early attempt is <a href="https://github.com/paradigmxyz/reth/tree/rkrasiuk/parallel">available</a>.</li>
<li>Live sync: combine serial and parallel execution based on static analysis, since Block STM has poor performance during heavy state contention periods; an early attempt is <a href="https://github.com/risechain/pevm">available</a>.</li>
</ul>
</div>
</div>
<div id="outline-container-org6bffaf9" class="outline-4">
<h4 id="org6bffaf9"><span class="section-number-4">2.1.3.</span> Optimized state commitment</h4>
<div class="outline-text-4" id="text-2-1-3">
<ul class="org-ul">
<li>Traditional EVM implementation <b><b>couples</b></b> the transaction execution and the state root computation: the state root is updated whenever a transaction updates a trie, since the state root computation has to be sequential from the updated node to the root, this is slow.</li>
<li>Reth <b><b>decouples</b></b> the process: raw state data is stored in KV databases, and each trie is <b><b>re-built</b></b> for each block from the databases in the end.
<ul class="org-ul">
<li>Pro: can use more efficient databases.</li>
<li>Con: need to re-calculate the entire trie, which costs >75% of end-to-end block production time.</li>
</ul></li>
<li>Optimizations:
<ul class="org-ul">
<li>Now already re-calculate the storage trie for each updated contract in parallel.</li>
<li>Can also calculate the account trie when the storage tries are computed.</li>
<li>Pre-fetch cached trie nodes (cached by the state root computation) by tracking updated accounts and storage, e.g., a part of the trie may remain the same hash.</li>
</ul></li>
<li>Going beyond:
<ul class="org-ul">
<li>Only calculate the state root every \(T\) blocks.</li>
<li><b><b>Lag</b></b> the state root computation a few blocks behind to advance executions.</li>
<li>Use a cheaper encoder and hash function (Blake3).</li>
<li>Use wider branch nodes.</li>
</ul></li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org266842c" class="outline-3">
<h3 id="org266842c"><span class="section-number-3">2.2.</span> Horizontal scaling (2025)</h3>
<div class="outline-text-3" id="text-2-2">
<ul class="org-ul">
<li>Spread the workload across multiple systems.</li>
</ul>
</div>
<div id="outline-container-org729b06d" class="outline-4">
<h4 id="org729b06d"><span class="section-number-4">2.2.1.</span> Multi-Rollup (?)</h4>
<div class="outline-text-4" id="text-2-2-1">
<ul class="org-ul">
<li>Reduce operational overhead of running multiple rollups.</li>
</ul>
</div>
</div>
<div id="outline-container-orgb4aacf1" class="outline-4">
<h4 id="orgb4aacf1"><span class="section-number-4">2.2.2.</span> Cloud-Native nodes.</h4>
<div class="outline-text-4" id="text-2-2-2">
<ul class="org-ul">
<li>Deploy the heavy node (e.g., sequencer) as a service stack that can autoscale with compute demand and use cloud storage for persistence.</li>
<li>Similar to serverless database projects, e.g., NeonDB.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org2b8c868" class="outline-3">
<h3 id="org2b8c868"><span class="section-number-3">2.3.</span> Open questions</h3>
<div class="outline-text-3" id="text-2-3">
<ul class="org-ul">
<li>Second order effects of above changes, e.g., on light clients.</li>
<li>What is the best, average and worst case scenarios for each optimization.</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-reth.html">reth</a> </div>
<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>