-
Notifications
You must be signed in to change notification settings - Fork 2
/
zh_ton.tex
1988 lines (1249 loc) · 286 KB
/
zh_ton.tex
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
\documentclass[12pt,oneside]{article}
\usepackage{xeCJK}
\setCJKmainfont{SimSun}
\usepackage[T1]{fontenc}
%\usepackage{euler}
\usepackage{amssymb, amsmath, amsfonts, stmaryrd}
\usepackage[mathscr]{euscript}
\usepackage{mathrsfs}
\usepackage{theorem}
\usepackage[english]{babel}
\usepackage{bm}
\usepackage[all]{xy}
%\usepackage{chngcntr}
%\CompileMatrices
\usepackage[bookmarks=false,pdfauthor={Nikolai Durov},pdftitle={The Open Network}]{hyperref}
\usepackage{fancyhdr}
\usepackage{caption}
%
\setlength{\headheight}{15.2pt}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0.5pt}
%
\def\makepoint#1{\medbreak\noindent{\bf #1.\ }}
\def\zeropoint{\setcounter{subsection}{-1}}
\def\zerosubpoint{\setcounter{subsubsection}{-1}}
\def\nxpoint{\refstepcounter{subsection}%
\smallbreak\makepoint{\thesubsection}}
\def\nxsubpoint{\refstepcounter{subsubsection}%
\smallbreak\makepoint{\thesubsubsection}}
\def\nxsubsubpoint{\refstepcounter{paragraph}%
\makepoint{\paragraph}}
%\setcounter{secnumdepth}{4}
%\counterwithin{paragraph}{subsubsection}
\def\refpoint#1{{\rm\textbf{\ref{#1}}}}
\let\ptref=\refpoint
\def\embt(#1.){\textbf{#1.}}
\def\embtx(#1){\textbf{#1}}
\long\def\nodo#1{}
%
%\def\markbothsame#1{\markboth{#1}{#1}}
\fancyhf{}
\fancyfoot[C]{\thepage}
\def\markbothsame#1{\fancyhead[C]{#1}}
\def\mysection#1{\section{#1}\fancyhead[C]{\textsc{Chapter \textbf{\thesection.} #1}}}
\def\mysubsection#1{\subsection{#1}\fancyhead[C]{\small{\textsc{\textrm{\thesubsection.} #1}}}}
\def\myappendix#1{\section{#1}\fancyhead[C]{\textsc{Appendix \textbf{\thesection.} #1}}}
%
\let\tp=\textit
\let\vr=\textit
\def\workchainid{\vr{workchain\_id\/}}
\def\shardpfx{\vr{shard\_prefix}}
\def\accountid{\vr{account\_id\/}}
\def\currencyid{\vr{currency\_id\/}}
\def\uint{\tp{uint}}
\def\opsc#1{\operatorname{\textsc{#1}}}
\def\blkseqno{\opsc{blk-seqno}}
\def\blkprev{\opsc{blk-prev}}
\def\blkhash{\opsc{blk-hash}}
\def\Hash{\opsc{Hash}}
\def\Sha{\opsc{sha256}}
\def\height{\opsc{height}}
\def\len{\opsc{len}}
\def\leaf{\opsc{Leaf}}
\def\node{\opsc{Node}}
\def\root{\opsc{Root}}
\def\emptyroot{\opsc{EmptyRoot}}
\def\code{\opsc{code}}
\def\Ping{\opsc{Ping}}
\def\Store{\opsc{Store}}
\def\FindNode{\opsc{Find\_Node}}
\def\FindValue{\opsc{Find\_Value}}
\def\Bytes{\tp{Bytes}}
\def\Transaction{\tp{Transaction}}
\def\Account{\tp{Account}}
\def\State{\tp{State}}
\def\Maybe{\opsc{Maybe}}
\def\List{\opsc{List}}
\def\Block{\tp{Block}}
\def\Blockchain{\tp{Blockchain}}
\def\isValidBc{\tp{isValidBc}}
\def\evtrans{\vr{ev\_trans}}
\def\evblock{\vr{ev\_block}}
\def\Hashmap{\tp{Hashmap}}
\def\Type{\tp{Type}}
\def\nat{\tp{nat\/}}
\def\hget{\vr{hget\/}}
\def\bbB{{\mathbb{B}}}
\def\st#1{{\mathbf{#1}}}
%
\hfuzz=0.8pt
\title{The Open Network}
\author{Nikolai Durov\\
TL: Dr Awesome Doge}% a.k.a. K.O.T.
\begin{document}
%\pagestyle{myheadings}
\maketitle
\begin{abstract}
本論文旨在首次詳述The Open Network (TON) 以及相關的區塊鏈、P2P (點對點)、分散式儲存及服務託管技術。為了確保本文件的篇幅在合理的範疇內,我們主要針對TON平台中具有獨特性和關鍵定義的功能進行探討,這些功能對於實現其明確設定的目標具有核心重要性。
\end{abstract}
\section*{緒論}
\markbothsame{緒論}
{\em The Open Network (TON)} 是一個快速、安全且可擴展的區塊鏈和網路專案,如有必要,它能夠處理每秒數百萬筆交易,對使用者和服務提供者都非常友好。我們希望它能夠承載所有目前提議和構想的合理應用程式。人們可以將TON視為一個巨大的分散式超級電腦,或者更恰當地說,一個巨大的``超級伺服器'',旨在托管和提供各種服務。
本文並非關於所有實作細節的終極參考。在開發和測試階段,部分具體內容有可能發生變更。
\clearpage
\tableofcontents
\clearpage
\mysection{TON組件的簡要描述}\label{sect:ton.components}
{\em The Open Network (TON)} 結合了以下組件:
\begin{itemize}
\item 一個靈活的多區塊鏈平台 ({\em TON Blockchain}; 參考第~\ptref{sect:blockchain}章),能夠處理每秒數百萬筆交易,擁有圖靈完全智能合約、可升級的正式區塊鏈規格、多加密貨幣價值轉移、支持微支付通道和鏈下支付網路。{\em TON Blockchain\/} 提供了一些新的和獨特的功能,例如「自我修復」垂直區塊鏈機制 (參考~\ptref{sp:inv.sh.blk.corr}) 和 Instant Hypercube Routing (參考~\ptref{sp:instant.hypercube}),使其同時快速、可靠、可擴展和自我一致。
\item 一個點對點網路 ({\em TON P2P Network}, 或簡稱 {\em TON Network}; 參考第~\ptref{sect:network}章),用於訪問TON區塊鏈、發送交易候選者,以及只接收客戶端感興趣的區塊鏈的部分更新(例如,與客戶端的賬戶和智能合約相關的部分),但也能支持任意分散服務,無論是否與區塊鏈相關。
\item 一種分散的文件儲存技術 {\em (TON Storage);} (參考~\ptref{sp:ex.ton.storage}),通過 {\em TON Network} 訪問,由TON Blockchain用於儲存區塊和狀態數據(快照)的存檔副本,但也可以用於儲存平台上的使用者或其他服務的任意文件,使用類似於torrent的訪問技術。
\item 一個網路代理/匿名層 {\em (TON Proxy);} (參考~\ptref{sp:ex.ton.proxy} 和~\ptref{sp:tunnels}),類似於 $I^2P$ (Invisible Internet Project),如有必要(例如,從擁有大量加密貨幣的賬戶提交交易的節點,或希望隱藏其確切IP地址和地理位置以對抗DDoS攻擊的高風險區塊鏈validator節點),用於隱藏 {\em TON Network\/} 節點的身份和IP地址。
\item 一個類似Kademlia的分散式雜湊表 ({\em TON DHT}; 參考~\ptref{sect:kademlia}),用作 {\em TON Storage} 的「torrent tracker」(參考~\ptref{sp:distr.torr.tr}),作為 {\em TON Proxy\/} 的「input tunnel locator」(參考~\ptref{sp:loc.abs.addr}),以及作為 {\em TON Services} 的服務定位器 (參考~\ptref{sp:loc.serv})。
\item 一個提供任意服務的平台 ({\em TON Services}; 參考第~\ptref{sect:services}章),居住在並可通過 {\em TON Network\/} 和 {\em TON Proxy} 訪問,具有正式化的界面 (參考~\ptref{sp:pub.int.smartc}) 使得瀏覽器或智能手機應用程序可以互動。這些正式界面和持久的服務入口點可以在TON Blockchain中發布 (參考~\ptref{sp:ui.ton.dns});提供服務的實際節點可以從在TON Blockchain中發布的信息開始,通過 {\em TON DHT\/} 查找 (參考~\ptref{sp:loc.serv})。服務可以在TON Blockchain中創建智能合約,為其客戶提供一些保證 (參考~\ptref{sp:mixed.serv})。
\item {\em TON DNS\/} (參考~\ptref{sp:ton.dns}),用於為賬戶、智能合約、服務和網路節點分配易讀的名稱。
\item {\em TON Payments\/} (參考第~\ptref{sect:payments}章),一個用於微支付、微支付通道和微支付通道網路的平台。它可用於快速的鏈下價值轉移,以及支付由 {\em TON Services} 提供的服務。
\item TON將允許輕鬆集成第三方消息和社交網路應用程序,從而使區塊鏈技術和分散服務終於可用且可被普通使用者訪問 (參考~\ptref{sp:ton.www}),而不僅僅是少數早期的加密貨幣採用者。我們將在我們的另一個專案中,Telegram Messenger (參考~\ptref{sp:telegram.integr}),提供這樣的集成例子。
\end{itemize}
雖然 TON Blockchain 是 TON 專案的核心,而其他組件可能被視為對區塊鏈扮演輔助角色,但它們自身也具有有趣和實用的功能。結合使用,它們允許平台容納比僅使用 TON Blockchain 更多樣化的應用程式 (參考~\ptref{sp:blockchain.facebook} 和~\ptref{sect:ton.service.impl})。
\clearpage
\mysection{TON Blockchain}\label{sect:blockchain}
我們從描述 The Open Network (TON) Blockchain 開始,這是該專案的核心組件。我們這裡的方法是「由上而下」:我們首先給出整體的一般描述,然後提供每個組件的更多細節。
為了簡單起見,我們在此談論 {\em the/} TON Blockchain,即使原則上這種區塊鏈協議可能有多個獨立運行的實例(例如,由於硬分叉的結果)。我們只考慮其中之一。
\mysubsection{TON Blockchain 作為 2-區塊鏈的集合}
TON Blockchain 實際上是區塊鏈的{\em 集合}(甚至是區塊鏈的區塊鏈集合,或稱為{\em 2-區塊鏈}---這一點將在~\ptref{sp:inv.sh.blk.corr}中進一步說明),因為沒有單一的區塊鏈專案能夠達到我們每秒處理數百萬交易的目標,而不是現在的每秒數十次交易的標準。
\nxsubpoint\label{sp:list.blkch.typ}
\embt(List of blockchain types.) 此系列中的區塊鏈包括:
\begin{itemize}
\item 唯一的{\em master blockchain},或簡稱為{\em masterchain},該區塊鏈包含有關協議的一般資訊、其參數的當前值、validator集合和他們的股份、當前活躍的工作鏈(workchains)及其"shards",以及最重要的,所有workchains和shardchains的最近區塊的雜湊集合。
\item 數個(最多 $2^{32}$)的{\em working blockchains},或簡稱為{\em workchains},實際上是這系統的"工作馬",包含價值轉移和智能合約交易。不同的workchains可能有不同的"規則",意味著帳戶地址的不同格式、交易的不同格式、智能合約的不同虛擬機(VMs)、不同的基本加密貨幣等等。然而,它們都必須滿足某些基本的互操作性標準,以確保不同的workchains之間的互動簡單和可能。在這方面,TON Blockchain是{\em heterogeneous}(參考~\ptref{sp:blkch.hom.het}),類似於EOS(參考~\ptref{sp:discuss.EOS})和PolkaDot(參考~\ptref{sp:discuss.PolkaDot})專案。
\item 每個workchain會進一步細分為多達 $2^{60}$ 的{\em shard blockchains},或簡稱為{\em shardchains},它們具有與workchain本身相同的規則和區塊格式,但只對帳戶的某個子集負責,這取決於帳戶地址的幾個首位(最重要的位)。換句話說,這系統內建了一種分片(sharding)的形式(參考~\ptref{sp:shard.supp})。因為所有這些shardchains共享通用的區塊格式和規則,TON Blockchain在這方面是{\em homogeneous}(參考~\ptref{sp:blkch.hom.het}),這與Ethereum的某個擴展建議相似。\footnote{\url{https://github.com/ethereum/wiki/wiki/Sharding-FAQ}}
\item shardchain(和masterchain)中的每個區塊實際上不只是一個區塊,而是一個小區塊鏈。通常,這"block blockchain"或"vertical blockchain"只包含一個區塊,然後我們可能會認為這只是shardchain的相對應區塊(在這種情況下也稱為"horizontal blockchain")。但是,如果需要修正不正確的shardchain區塊,新的區塊將被提交到"vertical blockchain",包含無效"horizontal blockchain"區塊的替代品,或一個"block difference",只包含該區塊先前版本中需要更改的部分的描述。這是一個TON特有的機制,用於替換檢測到的無效區塊,而不會真正地分叉所有涉及的shardchains;這將在~\ptref{sp:inv.sh.blk.corr}中詳細解釋。目前,我們只需指出,每個shardchain(和masterchain)不是一個常規的區塊鏈,而是一個{\em blockchain of blockchains},或{\em 2D-blockchain},或只是一個{\em 2-blockchain}。
\end{itemize}
\nxsubpoint\label{sp:ISP} \embt(Infinite Sharding Paradigm.)無限分片範式。 幾乎所有的區塊鏈分片提案都是「自上而下」:首先想像一個單一的區塊鏈,然後討論如何將它分割成幾個互動的分片鏈以提高效能和達到可擴展性。
TON的分片方法是「自下而上」,如下所述。
想像分片已被極端化,以至於每個分片鏈中只剩下一個帳戶或智能合約。然後我們有大量的「帳戶鏈」,每個鏈描述只有一個帳戶的狀態和狀態過渡,並向彼此發送具有價值的消息以傳輸價值和信息。
當然,擁有數億的區塊鏈是不切實際的,每個鏈中的更新(即新的區塊)通常出現得相對較少。為了更有效地實施它們,我們將這些「帳戶鏈」組合成「分片鏈」,以便分片鏈的每個區塊基本上是已分配給此分片的帳戶鏈的區塊的集合。因此,「帳戶鏈」只在「分片鏈」內部擁有純粹的虛擬或邏輯存在。
我們稱這種觀點為「無限分片範式」。它解釋了TON區塊鏈的許多設計決策。
\nxsubpoint\label{sp:msg.IHR} \embt(Messages. Instant Hypercube Routing.)消息。即時超立方路由。 無限分片範式告訴我們將每個帳戶(或智能合約)視為它自己的分片鏈中。然後,一個帳戶可能影響另一帳戶的狀態的唯一方式是向它發送一個「消息」(這是所謂的Actor模型的特殊實例,其中帳戶作為Actors;cf.~\ptref{sp:actors})。因此,帳戶間(和分片鏈間,因為源帳戶和目的地帳戶,一般來說,位於不同的分片鏈中)的消息系統對於像TON區塊鏈這樣的可擴展系統非常重要。事實上,TON區塊鏈的一個新特性,稱為「即時超立方路由」(cf.~\ptref{sp:instant.hypercube}),使它能夠將消息從一個分片鏈的區塊傳遞和處理到目的地分片鏈的下一個區塊,{\em 不考慮系統中的分片鏈總數。}
\nxsubpoint \embt(Quantity of masterchains, workchains and shardchains.) TON 區塊鏈中恰有一個主鏈(masterchain)。但是,此系統有潛能容納高達 \(2^{32}\) 的工作鏈(workchains),每個工作鏈都可細分為高達 \(2^{60}\) 的分片鏈(shardchains)。
\nxsubpoint \embt(Workchains can be virtual blockchains, not true blockchains.) 由於工作鏈通常被細分為分片鏈,工作鏈的存在是「虛擬的」,這意味著它不是一個真正的區塊鏈,如~\ptref{sp:gen.blkch.def}下提供的一般定義所描述,而只是一組分片鏈的集合。當只有一個分片鏈對應到一個工作鏈時,這個獨特的分片鏈可能與工作鏈相同,這樣它在某個時間點變成一個「真正的」區塊鏈,進而與常規的單一區塊鏈設計有相似性。然而,無限分片範式 (cf.~\ptref{sp:ISP}) 告訴我們這種相似性確實是表面的:能夠將潛在的大量「帳戶鏈」暫時分組到一個區塊鏈只是一個巧合。
\nxsubpoint \embt(Identification of workchains.) 每一個工作鏈都由其{\em number\/}或{\em workchain identifier\/}(\(\workchainid:\uint_{32}\))來識別,它只是一個無符號的32位整數。工作鏈是由主鏈中的特殊交易所創建,定義(先前未使用的)工作鏈識別符和工作鏈的正式描述,至少足以讓此工作鏈與其他工作鏈互動以及對此工作鏈的區塊進行表面驗證。
\nxsubpoint \embt(Creation and activation of new workchains.) 新的工作鏈的創建可以由社區中的任何成員啟動,只要他們準備支付發佈新工作鏈的正式規範所需的(高額)主鏈交易費用。但是,為了使新的工作鏈變得活躍,需要三分之二的validator達成共識,因為他們需要升級他們的軟件以處理新工作鏈的區塊,並通過特殊的主鏈交易表示他們準備好與新的工作鏈一起工作。對新工作鏈的啟動感興趣的方可能會提供某些激勵,讓validator透過智能合約分發的某些獎勵來支持新的工作鏈。
\nxsubpoint\label{sp:shard.ident} \embt(Identification of shardchains.) 每個分片鏈(shardchain)都由一對 $(w,s)=(\workchainid, \shardpfx)$ 來識別,其中 $\workchainid:\uint_{32}$ 識別相應的工作鏈(workchain),而 $\shardpfx:\st2^{0\ldots60}$ 是一個最長為60的位元串,定義此分片鏈所負責的帳戶子集。換句話說,所有以 $\shardpfx$ 開頭的帳戶 $\accountid$ (即,具有 $\shardpfx$ 作為最重要位元)都將被分配到這個分片鏈。
\nxsubpoint \embt(Identification of account-chains.) 回憶一下,帳戶鏈(account-chains)只有虛擬存在 (cf.~\ptref{sp:ISP})。然而,它們有一個自然的識別符——即,$(\workchainid,\accountid)$——因為任何帳戶鏈都包含關於恰好一個帳戶(無論是簡單帳戶還是智能合約——這裡的區別不重要)的狀態和更新的信息。
\nxsubpoint\label{sp:dyn.split.merge} \embt(Dynamic splitting and merging of shardchains; cf.~\ptref{sect:split.merge}.) 一個較不複雜的系統可能使用{\em static sharding},例如,使用 $\accountid$ 的前八位來選擇256個預定義的碎片之一。
TON 區塊鏈的一個重要特點是它實現了{\em dynamic sharding},這意味著碎片的數量不是固定的。相反,如果滿足某些正式條件(基本上,如果原始碎片上的交易負載在很長的時間內都足夠高),分片 $(w,s)$ 可以自動細分為分片 $(w,s.0)$ 和 $(w,s.1)$。相反,如果負載在一段時間內保持得太低,分片 $(w,s.0)$ 和 $(w,s.1)$ 可以自動合併回分片 $(w,s)$。
最初,只為工作鏈 $w$ 創建了一個分片 $(w,\emptyset)$。稍後,當這變得必要時,它被細分為更多的分片 (cf.~\ptref{sp:split.necess} and~\ptref{sp:merge.necess})。
\nxsubpoint\label{sp:basic.workchain} \embt(Basic workchain or Workchain Zero.) 雖然可以定義高達 $2^{32}$ 的工作鏈(workchains)並有其特定的規則和交易,但我們一開始只定義一個,即 $\workchainid=0$。這個工作鏈被稱為Workchain Zero或基礎工作鏈,它是用於操作{\em TON smart contracts\/} 和轉移{\em Toncoin},也稱為{\em Toncoin\/} (cf.\ Appendix~\ref{app:coins})。大多數應用可能只需要Workchain Zero。基礎工作鏈的分片鏈會被稱為{\em basic shardchains}。
\nxsubpoint \embt(Block generation intervals.) 我們預計每個分片鏈和主鏈大約每五秒會生成一個新的區塊。這將導致相對較小的交易確認時間。所有分片鏈的新區塊大約同時生成;主鏈的新區塊大約在一秒後生成,因為它必須包含所有分片鏈的最新區塊的雜湊值。
\nxsubpoint\label{sp:sc.hash.mc} \embt(Using the masterchain to make workchains and shardchains tightly coupled.) 一旦分片鏈的區塊的雜湊值被合併到主鏈的區塊中,該分片鏈區塊及其所有祖先都被認為是「正規的」,這意味著它們可以被所有分片鏈的後續區塊引用為固定且不可變的內容。實際上,每個新的分片鏈區塊都包含最近的主鏈區塊的雜湊值,並且從該主鏈區塊引用的所有分片鏈區塊在新區塊中都被認為是不可變的。
從本質上講,這意味著在分片鏈區塊中提交的交易或消息可以在其他分片鏈的下一個區塊中安全地使用,而不需要等待,例如,二十次確認(即在同一區塊鏈中在原始區塊之後生成的二十個區塊)之前轉發消息或基於之前的交易採取其他操作,這在大多數建議的「鬆散連接」系統中很常見(cf.~\ptref{sp:blkch.interact}),如EOS。我們相信,這種能力在提交後的五秒內在其他分片鏈中使用交易和消息是我們這種「緊密連接」系統能夠提供前所未有的性能的原因之一(cf.~\ptref{sp:shard.supp} and~\ptref{sp:blkch.interact})。
\nxsubpoint \embt(Masterchain block hash as a global state.) 根據~\ptref{sp:sc.hash.mc},最後一個主鏈區塊的雜湊完全確定了外部觀察者的整體系統狀態。人們不需要單獨監視所有分片鏈的狀態。
\nxsubpoint \embt(Generation of new blocks by validators; cf.~\ptref{sect:validators}.) TON 區塊鏈使用 Proof-of-Stake (PoS) 方法在分片鏈和主鏈中生成新的區塊。這意味著有一組,例如,多達幾百個的{\em validators}---特殊的節點,透過特殊的主鏈交易存放{\em stakes\/}(大量的 Toncoin)以符合生成和驗證新區塊的資格。
然後,小部分的validator被分配給每一個分片 $(w,s)$,這是以決定性的偽隨機方式進行的,每1024個區塊大約會改變一次。這部分的validator建議並在下一個分片鏈區塊應是什麼上達成共識,通過從客戶端收集適當的建議交易到新的有效的區塊候選。對於每個區塊,validator上有一個偽隨機選定的順序,以確定誰的區塊候選在每一輪中有最高的優先順序被提交。
validator和其他節點檢查所提議的區塊候選的有效性;如果validator簽署了一個無效的區塊候選,它可能會自動被懲罰,失去部分或全部的 stake,或被暫停從validator集合一段時間。之後,validator應達成對下一個區塊的選擇的共識,本質上是 BFT (Byzantine Fault Tolerant; cf.~\ptref{sp:dpos.bft}) 共識協議的高效變體,類似於 PBFT~\cite{PBFT} 或 Honey Badger BFT~\cite{HoneyBadger}。如果達到共識,將創建新的區塊,且validator在交易費用上進行分割,包括交易,加上一些新創建的(“鑄造的”)硬幣。
每個validator可以被選舉參與多個validator子集;在這種情況下,預計它將平行運行所有的驗證和共識算法。
在生成所有新的分片鏈區塊之後或超時之後,將生成一個新的主鏈區塊,包括所有分片鏈的最新區塊的雜湊值。這是通過{\em all\/} validator的 BFT 共識完成的。\footnote{實際上,兩個三分之一的 stake 就足夠達成共識,但努力收集盡可能多的簽名。}
TON PoS 方法及其經濟模型的更多細節提供在 section~\ptref{sect:validators}。
\nxsubpoint \embt(Forks of the masterchain.) 我們緊密耦合的方法帶來的一個複雜性是,切換到主鏈的不同分叉幾乎必然需要在至少一些分片鏈中切換到另一個分叉。另一方面,只要主鏈中沒有分叉,分片鏈中的分叉甚至都是不可能的,因為分片鏈的替代分叉中的沒有區塊可以通過將其雜湊值納入主鏈區塊而變得「標準化」。
一般的規則是,{\em 如果主鏈區塊 $B'$ 是 $B$ 的前輩,$B'$ 包括 $(w,s)$-分片鏈區塊 $B'_{w,s}$ 的雜湊 $\Hash(B'_{w,s})$,且 $B$ 包括雜湊 $\Hash(B_{w,s})$,那麼 $B'_{w,s}$ {\bf 必須}是 $B_{w,s}$ 的前輩; 否則,主鏈區塊 $B$ 就是無效的。}
我們預期主鏈分叉將會很少,幾乎不存在,因為在由 TON 區塊鏈所採用的 BFT 範疇中,它們只能在{\em 大部分\/} validator行為不正確的情況下發生(參見~\ptref{sp:validators} 和~\ptref{sp:new.master.blk}),這將意味著由違反者承擔的重大的 stake 損失。因此,不應期待分片鏈中存在真正的分叉。相反,如果檢測到一個無效的分片鏈區塊,將通過 2-blockchain 的「垂直區塊鏈」機制進行修正(參見~\ptref{sp:inv.sh.blk.corr}),這可以在不分叉「水平區塊鏈」(即,分片鏈)的情況下實現此目標。同樣的機制也可以用來修正主鏈區塊中的非致命性錯誤。
\nxsubpoint\label{sp:inv.sh.blk.corr} \embt(Correcting invalid shardchain blocks.) 通常,只有有效的分片鏈區塊會被提交,因為分配給分片鏈的validator在新區塊可以被提交之前必須達到三分之二的拜占庭共識。然而,系統必須允許檢測先前提交的無效區塊及其校正。
當然,一旦找到一個無效的分片鏈區塊 —— 不論是由一個validator(不一定分配到這個分片鏈)還是一個「fisherman」(系統的任何節點,它已經支付了某個存款以便對區塊有效性提出疑問;參見~\ptref{sp:fish})—— 無效性的主張及其證明都會被提交到主鏈,而已經簽署無效區塊的validator將被懲罰,部分或全部扣除他們的 stake,和/或暫時從validator集合中被停權(後者的措施對於攻擊者竊取本質上良性的validator的私有簽名鍵非常重要)。
然而,這還不夠,因為由於先前提交的無效分片鏈區塊,系統(TON 區塊鏈)的整體狀態結果是無效的。這個無效區塊必須被一個新的有效版本替換。
大多數系統會通過「回滾」到該分片鏈中的無效區塊之前的最後一個區塊,以及每個其他分片鏈中不受從無效區塊傳播的消息影響的最後區塊,並從這些區塊創建一個新的分叉來實現這一點。這種方法的缺點是,大量本來正確且已提交的交易突然被回滾,且不清楚它們是否會在稍後再次被包括。
TON 區塊鏈通過使每個分片鏈和主鏈的每個「區塊」(「水平區塊鏈」)本身都成為一個小型區塊鏈(「垂直區塊鏈」),包含這個「區塊」的不同版本,或其「差異」來解決這個問題。通常,垂直區塊鏈只包含一個區塊,而分片鏈看起來像一個經典的區塊鏈。但是,一旦一個區塊的無效性被確認並提交到主鏈區塊中,該無效區塊的「垂直區塊鏈」就被允許在垂直方向上增加一個新區塊,替換或編輯無效區塊。這個新區塊是由當前問題分片鏈的validator子集生成的。
新的“垂直”區塊要有效的規則非常嚴格。特別是,如果無效區塊中包含的虛擬“帳戶鏈區塊”(參見 \ptref{sp:ISP})本身是有效的,則它必須被新的垂直區塊保持不變。
一旦在無效區塊上方提交了新的“垂直”區塊,它的雜湊就會在新的Masterchain區塊中公布(或者更正確地說,在原始Masterchain區塊上方的新“垂直”區塊中公布,該區塊中最初發布了無效Shardchain區塊的雜湊),並且進一步將更改傳播到任何參照此區塊的Shardchain區塊(例如,那些從不正確的區塊接收消息的區塊)。這可以通過在先前參照“不正確”區塊的所有區塊的垂直區塊鏈中提交新的“垂直”區塊來進行修正;新的垂直區塊將參照最新(已更正)的版本。同樣,嚴格的規則禁止更改未受到實際影響的帳戶鏈(即,與前一版本中收到的消息相同的帳戶鏈)。通過這種方式,修正不正確的區塊產生“漣漪”,最終傳播到所有受影響的Shardchain的最新區塊;這些更改也反映在新的“垂直”Masterchain區塊中。
一旦“歷史重寫”的漣漪到達最新區塊,新的Shardchain區塊僅以一個版本生成,僅作為最新區塊版本的後繼者。這意味著它們將從一開始就包含對正確(最新)的垂直區塊的引用。
Masterchain狀態隱含地定義了一個映射,將每個“垂直”區塊鏈的第一個區塊的雜湊轉換為其最新版本的雜湊。這使客戶端可以通過其第一個(通常是唯一的)區塊的雜湊識別和定位任何垂直區塊鏈。
\nxsubpoint \embt(Toncoin and multi-currency workchains.) TON區塊鏈支持多達$2^{32}$種不同的“加密貨幣”、“硬幣”或“代幣”,通過32位的$\currencyid$加以區分。新的加密貨幣可以通過主鏈中的特殊交易來添加。每個工作鏈都有一種基本加密貨幣,並且可以有幾種其他加密貨幣。
有一種特殊的加密貨幣,$\currencyid=0$,即{\em TON幣},也稱為{\em Toncoin}(參見附錄~\ref{app:coins})。這是工作鏈零的基本加密貨幣。它也用於交易費和validator的權益股份。
原則上,其他工作鏈可能會以其他代幣收取交易費。在這種情況下,應該提供一些智能合約,用於將這些交易費自動轉換為Toncoin。
\nxsubpoint \embt(Messaging and value transfer.) 屬於相同或不同工作鏈的分片鏈可以互相傳送{\em messages\/}。儘管允許的訊息的確切形式取決於接收工作鏈和接收帳戶(智能合約),但有一些共同的欄位使跨工作鏈的訊息成為可能。特別是,每條訊息可能會有一些{\em value},以一定數量的Toncoin(Toncoin)和/或其他註冊的加密貨幣的形式附加,前提是它們被接收工作鏈宣布為可接受的加密貨幣。
這種訊息的最簡單形式是從一個(通常不是智能合約)帳戶到另一個帳戶的價值轉移。
\nxsubpoint\label{sp:tonvm} \embt(TON Virtual Machine.) {\em TON Virtual Machine},也縮寫為{\em TON VM\/}或{\em TVM\/},是用於在主鏈和基本工作鏈中執行智能合約程式碼的虛擬機器。其他工作鏈可能使用其他虛擬機器,與TVM一起或替代TVM。
以下我們列出了其一些特性。它們在~\ptref{sp:pec.tvm}、\ptref{sp:tvm.cells}和其他地方進一步討論。
\begin{itemize}
\item TVM 將所有資料表示為一系列的{\em (TVM) cells/} (參考~\ptref{sp:tvm.cells})。每一個 cell 包含最多 128 個資料位元組,以及最多 4 個指向其他 cells 的參考。基於“一切皆為 cell 包”的理念 (參考~\ptref{sp:everything.is.BoC}),這使得 TVM 能夠處理與 TON 區塊鏈相關的所有資料,包括必要時的區塊和區塊鏈全域狀態。
\item TVM 可以處理任意代數資料型態的值 (參考~\ptref{sp:pec.tvm}),表示為 TVM cells 的樹或有向非循環圖。但它對代數資料型態的存在是不知情的;它只是處理 cells。
\item TVM 內建支援 hashmaps (參考~\ptref{sp:patricia})。
\item TVM 是一個堆疊機器。它的堆疊保存 64 位元整數或 cell 參考。
\item 支援 64-bit, 128-bit 和 256-bit 的算術運算。所有 $n$-bit 的算術操作都有三種形式:用於無符號整數,用於有符號整數,以及對於模 $2^n$ 的整數(後者不自動檢查溢出)。
\item TVM 有從 $n$-bit 轉換到 $m$-bit 的無符號和有符號整數,對所有 $0\leq m,n\leq 256$,並具有溢出檢查。
\item 所有算術操作預設執行溢出檢查,這大大簡化了智能合約的開發。
\item TVM 有“乘然後移位”和“移位然後除”的算術操作,中間值在更大的整數型態中計算;這簡化了固定點算術的實現。
\item TVM 提供對位串和字節串的支援。
\item 提供對某些預定義曲線,包括 Curve25519 的 256-bit 橢圓曲線加密 (ECC) 的支援。
\item 對於在某些橢圓曲線上的 Weil 配對的支援也存在,這對於快速實現 zk-SNARKs 很有用。
\item 支援包括 $\Sha$ 在內的流行雜湊函數。
\item TVM 可以處理 Merkle 證明 (參考~\ptref{sp:ton.smart.pc.supp})。
\item TVM 提供對“大型”或“全域”智能合約的支援。這類智能合約必須知道分片 (參考~\ptref{sp:loc.glob.smct} 和 \ptref{sp:tvm.data.shard})。常規(本地)智能合約可以是不知道分片的。
\item TVM 支援閉包。
\item 一個“無脊標籤 $G$-機器” \cite{STGM} 可以容易地在 TVM 內部實現。
\end{itemize}
除了“TVM 組件”,還可以為 TVM 設計幾種高級語言。所有這些語言都將具有靜態類型,並支援代數資料型態。我們預見以下可能性:
\begin{itemize}
\item 類似 Java 的命令式語言,每個智能合約都像一個獨立的類。
\item 惰性的功能語言 (如 Haskell)。
\item 積極的功能語言 (如 ML)。
\end{itemize}
\nxsubpoint\label{sp:config.param} \embt(Configurable parameters.)
TON Block\-chain 的一個重要特性是它有許多{\em 可配置的}參數。這意味著它們是 masterchain 狀態的一部分,且可以通過 masterchain 中的某些特殊的提議/投票/結果交易來更改,而不需要硬分叉。更改這些參數需要收集三分之二的validator投票,以及超過一半想要參與投票過程的所有其他參與者的投票以支持該提議。
\mysubsection{關於區塊鏈的概論}
\nxsubpoint\label{sp:gen.blkch.def} \embt(General blockchain definition.)
一般來說,任何{\em (真實的) 區塊鏈\/}都是一系列的{\em 區塊},每個區塊 \(B\) 都包含一個參考至前一個區塊的 $\blkprev(B)$ (通常是將前一個區塊的雜湊包含在當前區塊的標頭中),以及一個{\em 交易}的列表。每筆交易都描述了{\em 全域區塊鏈狀態}的某種轉換; 一個區塊中列出的交易是按順序應用的,從舊狀態開始計算新狀態,這是在評估前一個區塊後的結果狀態。
\nxsubpoint \embt(Relevance for the TON Blockchain.)
請注意,{\em TON Block\-chain\/} 並不是真正的區塊鏈,而是 2-區塊鏈的集合(即,區塊鏈的區塊鏈集合; 參考~\ptref{sp:list.blkch.typ}),所以上述內容並不直接適用於它。然而,我們從真正的區塊鏈的這些一般性開始,用它們作為我們更複雜建構的基礎。
\nxsubpoint \embt(Blockchain instance and blockchain type.) 人們經常使用「{\em blockchain\/}」一詞來表示一般的{\em blockchain type\/} 和其特定的 {\em blockchain instances},定義為滿足某些條件的區塊序列。例如,\ptref{sp:gen.blkch.def} 是指區塊鏈的實例。
由此,一個區塊鏈類型通常是類型 $\Block^*$ 的「子類型」,由那些滿足某些相容性和有效性條件的區塊序列組成:
\begin{equation}
\Blockchain \subset \Block^*
\end{equation}
更好的定義方式是說 $\Blockchain$ 是一個{\em dependent couple type},由 couple $(\bbB,v)$組成,第一部分 $\bbB:\Block^*$ 是類型 $\Block^*$(即區塊列表),第二部分 $v:\isValidBc(\bbB)$ 是 $\bbB$ 的有效性的證明或證人。由此,
\begin{equation}
\Blockchain\equiv\Sigma_{(\bbB:\Block^*)}\isValidBc(\bbB)
\end{equation}
我們在這裡使用了從~\cite{HoTT} 借用的依賴型態和的表示法。
\nxsubpoint \embt(Dependent type theory, Coq and TL.) 注意,我們在此使用的是(Martin-L\"of)依賴型態理論,類似於 Coq\footnote{\url{https://coq.inria.fr}} 證明助手中使用的。依賴型態理論的簡化版本也用於{\em TL (Type
Language)}\footnote{\url{https://core.telegram.org/mtproto/TL}},將在 TON Blockchain 的正式規範中使用,描述所有資料結構的序列化以及區塊、交易等的佈局。
事實上,依賴型態理論提供了對證明是什麼的有用形式化。當需要提供某個區塊的無效性證明時,這種形式的證明(或它們的序列化)可能會變得很有用。
\nxsubpoint\label{sp:TL} \embt(TL, or the Type Language.) 由於 TL(Type Language)將被用於 TON 區塊、交易和網路數據包的正式規範,因此值得簡短地討論。
TL 是一種適用於描述依賴代數的{\em types}的語言,允許具有數字(自然數)和型態參數。每個型態都通過幾個{\em constructors}來描述。每個構造器都有一個(人類可讀的)識別碼和一個{\em name},這是一個位元組列(預設為32位整數)。除此之外,構造器的定義包含一個與其型態一起的字段列表。
構造器和型態定義的集合被稱為{\em TL-scheme}。它通常保存在一個或多個帶有 \texttt{.tl} 後綴的文件中。
TL-schemes 的一個重要特性是,它們確定了序列化和反序列化定義的代數型態的值(或對象)的明確方式。具體來說,當一個值需要被序列化為一串位元組時,首先序列化用於此值的構造器的名稱。然後是每個字段的遞迴計算的序列化。
一個適合序列化任意對象為 32 位整數序列的 TL 的先前版本的描述,可以在 \url{https://core.telegram.org/mtproto/TL} 上找到。一個新版本的 TL,名為 {\em TL-B},正在開發中,用於描述 TON Project 使用的對象的序列化。這個新版本可以將對象序列化為位元組流,甚至是位元流(而不僅僅是32位整數),並提供將其序列化為 TVM cell 樹的支持(cf.~\ptref{sp:tvm.cells})。TL-B 的描述將是 TON Blockchain 的正式規範的一部分。
\nxsubpoint\label{sp:blk.transf} \embt(Blocks and transactions as
state transformation operators.) 通常,任何區塊鏈(型態)
$\Blockchain$ 都有一個關聯的全域狀態(型態) $\State$,以及一個
交易(型態) $\Transaction$。區塊鏈的語意在很大程度上是由交易應用函數所決定的:
\begin{equation}
\evtrans':\Transaction\times\State\to\State^?
\end{equation}
這裡的 $X^?$ 表示 $\Maybe X$,是將 $\Maybe$ 單子應用於型態 $X$ 的結果。這與我們使用 $X^*$ 表示 $\List
X$ 類似。本質上,型態 $X^?$ 的值要麼是型態 $X$ 的值,要麼是一個特殊值 $\bot$ 表示實際值的缺失
(想想空指標)。在我們的情境中,我們使用 $\State^?$ 而不是 $\State$ 作為結果型態,因為某個交易從某些原始狀態
呼叫可能是無效的 (想想從賬戶中提款的金額超過實際存在的金額的情況)。
我們可能更偏好 $\evtrans'$ 的柯里化版本:
\begin{equation}
\evtrans:\Transaction\to\State\to\State^?
\end{equation}
因為一個區塊本質上是交易的列表,所以區塊的評估函數
\begin{equation}
\evblock:\Block\to\State\to\State^?
\end{equation}
可以從 $\evtrans$ 中衍生出來。它接受一個區塊 $B:\Block$ 和前一個區塊鏈狀態 $s:\State$ (可能包括前一個區塊的雜湊) 並計算下一個區塊鏈狀態
$s'=\evblock(B)(s):\State$,它要么是一個真正的狀態,要么是一個特殊值 $\bot$ 表示下一狀態無法被計算 (也就是說,從給定的起始狀態評估時該區塊是無效的——例如,該區塊包含試圖從一個空帳戶扣款的交易)。
\nxsubpoint \embt(Block sequence numbers.) 每個在區塊鏈中的區塊 $B$
可以由其{\em 序列號} $\blkseqno(B)$ 來參照,從第一個區塊開始為零,並在過渡到下一個區塊時加一。更正式地說,
\begin{equation}
\blkseqno(B)=\blkseqno\bigl(\blkprev(B)\bigr)+1
\end{equation}
請注意,序列號在有{\em 分叉}的情況下不能唯一識別一個區塊。
\nxsubpoint \embt(Block hashes.) 參考區塊 $B$ 的另一種方式是通過其雜湊 $\blkhash(B)$,其實際上是區塊 $B$ 的
{\em 頭部\/}的雜湊(但是,區塊的頭部通常包含依賴於區塊 $B$ 的所有內容的雜湊)。假設所使用的雜湊函數沒有碰撞(或至少它們是非常不可能的),一個區塊可以由其雜湊唯一識別。
\nxsubpoint \embt(Hash assumption.) 在對區塊鏈算法進行正式分析時,我們假設使用的 $k$-bit 雜湊函數 $\Hash:\Bytes^*\to\st2^{k}$ 沒有碰撞:
\begin{equation}\label{eq:hash.coll}
\Hash(s)=\Hash(s')\Rightarrow s=s'\quad\text{對任何 $s$,
$s'\in\Bytes^*$}
\end{equation}
這裡的 $\Bytes=\{0\ldots255\}=\st2^8$ 是位元組的類型,或所有位元組值的集合,而 $\Bytes^*$ 是任意(有限)位元組列表的類型或集合;而 $\st2=\{0,1\}$ 是位元類型,和 $\st2^k$ 是所有 $k$-bit 序列的集合(即,$k$-bit 數字)。
當然,\eqref{eq:hash.coll} 在數學上是不可能的,因為從一個無窮集合到一個有限集合的映射不能是單射。一個更嚴格的假設是
\begin{equation}\label{eq:hash.coll.prec}
\forall s, s': s\neq s', P\bigl(\Hash(s)=\Hash(s')\bigr)=2^{-k}
\end{equation}
然而,這對於證明不太方便。如果在某個小的 $\epsilon$(例如,$\epsilon=10^{-18}$)的證明中\eqref{eq:hash.coll.prec} 至多使用了 $N$ 次,其中 $2^{-k}N<\epsilon$,我們可以像 \eqref{eq:hash.coll} 是真的那樣推理,只要我們接受失敗概率 $\epsilon$(即,最終的結論至少以概率 $1-\epsilon$ 為真)。
最後的備註:為了使~\eqref{eq:hash.coll.prec} 的概率說明真正嚴格,必須在所有位元組序列的集合 $\Bytes^*$ 上引入一個概率分佈。做到這一點的一種方法是假設相同長度 $l$ 的所有位元組序列都是等概率的,並設置觀察到長度為 $l$ 的序列的概率等於 $p^l-p^{l+1}$,對於某些 $p\to1-$。然後應該將\eqref{eq:hash.coll.prec} 理解為當 $p$ 從下面趨近於一時的條件概率 $P\bigl(\Hash(s)=\Hash(s')|s\neq s'\bigr)$ 的極限。
\nxsubpoint\label{sp:hash.change} \embt(Hash used for the TON
Blockchain.) 我們目前為TON Blockchain使用256-bit的$\Sha$雜湊。如果它被證明比預期弱,未來可以被另一個雜湊函數所取代。雜湊函數的選擇是協議的可配置參數,所以可以在~\ptref{sp:config.param}中解釋的,無需硬分叉即可更改。
\mysubsection{區塊鏈狀態、帳戶和雜湊映射}
如上所述,任何區塊鏈都定義了某種全域狀態,且每個區塊和每個交易都定義了這個全域狀態的轉換。在此我們描述由TON區塊鏈使用的全域狀態。
\nxsubpoint \embt(Account IDs.) TON區塊鏈使用的基本帳戶ID──或者至少由其主鏈和工作鏈零所使用──是256-bit整數,假設是針對特定橢圓曲線的256-bit橢圓曲線密碼學(ECC)的公鑰。這樣,
\begin{equation}
\accountid:\Account=\uint_{256}=\st2^{256}
\end{equation}
這裡的$\Account$是帳戶的{\em 類型},而$\accountid:\Account$是類型$\Account$的特定變量。
其他工作鏈可以使用其他帳戶ID格式,無論是256-bit還是其他格式。例如,可以使用等於ECC公鑰的$\Sha$的比特幣風格的帳戶ID。
但是,帳戶ID的位長度$l$必須在工作鏈的創建期間(在主鏈中)固定,且必須至少為64,因為$\accountid$的前64位用於分片和訊息路由。
\nxsubpoint \embt(Main component: {\em Hashmaps}.) TON區塊鏈狀態的主要組件是一個{\em 雜湊映射}。在某些情況下,我們考慮(部分定義的)``映射'' $h:\st2^n\dashrightarrow\st2^m$。更一般地說,我們可能對於複合類型$X$的雜湊映射$h:\st2^n\dashrightarrow X$感興趣。但是,源(或索引)類型幾乎總是$\st2^n$。
有時,我們有一個``預設值'' $\vr{empty}:X$,且雜湊映射$h:\st2^n\to X$由其``預設值'' $i\mapsto\vr{empty}$「初始化」。
\nxsubpoint \embt(Example: TON account balances.) 一個重要的例子是TON帳戶餘額。它是一個雜湊映射
\begin{equation}
\vr{balance}:\Account\to\uint_{128}
\end{equation}
將 $\Account=\st2^{256}$ 映射為類型為 $\uint_{128}=\st2^{128}$ 的Toncoin (TON幣) 餘額。此雜湊映射的預設值為零,這意味著最初(在處理第一個區塊之前)所有帳戶的餘額都是零。
\nxsubpoint \embt(Example: smart-contract persistent storage.) 另一個例子是智能合約的持久儲存,可以(非常大致地)表示為一個雜湊映射
\begin{equation}
\vr{storage}:\st2^{256}\dashrightarrow\st2^{256}
\end{equation}
此雜湊映射的預設值也為零,這意味著未初始化的持久儲存cells被認為是零。
\nxsubpoint \embt(Example: persistent storage of all smart contracts.) 因為我們有多於一個的智能合約,由 $\accountid$ 區分,每個合約都有其獨立的持久儲存,所以我們實際上必須有一個雜湊映射
\begin{equation}
\vr{Storage}:\Account\dashrightarrow(\st2^{256}\dashrightarrow\st2^{256})
\end{equation}
將智能合約的 $\accountid$ 映射到其持久儲存。
\nxsubpoint \embt(Hashmap type.) 雜湊映射不僅僅是一個抽象的(部分定義的)函數 $\st2^n\dashrightarrow X$;它具有特定的表示方式。因此,我們假設我們有一個特殊的雜湊映射類型
\begin{equation}
\Hashmap (n,X):\Type
\end{equation}
對應於編碼(部分)映射 $\st2^n\dashrightarrow X$ 的資料結構。我們也可以寫作
\begin{equation}
\Hashmap (n:\nat) (X:\Type) : \Type
\end{equation}
或
\begin{equation}
\Hashmap:\nat\to\Type\to\Type
\end{equation}
我們總是可以將 $h:\Hashmap(n,X)$ 轉換為一個映射 $\hget(h):\st2^n\to X^?$。從此,我們通常寫作 $h[i]$ 而非 $\hget(h)(i)$:
\begin{equation}
h[i]:\equiv\hget(h)(i):X^?\quad\text{對於任何 $i:\st2^n$, $h:\Hashmap(n,X)$}
\end{equation}
\nxsubpoint\label{sp:patricia} \embt(Definition of hashmap type as a Patricia tree.) 從邏輯上講,我們可能會定義 $\Hashmap(n,X)$ 為一個深度為 $n$ 的(不完整的)二進制樹,其邊的標籤為 $0$ 和 $1$,而葉子中的值類型為 $X$。描述相同結構的另一種方式是作為長度等於 $n$ 的二進制字符串的{\em (按位) trie\/}。
在實際應用中,我們更傾向於使用這種 trie 的緊湊表示,通過壓縮每個只有一個子節點的頂點及其父節點。得到的表示稱為 {\em Patricia tree\/} 或 {\em binary radix tree\/}。每個中間頂點現在都有確切的兩個子節點,由兩個非空的二進制字符串標記,左子節點開始為零,右子節點開始為一。
換句話說,在 Patricia 樹中有兩種類型的(非根)節點:
\begin{itemize}
\item $\leaf(x)$,包含類型為 $X$ 的值 $x$。
\item $\node(l,s_l,r,s_r)$,其中 $l$ 是左子節點或子樹的(引用),$s_l$ 是連接此頂點到其左子節點的邊的位字符串標籤(始終以 0 開頭),$r$ 是右子樹,$s_r$ 是到右子節點的邊的位字符串標籤(始終以 1 開頭)。
\end{itemize}
還需要第三種節點類型,只在 Patricia 樹的根上使用一次:
\begin{itemize}
\item $\root(n,s_0,t)$,其中 $n$ 是 $\Hashmap(n,X)$ 的索引位字符串的公共長度,$s_0$ 是所有索引位字符串的公共前綴,$t$ 是指向 $\leaf$ 或 $\node$ 的引用。
\end{itemize}
如果我們想允許 Patricia 樹為空,則會使用第四種類型的(根)節點:
\begin{itemize}
\item $\emptyroot(n)$,其中 $n$ 是所有索引位字符串的公共長度。
\end{itemize}
我們通過以下方式定義 Patricia 樹的高度:
\begin{align}
\height(\leaf(x))&=0\\ \height\bigl(\node(l,s_l,r,s_r)\bigr)&=\height(l)+\len(s_l)=\height(r)+\len(s_r)\\ \height\bigl(\root(n,s_0,t)\bigr)&=\len(s_0)+\height(t)=n
\end{align}
最後兩個公式中的最後兩個表達式必須相等。我們使用高度為 $n$ 的 Patricia 樹來表示類型為 $\Hashmap(n,X)$ 的值。
如果樹中有 $N$ 個葉子(即,我們的雜湊映射包含 $N$ 個值),則確切有 $N-1$ 個中間頂點。插入一個新值總是涉及通過在中間插入一個新頂點來分割一個現有的邊,並添加一個新葉子作為這個新頂點的另一個子節點。從雜湊映射中刪除一個值做的恰恰相反:葉子和它的父節點被刪除,並且父節點的父節點和其另一個子節點直接連接。
\nxsubpoint\label{sp:merkle.patr.hash} \embt(Merkle-Patricia trees.) 當使用區塊鏈時,我們希望能夠比較 Patricia 樹(即,雜湊映射)及其子樹,並將它們縮減為單一的雜湊值。實現此目的的經典方法是由 Merkle 樹給出的。本質上,我們希望描述一種利用雜湊函數 $\Hash$(為二進制字符串定義)對類型為 $\Hashmap(n,X)$ 的對象 $h$ 進行雜湊的方法,只要我們知道如何計算對象 $x:X$ 的雜湊 $\Hash(x)$ (例如,通過將雜湊函數 $\Hash$ 應用於對象 $x$ 的二進制序列化)。
我們可能會如下遞迴地定義 $\Hash(h)$:
\begin{align}\label{eq:hash.leaf}
\Hash\bigl(\leaf(x)\bigr):=&\Hash(x)\\
\label{eq:hash.node}
\Hash\bigl(\node(l,s_l,r,s_r)\bigr):=&\Hash\bigl(\Hash(l).\Hash(r).\code(s_l).\code(s_r)\bigr)\\ \Hash\bigl(\root(n,s_0,t)\bigr):=&\Hash\bigl(\code(n).\code(s_0).\Hash(t)\bigr)
\end{align}
在此,$s.t$ 表示 (位) 字符串 $s$ 和 $t$ 的連接,而 $\code(s)$ 是所有位字符串 $s$ 的前綴碼。例如,可以通過 10 來編碼 0,通過 11 來編碼 1,並通過 0 來編碼字符串的結尾。%
\footnote{可以證明對於大約一半的 Patricia 樹的邊標籤(具有隨機或連續索引)來說,這種編碼是最優的。其餘的邊標籤可能會很長(即,幾乎有 256 位)。因此,邊標籤的幾乎最優編碼是使用上述碼,對於「短」位字符串使用前綴 0,然後編碼 1,然後是包含位字符串 $s$ 的長度 $l=|s|$ 的九位,然後是 $s$ 的 $l$ 位,用於「長」位字符串(其中 $l\geq10$)。}
我們稍後會看到(參見 \ptref{sp:pec.tvm} 和 \ptref{sp:tvm.cells}),這是針對任意(依賴型)代數類型的值的遞迴定義的雜湊的(稍微調整的)版本。
\nxsubpoint \embt(Recomputing Merkle tree hashes.) 這種遞迴定義 $\Hash(h)$ 的方法,稱為 {\em Merkle tree hash},具有以下優點:如果與每個節點 $h'$ 一起明確儲存 $\Hash(h')$(結果在結構上被稱為 {\em Merkle tree},或在我們的情況下,稱為 {\em Merkle--Patricia tree}),則當元素被添加到雜湊映射、從雜湊映射中刪除或在雜湊映射中更改時,最多只需要重新計算 $n$ 個雜湊。
因此,如果將全域區塊鏈狀態表示為適當的 Merkle 樹雜湊,則在每次交易後,重新計算此狀態雜湊就變得很容易。
\nxsubpoint\label{sp:merkle.proof} \embt(Merkle proofs.) 根據所選雜湊函數 $\Hash$ 的「單射性」假設 \eqref{eq:hash.coll},可以構造一個證明,對於 geven 值 $z$ 的 $\Hash(h)$, $h:\Hashmap(n,X)$, 存在某些 $i:\st2^n$ 和 $x:X$ 使得 $\hget(h)(i)=x$。這樣的證明將包括從對應於 $i$ 的葉子到根的 Merkle--Patricia 樹中的路徑,由此路徑上出現的所有節點的所有兄弟的雜湊增強。
這樣,一個輕量節點%
\footnote{「輕量節點」不跟踪 shardchain 的完整狀態;相反,它保留最小的資訊,例如幾個最近的區塊的雜湊,並在需要檢查完整狀態的某些部分時依賴於從完整節點獲得的資訊。} %
只知道某些 hashmap $h$ 的 $\Hash(h)$ 值(例如,智能合約的持久儲存或全域區塊鏈狀態)可能會從完整節點%
\footnote{「完整節點」是跟踪有關 shardchain 的完整最新狀態的節點。} %
請求不僅僅是值 $x=h[i]=\hget(h)(i)$,而是伴隨著從已知值 $\Hash(h)$ 開始的 Merkle 證明的這樣一個值。然後,在假設 \eqref{eq:hash.coll} 下,輕量節點可以自己檢查 $x$ 確實是 $h[i]$ 的正確值。
在某些情況下,客戶端可能希望獲得值 $y=\Hash(x)=\Hash(h[i])$,例如,如果 $x$ 本身非常大(例如,是一個 hashmap)。然後,可以提供 $(i,y)$ 的 Merkle 證明。如果 $x$ 也是一個 hashmap,那麼可以從完整節點獲得從 $y=\Hash(x)$ 開始的第二個 Merkle 證明,以提供值 $x[j]=h[i][j]$ 或僅其雜湊。
\nxsubpoint \embt(Importance of Merkle proofs for a multi-chain system such as TON.) 請注意,節點通常不能為 TON 環境中存在的所有 shardchains 成為完整節點。它通常只是某些 shardchains 的完整節點——例如,包含其自己的帳戶,它感興趣的智能合約,或者該節點已被指派為其validator的那些。對於其他 shardchains,它必須是一個輕量節點——否則儲存、計算和網路帶寬的要求將是禁止的。這意味著這樣的節點不能直接檢查關於其他 shardchains 狀態的斷言;它必須依賴於從那些 shardchains 的完整節點獲得的 Merkle 證明,除非 \eqref{eq:hash.coll} 失敗(即,找到一個雜湊碰撞),這同樣安全。
\nxsubpoint\label{sp:pec.tvm} \embt(Peculiarities of TON VM.) TON VM 或 TVM (Telegram Virtual Machine),用於在 masterchain 和 Workchain Zero 中運行智能合約,與受到 EVM (Ethereum Virtual Machine) 啟發的常見設計有很大的不同:它不僅僅與 256 位整數工作,實際上它與(幾乎)任意的「紀錄」、「結構」或「總乘積類型」一起工作,使其更適合執行用高級(尤其是功能性)語言編寫的程式碼。實際上,TVM 使用的是帶有標籤的數據類型,這與 Prolog 或 Erlang 的實現中使用的不太相同。
人們首先可以想像,TVM 智能合約的狀態不僅僅是一個 hashmap $\st2^{256}\to\st2^{256}$ 或 $\Hashmap(256,\st2^{256})$,但(作為第一步)是 $\Hashmap(256,X)$,其中 $X$ 是具有幾個構造器的類型,使其除了 256 位整數之外,還能儲存其他數據結構,尤其是其他的 hashmap $\Hashmap(256,X)$。這意味著 TVM(持久或臨時)儲存的一個cells——或者一個在 TVM 智能合約程式碼中的變量或數組元素——可能不僅包含一個整數,還包含一個全新的 hashmap。當然,這意味著一個cells不僅僅包含 256 位,還包含,例如,一個 8 位的標籤,描述如何解釋這 256 位。
事實上,值不需要確切地是 256 位的。TVM 使用的值格式由原始字節和對其他結構的引用組成,這些引用以任意順序混合,並在合適的位置插入一些描述字節,以便能夠區分指針和原始數據(例如,字符串或整數);請參見~\ptref{sp:tvm.cells}。
這種原始值格式可以用來實現任意的總乘積代數類型。在這種情況下,該值首先包含一個原始字節,描述正在使用的「構造器」(從高級語言的角度看),然後是其他「字段」或「構造器參數」,由原始字節和對其他結構的引用組成,具體取決於選擇的構造器(參考~\ptref{sp:TL})。然而,TVM 並不知道構造器及其參數之間的對應關係;字節和引用的混合由某些描述字節明確描述。\footnote{這兩個描述字節,在任何 TVM cells中都存在,僅描述參考總數和原始字節總數;參考總是放在所有原始字節之前或之後。}
Merkle 樹雜湊被擴展到任意這樣的結構:要計算這樣一個結構的雜湊,所有的參考都被遞歸地替換為被參考對象的雜湊,然後計算結果字節串(包括描述字節)的雜湊。
通過這種方式,對 hashmaps 的 Merkle 樹雜湊,如~\ptref{sp:merkle.patr.hash}所述,只是用於類型 $\Hashmap(n,X)$ 的兩個構造器的任意(依賴的)代數數據類型的雜湊的特殊情況。\footnote{實際上,$\leaf$ 和 $\node$ 是輔助類型 $\tp{HashmapAux}(n,X)$ 的構造器。類型 $\Hashmap(n,X)$ 有構造器 $\root$ 和 $\emptyroot$,其中 $\root$ 包含類型 $\tp{HashmapAux}(n,X)$ 的值。}
\nxsubpoint \embt(Persistent storage of TON smart contracts.)
TON 智能合約的持久性儲存主要由其「全域變數」組成,這些變數在調用智能合約之間保持不變。因此,它只是一個「產品」、「元組」或「記錄」類型,由相應於每一個全域變數的正確類型的字段組成。如果全域變數太多,由於 TON cells大小的全域限制,它們不能放入一個 TON cells。在這種情況下,它們被分割成幾個記錄並組織成一棵樹,基本上變成了「產品的產品」或「產品的產品的產品」類型,而不僅僅是一個產品類型。
\nxsubpoint\label{sp:tvm.cells} \embt(TVM Cells.) 最終,TON VM 在一系列的{\em (TVM) cells}中保留所有數據。每個cells首先包含兩個描述符字節,表示此cells中有多少原始數據字節(最多 128)以及有多少對其他cells的引用(最多四個)。然後是這些原始數據字節和引用。每個cells只被引用一次,所以我們可能已經在每個cells中包括了對其「父級」的引用(唯一引用此cells的cells)。但是,這個引用不必是明確的。
通過這種方式,TON 智能合約的持久數據儲存cells被組織成一棵樹,\footnote{邏輯上;在~\ptref{sp:bag.of.cells}中描述的「bag of cells」表示法識別所有重複的cells,當序列化時,將此樹轉換為一個有向無環圖(dag)。} 智能合約描述中保留了對這棵樹的根的引用。如果需要,可以遞歸計算這整個持久儲存的 Merkle 樹雜湊,從葉子開始,然後簡單地將一個cells中的所有引用替換為所引用的cells的遞歸計算的雜湊,然後計算所得字節串的雜湊。
\nxsubpoint\label{sp:gen.merkle.proof} \embt(Generalized Merkle proofs
for values of arbitrary algebraic types.) 由於 TON VM 通過由 (TVM) cells組成的樹來表示任意代數類型的值,且每個cells都有一個明確定義的(遞歸計算的)Merkle 雜湊,實際上依賴於此cells為根的整個子樹,我們可以為任意代數類型的值(的部分)提供「一般化的 Merkle 證明」,旨在證明具有已知 Merkle 雜湊的樹的某個子樹具有特定值或具有特定雜湊的值。這概括了 \ptref{sp:merkle.proof} 的方法,其中只考慮了 $x[i]=y$ 的 Merkle 證明。
\nxsubpoint\label{sp:tvm.data.shard} \embt(Support for sharding in TON VM data structures.)
我們剛剛概述了如何在不過於複雜的情況下,TON VM 支持高級智能合約語言中的任意(依賴)代數數據類型。然而,對於大型(或全域)智能合約的分片需要在 TON VM 級別上的特殊支援。為此,系統中增加了 hashmap 類型的特殊版本,相當於一個「映射」 $\Account\dashrightarrow X$。這個「映射」可能看起來等同於 $\Hashmap(m,X)$,其中 $\Account=\st2^m$。但是,當一個分片被分成兩個,或兩個分片被合併時,這樣的 hashmaps 會自動被分成兩個,或合併回來,以保留只屬於相應分片的鍵。
\nxsubpoint \embt(Payment for persistent storage.)
TON 區塊鏈的一個值得注意的特點是從智能合約中扣除用於儲存其持久數據的支付(即,增加區塊鏈的總狀態)。它的工作原理如下:
每個區塊都宣布兩種費率,以區塊鏈的主要貨幣(通常是 Toncoin)來提名:保持一個cells在持久儲存中的價格,以及在持久儲存的某個cells中保持一個原始字節的價格。每個賬戶使用的cells和字節的總數據作為其狀態的一部分儲存,所以通過將這些數字乘以在區塊頭中宣布的兩個費率,我們可以計算從賬戶餘額中扣除的支付,以保持其數據在前一個區塊和當前區塊之間。
然而,對於每個賬戶和每個智能合約在每個區塊中的持久儲存使用的支付並不是每次都收取的;而是在賬戶數據中儲存上次收取此支付的區塊的序列號,並且當對賬戶進行任何操作時(例如,轉移價值或接收並由智能合約處理一條消息),在執行任何進一步的操作之前,從賬戶餘額中扣除自上次這樣的支付以來的所有區塊的儲存使用支付。如果賬戶的餘額在此之後變為負數,則該賬戶將被銷毀。
一個工作鏈可能宣稱每個賬戶的一些原始數據字節是「免費的」(即,不參與持久儲存支付),以使「簡單」的賬戶,只在一兩種加密貨幣中保持它們的餘額,免於這些常數支付。
請注意,如果沒有人給一個賬戶發送任何消息,它的持久儲存支付不會被收集,並且它可以無限期地存在。然而,任何人都可以發送,例如,一條空消息來銷毀這樣的賬戶。可以給發送這樣一條消息的人提供一個小的激勵,從要被銷毀的賬戶的原始餘額中收取部分資金。然而,我們預期,validator會免費銷毀這樣的無資金賬戶,僅僅是為了減少全域區塊鏈的狀態大小,並避免保持大量的數據而不得到賠償。
為持久數據的保持收集的支付在 shardchain 或 masterchain 的validator之間分配(在後一種情況下按比例分配他們的股份)。
\nxsubpoint\label{sp:loc.glob.smct} \embt(Local and global smart contracts; smart-contract instances.)
一個智能合約通常只存在於一個分片中,根據智能合約的 $\accountid$ 選擇,與「普通」賬戶類似。這通常對大多數應用程序來說都是足夠的。然而,一些「高負載」的智能合約可能希望在某個工作鏈的每個分片鏈中都有一個「實例」。為了實現這一點,它們必須將它們的創建交易傳播到所有的分片鏈中,例如,通過將此交易提交到工作鏈 $w$ 的「根」分片鏈 $(w,\emptyset)$ 中,並支付一大筆佣金。\footnote{一個更昂貴的選擇是在主鏈中發布這樣一個「全域」智能合約。}
這個動作實際上在每個分片中創建了智能合約的實例,具有單獨的餘額。原始地,創建交易中傳輸的餘額只是通過給分片 $(w,s)$ 的實例 $2^{-|s|}$ 的總餘額的部分來分配。當一個分片分裂成兩個子分片時,所有全域智能合約的實例的餘額都分裂為一半;當兩個分片合併時,餘額加在一起。
在某些情況下,分裂/合併全域智能合約的實例可能涉及這些智能合約的特殊方法的(延遲)執行。默認情況下,餘額按照上述方式分裂和合併,一些特殊的「賬戶索引」的 hashmaps 也是自動分裂和合併的(參見~\ptref{sp:tvm.data.shard})。
\nxsubpoint \embt(Limiting splitting of smart contracts.)
一個全域智能合約可以在其創建時限制其分裂深度 $d$,以使持久儲存費用更具可預測性。這意味著,如果分片鏈 $(w,s)$ 滿足 $|s|\geq d$ 被分裂成兩個,只有兩個新分片鏈中的一個繼承智能合約的實例。這個分片鏈是確定性選擇的:每個全域智能合約都有一個「$\accountid$」,本質上是其創建交易的雜湊,並且其實例具有與前 $\leq d$ 位替換為適當值的相同的 $\accountid$,以落入正確的分片。這個 $\accountid$ 選擇了分裂後哪個分片將繼承智能合約實例。
\nxsubpoint\label{sp:account.state} \embt(Account/Smart-contract state.)
我們可以總結以上所有內容,得出賬戶或智能合約的狀態包括以下內容:
\begin{itemize}
\item 區塊鏈的主要貨幣的餘額
\item 區塊鏈其他貨幣的餘額
\item 智能合約的程式碼(或其雜湊)
\item 智能合約的持久性數據(或其 Merkle 雜湊)
\item 持久性儲存cells和原始字節使用數量的統計
\item 上次收取智能合約持久性儲存付款的時間(實際上,是主鏈區塊號)
\item 轉移貨幣和從此賬戶發送消息所需的公鑰(可選;默認等於 $\accountid$ 本身)。在某些情況下,更為複雜的簽名檢查程式碼可能位於此處,與比特幣交易輸出類似;然後,$\accountid$ 將等於此程式碼的雜湊。
\end{itemize}
我們還需要在某處保存以下數據,無論是在賬戶狀態中還是在某個其他的賬戶索引的雜湊圖中:
\begin{itemize}
\item 賬戶的輸出消息隊列(參見~\ptref{sp:out.queue})
\item 最近傳送消息的(雜湊的)集合(參見~\ptref{sp:deliver.q})
\end{itemize}
並不是每個賬戶都真正需要所有這些;例如,只有智能合約需要智能合約程式碼,而「簡單」的賬戶則不需要。此外,儘管任何賬戶必須在主要貨幣中有一個非零餘額(例如,基礎工作鏈的主鏈和分片鏈的Toncoin),但在其他貨幣中可能有零餘額。為了避免保留未使用的數據,定義了一個乘積型別(取決於工作鏈)(在工作鏈的創建期間),它使用不同的標籤字節(例如,TL 構造器;參見~\ptref{sp:TL})來區分使用的不同「構造器」。最終,賬戶狀態本身作為TVM持久性儲存的cells集合保存。
\mysubsection{分片鏈間的消息}
TON 區塊鏈的一個重要組件是{\em 區塊鏈間的消息系統\/}。這些區塊鏈可以是同一工作鏈的分片鏈,或者是不同工作鏈的分片鏈。
\nxsubpoint \embt(Messages, accounts and transactions: a bird's eye view of the system.)
{\em 消息\/}從一個賬戶發送到另一個賬戶。每一個{\em 交易\/}包括一個賬戶接收一個消息,根據某些規則改變其狀態,並生成到其他賬戶的多個(可能是一個或零個)新消息。每條消息生成並接收(傳遞)確切一次。
這意味著消息在系統中扮演了基本的角色,與賬戶(智能合約)的角色相當。從無窮分片範式的角度看(參見~\ptref{sp:ISP}),每個賬戶都位於其獨立的「賬戶鏈」中,並且它唯一可以影響某其他賬戶的狀態的方式是通過發送消息。
\nxsubpoint\label{sp:actors} \embt(Accounts as processes or actors; Actor model.)
可以將賬戶(和智能合約)視為「進程」或「角色」,它們能夠處理進入的消息、改變其內部狀態,並因此生成一些出站消息。這與所謂的{\em Actor model}密切相關,該模型在Erlang之類的語言中使用(但是,Erlang中的角色通常稱為「進程」)。由於新的角色(即,智能合約)也允許由現有角色作為處理入站消息的結果來創建,因此與Actor model的對應基本上是完整的。
\nxsubpoint \embt(Message recipient.)
任何消息都有其{\em 接收者},由{\em 目標工作鏈識別符 $w$}(默認情況下與原始分片鏈相同)和{\em 接收賬戶 $\accountid$}進行描述。$\accountid$的確切格式(即,位數)取決於$w$;但是,碎片始終由其第一個(最重要的)64位確定。
\nxsubpoint\label{sp:msg.sender} \embt(Message sender.)
在大多數情況下,消息都有一個{\em 發送者},再次由$(w',\accountid')$對進行描述。如果存在,它位於消息接收者和消息值之後。有時,發送者不重要,或者他是區塊鏈之外的某人(即,不是智能合約),在這種情況下,此字段不存在。
值得注意的是,Actor model並不要求消息有一個隱式發送者。相反,消息可能包含對應該發送請求回覆的Actor的引用;它通常與發送者相符。但是,在加密貨幣(Byzantine)環境中,在消息中有一個明確的不可偽造的發送者字段是很有用的。
\nxsubpoint \embt(Message value.)
消息的另一個重要特性是其附加的{\em 值},它是源工作鏈和目標工作鏈均支持的一種或多種加密貨幣。消息的值在消息接收者之後的開頭處指示;它實際上是一系列的$(\currencyid,\vr{value})$對。
請注意,「簡單」賬戶之間的「簡單」值轉移只是帶有某些值的空(無操作)消息。另一方面,略為複雜的消息主體可能包含一個簡單的文本或二進制評論(例如,關於付款的目的)。
\nxsubpoint\label{sp:ext.msg} \embt(External messages, or ``messages from nowhere''.)
有些消息是從「無處」來的,也就是它們並非由位於區塊鏈中的賬戶(無論是否是智能合約)生成的。最典型的例子是當用戶希望從她控制的賬戶轉移一些資金到另一個賬戶時。在這種情況下,用戶發送一個「來自無處的消息」到她自己的賬戶,要求它生成一個發送給接收賬戶的消息,帶有指定的值。如果此消息被正確簽名,她的賬戶就會接收到它並生成所需的出站消息。
實際上,人們可能會認為「簡單」賬戶是帶有預定義程式碼的智能合約的特例。這種智能合約只接收一種類型的消息。這種入站消息必須包含作為傳遞(處理)入站消息結果要生成的出站消息列表,以及一個簽名。智能合約檢查簽名,如果它是正確的,則生成所需的消息。
當然,「來自無處的消息」和普通消息之間有所不同,因為「來自無處的消息」不能承載值,所以它們不能為自己的「gas」(即它們的處理)付款。相反,它們在甚至被建議包含在新的shardchain塊中之前,會先嘗試執行一個小的gas限制;如果執行失敗(簽名不正確),則「來自無處的消息」被視為不正確並被丟棄。如果執行在小的gas限制內不失敗,則消息可能被包含在新的shardchain塊中並完全處理,從接收者的賬戶中扣除所消耗的gas(處理能力)的付款。 「來自無處的消息」也可以定義一些交易費,這些費用在gas付款之外從接收者的賬戶中扣除,以重新分配給validator。
在這個意義上,「來自無處的消息」或「外部消息」起到了在其他區塊鏈系統中使用的交易候選人的作用(例如,比特幣和以太坊)。
\nxsubpoint \embt(Log messages, or ``messages to nowhere''.)
同樣,有時可以生成並路由到特定的shardchain的特殊消息,不是為了交付給其收件人,而是為了記錄,以便任何人接收到有關該碎片的更新時都可以輕鬆觀察。這些記錄的消息可以在用戶的控制台中輸出,或觸發某個離鏈伺服器上的某個腳本的執行。在這種意義上,它們代表了「區塊鏈超級電腦」的外部「輸出」,正如「來自無處的消息」代表了「區塊鏈超級電腦」的外部「輸入」。
\nxsubpoint \embt(Interaction with off-chain services and external blockchains.)
這些外部輸入和輸出消息可以用於與離鏈服務和其他(外部)區塊鏈互動,如比特幣或以太坊。人們可以在TON區塊鏈中創建與比特幣、以太或在以太坊區塊鏈中定義的任何ERC-20代幣相關聯的代幣或加密貨幣,並使用「來自無處的消息」和「去無處的消息」,由位於某些第三方離鏈伺服器上的腳本生成和處理,以實現TON區塊鏈與這些外部區塊鏈之間的必要互動。
\nxsubpoint \embt(Message body.) {\em message body\/} 基本上就是一系列的位元組,其含義只由接收的工作鏈和/或智能合約決定。對於使用TON VM的區塊鏈,這可以是通過 \texttt{Send()} 操作自動生成的任何 TVM cell 的序列化。這種序列化是通過遞迴地替換 TON VM cell 中的所有參照來獲得的。最終,會出現一串原始位元組,通常在前面加上一個 4 位元組的「消息類型」或「消息建構器」,用於選擇接收智能合約的正確方法。
另一種選擇是使用 TL-序列化對象(參見 \ptref{sp:TL})作為消息主體。這對於不同工作鏈之間的通信可能尤其有用,其中一個或兩個不一定使用TON VM。
\nxsubpoint \embt(Gas limit and other workchain/VM-specific parameters.) 有時消息需要攜帶有關 gas 限制、gas 價格、交易費用和相似值的資訊,這些值取決於接收的工作鏈,並且只與接收的工作鏈有關,但不一定與原始工作鏈有關。這些參數包含在消息主體中或之前,有時(取決於工作鏈)有特殊的 4 位元組前綴表示它們的存在(可以由 TL-方案定義;參見 \ptref{sp:TL})。
\nxsubpoint \embt(Creating messages: smart contracts and transactions.) 新消息的來源有兩個。大多數消息是在智能合約執行期間創建的(通過 TON VM中的 \texttt{Send()} 操作),當某個智能合約被調用以處理一個入站消息時。或者,消息可能來自外部,作為「外部消息」或「來自無處的消息」(參見 \ptref{sp:ext.msg})。%
\footnote{上述只需要在基本工作鏈及其分片鏈上文字上是真實的;其他工作鏈可能提供其他創建消息的方法。}
\nxsubpoint \embt(Delivering messages.) 當一條消息到達包含其目的賬戶的 shardchain 時,\footnote{作為一個退化情況,這個 shardchain 可能與原始的 shardchain 重合——例如,如果我們正在內部工作的工作鏈尚未被分裂。} 它被「傳遞」到其目的地賬戶。接下來會發生什麼取決於工作鏈;從外部觀點看,重要的是這樣的消息從這個 shardchain 永遠不會被進一步轉發。
對於基礎工作鏈的 shardchains,傳送包括將消息值(扣除任何 gas 付款)添加到接收賬戶的餘額,並可能之後調用接收智能合約的一個依賴於消息的方法,如果接收賬戶是一個智能合約。事實上,一個智能合約只有一個進入點用於處理所有傳入消息,並且它必須通過查看它們的前幾個位元組來區分不同類型的消息(例如,包含 TL 建構器的前四個位元組;參見 \ptref{sp:TL})。
\nxsubpoint \embt(Delivery of a message is a transaction.) 因為消息的交付更改了賬戶或智能合約的狀態,所以它在接收的 shardchain 中是一個特殊的 {\em 交易\/},並明確地註冊為這樣。本質上,{\em 所有\/} TON 區塊鏈交易都包括將一個入站消息傳遞給其接收賬戶(智能合約),忽略一些次要技術細節。
\nxsubpoint \embt(Messages between instances of the same smart contract.) 回憶一下,一個智能合約可能是 {\em 本地\/} 的(即,像任何普通賬戶一樣駐留在一個 shardchain 中)或 {\em 全域\/} 的(即,在所有的 shards 中都有實例,或至少在所有深度為 $d$ 的 shards 中;參見 \ptref{sp:loc.glob.smct})。全域智能合約的實例可能需要交換特殊消息以在彼此之間傳遞信息和價值。在這種情況下,(不可偽造的)發件人 $\accountid$ 變得很重要(參見 \ptref{sp:msg.sender})。
\nxsubpoint \embt(Messages to any instance of a smart contract; wildcard addresses.) 有時候一條消息(例如,客戶端請求)需要被交付給全域智能合約的任何實例,通常是最近的一個(如果有一個駐留在與發件人相同的 shardchain 中,它是明顯的候選人)。做到這一點的一種方法是使用「通配符收件人地址」,其中目標 $\accountid$ 的前 $d$ 位可以取任意值。實際上,人們通常會將這 $d$ 位設置為與發件人的 $\accountid$ 中的相同值。
\nxsubpoint \embt(Input queue is absent.) 由區塊鏈接收的所有消息(通常是 shardchain;有時是 masterchain)——或基本上是駐留在某個 shardchain 內的「賬戶鏈」——都立即被交付(即,由接收賬戶處理)。因此,沒有像這樣的「輸入隊列」。相反,如果由於對區塊總大小和 gas 使用的限制,不是所有目的為特定 shardchain 的消息都可以被處理,一些消息簡單地留在原始 shardchains 的輸出隊列中積累。
\nxsubpoint\label{sp:out.queue} \embt(Output queues.) 從無限分割範例(Infinite Sharding Paradigm)的角度看 (cf.~\ptref{sp:ISP}),每個賬戶鏈(即,每個賬戶)都有其自己的輸出隊列,由它生成但尚未傳遞給其接收者的所有消息組成。當然,賬戶鏈只有一個虛擬的存在;它們被分組到shardchains中,而一個shardchain有一個輸出「隊列」,由屬於該shardchain的所有賬戶的輸出隊列的聯合組成。
這個shardchain輸出「隊列」只對其成員消息施加部分順序。即,在先前的區塊中生成的消息必須在隨後的區塊中生成的任何消息之前被傳遞,並且由相同賬戶生成且具有相同目的地的任何消息必須按照它們的生成順序傳遞。
\nxsubpoint\label{sp:intershard.msgs} \embt(Reliable and fast inter-chain messaging.) 對於像TON這樣的可擴展多區塊鏈專案,能夠在不同的shardchains之間轉發和傳遞消息是至關重要的 (cf.~\ptref{sp:msg.IHR}),即使系統中有數百萬個。消息應該被{\em 可靠地\/}(即,消息不應該丟失或傳遞多次)和{\em 快速地}傳遞。TON區塊鏈通過使用兩種「消息路由」機制的組合來實現這一目標。
\nxsubpoint\label{sp:hypercube} \embt(Hypercube routing: ``slow path''
for messages with assured delivery.) TON Blockchain 使用「超立方體路由」作為一種緩慢,但安全可靠的方法,從一個 shardchain 傳遞消息到另一個 shardchain,如有必要,使用幾個中間的 shardchain 進行轉發。否則,任何給定的 shardchain 的validator都需要追踪所有其他 shardchain 的狀態(輸出隊列),隨著 shardchain 總數的增加,這將需要過多的計算能力和網路帶寬,從而限制了系統的可擴展性。因此,無法直接從任何 shard 傳遞消息到其他每一個 shard。相反,每個 shard 只與其 $(w,s)$ shard 標識符中確切一個十六進制數位不同的 shard「連接」(cf.~\ptref{sp:shard.ident})。這樣,所有的 shardchain 構成一個「超立方體」圖,消息沿著這個超立方體的邊緣移動。
如果消息被發送到與當前的 shard 不同的 shard,當前的 shard 標識符的十六進制數字(確定地選擇)被替換為目標 shard 的相應數字,並使用所得的標識符作為轉發消息的近端目標。\footnote{這不一定是用於計算超立方體路由的下一跳的算法的最終版本。特別是,十六進制數字可能會被 $r$-位群組替換,其中 $r$ 是一個可配置的參數,不一定等於四。}
超立方體路由的主要優點是區塊有效性條件意味著創建 shardchain 的區塊的validator必須收集和處理「鄰近」shardchain 的輸出隊列中的消息,否則將失去他們的 stake 。這樣,任何消息都可以預期最終會達到其最終目的地;消息不能在過程中丟失或傳遞兩次。
請注意,超立方體路由帶來了一些額外的延遲和開銷,因為必須通過幾個中間的 shardchain 轉發消息。然而,這些中間的 shardchain 的數量增長非常緩慢,作為 shardchain 總數 $N$ 的對數 $\log N$(更確切地說,$\lceil\log_{16}N\rceil-1$)。例如,如果 $N\approx250$,最多只有一個中間的 hop;對於 $N\approx4000$ 的 shardchain,最多有兩個。四個中間的 hop,我們可以支持多達一百萬的 shardchain。我們認為為系統的基本無限的可擴展性支付的這個代價是非常小的。事實上,甚至不必支付這個價格:
\nxsubpoint\label{sp:instant.hypercube} \embt(Instant Hypercube
Routing: ``fast path'' for messages.) TON Blockchain 的一個新功能是它引入了一個「快速路徑」,從一個 shardchain 轉發消息到任何其他 shardchain,在大多數情況下都可以完全繞過 \ptref{sp:hypercube} 中的「慢速」超立方體路由,並在最終目的地 shardchain 的下一個區塊中傳遞消息。
該思路如下。在「慢速」的超立方體路由中,消息在超立方體的邊緣上(在網路中)旅行,但在每個中間頂點都會被延遲(大約五秒鐘),以將其提交到相應的 shardchain,然後再繼續其旅程。
為了避免不必要的延遲,可以沿著超立方體的邊緣轉發消息和一個適當的 Merkle 證明,而不用等待將其提交到中間的 shardchains。實際上,網路消息應該從原始 shard 的「任務組」的validator(cf.~\ptref{sp:val.task.grp})轉發到目的地 shard 的「任務組」的指定區塊生產者(cf.~\ptref{sp:rot.gen.prio});這可能可以直接完成,而不沿著超立方體的邊緣。當這條帶有 Merkle 證明的消息到達目的地 shardchain 的validator(更確切地說,是 collators;cf.~\ptref{sp:collators})時,他們可以立即將其提交到一個新的區塊,而不用等待消息完成沿著「慢路徑」的旅程。然後將交付確認以及一個適當的 Merkle 證明沿著超立方體的邊緣發回,並且可以通過提交一個特殊的交易來停止消息沿著「慢路徑」的旅程。
請注意,這種「即時交付」機制並未取代在~\ptref{sp:hypercube} 中描述的「慢速」但是不會失敗的機制。仍然需要「慢路徑」,因為validator不能因失去或簡單地決定不將「快速路徑」消息提交到他們區塊鏈的新區塊而受到懲罰。\footnote{然而,validator有一定的動機盡快這樣做,因為他們將能夠收集與消息相關的所有轉發費用,這些費用尚未在慢路徑中被消耗。}
因此,兩種消息轉發方法是平行運行的,只有在「快速」機制的成功證明被提交到一個中間的 shardchain 時,「慢速」機制才會被中止。%\footnote{實際上,可以暫時或永久禁用「即時交付」機制,系統將繼續運行,但速度會慢一些。}
\nxsubpoint\label{sp:collect.input.msg} \embt(Collecting input
messages from output queues of neighboring shardchains.) 當為 shardchain 提議一個新的區塊時,鄰近(在\ptref{sp:hypercube}的路由超立方體意義上)的 shardchains 的一些輸出消息被包含在新的區塊中作為「輸入」消息,並立即被傳遞(即,處理)。關於這些鄰居的輸出消息必須以哪種順序進行處理,有一定的規則。基本上,一個「較舊」的消息(來自參照較舊的主鏈區塊的 shardchain 區塊)必須在任何「較新」的消息之前傳遞;對於來自同一鄰近 shardchain 的消息,必須遵守\ptref{sp:out.queue}中描述的輸出隊列的部分順序。
\nxsubpoint\label{sp:out.q.del} \embt(Deleting messages from output queues.) 一旦觀察到輸出隊列中的訊息已被相鄰的分片鏈交付,則通過特殊交易明確地從輸出隊列中刪除它。
\nxsubpoint\label{sp:deliver.q} \embt(Preventing double delivery of messages.) 為了防止從相鄰的分片鏈的輸出隊列中雙重交付訊息,每個分片鏈(更確切地說,其中的每個賬戶鏈)作為其狀態的一部分保持最近交付的訊息的集合(或僅其雜湊值)。當觀察到已交付的訊息從其源相鄰分片鏈(參見\ptref{sp:out.q.del})的輸出隊列中被刪除時,它也從最近交付的訊息的集合中被刪除。
\nxsubpoint \embt(Forwarding messages intended for other shardchains.) 通過 Hypercube 路由(參見\ptref{sp:hypercube})有時出站訊息不是交付給包含預期收件人的分片鏈,而是交付給位於到目的地的超立方體路徑上的相鄰分片鏈。在這種情況下,"交付"包括將入站訊息移動到出站隊列。這在塊中明確地反映為一個特殊的{\em 轉發交易},其中包含該訊息。本質上,這看起來就像該訊息已被分片鏈內的某人接收,並且生成了一個相同的訊息作為結果。
\nxsubpoint \embt(Payment for forwarding and keeping a message.) 轉發交易實際上消耗了一些瓦斯(取決於被轉發的訊息的大小),因此從被轉發的訊息的值中扣除了一筆瓦斯支付,代表此分片鏈的validator。此轉發支付通常遠小於當訊息最終交付給其收件人時所確定的瓦斯支付,即使該訊息由於超立方體路由而被轉發了多次。此外,只要某個分片鏈的輸出隊列中保持有訊息,它就是分片鏈的全域狀態的一部分,因此特殊交易也可能收取長時間保持全域數據的支付。
\nxsubpoint \embt(Messages to and from the masterchain.) 訊息可以直接從任何分片鏈發送到主鏈,反之亦然。但是,發送訊息到主鏈以及在主鏈中處理訊息的瓦斯價格相當高,因此只有在真正需要時才會使用此功能——例如,由validator來存入他們的 stake 。在某些情況下,可能會定義發送到主鏈的訊息的最小存款(附加值),只有當接收方認為該訊息是“有效”的時候才會退還。
訊息不能自動通過主鏈路由。帶有 $\workchainid\neq-1$ 的訊息(其中 $-1$ 是表示主鏈的特殊 $\workchainid$)不能交付給主鏈。
原則上,人們可以在主鏈內部創建一個訊息轉發智能合約,但使用它的價格將是禁止性的。
\nxsubpoint \embt(Messages between accounts in the same shardchain.)
在某些情況下,某個分片鏈中的賬戶生成的訊息,目標是同一分片鏈中的另一賬戶。例如,這發生在新的工作鏈中,因為負載是可管理的,所以尚未分裂成多個分片鏈。
這樣的訊息可能會在分片鏈的輸出隊列中累積,然後在後續的區塊中作為入站訊息進行處理(為此目的,任何分片都被視為其本身的鄰居)。然而,在大多數情況下,有可能在起源區塊本身內交付這些訊息。
為了實現這一點,對包含在分片鏈區塊中的所有交易施加了部分排序,並尊重此部分順序處理交易(每個交易都包含將訊息交付給某個賬戶)。特別是,允許一個交易處理與此部分順序相對的前一個交易的某個輸出訊息。
在這種情況下,訊息主體不會被複製兩次。相反,起源交易和處理交易都參照訊息的共享副本。
\mysubsection{全域 Shardchain 狀態。"Bag of Cells"哲學。}
現在我們準備描述TON區塊鏈的全域狀態,或者至少是基本工作鏈的分片鏈。
我們從“高級”或“邏輯”描述開始,即全域狀態是代數類型 $\tp{ShardchainState}$ 的值。
\nxsubpoint\label{sp:shard.state} \embt(Shardchain state as a
collection of account-chain states.) 根據無限分片模型(參見\ptref{sp:ISP}),任何分片鏈只是虛擬“賬戶鏈”的(臨時)集合,每個賬戶鏈只包含一個賬戶。這意味著,本質上,全域分片鏈狀態必須是一個雜湊映射
\begin{equation}\label{eq:simple.shard.st}
\tp{ShardchainState}:=(\Account\dashrightarrow\tp{AccountState})
\end{equation}
其中所有作為此雜湊映射的指數出現的 $\accountid$ 必須以前綴 $s$ 開始,如果我們正在討論分片 $(w,s)$ 的狀態(參見\ptref{sp:shard.ident})。
實際上,我們可能希望將 $\tp{AccountState}$ 分成幾個部分(例如,保持賬戶輸出訊息隊列的獨立,以簡化相鄰分片鏈的檢查),並在 $\tp{ShardchainState}$ 內部擁有幾個雜湊映射 $(\Account\dashrightarrow\tp{AccountStatePart}_i)$。我們還可能向 $\tp{ShardchainState}$ 添加少量“全域”或“整體”參數,(例如,屬於此分片的所有賬戶的總餘額,或所有輸出隊列中的訊息總數)。
然而,\eqref{eq:simple.shard.st} 是分片鏈全域狀態的一個很好的初步近似值,至少從“邏輯”(“高級”)的角度來看。可以使用TL方案(參見\ptref{sp:TL})的幫助來進行代數類型 $\tp{AccountState}$ 和 $\tp{ShardchainState}$ 的正式描述,該描述將在其他地方提供。
\nxsubpoint\label{sp:split.merge.state} \embt(Splitting and merging shardchain states.)
請注意,無限分片模型描述的分片鏈狀態 \eqref{eq:simple.shard.st} 顯示了當分片被分裂或合併時,該狀態應如何被處理。實際上,這些狀態變換變得是非常簡單的雜湊映射操作。
\nxsubpoint \embt(Account-chain state.)
(虛擬的)賬戶鏈狀態只是一個賬戶的狀態,由類型 $\tp{AccountState}$ 描述。通常它具有在~\ptref{sp:account.state} 中列出的所有或某些字段,具體取決於使用的構造器。
\nxsubpoint \embt(Global workchain state.)
與 \eqref{eq:simple.shard.st} 類似,我們可以使用相同的公式定義全域的 {\em workchain\/} 狀態,但 $\accountid$'s 可以取任何值,不僅僅是屬於一個分片的值。在這種情況下,也適用於~\ptref{sp:shard.state} 中所做的類似備註:我們可能想要將此雜湊映射分裂成幾個雜湊映射,我們可能想要添加一些“整體”的參數,如總餘額。
本質上,全域的工作鏈狀態 {\em must\/} 被給予與分片鏈狀態相同的類型 $\tp{ShardchainState}$,因為如果這個工作鏈的所有現有分片鏈突然合併成一個,我們會得到的就是這個分片鏈狀態。
\nxsubpoint\label{sp:bag.of.cells} \embt(Low-level perspective: ``bag of cells''.)
存在一個「低階」描述關於賬戶鏈或shardchain狀態,這與上述的「高階」描述是互補的。此描述相當重要,因為它事實上是非常普遍的,為代表、儲存、序列化和通過網路轉移TON Blockchain(包括blocks、shardchain states、smart-contract storage、Merkle proofs等)所用的幾乎所有資料提供了一個共同的基礎。同時,一旦這樣的普遍「低階」描述被理解和實施,我們就可以集中注意力僅考慮「高階」。
回想一下,TVM用一棵「TVM cells」樹,或簡稱為「cells」(參見~\ptref{sp:tvm.cells}和~\ptref{sp:TL})來表示任意代數類型的值(例如,~\eqref{eq:simple.shard.st}中的$\tp{ShardchainState}$)。
每個這樣的cell都由兩個「descriptor bytes」組成,定義某些標誌和值$0\leq b\leq 128$,表示原始bytes的數量,以及$0\leq c\leq 4$,這是指向其他cells的引用數量。然後是$b$個原始bytes和$c$個cell引用。\footnote{可以顯示,如果經常需要儲存在cell樹中的所有資料的Merkle proofs,則應該使用$b+ch\approx 2(h+r)$的cells來最小化平均Merkle proof大小,其中$h=32$是hash在bytes中的大小,而$r\approx4$是cell引用的「byte大小」。換句話說,一個cell應該包含兩個引用和一些原始bytes,或一個引用和大約36原始bytes,或完全沒有引用但是有72原始bytes。}
cell引用的確切格式取決於它的實現,以及cell是否位於RAM、磁碟、網路封包、block等。一個有用的抽象模型是想像所有cells都存放在內容可寄存的記憶體中,cell的地址等於其($\Sha$) hash。回想一下,cell的(Merkle) hash正是通過將其子cell的引用替換為它們(遞迴計算的)hashes並hash生成的byte string來計算的。
這樣,如果我們使用cell hashes來引用cells(例如,在其他cells的描述中),系統稍微簡化,且cell的hash開始與代表它的byte string的hash相符。
現在我們看到,{\em 任何TVM可以表示的對象,包括全域shardchain狀態,都可以表示為一個「bag of cells」} ——即,{\em 一個cells的集合以及指向其中之一的「root」引用}(例如,通過hash)。請注意,重複的cells從此描述中被刪除了(「bag of cells」是cells的集合,而不是多重集),所以抽象的樹表示實際上可能變成了一個有向無環圖(dag)表示。
人甚至可以在硬碟上使用$B$-tree或$B+$-tree來保存這個狀態,包含所有相關的cells(也許還有一些附加數據,如子樹高度或引用計數器),並由cell hash進行索引。但是,這個想法的簡單實現會導致一個智能合約的狀態被散佈在硬碟文件的遠處,這是我們想要避免的。\footnote{更好的實現方法是,如果smart contract的狀態很小,就將其保存為序列化的字符串,如果很大,則保存在另一個$B$-tree中;然後代表blockchain狀態的頂層結構將是一個$B$-tree,其葉子節點被允許包含對其他$B$-tree的引用。}
現在我們將詳細解釋TON Blockchain使用的幾乎所有對象如何可以表示為「bag of cells」,從而展示這種方法的普遍性。
\nxsubpoint \embt(Shardchain block as a ``bag of cells''.)
Shardchain block本身也可以用代數類型來描述,並儲存為「bag of cells」。然後可以通過簡單地連接表示「bag of cells」中每個cell的byte strings(以任意順序)來獲得block的簡單二進制表示。這種表示可以進一步改進和優化,例如,在block的開頭提供所有cells的偏移量列表,並在可能的情況下用32位索引替換對其他cells的hash引用。然而,人們應該認識到block本質上是一個「bag of cells」,所有其他技術細節只是次要的優化和實現問題。
\nxsubpoint\label{sp:obj.update} \embt(Update to an object as a ``bag of cells''.)
想像我們有一個以「bag of cells」表示的對象的舊版本,我們想要表示同一對象的新版本,這個新版本應該與前一個不太不同。一個方法是簡單地將新狀態表示為具有自己root的另一個「bag of cells」,{\em 並從中刪除所有在舊版本中出現的cells}。剩下的「bag of cells」基本上是對象的{\em update\/}。每個擁有此對象的舊版本和update的人都可以計算新版本,只需合併兩個bag of cells,並刪除舊的root(減少其引用計數,並在引用計數變為零時釋放cell)。
\nxsubpoint \embt(Updates to the state of an account.)
特別是,對賬戶的狀態、shardchain的全域狀態或任何hashmap的更新都可以使用在~\ptref{sp:obj.update}中描述的想法進行表示。這意味著當我們接收到一個新的shardchain block(即是「bag of cells」)時,我們不只是單獨解釋這個「bag of cells」,而是首先將其與代表shardchain先前狀態的「bag of cells」結合。從這個意義上說,每個block可能都「包含」blockchain的整體狀態。
\nxsubpoint \embt(Updates to a block.)
回憶一下,block本身就是一個「bag of cells」,所以,如果需要編輯block,則可以類似地將「block update」定義為「bag of cells」,並在存在該block的先前版本的「bag of cells」的情境下進行解釋。這大致上是在~\ptref{sp:inv.sh.blk.corr}中討論的「垂直blocks」背後的想法。
\nxsubpoint\label{sp:merkle.as.BoC} \embt(Merkle proof as a ``bag of cells''.)
注意,一個(廣義的)Merkle證明——例如,從已知的$\Hash(x)=h$開始聲稱$x[i]=y$(參見~\ptref{sp:merkle.proof}和~\ptref{sp:gen.merkle.proof})——也可以表示為「bag of cells」。具體來說,只需要提供一組cells子集,對應從$x:\Hashmap(n,X)$的根到其所需的具有索引$i:\st2^n$和值$y:X$的葉子的路徑。在此證明中,不位於此路徑上的這些cells的子項的引用將保持「未解決」,由cell hashes表示。還可以同時提供,例如,$x[i]=y$和$x[i']=y'$的Merkle證明,通過在「bag of cells」中包括位於從$x$的根到對應於索引$i$和~$i'$的葉子的兩條路徑的聯合上的cells。
\nxsubpoint\label{sp:merkle.query.resp} \embt(Merkle proofs as query responses from full nodes.)
實質上,擁有shardchain(或account-chain)狀態完整副本的完整節點可以在被輕節點(例如,運行TON Blockchain客戶端輕版本的網路節點)請求時提供Merkle證明,使接收者能夠僅使用此Merkle證明中提供的cells執行一些簡單的查詢,而不需要外部幫助。輕節點可以將其查詢以序列化格式發送給完整節點,並接收正確的答案和Merkle證明——或僅僅是Merkle證明,因為請求者應該能夠僅使用Merkle證明中包含的cells來計算答案。這個Merkle證明將僅由一個「bag of cells」組成,只包含屬於shardchain狀態的那些cells,在執行輕節點的查詢時由完整節點訪問。此方法尤其可用於執行智能合約的「get queries」(參見~\ptref{sp:tent.exec.get})。
\nxsubpoint\label{sp:aug.upd} \embt(Augmented update, or state update with Merkle proof of validity.)
回想一下(參見~\ptref{sp:obj.update}),我們可以透過「update」來描述從舊值$x:X$到新值$x':X$的物件狀態變化,這只是一個「bag of cells」,其中包含那些位於表示新值$x'$的子樹中的cells,但不包含位於表示舊值$x$的子樹中的cells,因為假設接收者擁有舊值$x$及其所有的cells複本。
然而,如果接收者並沒有$x$的完整複本,而只知道其(Merkle)hash $h=\Hash(x)$,它將無法檢查update的有效性(即update中的所有「懸空」cell引用確實指向存在於$x$的樹中的cells)。我們希望能夠具有可驗證性的update,並加上對舊狀態中所有引用cells存在的Merkle證明。這樣,只知道$h=\Hash(x)$的任何人都能夠檢查update的有效性,並自行計算新的$h'=\Hash(x')$。
因為我們的Merkle證明本身就是「bags of cells」(參見~\ptref{sp:merkle.as.BoC}),可以將這樣的「增強update」構造為一個「bag of cells」,其中包含$x$的舊根、其某些子孫以及從$x$的根到它們的路徑,以及$x'$的新根和其所有不屬於$x$的子孫。
\nxsubpoint \embt(Account state updates in a shardchain block.)
特別是,在shardchain block中的賬戶狀態更新應按照~\ptref{sp:aug.upd}中討論的方式進行增強。否則,某人可能提交一個包含在舊狀態中不存在的cell引用的無效狀態更新的block;證明此block的無效性將是困難的(挑戰者如何證明cell {\em 不是\/}先前狀態的一部分?)。
現在,如果包含在block中的所有狀態更新都是增強的,它們的有效性可以輕鬆檢查,並且其無效性也可以輕鬆顯示為違反(廣義)Merkle hashes的遞迴定義特性。
\nxsubpoint\label{sp:everything.is.BoC} \embt(``Everything is a bag of cells'' philosophy.)
前面的討論表明,我們在TON Blockchain或網路中需要儲存或傳輸的所有內容都可以表示為「bag of cells」。這是TON Blockchain設計哲學的重要部分。一旦解釋了「bag of cells」方法並定義了一些「bags of cells」的「低階」序列化,就可以在抽象(依賴性)代數數據類型的高層次上定義所有內容(如block格式、shardchain和賬戶狀態等)。
「一切都是bag of cells」哲學的統一效果大大簡化了看似不相關的服務的實現;有關涉及付款通道的示例,請參見~\ptref{sp:ton.smart.pc.supp}。
\nxsubpoint \embt(Block ``headers'' for TON blockchains.) 通常,blockchain中的block會從一個小型的header開始,其中包含前一個block的hash、創建時間、block中所有交易的樹的Merkle hash等。然後,block的hash被定義為這個小型block header的hash。因為block header最終取決於block中包含的所有數據,所以無法在不改變其hash的情況下修改block。
在TON blockchains的block使用的``bag of cells''方法中,沒有指定的block header。相反,block hash被定義為block的根cell的(Merkle) hash。因此,block的頂部(根)cell可能被視為此block的小型``header''。
但是,根cell可能不包含通常期望從這樣的header中獲得的所有數據。本質上,人們希望header包含$\Block$數據類型中定義的某些字段。通常,這些字段將包含在幾個cell中,包括根cell。這些cell一起構成了有關字段值的``Merkle proof''。人們可能會堅持在block中的任何其他cell之前,在一開始就包含這些``header cells''。然後,只需要下載block序列化的前幾個字節,就可以獲得所有的``header cells'',並了解所有期望的字段。
\mysubsection{創建和驗證新的Blocks}\label{sect:validators}
TON Blockchain最終由shardchain和masterchain blocks組成。為了系統順利且正確地運作,必須創建、驗證這些blocks,並通過網路將其傳播到所有相關方。
\nxsubpoint\label{sp:validators} \embt(validators.) 新的blocks由特定的節點創建和驗證,這些節點被稱為{\em validators}。實質上,任何希望成為validator的節點都可以成為validator,前提是它可以在masterchain中存入足夠多的抵押金(以TON幣,即Toncoin;參考\ Appendix~\ptref{app:coins})。validators為良好的工作獲得一些「獎勵」,即所有交易、儲存和燃氣費用,以及一些新鑄造的幣,這反映了整個社群對validators的「感激」,因為它們使TON Blockchain持續運作。這筆收入按照所有參與validators的抵押金比例分配。
然而,成為validator是一項重大的責任。如果validator簽署了一個無效的block,它可能會失去部分或全部的抵押金,並且可能會暫時或永久地被排除在validators之外。如果validator不參與創建block,它不會收到與該block相關的獎勵部分。如果validator長時間不創建新的blocks,它可能會失去部分的抵押金,並被暫停或永久排除在validators之外。
這一切都意味著validator不是輕而易舉地獲得金錢。事實上,它必須追踪所有或某些shardchains的狀態(每個validator負責驗證和創建某一子集shardchains中的新blocks),執行這些shardchains中的智能合約所請求的所有計算,接收其他shardchains的更新等等。這項活動需要大量的磁碟空間、計算能力和網路帶寬。
\nxsubpoint \embt(validators instead of miners.) 請記住,TON Blockchain使用的是Proof-of-Stake方法,而不是Bitcoin、當前版本的Ethereum和大多數其他加密貨幣採用的Proof-of-Work方法。這意味著人們不能通過提供某些工作證明(計算大量其他無用的hashes)來「挖掘」新的block,並因此獲得一些新的幣。相反,人們必須成為validator,並花費自己的計算資源來儲存和處理TON Blockchain的請求和數據。簡而言之,{\em 要挖新幣,必須成為validator。}就這一點而言,{\em validators就是新的miners。}
但是,除了成為validator之外,還有一些其他方式可以賺取幣。
\nxsubpoint\label{sp:nominators} \embt(Nominators and ``mining pools''.) 要成為validator,通常需要購買和安裝幾臺高性能的伺服器,並為它們提供良好的互聯網連接。這不像當前挖掘比特幣所需的ASIC設備那麼昂貴。但你絕對不能在家用電腦上挖新的TON幣,更不用說智能手機了。
在比特幣、以太坊和其他Proof-of-Work加密貨幣挖掘社區中,有一個名為{\em mining pools}的概念,其中許多節點因計算能力不足而無法自行挖掘新的blocks,所以他們合併力量並在之後分享獎勵。
Proof-of-Stake世界中的相應概念是{\em nominator}。實質上,這是一個將其資金借給validator以增加其抵押金的節點;然後validator將其獎勵的相應部分(或之前同意的一部分,例如50\%)分配給nominator。
通過這種方式,nominator也可以參與「挖掘」並獲得與其存款金額成正比的一些獎勵。它只獲得validator獎勵的一部分,因為它只提供了「資本」,但不需要購買計算能力、儲存和網路帶寬。
但是,如果validator因無效行為而失去其抵押金,nominator也會失去其抵押金的部分。在這種意義上,nominator {\em 分擔風險}。它必須明智地選擇其nominated validator,否則可能會損失資金。在這種意義上,nominator進行加權決策並使用其資金「投票」支持某些validator。
另一方面,這種提名或借貸系統使人們能夠成為validator,而無需首先投入大量金錢購買Toncoin(TON幣)。換句話說,它防止持有大量Toncoin的人壟斷validator的供應。
\nxsubpoint\label{sp:fish} \embt(Fishermen: obtaining money by pointing out others' mistakes.) 另一種不成為validator而獲得一些獎勵的方式是成為一名{\em fisherman}。實質上,任何節點都可以通過在masterchain中存入少量資金成為fisherman。然後,它可以使用特殊的masterchain交易來發布某些由validators之前簽名和發布的(通常是shardchain)blocks的(Merkle)無效性證明。如果其他validators同意這個無效性證明,則違規的validators將被懲罰(失去其抵押金的一部分),fisherman則獲得一些獎勵(從違規的validators中沒收的幣的一部分)。之後,如~\ptref{sp:inv.sh.blk.corr}中所述,必須更正無效的(shardchain)block。更正無效的masterchain blocks可能需要在先前提交的masterchain blocks之上創建「垂直」blocks(參見~\ptref{sp:inv.sh.blk.corr});無需創建masterchain的分叉。
通常,一個fisherman需要成為至少某些shardchains的完整節點,並花費一些計算資源來運行至少一些智能合約的程式碼。雖然fisherman不需要像validator那麼多的計算能力,但我們認為,一個天生的fisherman是一個準備處理新blocks,但尚未被選為validator的候選者(例如,由於未能存入足夠大的抵押金)。
\nxsubpoint\label{sp:collators} \embt(Collators: obtaining money by
suggesting new blocks to validators.) 另一種不成為validator但可以獲得一些獎勵的方法是成為一個{\em collator}。這是一個節點,它為validator準備並建議新的shardchain block候選者,並使用從此shardchain的狀態和其他(通常是相鄰的) shardchains中取得的資料進行補充(collated),伴隨適當的Merkle證明。當需要從鄰近的shardchains轉發一些消息時,這是必要的。然後,validator可以輕鬆檢查所提議的block候選者的有效性,無需下載此或其他shardchains的完整狀態。
由於validator需要提交新的(collated) block候選者以獲得一些(``mining'')獎勵,因此有理由支付一部分獎勵給願意提供適當block候選者的collator。這樣,validator可以避免觀察鄰近shardchains的狀態,將其外包給collator。
然而,我們預期在系統的初始部署階段不會有單獨指定的collators,因為所有validators都將能夠為自己充當collators。
\nxsubpoint \embt(Collators or validators: obtaining money for
including user transactions.) 使用者可以向一些collators或validators打開micropayment通道,並支付少量的幣以換取在shardchain中包括他們的交易。
\nxsubpoint\label{sp:global.valid} \embt(Global validator set
election.) 每月一次(實際上是每$2^{19}$個masterchain blocks)選舉``global''的validators集合。此集合在一個月前確定並被全域知悉。
要成為validator,節點必須將一些TON幣(Toncoin)轉入masterchain,然後將它們發送到特定的智能合約作為其建議的抵押金$s$。與抵押金一起發送的另一個參數是$l\geq 1$,這是此節點願意接受的相對於最小可能值的最大驗證負載。還有一個$l$的全域上限(另一個可配置參數)$L$,例如說是10。
然後,這個智能合約選舉global的validator集合,只需選擇最大的建議抵押金的前$T$個候選者並公布其身份。最初,validators的總數是$T=100$;隨著負載的增加,我們預期它將增長到1000。它是一個可配置參數(參見~\ptref{sp:config.param})。
每個validator的實際抵押金如下計算:如果前$T$個提議的抵押金是$s_1\geq s_2\geq\cdots\geq s_T$,那麼第$i$個validator的實際抵押金設定為$s'_i:=\min(s_i,l_i\cdot s_T)$。這樣,$s'_i/s'_T\leq l_i$,所以第$i$個validator不會獲得超過$l_i\leq L$倍最弱validator的負載(因為負載最終與抵押金成正比)。
然後,當選的validators可以撤回他們未使用的抵押金部分,$s_i-s'_i$。不成功的validator候選人可以撤回他們所有的建議抵押金。
每個validator發布其{\em public signing key},並不一定等於抵押金來源的帳戶的公鑰。\footnote{對於每次validator選舉,生成和使用新的密鑰對是有意義的。}
validators的抵押金被凍結,直到他們被選舉的時期結束,再加上一個月,以防新的爭議出現(例如,發現一個由這些validators簽名的無效block)。之後,將返回抵押金,以及在此期間鑄造的validator的幣份額和處理的交易的費用。
\nxsubpoint\label{sp:val.task.grp} \embt(Election of validator ``task
groups''.) 整體的全域validator集合(其中每個validator都被視為具有與其股份相等的多重性 - 否則validator可能會被誘使承擔多個身份並在它們之間劃分其股份)只用於驗證新的 masterchain 區塊。 shardchain 的區塊只由特定選擇的validator子集驗證,這些validator是從在\ptref{sp:global.valid}中描述的選擇的全域validator集合中選擇的。
這些validator「子集」或「任務組」,為每個 shard 定義,每小時(實際上,每 $2^{10}$ 個 masterchain 區塊)旋轉一次,它們在一小時前就已知,因此每個validator都知道它將需要驗證哪些 shards,並可以為此做準備(例如,通過下載丟失的 shardchain 數據)。
用於為每個 shard $(w,s)$ 選擇validator任務組的算法是確定性偽隨機的。它使用validator嵌入到每個 masterchain 區塊中的偽隨機數(通過使用閾值簽名生成的共識生成)來創建一個隨機種子,然後例如為每個validator計算 $\Hash(\code(w).\code(s).\vr{validator\_id}.\vr{rand\_seed})$。然後按此 hash 的值對validator進行排序,並選擇第一個validator,以便至少具有總validator股份的 $20/T$ 並且由至少5個validator組成。
這種選擇可以由特殊的智能合約完成。在這種情況下,選擇算法將可以輕鬆升級,無需通過\ptref{sp:config.param}中提到的投票機制進行硬分叉。迄今為止提到的所有其他「常數」(例如 $2^{19}$、$2^{10}$、$T$、20 和 5)也都是可配置的參數。
\nxsubpoint\label{sp:rot.gen.prio} \embt(Rotating priority order on
each task group.) 在 shard 任務組的成員上有一個特定的「優先順序」,取決於先前 masterchain 區塊的 hash 和 (shardchain) 區塊序列號。此順序是通過生成並排序上述的某些 hash 來確定的。
當需要生成新的 shardchain 區塊時,通常選擇用於創建此區塊的 shard 任務組validator是根據此旋轉「優先順序」的第一名。如果它未能創建該區塊,第二或第三個validator也可能這樣做。基本上,他們都可以建議他們的區塊候選者,但是由具有最高優先權的validator建議的候選者應該作為 Byzantine Fault Tolerant (BFT) 共識協議的結果獲勝。
\nxsubpoint\label{sp:sh.blk.cand.prop} \embt(Propagation of shardchain
block candidates.) 因為shardchain任務組的成員資格提前一小時就已知,它們的成員可以利用這段時間建立一個專用的「shard validator多播覆蓋網路」,使用TON Network的一般機制 (cf.~\ptref{sect:overlay})。當需要生成一個新的shardchain區塊時—通常在最近的masterchain區塊被傳播後的一兩秒鐘—每個人都知道誰有最高的優先權生成下一個區塊 (cf.~\ptref{sp:rot.gen.prio})。這個validator將創建一個新的整合的區塊候選者,無論是自己還是在整合者的幫助下 (cf.~\ptref{sp:collators})。validator必須檢查(驗證)此區塊候選者(尤其是如果它是由某個整合者準備的)並用其(validator)私鑰簽名。然後,使用預先安排的多播覆蓋網路將區塊候選者傳播到任務組的其餘部分 (該任務組根據\ptref{sect:overlay}中的解釋創建自己的私有覆蓋網路,然後使用\ptref{sp:streaming.multicast}中描述的串流多播協議的版本來傳播區塊候選者)。
真正的BFT方式是使用拜占庭多播協議,例如Honey Badger BFT中使用的協議~\cite{HoneyBadger}:通過一個$(N,2N/3)$-消除程式碼對區塊候選者進行編碼,將結果數據的$1/N$直接發送到組的每個成員,並期望他們將其數據的部分直接多播到組的所有其他成員。
然而,一個更快且更簡單的方法(參見\ptref{sp:streaming.multicast})是將區塊候選者分成一系列簽名的一千字節區塊(「chunks」),通過Reed--Solomon或泉程式碼(如RaptorQ code~\cite{RaptorQ} \cite{Raptor})擴充它們的序列,並開始傳輸chunks到「多播網格」(即覆蓋網路)中的鄰居,期望他們將這些chunks進一步傳播。一旦validator獲得足夠的chunks來從中重建區塊候選者,它就會簽署一個確認收據並通過其鄰居將其傳播到整個組。然後,它的鄰居停止向它發送新的chunks,但可能會繼續發送這些chunks的(原始)簽名,認為該節點可以通過應用Reed--Solomon或泉程式碼自行生成後續的chunks(擁有所有必要的數據),將它們與簽名組合起來,並傳播給還沒有準備好的鄰居。
如果在移除所有「壞」節點後「多播網格」(覆蓋網路)仍保持連接(回想一下,允許最多三分之一的節點以拜占庭方式壞掉,即以任意惡意方式行為),則此算法將以最快的方式傳播區塊候選者。
不僅指定的高優先級區塊創建者可以將其區塊候選者多播到整個組。第二和第三優先順序的validator可能會開始多播他們的區塊候選者,無論是立即還是在未能從最高優先級的validator那裡接收到區塊候選者之後。但是,通常只有最大優先權的區塊候選者將被所有(實際上,至少由三分之二的任務組)validator簽名並作為新的shardchain區塊提交。
\nxsubpoint \embt(Validation of block candidates.) 一旦 block candidate 被 validator 接收並檢查其起始 validator 的簽名,接收 validator 會檢查此 block candidate 的有效性,執行其中的所有交易並確保其結果與所聲稱的一致。從其他區塊鏈導入的所有消息都必須在 collated data 中有適當的 Merkle 證明,否則 block candidate 將被視為無效(並且,如果此證明被提交到 masterchain,則可能會懲罰已經簽署此 block candidate 的 validator)。另一方面,如果 block candidate 被認定為有效,接收 validator 會簽署它並將其簽名傳播給組中的其他 validator,可以通過「mesh multicast network」或直接的網路消息。
我們想強調,{\em validator 在檢查(collated)block candidate 的有效性時,不需要訪問此 shardchain 或相鄰 shardchain 的狀態}。\footnote{一個可能的例外是相鄰 shardchain 的輸出隊列的狀態,因為在這種情況下,Merkle 證明的大小可能會變得過大。} 這使得驗證可以非常快速地進行(不需要硬碟訪問),並減輕了 validator 的計算和儲存負擔(尤其是如果他們願意接受外部 collators 的幫助來創建 block candidate)。
\nxsubpoint\label{sp:new.shardc.blk} \embt(Election of the next block candidate.) 一旦 block candidate 收集到 task group 中至少三分之二(按 stake)的 validator 的有效簽名,它就有資格被提交為下一個 shardchain block。運行一個 BFT 協議來達成對所選 block candidate 的共識(可能有多個提議),所有「好的」validator 都會優先選擇該輪中優先級最高的 block candidate。運行此協議的結果是,該 block 會被至少三分之二的 validator(按 stake)的簽名所增強。這些簽名不僅證明了所問 block 的有效性,還證明了它是由 BFT 協議選出的。之後,將 block(無 collated data)與這些簽名組合,以確定的方式序列化,然後通過網路傳播給所有相關方。
\nxsubpoint \embt(validators must keep the blocks they have signed.) 在他們成為 task group 的成員期間,以及之後至少一小時(或者 $2^{10}$ blocks),validator 預期會保留他們已簽署和提交的 block。如果未能向其他 validator 提供簽署的 block,可能會受到懲罰。
\nxsubpoint \embt(Propagating the headers and signatures of new shardchain blocks to all validators.) validator 將新生成的 shardchain block 的 headers 和簽名傳播到全域 set of validators,使用類似於為每個 task group 創建的 multicast mesh network。
\nxsubpoint\label{sp:new.master.blk} \embt(Generation of new masterchain blocks.) 在所有(或幾乎所有)新的 shardchain block 生成之後,可以生成一個新的 masterchain block。這個程序基本上與 shardchain block 相同(參見~\ptref{sp:new.shardc.blk}),不同之處在於所有 validator(或至少三分之二的 validator)都必須參與此過程。因為新的 shardchain block 的 headers 和簽名被傳播給所有的 validator,所以每個 shardchain 中最新的 block 的 hash 可以並且必須被包含在新的 masterchain block 中。一旦這些 hash 被提交到 masterchain block,外部觀察者和其他 shardchain 可以認為新的 shardchain block 已經提交並且是不可變的(參見~\ptref{sp:sc.hash.mc})。
\nxsubpoint \embt(validators must keep the state of masterchain.)
所有的validator都預期要追踪 masterchain 的狀態,而不依賴於彙整的數據。這很重要,因為validator工作組的知識是從 masterchain 的狀態中衍生出來的。
\nxsubpoint \embt(Shardchain blocks are generated and propagated in parallel.)
通常,每個validator都是幾個 shardchain 任務組的成員;他們的數量(因此validator的負載)大約與validator的股份成正比。這意味著validator同時運行多個新的 shardchain 區塊生成協議。
\nxsubpoint \embt(Mitigation of block retention attacks.)
因為所有validator在只看到其標頭和簽名後就將一個新的 shardchain 區塊的 hash 插入到 masterchain 中,因此存在一個小概率,即生成此區塊的validator會密謀並試圖避免發佈整個新區塊。這將導致鄰近 shardchains 的validator無法創建新的區塊,因為一旦它的 hash 被提交到 masterchain 中,他們必須至少知道新區塊的輸出消息隊列。
為了緩解這種情況,新區塊必須從其他一些validator(例如,鄰近 shardchains 的任務組聯合的三分之二)收集簽名,證明這些validator確實擁有此區塊的副本並且願意在需要時將它們發送給其他validator。只有在提供這些簽名之後,新區塊的 hash 才可能包含在 masterchain 中。
\nxsubpoint \embt(Masterchain blocks are generated later than shardchain blocks.)
Masterchain 區塊大約每五秒生成一次,就像 shardchain 區塊一樣。但是,雖然所有 shardchains 中的新區塊的生成基本上是同時進行的(通常由釋放新的 masterchain 區塊觸發),但新的 masterchain 區塊的生成被故意延遲,以允許在 masterchain 中包含新生成的 shardchain 區塊的 hashes。
\nxsubpoint\label{sp:slow.valid} \embt(Slow validators may receive lower rewards.)
如果一個validator“慢”,它可能無法驗證新的區塊候選者,並且收集提交新區塊所需的三分之二的簽名可能不需要它的參與。在這種情況下,它將收到與此區塊相關的較低份額的獎勵。
這為validator提供了一個激勵,以優化他們的硬體、軟體和網路連接,以便盡可能快地處理用戶交易。
但是,如果validator在區塊提交之前未簽名,則其簽名可能包含在接下來的一個或多個區塊中,然後這部分獎勵(根據已生成多少區塊而呈指數下降---例如,如果validator延遲$k$區塊則為$0.9^k$)仍將給予此validator。
\nxsubpoint\label{sp:val.sign.depth} \embt(``Depth'' of validator signatures.)
通常,當validator簽署一個區塊時,該簽名只證明了區塊的{\em 相對有效性\/}:只要這個和其他 shardchains 的所有先前區塊都是有效的,這個區塊就是有效的。validator不能因為將先前區塊中提交的無效數據視為理所當然而受到懲罰。
然而,區塊的validator簽名有一個稱為“深度”的整數參數。如果它是非零的,那就意味著validator也宣稱先前指定數量的區塊的(相對)有效性。這是“慢”或“暫時離線”的validator趕上並簽署一些已經提交但未經他們簽名的區塊的方式。然後區塊獎勵的一部分仍將給予他們(參見~\ptref{sp:slow.valid})。
\nxsubpoint\label{sp:abs.val.from.rel} \embt(validators are responsible for {\em relative\/} validity of signed shardchain blocks; absolute validity follows.)
我們想再次強調,validator在 shardchain 區塊 \(B\) 上的簽名只證明了該區塊的{\em 相對\/}有效性(或者如果簽名有“深度” \(d\),也可能是 \(d\) 個先前的區塊的相對有效性,參見~\ptref{sp:val.sign.depth};但這不太影響下面的討論)。換句話說,validator聲稱 shardchain 的下一個狀態 \(s'\) 是通過應用在~\ptref{sp:blk.transf}中描述的區塊評估函數 \(\evblock\) 從先前的狀態 \(s\) 獲得的:
\begin{equation}\label{eq:ev.block.2}
s'=\evblock(B)(s)
\end{equation}
這樣,如果原始狀態 \(s\) 被證明為“不正確”(例如,由於先前區塊的無效性),那麼簽署了區塊 \(B\) 的validator不能被懲罰。fisherman(參見~\ptref{sp:fish})只有在發現一個區塊是{\em 相對地\/}無效時才會抱怨。PoS 系統作為一個整體努力使每個區塊都是{\em 相對地\/}有效的,而不是{\em 遞迴地(或絕對地)}有效的。然而,注意到,{\em 如果 blockchain 中的所有區塊都是相對有效的,那麼它們所有的和 blockchain 作為一個整體都是絕對有效的};使用對 blockchain 的長度的數學歸納法可以輕易地證明這一語句。通過這種方式,輕鬆可驗證的區塊的{\em 相對\/}有效性的聲明一起證明了整個 blockchain 的更強大的{\em 絕對有效性\/}。
注意,通過簽署一個區塊~\(B\),validator聲稱該區塊給定原始狀態 \(s\) 是有效的(即,~\eqref{eq:ev.block.2}的結果不是值 \(\bot\),表示下一個狀態不能被計算)。因此,validator必須執行在評估~\eqref{eq:ev.block.2}期間訪問的原始狀態的 cell 的最小形式檢查。
例如,想像一個情境,期望從提交到區塊的交易中訪問的賬戶的原始餘額的 cell 被發現有零個原始字節,而不是期望的 8 或 16。然後,原始餘額簡單地不能從 cell 中檢索,並且在嘗試處理該區塊時會發生“未處理的異常”。在這種情況下,validator不應該簽署這樣的區塊,否則將受到懲罰。
\nxsubpoint \embt(Signing masterchain blocks.)
與masterchain區塊的情況略有不同:簽署一個masterchain區塊,validator不僅聲明其相對有效性,而且還聲明所有先前區塊的相對有效性,直到這個validator承擔其責任的第一個區塊(但不再往回)。
\nxsubpoint \embt(The total number of validators.)
validator被選舉的總數的上限 \(T\) (參見~\ptref{sp:global.valid})在迄今為止描述的系統中,不能超過,例如,幾百或一千,因為所有validator都預計參與BFT共識協議來創建每個新的masterchain區塊,並且尚不清楚這樣的協議是否可以擴展到數千參與者。更重要的是,masterchain區塊必須收集至少三分之二的所有validator(按權益)的簽名,並且這些簽名必須包含在新區塊中(否則系統中的所有其他節點都沒有理由信任新區塊而不自己驗證它)。如果必須在每個masterchain區塊中包括超過,例如,一千個validator簽名,這將意味著每個masterchain區塊中有更多的數據,所有完整節點都要儲存並通過網路傳播,以及花費更多的處理能力來檢查這些簽名(在PoS系統中,完整節點不需要自己驗證區塊,但他們需要相反地檢查validator的簽名)。
雖然將 \(T\) 限制為一千個validator對於TON Blockchain的部署的第一階段似乎足夠了,但必須為未來的增長提供條款,當shardchains的總數變得如此之大,以至於幾百個validator不足以處理所有的shardchains。為此,我們引入了一個額外的可配置參數 \(T'\leq T\)(原本等於~\(T\)),並且只有前 \(T'\) 名被選舉的validator(按權益)預計創建和簽署新的masterchain區塊。
\nxsubpoint \embt(Decentralization of the system.)
有人可能會懷疑,像TON Blockchain這樣的Proof-of-Stake系統,依賴\(T\approx1000\)的validator來創建所有shardchain和masterchain區塊,是否會變得“太集中”,與像Bitcoin或Ethereum這樣的傳統Proof-of-Work區塊鏈相反,其中每個人(原則上)都可能開採一個新區塊,沒有礦工總數的明確上限。
但是,像Bitcoin和Ethereum這樣的受歡迎的Proof-of-Work區塊鏈,目前需要大量的計算能力(高“hash rates”)以成功的概率開採新區塊。因此,新區塊的開採趨於集中在幾個大玩家手中,他們投資大量資金建立充滿為開採優化的定制硬體的數據中心;以及幾個大型的開採池手中,它們集中並協調了無法自己提供足夠“hash rate”的大量人的努力。
因此,到2017年,超過75%的新Ethereum或Bitcoin區塊由少於十個礦工產生。實際上,兩個最大的Ethereum開採池共同生產了超過一半的所有新區塊!顯然,這樣的系統比依賴\(T\approx1000\)節點生產新區塊的系統更為集中。
人們還可能注意到,成為TON Blockchainvalidator所需的投資——即購買硬體(例如,幾個高性能伺服器)和權益(如有必要,可以通過 nominator pool 輕鬆收集;參見~\ptref{sp:nominators})——比成為成功的獨立Bitcoin或Ethereum礦工所需的要少。實際上,~\ptref{sp:global.valid}的參數\(L\)將迫使 nominator 不加入最大的“開採池”(即,積累了最大權益的validator),而是尋找目前正在接受 nominator 資金的較小的validator,甚至創建新的validator,因為這將允許更高比例的validator的——並且也是 nominator 的——權益被使用,從而獲得更大的開採獎勵。這種方式,TON Proof-of-Stake系統實際上{\em 鼓勵\/}去中心化(創建和使用更多的validator)並{\em 懲罰\/}集中化。
\nxsubpoint\label{sp:rel.rel} \embt(Relative reliability of a block.)
區塊的{\em (相對) 可靠性\/}簡單地說是已簽署此區塊的所有validator的總權益。換句話說,如果這個區塊被證明是無效的,某些行為者會失去的金額。如果有人關心的交易傳輸值低於區塊的可靠性,可以認為它們足夠安全。從這個意義上說,相對可靠性是外部觀察者可以對特定區塊的信任度的衡量。
注意,我們談論的是區塊的{\em 相對\/}可靠性,因為它保證該區塊是有效的{\em 前提是前一個區塊和所有其他被參考的shardchains'區塊都是有效的\/}(參見~\ptref{sp:abs.val.from.rel})。
一個區塊的相對可靠性在提交後可能會增加——例如,當遲來的validator的簽名被添加時(參見~\ptref{sp:val.sign.depth})。另一方面,如果其中一個validator因與其他區塊相關的不當行為而失去部分或全部權益,區塊的相對可靠性可能{\em 減少}。
\nxsubpoint \embt("Strengthening" the blockchain.) 提供驅使validator提高區塊相對可靠性的激勵是很重要的。這樣做的一種方法是為validator分配小量的獎勵,以在其他shardchains的區塊上添加簽名。即使是“即將成為”的validator,他們已存入的股份不足以進入按股份排名前$T$的validator,並被包括在全域validator集合中(參見~\ptref{sp:global.valid}),也可能參與這項活動(如果他們同意在失去選舉後保持其股份凍結,而不是撤回)。這樣的validator可能同時充當fisherman(參見~\ptref{sp:fish}):如果他們必須檢查某些區塊的有效性,他們也可以選擇報告無效的區塊並收集相關獎勵。
\nxsubpoint\label{sp:rec.rel} \embt(Recursive reliability of a block.) 人們也可以定義一個區塊的{\em recursive reliability\/},這是其相對可靠性與其引用的所有區塊的遞歸可靠性之間的最小值(即,masterchain區塊、先前的shardchain區塊和一些相鄰shardchains的區塊)。換句話說,如果該區塊被證明是無效的,無論是因為它本身無效還是因為它所依賴的某個區塊無效,至少有人會失去這筆錢。如果人們真的不確定是否信任區塊中的特定交易,人們應該計算這個區塊的{\em recursive\/}可靠性,而不僅僅是{\em relative\/}的可靠性。
當計算遞歸可靠性時,沒有必要回溯太遠,因為如果我們回溯太遠,我們會看到已經解凍並提取的validator簽名的區塊。無論如何,我們不允許validator自動重新考慮那些舊的區塊(即,創建超過兩個月的區塊,如果使用當前的可配置參數的值),並從中創建分叉或使用“垂直blockchains”(參見~\ptref{sp:inv.sh.blk.corr})修正它們,即使它們被證明是無效的。我們假設兩個月的時期提供了充足的機會來檢測和報告任何無效的區塊,因此如果在這段時期內沒有挑戰某個區塊,那麼它不太可能受到挑戰。
\nxsubpoint \embt(Consequence of Proof-of-Stake for light nodes.) TON Blockchain 採用的 Proof-of-Stake 方法的一個重要結果是,TON Blockchain 的輕型節點(運行輕型客戶端軟體)不需要下載所有 shardchain 或甚至 masterchain 區塊的「標頭」,以便能夠自行檢查完整節點提供給其的 Merkle 證明,作為對其查詢的回答。
實際上,由於最近的 shardchain 區塊 hash 已包含在 masterchain 區塊中,完整節點可以輕鬆提供一個 Merkle 證明,從已知的 masterchain 區塊的 hash 開始,說明給定的 shardchain 區塊是有效的。接下來,輕型節點只需要知道 masterchain 的第一個區塊(其中宣布了第一組validator),這個區塊(或至少其 hash)可能被內置到客戶端軟體中,並且每個月後只需一個 masterchain 區塊,其中宣布了新當選的validator集合,因為這個區塊將由上一組validator簽署。從那時起,它可以獲得最近的幾個 masterchain 區塊,或至少他們的標頭和validator簽名,並使用它們作為檢查完整節點提供的 Merkle 證明的基礎。
\mysubsection{分割和合併 Shardchains}\label{sect:split.merge}
TON Blockchain 最具特色和獨特的功能之一是,當負載過高時,它能夠自動將 shardchain 分割為兩部分,並在負載下降時將它們合併回來(參見~\ptref{sp:dyn.split.merge})。由於其獨特性和對整個專案可擴展性的重要性,我們必須詳細討論它。
\nxsubpoint \embt(Shard configuration.) 請回憶,在任何給定的時間點,每個工作鏈 $w$ 都被分割成一個或多個 shardchains $(w,s)$ (參見~\ptref{sp:shard.ident})。這些 shardchains 可以由一棵二進制樹的葉子表示,其根為 $(w,\emptyset)$,且每個非葉子節點 $(w,s)$ 都有子節點 $(w,s.0)$ 和 $(w,s.1)$。這樣,屬於工作鏈 $w$ 的每個賬戶都被分配到確切的一個 shard,而知道當前的 shardchain 配置的每個人都可以確定包含賬戶 $\accountid$ 的 shard $(w,s)$:它是二進制字符串 $s$ 是 $\accountid$ 前綴的唯一 shard。
shard 配置—即,這個 {\em shard binary tree},或給定 $w$ 的所有活躍 $(w,s)$ 的集合(對應於 shard binary tree 的葉子)—是 masterchain 狀態的一部分,且對於跟踪 masterchain 的每個人都可用。\footnote{實際上,shard 配置完全由最後的 masterchain 區塊確定;這簡化了獲取 shard 配置的訪問。}
\nxsubpoint \embt(Most recent shard configuration and state.) 回想一下,最近的 shardchain 區塊的 hashes 被包含在每個 masterchain 區塊中。這些 hashes 被組織成一個 shard binary tree(實際上,是每個 workchain 的一系列樹)。這樣,每個 masterchain 區塊都包含最近的 shard 配置。
\nxsubpoint \embt(Announcing and performing changes in the shard configuration.) shard 配置可以通過兩種方式更改:要麼將 shard $(w,s)$ {\em split\/} 為兩個 shards $(w,s.0)$ 和 $(w,s.1)$,要麼將兩個「sibling」shards $(w,s.0)$ 和 $(w,s.1)$ {\em merged\/} 為一個 shard $(w,s)$。
這些 split/merge 操作在事先(例如,$2^6$;這是一個可配置的參數)的區塊中被宣布,首先在相應的 shardchain 區塊的「標頭」中,然後在引用這些 shardchain 區塊的 masterchain 區塊中。這個提前公告是為了讓所有相關方為計劃的變更做好準備(例如,建立一個 overlay multicast network 來分發新創建的 shardchains 的新區塊,如~\ptref{sect:overlay}所述)。然後,更改首先提交到 shardchain 區塊的(標頭),然後傳播到 masterchain 區塊。這樣,masterchain 區塊不僅定義了在其創建之前的最新 shard 配置,而且還定義了下一個立即的 shard 配置。
\nxsubpoint \embt(validator task groups for new shardchains.) 回憶一下,每個 shard,即每個 shardchain,通常都被分配一個validator的子集(一個 validator task group)專用於在相應的 shardchain 中創建和驗證新區塊(參見~\ptref{sp:val.task.grp})。這些 task groups 被選為某段時間(大約一小時),並且在提前知道的時間(也大約是一小時),在此期間是不變的。\footnote{除非某些validator因簽署無效的區塊而被臨時或永久禁止,那麼他們將自動從所有 task groups 中被排除。}
但是,實際的 shard 配置可能會在此期間因為 split/merge 操作而發生變化。必須為新創建的 shards 分配 task groups。這是如此完成的:
注意,任何活躍的 shard $(w,s)$ 要麼是某個唯一確定的原始 shard $(w,s')$ 的後代,意味著 $s'$ 是 $s$ 的前綴,要麼它將是原始 shards $(w,s')$ 的子樹的根,其中 $s$ 將是每個 $s'$ 的前綴。在第一種情況下,我們簡單地將原始 shard $(w,s')$ 的 task group 作為新 shard $(w,s)$ 的 task group。在後一種情況下,新 shard $(w,s)$ 的 task group 將是所有原始 shards $(w,s')$ 的 task groups 的聯集,這些 shards 是 shard tree 中的 $(w,s)$ 的後代。
這樣,每個活躍的 shard $(w,s)$ 都被分配了一個明確定義的validator子集(task group)。當一個 shard 被分割時,兩個子節點都繼承了原始 shard 的整個 task group。當兩個 shards 被合併時,它們的 task groups 也被合併。
任何追踪 masterchain 狀態的人都可以計算每個活躍 shard 的validator task groups。
\nxsubpoint \embt(Limit on split/merge operations during the period of
responsibility of original task groups.) 最終,新的 shard 配置將被考慮到,並且新的專用validator子集(task groups)將自動分配給每個 shard。在此之前,必須對 split/merge 操作施加某種限制;否則,如果原始 shard 迅速分裂成 $2^k$ 個新的 shards,則原始 task group 可能最終同時驗證 $2^k$ shardchains,對於大的 $k$。
這是通過對 active shard 配置與原始 shard 配置(目前用於選擇 validator task groups 的配置)之間的距離施加限制來實現的。例如,可能要求從 active shard $(w,s)$ 到原始 shard $(w,s')$ 在 shard tree 中的距離,如果 $s'$ 是 $s$ 的前驅(即 $s'$ 是 binary string $s$ 的前綴),則不得超過3,如果 $s'$ 是 $s$ 的後繼(即 $s$ 是 $s'$ 的前綴),則不得超過2。否則,不允許進行 split 或 merge 操作。
大致上,對於給定的 validator task groups 集合的責任期間,一個 shard 可以被分裂(例如,三次)或合併(例如,兩次)的次數施加了限制。除此之外,合併或分裂創建 shard 之後,某段時間(某些區塊數)內不能重新配置它。
\nxsubpoint\label{sp:split.necess} \embt(Determining the necessity of
split operations.) shardchain 的 split 操作是由某些正式條件觸發的(例如,如果連續64個區塊的 shardchain 區塊至少有 $90\%$ 是滿的)。這些條件由 shardchain task group 監控。如果它們得到滿足,首先在新的 shardchain 區塊的標頭中包含一個「split 準備」標誌(並傳播到引用這個 shardchain 區塊的 masterchain 區塊)。然後,在幾個區塊之後,shardchain 區塊的標頭中包含「split 提交」標誌(並傳播到下一個 masterchain 區塊)。
\nxsubpoint \embt(Performing split operations.) 在 shardchain $(w,s)$ 的區塊 $B$ 中包含「split commit」標誌後,該 shardchain 中不能有後續的區塊 $B'$。相反,將創建 shardchains $(w,s.0)$ 和 $(w,s.1)$ 的兩個區塊 $B'_0$ 和 $B'_1$,分別參考區塊 $B$ 作為它們的前一個區塊(並且它們都將通過標頭中的標誌指示 shard 剛剛被分裂)。下一個 masterchain 區塊將包含新 shardchains 的區塊 $B'_0$ 和 $B'_1$ 的 hashes;它不允許包含 shardchain $(w,s)$ 的新區塊 $B'$ 的 hash,因為「split commit」事件已經被提交到前一個 masterchain 區塊。
請注意,兩個新的 shardchains 將由與舊的 shardchain 相同的 validator task group 驗證,所以它們將自動擁有其狀態的副本。從 Infinite Sharding Paradigm 的角度來看,狀態分裂操作本身相對簡單(參見~\ptref{sp:split.merge.state})。
\nxsubpoint\label{sp:merge.necess} \embt(Determining the necessity of
merge operations.) 合併 shard 操作的必要性也由某些正式條件檢測 (例如,如果連續64個區塊的兩個兄弟 shardchains 的區塊大小總和不超過最大區塊大小的 $60\%$)。這些正式條件還應考慮這些區塊所消耗的總 gas,並將其與當前的區塊 gas 限制進行比較,否則由於有一些計算密集型的交易阻止了更多交易的納入,區塊可能會偶然變小。
這些條件由兩個兄弟 shards $(w,s.0)$ 和 $(w,s.1)$ 的 validator task groups 監控。請注意,兄弟節點在 hypercube 路由方面必然是鄰居 (參考~\ptref{sp:hypercube}),因此任何 shard 的 task group 的 validators 都將在某種程度上監控兄弟 shard。
當滿足這些條件時,validator 子組之一可以通過發送特殊消息建議另一個合併。然後,它們組合成一個臨時的「合併任務組」,具有組合的成員資格,能夠運行 BFT 共識算法,並在必要時傳播區塊更新和區塊候選者。
如果他們就合併的必要性和準備情況達成共識,「merge prepare」標誌將提交到每個 shardchain 的一些區塊的頭部,並附帶至少三分之二的兄弟 task group 的 validators 的簽名(並被傳播到下一個 masterchain 區塊,以便每個人都可以為即將到來的重新配置做好準備)。但是,他們繼續為一些預定義數量的區塊創建單獨的 shardchain 區塊。
\nxsubpoint \embt(Performing merge operations.) 之後,當來自兩個原始 task groups 的聯合的 validators 準備成為已合併 shardchain 的 validators 時 (這可能涉及從兄弟 shardchain 的狀態轉移和一個狀態合併操作),他們在其 shardchain 的區塊的頭部提交一個「merge commit」標誌 (這一事件傳播到下一個 masterchain 區塊),並停止在單獨的 shardchains 中創建新的區塊 (一旦出現 merge commit 標誌,在單獨的 shardchains 中創建區塊是被禁止的)。相反,創建了一個已合併的 shardchain 區塊 (由兩個原始 task groups 的聯合創建),在其「header」中參考它的兩個「preceding blocks」。這反映在下一個 masterchain 區塊中,該區塊將包含已合併 shardchain 的新創建區塊的 hash。之後,已合併的 task group 繼續在已合併的 shardchain 中創建區塊。
\mysubsection{區塊鏈專案的分類}\label{sect:class.blkch}
我們將通過將 TON 區塊鏈與現有和擬議的區塊鏈專案進行比較,來結束我們對 TON 區塊鏈的簡短討論。但在此之前,我們必須引入一個足夠通用的區塊鏈專案分類。基於此分類的特定區塊鏈專案的比較,將被推遲到~\ptref{sect:compare.blkch}。
\nxsubpoint \embt(Classification of blockchain projects.) 作為第一步,我們建議一些用於區塊鏈(即,對於區塊鏈專案)的分類標準。任何這種分類都是有點不完整和表面的,因為它必須忽略正在考慮的專案的一些最具體和獨特的特點。然而,我們認為這是在提供至少一個非常粗略和大約的區塊鏈專案地圖的必要第一步。
我們考慮的標準列表如下:
\begin{itemize}
\item 單一區塊鏈與多區塊鏈架構 (參見~\ptref{sp:single.multi})
\item 共識算法:Proof-of-Stake 與 Proof-of-Work (參見~\ptref{sp:pow.pos})
\item 對於 Proof-of-Stake 系統,使用的確切的區塊生成、驗證和共識算法(兩個主要選項是 DPOS 與 BFT; 參見~\ptref{sp:dpos.bft})
\item 對「任意的」(Turing-complete) 智能合約的支持 (參見~\ptref{sp:smartc.supp})
\end{itemize}
多區塊鏈系統有額外的分類標準 (參見~\ptref{sp:class.multichain}):
\begin{itemize}
\item 成員區塊鏈的類型和規則:同質的、異質的 (參見~\ptref{sp:blkch.hom.het}),混合的 (參見~\ptref{sp:mixed.het.hom})。聯邦 (參見~\ptref{sp:het.confed})
\item 有無{\em 主鏈},內部或外部 (參見~\ptref{sp:pres.masterch})
\item 對 sharding 的原生支持 (參見~\ptref{sp:shard.supp})。靜態或動態 sharding (參見~\ptref{sp:dyn.stat.shard})
\item 成員區塊鏈之間的互動:鬆散聯接和緊密聯接的系統 (參見~\ptref{sp:blkch.interact})
\end{itemize}
\nxsubpoint\label{sp:single.multi} \embt(Single-blockchain vs.\ multi-blockchain projects.) 第一個分類標準是系統中的區塊鏈數量。最古老和最簡單的專案由一個{\em 單一區塊鏈}組成(簡稱「單鏈專案」);更複雜的專案使用(或更確切地說,計劃使用){\em 多個區塊鏈}(「多鏈專案」)。
單鏈專案通常更簡單且經過更好的測試;它們經受住了時間的考驗。它們的主要缺點是低性能,或者至少是交易吞吐量,對於通用系統來說,這一數量在十 (Bitcoin) 到不到一百 (Ethereum) 的交易每秒。一些專用系統(如 Bitshares)能夠在區塊鏈狀態適合於記憶體的情況下,處理每秒數萬的專用交易,並將處理限制於一個預定義的特殊交易集,然後由像 C++ 這樣的語言編寫的高度優化的程式碼執行(這裡沒有 VMs)。
多鏈專案提供了每個人都渴望的可擴展性。他們可能支持更大的總狀態和更多的每秒交易,但代價是使專案變得更為複雜,其實施更具挑戰性。因此,已經運行的多鏈專案很少,但大多數擬議的專案都是多鏈的。我們相信未來屬於多鏈專案。
\nxsubpoint\label{sp:pow.pos} \embt(創建和驗證區塊: 工作量證明 vs. 權益證明.) 另一個重要的區別是用於創建和傳播新區塊、檢查其有效性,以及在出現多個分支時選擇其中之一的算法和協議。
兩種最常見的範疇是 {\em Proof-of-Work (PoW)} 和 {\em Proof-of-Stake (PoS)}。工作量證明方法通常允許任何節點創建(“挖掘”)一個新區塊(並獲得與挖掘區塊相關的一些獎勵),前提是它有幸在其他競爭者成功之前解決一個否則無用的計算問題(通常涉及計算大量的hashes)。在出現分支的情況下(例如,如果兩個節點發布兩個否則有效但不同的區塊來跟隨前一個),最長的分支勝出。這樣,區塊鏈的不變性保證是基於生成區塊鏈所花費的{\em 工作量}(計算資源):任何希望創建此區塊鏈的分支的人都需要重新做這些工作,以創建已提交區塊的替代版本。為此,一個人需要控制超過$50\%$的創建新區塊所花費的總計算能力,否則替代分支變得最長的機會會指數性地降低。
權益證明方法基於一些特殊節點({\em validator})所做的大量{\em stake }(以加密貨幣提名),以斷言它們已經檢查了一些區塊並發現它們是正確的。validator簽署區塊,並因此收到一些小獎勵;但是,如果一個validator被發現簽署了一個不正確的區塊,並且提供了這方面的證據,則其全部或部分 stake 將被沒收。這樣,區塊鏈的有效性和不變性保證是由validator對區塊鏈有效性的總 stake 給出的。
從這個角度看,權益證明更為自然,因為它激勵validator(它們取代了PoW礦工)執行有用的計算(需要檢查或創建新區塊,尤其是執行區塊中列出的所有交易),而不是計算其他無用的hashes。這樣,validator會購買更適合處理用戶交易的硬件,以獲得與這些交易相關的獎勵,從整個系統的角度看,這似乎是一項相當有用的投資。
然而,權益證明系統在實施上有些挑戰,因為必須為許多罕見但可能的情況提供支援。例如,一些惡意的validator可能密謀破壞系統以獲取利益(例如,通過改變自己的加密貨幣餘額)。這導致了一些非常重要的博弈論問題。
簡而言之,權益證明更為自然且更有前景,尤其是對於多區塊鏈專案(因為如果有許多區塊鏈,工作量證明將需要過多的計算資源),但必須更加小心地考慮和實施。大多數目前運行的區塊鏈專案,尤其是最古老的專案(如Bitcoin和至少是原始的Ethereum),使用工作量證明。