-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathtw_ton.tex.bak
More file actions
1821 lines (1126 loc) · 282 KB
/
Copy pathtw_ton.tex.bak
File metadata and controls
1821 lines (1126 loc) · 282 KB
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[T1]{fontenc} % XeLaTeX 不相容,已註解
%\usepackage{euler}
\usepackage{amssymb, amsmath, amsfonts, stmaryrd}
\usepackage[mathscr]{euscript}
\usepackage{mathrsfs}
\usepackage{theorem}
%\usepackage[english]{babel} % XeLaTeX 不相容,已註解
\usepackage{bm}
\usepackage[all]{xy}
%\usepackage{chngcntr}
%\CompileMatrices
\usepackage[bookmarks=false,pdfauthor={Nikolai Durov},pdftitle={Telegram 開放網路}]{hyperref}
\usepackage{fancyhdr}
\usepackage{caption}
% XeLaTeX 中文支援
\usepackage{xeCJK}
\setCJKmainfont{Noto Serif CJK TC}
%
\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{第 \textbf{\thesection} 章\ #1}}}
\def\mysubsection#1{\subsection{#1}\fancyhead[C]{\small{\textsc{\textrm{\thesubsection.} #1}}}}
\def\myappendix#1{\section{#1}\fancyhead[C]{\textsc{附錄 \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{Telegram 開放網路}
\author{Dr.\ Nikolai Durov}% a.k.a. K.O.T.
\begin{document}
%\pagestyle{myheadings}
\maketitle
\begin{abstract}
本文旨在提供 Telegram 開放網路(TON)及相關區塊鏈、點對點、分散式儲存和服務託管技術的首次描述。為了將本文件的篇幅控制在合理範圍內,我們主要關注 TON 平台的獨特和決定性功能,這些功能對於實現其既定目標至關重要。
\end{abstract}
\section*{簡介}
\markbothsame{簡介}
{\em Telegram 開放網路(TON)}是一個快速、安全且可擴展的區塊鏈和網路專案,如有必要,能夠每秒處理數百萬筆交易,同時對使用者和服務提供者都友善。我們的目標是使其能夠託管目前提出和構思的所有合理應用程式。人們可以將 TON 想像成一個巨大的分散式超級電腦,或者更確切地說,是一個巨大的「超級伺服器」,旨在託管並提供各種服務。
本文並非旨在成為所有實作細節的終極參考。某些細節可能會在開發和測試階段發生變化。
\clearpage
\tableofcontents
\clearpage
\mysection{TON 組件簡述}\label{sect:ton.components}
{\em Telegram 開放網路(TON)}是以下組件的組合:
\begin{itemize}
\item 一個靈活的多區塊鏈平台({\em TON 區塊鏈};參見第~\ptref{sect:blockchain}~章),能夠每秒處理數百萬筆交易,具有圖靈完備的智慧合約、可升級的正式區塊鏈規範、多加密貨幣價值轉移、支援微支付通道和鏈下支付網路。{\em TON 區塊鏈}呈現了一些新穎且獨特的功能,例如「自我修復」垂直區塊鏈機制(參見~\ptref{sp:inv.sh.blk.corr})和即時超立方體路由(參見~\ptref{sp:instant.hypercube}),使其能夠同時具有快速、可靠、可擴展和自洽的特性。
\item 一個點對點網路({\em TON P2P 網路},或簡稱 {\em TON 網路};參見第~\ptref{sect:network}~章),用於存取 TON 區塊鏈、傳送交易候選,以及接收有關客戶端感興趣的區塊鏈部分的更新(例如,與客戶端帳戶和智慧合約相關的部分),但也能夠支援任意的分散式服務,無論是否與區塊鏈相關。
\item 一種分散式檔案儲存技術({\em TON 儲存};參見~\ptref{sp:ex.ton.storage}),可透過 {\em TON 網路}存取,由 TON 區塊鏈用於儲存區塊和狀態資料(快照)的存檔副本,但也可用於為使用者或平台上執行的其他服務儲存任意檔案,具有類似 torrent 的存取技術。
\item 一個網路代理/匿名化層({\em TON 代理};參見~\ptref{sp:ex.ton.proxy} 和~\ptref{sp:tunnels}),類似於 $I^2P$(隱形網際網路專案),在必要時用於隱藏 {\em TON 網路}節點的身分和 IP 位址(例如,從擁有大量加密貨幣的帳戶提交交易的節點,或希望隱藏其確切 IP 位址和地理位置以防範 DDoS 攻擊的高風險區塊鏈驗證者節點)。
\item 一個類似 Kademlia 的分散式雜湊表({\em TON DHT};參見~\ptref{sect:kademlia}),用作 {\em TON 儲存}的「torrent 追蹤器」(參見~\ptref{sp:distr.torr.tr})、{\em TON 代理}的「輸入通道定位器」(參見~\ptref{sp:loc.abs.addr})以及 {\em TON 服務}的服務定位器(參見~\ptref{sp:loc.serv})。
\item 一個用於任意服務的平台({\em TON 服務};參見第~\ptref{sect:services}~章),駐留於 {\em TON 網路}和 {\em TON 代理}中並可透過它們存取,具有正式化的介面(參見~\ptref{sp:pub.int.smartc}),使瀏覽器或智慧型手機應用程式能夠進行互動。這些正式介面和持久服務入口點可以發佈在 TON 區塊鏈中(參見~\ptref{sp:ui.ton.dns});在任何給定時刻提供服務的實際節點可以透過 {\em TON DHT} 查找,從 TON 區塊鏈中發佈的資訊開始(參見~\ptref{sp:loc.serv})。服務可以在 TON 區塊鏈中建立智慧合約,以向其客戶提供某些保證(參見~\ptref{sp:mixed.serv})。
\item {\em TON DNS}(參見~\ptref{sp:ton.dns}),一種為帳戶、智慧合約、服務和網路節點分配人類可讀名稱的服務。
\item {\em TON 支付}(參見第~\ptref{sect:payments}~章),一個用於微支付、微支付通道和微支付通道網路的平台。它可用於快速的鏈下價值轉移,以及為 {\em TON 服務}提供的服務付費。
\item TON 將允許輕鬆整合第三方訊息傳遞和社交網路應用程式,從而使區塊鏈技術和分散式服務最終對普通使用者可用且易於存取(參見~\ptref{sp:ton.www}),而不僅僅是少數早期加密貨幣採用者。我們將在我們的另一個專案 Telegram Messenger(參見~\ptref{sp:telegram.integr})中提供此類整合的範例。
\end{itemize}
雖然 TON 區塊鏈是 TON 專案的核心,而其他組件可能被認為是為區塊鏈扮演支援角色,但它們本身具有有用且有趣的功能。結合起來,它們使平台能夠託管比僅使用 TON 區塊鏈更多樣化的應用程式(參見~\ptref{sp:blockchain.facebook} 和~\ptref{sect:ton.service.impl})。
\clearpage
\mysection{TON 區塊鏈}\label{sect:blockchain}
我們從描述 Telegram 開放網路(TON)區塊鏈開始,這是該專案的核心組件。我們這裡的方法是「自上而下」的:我們首先對整體進行概述,然後提供每個組件的更多細節。
為了簡單起見,我們在這裡談論{\em 該\/} TON 區塊鏈,儘管原則上該區塊鏈協議的幾個實例可能獨立執行(例如,由於硬分叉的結果)。我們只考慮其中之一。
\mysubsection{TON 區塊鏈作為 2-區塊鏈的集合}
TON 區塊鏈實際上是一個區塊鏈的{\em 集合}(甚至是一個{\em 區塊鏈的區塊鏈},或 {\em 2-區塊鏈}的集合——這一點將在稍後的~\ptref{sp:inv.sh.blk.corr} 中澄清),因為沒有單一的區塊鏈專案能夠實現我們每秒處理數百萬筆交易的目標,而不是目前標準的每秒數十筆交易。
\nxsubpoint\label{sp:list.blkch.typ}
\embt(區塊鏈類型列表.) 此集合中的區塊鏈包括:
\begin{itemize}
\item 唯一的{\em 主區塊鏈},或簡稱{\em 主鏈},包含有關協議和其參數當前值的一般資訊、驗證者及其權益的集合、目前活躍的工作鏈及其「分片」的集合,以及最重要的,所有工作鏈和分片鏈最新區塊的雜湊集合。
\item 數個(最多 $2^{32}$ 個){\em 工作區塊鏈},或簡稱{\em 工作鏈},實際上是「工作馬」,包含價值轉移和智慧合約交易。不同的工作鏈可能有不同的「規則」,意味著不同的帳戶地址格式、不同的交易格式、不同的智慧合約虛擬機(VM)、不同的基礎加密貨幣等等。然而,它們都必須滿足某些基本的互通性標準,以使不同工作鏈之間的互動成為可能且相對簡單。在這方面,TON 區塊鏈是{\em 異質的}(參見~\ptref{sp:blkch.hom.het}),類似於 EOS(參見~\ptref{sp:discuss.EOS})和 PolkaDot(參見~\ptref{sp:discuss.PolkaDot})專案。
\item 每個工作鏈又細分為最多 $2^{60}$ 個{\em 分片區塊鏈},或簡稱{\em 分片鏈},與工作鏈本身具有相同的規則和區塊格式,但僅負責帳戶的子集,取決於帳戶地址的前幾個(最高有效)位元。換句話說,一種分片形式內建於系統中(參見~\ptref{sp:shard.supp})。由於所有這些分片鏈共享共同的區塊格式和規則,TON 區塊鏈在這方面是{\em 同質的}(參見~\ptref{sp:blkch.hom.het}),類似於 Ethereum 擴展提案中討論的內容。\footnote{\url{https://github.com/ethereum/wiki/wiki/Sharding-FAQ}}
\item 分片鏈(和主鏈)中的每個區塊實際上不僅僅是一個區塊,而是一個小區塊鏈。通常,這個「區塊區塊鏈」或「垂直區塊鏈」恰好由一個區塊組成,那麼我們可能認為這只是分片鏈的相應區塊(在這種情況下也稱為「水平區塊鏈」)。然而,如果有必要修復不正確的分片鏈區塊,則會將新區塊提交到「垂直區塊鏈」中,包含無效「水平區塊鏈」區塊的替代品,或「區塊差異」,僅包含需要更改的該區塊先前版本的那些部分的描述。這是 TON 特有的機制,用於替換檢測到的無效區塊而不對所有相關的分片鏈進行真正的分叉;它將在~\ptref{sp:inv.sh.blk.corr} 中更詳細地解釋。現在,我們只是注意到每個分片鏈(和主鏈)不是傳統的區塊鏈,而是一個{\em 區塊鏈的區塊鏈},或 {\em 2D-區塊鏈},或簡稱 {\em 2-區塊鏈}。
\end{itemize}
\nxsubpoint\label{sp:ISP} \embt(無限分片範式。) 幾乎所有的區塊鏈分片提案都是「自上而下」的:人們首先想像一個單一的區塊鏈,然後討論如何將其拆分為幾個互動的分片鏈以提高效能並實現可擴展性。
TON 的分片方法是「自下而上」的,解釋如下。
想像一下,分片已經被推向極端,因此每個分片鏈中恰好保留一個帳戶或智慧合約。然後我們有大量的「帳戶鏈」,每個都只描述一個帳戶的狀態和狀態轉換,並相互傳送帶有價值的訊息以轉移價值和資訊。
當然,擁有數億條區塊鏈是不切實際的,因為每條區塊鏈中的更新(即新區塊)通常很少出現。為了更有效地實作它們,我們將這些「帳戶鏈」分組為「分片鏈」,因此分片鏈的每個區塊本質上是分配給該分片的帳戶鏈區塊的集合。因此,「帳戶鏈」在「分片鏈」內僅具有純粹的虛擬或邏輯存在。
我們稱這種觀點為{\em 無限分片範式}。它解釋了 TON 區塊鏈的許多設計決策。
\nxsubpoint\label{sp:msg.IHR} \embt(訊息。即時超立方體路由。)
無限分片範式指示我們將每個帳戶(或智慧合約)視為彷彿它本身就在自己的分片鏈中。那麼一個帳戶可能影響另一個帳戶狀態的唯一方式就是向其傳送一個{\em 訊息}(這是所謂 Actor 模型的特殊實例,帳戶作為 Actor;參見~\ptref{sp:actors})。因此,帳戶之間(以及分片鏈之間,因為來源和目的帳戶通常位於不同的分片鏈中)的訊息系統對於像 TON 區塊鏈這樣的可擴展系統至關重要。事實上,TON 區塊鏈的一個新穎功能,稱為{\em 即時超立方體路由}(參見~\ptref{sp:instant.hypercube}),使其能夠將在一個分片鏈的區塊中建立的訊息傳遞並處理到目的分片鏈的{\em 下一個區塊中,無論系統中的分片鏈總數如何。}
\nxsubpoint \embt(主鏈、工作鏈和分片鏈的數量。) TON 區塊鏈恰好包含一個主鏈。然而,系統可能容納最多 $2^{32}$ 個工作鏈,每個又細分為最多 $2^{60}$ 個分片鏈。
\nxsubpoint \embt(工作鏈可以是虛擬區塊鏈,而非真正的區塊鏈。) 由於工作鏈通常細分為分片鏈,工作鏈的存在是「虛擬的」,意味著它不是下面~\ptref{sp:gen.blkch.def} 中提供的一般定義意義上的真正區塊鏈,而只是分片鏈的集合。當只有一個分片鏈對應於一個工作鏈時,這個唯一的分片鏈可能與工作鏈識別,在這種情況下,工作鏈至少在一段時間內成為「真正的」區塊鏈,從而獲得與傳統單區塊鏈設計的表面相似性。然而,無限分片範式(參見~\ptref{sp:ISP})告訴我們,這種相似性確實是表面的:潛在的大量「帳戶鏈」可以暫時分組為一個區塊鏈,這只是一個巧合。
\nxsubpoint \embt(工作鏈的識別。) 每個工作鏈由其{\em 編號}或{\em 工作鏈識別符}($\workchainid:\uint_{32}$)識別,這只是一個無符號 32 位元整數。工作鏈是由主鏈中的特殊交易建立的,定義(先前未使用的)工作鏈識別符和工作鏈的正式描述,至少足以用於該工作鏈與其他工作鏈的互動以及對該工作鏈區塊的表面驗證。
\nxsubpoint \embt(新工作鏈的建立和啟動。) 新工作鏈的建立可以由社群中的任何成員發起,準備支付發佈新工作鏈正式規範所需的(高昂的)主鏈交易費用。然而,為了使新工作鏈變得活躍,需要驗證者的三分之二共識,因為他們需要升級其軟體以處理新工作鏈的區塊,並透過特殊的主鏈交易發出信號表示他們已準備好與新工作鏈合作。對新工作鏈啟動感興趣的一方可能透過智慧合約分配的一些獎勵,為驗證者提供一些激勵以支援新工作鏈。
\nxsubpoint\label{sp:shard.ident} \embt(分片鏈的識別。) 每個分片鏈由一對 $(w,s)=(\workchainid, \shardpfx)$ 識別,其中 $\workchainid:\uint_{32}$ 識別對應的工作鏈,而 $\shardpfx:\st2^{0\ldots60}$ 是長度最多為 60 的位元字串,定義該分片鏈負責的帳戶子集。也就是說,所有以 $\shardpfx$ 開頭(即,將 $\shardpfx$ 作為最高有效位元)的 $\accountid$ 的帳戶將被分配到該分片鏈。
\nxsubpoint \embt(帳戶鏈的識別。) 回想一下,帳戶鏈只有虛擬存在(參見~\ptref{sp:ISP})。然而,它們有一個自然的識別符——即 $(\workchainid,\accountid)$——因為任何帳戶鏈都包含有關恰好一個帳戶(簡單帳戶或智慧合約——這裡的區別並不重要)的狀態和更新的資訊。
\nxsubpoint\label{sp:dyn.split.merge} \embt(分片鏈的動態拆分和合併;參見~\ptref{sect:split.merge}。) 一個不太複雜的系統可能使用{\em 靜態分片}——例如,透過使用 $\accountid$ 的前八位元來選擇 256 個預定義分片之一。
TON 區塊鏈的一個重要功能是它實作了{\em 動態分片},意味著分片的數量不是固定的。相反,如果滿足某些正式條件(本質上,如果原始分片上的交易負載在很長一段時間內足夠高),分片 $(w,s)$ 可以自動細分為分片 $(w,s.0)$ 和 $(w,s.1)$。相反,如果負載在一段時間內保持太低,則分片 $(w,s.0)$ 和 $(w,s.1)$ 可以自動合併回分片 $(w,s)$。
最初,僅為工作鏈 $w$ 建立一個分片 $(w,\emptyset)$。稍後,如果並且當這變得必要時(參見~\ptref{sp:split.necess} 和~\ptref{sp:merge.necess}),它會被細分為更多分片。
\nxsubpoint\label{sp:basic.workchain} \embt(基本工作鏈或工作鏈零。) 雖然最多可以定義 $2^{32}$ 個具有其特定規則和交易的工作鏈,但我們最初只定義了一個,$\workchainid=0$。這個工作鏈,稱為工作鏈零或基本工作鏈,是用於處理 {\em TON 智慧合約}和轉移 {\em TON 幣}(也稱為 {\em Gram};參見附錄~\ref{app:coins})的工作鏈。大多數應用程式可能只需要工作鏈零。基本工作鏈的分片鏈將被稱為{\em 基本分片鏈}。
\nxsubpoint \embt(區塊生成間隔。) 我們預期每個分片鏈和主鏈大約每五秒生成一個新區塊。這將導致相當小的交易確認時間。所有分片鏈的新區塊大約同時生成;主鏈的新區塊大約在一秒後生成,因為它必須包含所有分片鏈最新區塊的雜湊。
\nxsubpoint\label{sp:sc.hash.mc} \embt(使用主鏈使工作鏈和分片鏈緊密耦合。) 一旦分片鏈區塊的雜湊被納入主鏈的區塊中,該分片鏈區塊及其所有祖先都被視為「規範的」,意味著它們可以從所有分片鏈的後續區塊中被引用為固定且不可變的東西。事實上,每個新的分片鏈區塊都包含最新主鏈區塊的雜湊,而從該主鏈區塊引用的所有分片鏈區塊都被新區塊視為不可變的。
本質上,這意味著在分片鏈區塊中提交的交易或訊息可以安全地在其他分片鏈的下一個區塊中使用,而無需等待(例如)二十個確認(即在同一區塊鏈的原始區塊之後生成的二十個區塊),然後才能轉發訊息或根據先前的交易採取其他行動,這在大多數提議的「鬆散耦合」系統(參見~\ptref{sp:blkch.interact})中很常見,例如 EOS。這種在提交後僅五秒鐘就能在其他分片鏈中使用交易和訊息的能力,是我們相信我們的「緊密耦合」系統(同類首創)將能夠提供前所未有的效能(參見~\ptref{sp:shard.supp} 和~\ptref{sp:blkch.interact})的原因之一。
\nxsubpoint \embt(主鏈區塊雜湊作為全域狀態。) 根據~\ptref{sp:sc.hash.mc},最後一個主鏈區塊的雜湊從外部觀察者的角度完全決定了系統的整體狀態。不需要單獨監控所有分片鏈的狀態。
\nxsubpoint \embt(驗證者生成新區塊;參見~\ptref{sect:validators}。) TON 區塊鏈使用權益證明(PoS)方法在分片鏈和主鏈中生成新區塊。這意味著有一組(比如說,最多幾百個){\em 驗證者}——特殊節點,它們透過特殊的主鏈交易存入{\em 權益}(大量 TON 幣),以便有資格進行新區塊生成和驗證。
然後以確定性偽隨機方式將驗證者的較小子集分配給每個分片 $(w,s)$,大約每 1024 個區塊更換一次。這個驗證者子集建議下一個分片鏈區塊是什麼,並透過將客戶端提出的合適交易收集到新的有效區塊候選中來達成共識。對於每個區塊,驗證者上有一個偽隨機選擇的順序,以確定誰的區塊候選在每次輪次中具有最高優先順序被提交。
驗證者和其他節點檢查提議的區塊候選的有效性;如果驗證者簽署了無效的區塊候選,它可能會因失去部分或全部權益,或被暫時從驗證者集合中停權一段時間而自動受到懲罰。之後,驗證者應該就下一個區塊的選擇達成共識,本質上透過 BFT(拜占庭容錯;參見~\ptref{sp:dpos.bft})共識協議的有效變體,類似於 PBFT~\cite{PBFT} 或 Honey Badger BFT~\cite{HoneyBadger}。如果達成共識,則建立新區塊,驗證者之間分配所包含交易的交易費用,加上一些新建立(「鑄造的」)幣。
每個驗證者可以被選舉參與多個驗證者子集;在這種情況下,預期它會並行執行所有驗證和共識演算法。
在生成所有新的分片鏈區塊或超時後,生成新的主鏈區塊,包括所有分片鏈最新區塊的雜湊。這是透過{\em 所有}驗證者的 BFT 共識完成的。\footnote{實際上,三分之二的權益就足以達成共識,但會努力收集盡可能多的簽名。}
有關 TON PoS 方法及其經濟模型的更多細節在~\ptref{sect:validators} 節中提供。
\nxsubpoint \embt(主鏈的分叉。) 我們的緊密耦合方法產生的一個複雜性是,切換到主鏈中的不同分叉幾乎必然需要切換到至少某些分片鏈中的另一個分叉。另一方面,只要主鏈中沒有分叉,分片鏈中的分叉甚至是不可能的,因為分片鏈替代分叉中的區塊不能透過將其雜湊納入主鏈區塊而成為「規範的」。
一般規則是{\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 大多數}驗證者行為不正確的情況下發生(參見~\ptref{sp:validators} 和~\ptref{sp:new.master.blk}),這將意味著違規者的重大權益損失。因此,不應該預期分片鏈中會出現真正的分叉。相反,如果檢測到無效的分片鏈區塊,它將透過 2-區塊鏈的「垂直區塊鏈」機制進行糾正(參見~\ptref{sp:inv.sh.blk.corr}),該機制可以在不分叉「水平區塊鏈」(即分片鏈)的情況下實現此目標。同樣的機制也可用於修復主鏈區塊中的非致命錯誤。
\nxsubpoint\label{sp:inv.sh.blk.corr} \embt(糾正無效的分片鏈區塊。) 通常,只有有效的分片鏈區塊才會被提交,因為分配給分片鏈的驗證者在提交新區塊之前必須達成三分之二的拜占庭共識。然而,系統必須允許檢測先前提交的無效區塊並對其進行糾正。
當然,一旦發現無效的分片鏈區塊——無論是由驗證者(不一定分配給此分片鏈)還是由「漁夫」(系統中任何進行了一定存款以能夠對區塊有效性提出質疑的節點;參見~\ptref{sp:fish})發現——無效性宣告及其證明將被提交到主鏈中,簽署無效區塊的驗證者將因失去部分權益和/或被暫時從驗證者集合中停權而受到懲罰(後一措施對於攻擊者竊取原本良性驗證者的私有簽名金鑰的情況很重要)。
然而,這還不夠,因為由於先前提交的無效分片鏈區塊,系統(TON 區塊鏈)的整體狀態變得無效。這個無效區塊必須被更新的有效版本替換。
大多數系統會透過「回滾」到此分片鏈中無效區塊之前的最後一個區塊,以及每個其他分片鏈中不受從無效區塊傳播的訊息影響的最後一個區塊,並從這些區塊建立新的分叉來實現這一點。這種方法的缺點是大量原本正確並已提交的交易會突然被回滾,並且不清楚它們以後是否會被包含。
TON 區塊鏈透過使每個分片鏈和主鏈(「水平區塊鏈」)的每個「區塊」本身成為一個小區塊鏈(「垂直區塊鏈」),包含此「區塊」的不同版本或它們的「差異」來解決這個問題。通常,垂直區塊鏈恰好由一個區塊組成,分片鏈看起來像傳統的區塊鏈。然而,一旦區塊的無效性被確認並提交到主鏈區塊中,無效區塊的「垂直區塊鏈」就允許在垂直方向上透過新區塊增長,替換或編輯無效區塊。新區塊由有關分片鏈的當前驗證者子集生成。
新「垂直」區塊有效的規則非常嚴格。特別是,如果無效區塊中包含的虛擬「帳戶鏈區塊」(參見~\ptref{sp:ISP})本身是有效的,則新垂直區塊必須保持不變。
一旦新的「垂直」區塊被提交到無效區塊之上,其雜湊就會在新的主鏈區塊中發佈(或者更確切地說,在新的「垂直」區塊中發佈,該區塊位於最初發佈無效分片鏈區塊雜湊的原始主鏈區塊之上),並且更改會進一步傳播到引用該區塊先前版本的任何分片鏈區塊(例如,那些從不正確區塊接收訊息的區塊)。這透過為先前引用「不正確」區塊的所有區塊在垂直區塊鏈中提交新的「垂直」區塊來修復;新的垂直區塊將引用最新(已糾正的)版本。同樣,嚴格的規則禁止更改實際上沒有受到影響(即,接收與先前版本中相同的訊息)的帳戶鏈。透過這種方式,修復不正確的區塊會產生「漣漪」,最終傳播到所有受影響分片鏈的最新區塊;這些變化也反映在新的「垂直」主鏈區塊中。
一旦「歷史改寫」漣漪到達最新區塊,新的分片鏈區塊就只以一個版本生成,成為最新區塊版本的後繼者。這意味著它們從一開始就會包含對正確(最新)垂直區塊的引用。
主鏈狀態隱含地定義了一個映射,將每個「垂直」區塊鏈的第一個區塊的雜湊轉換為其最新版本的雜湊。這使客戶端能夠透過其第一個(通常是唯一的)區塊的雜湊來識別和定位任何垂直區塊鏈。
\nxsubpoint \embt(TON 幣和多幣種工作鏈。) TON 區塊鏈支援最多 $2^{32}$ 種不同的「加密貨幣」、「幣」或「代幣」,由 32 位元 $\currencyid$ 區分。新的加密貨幣可以透過主鏈中的特殊交易新增。每個工作鏈都有一個基本加密貨幣,並且可以有幾種附加的加密貨幣。
有一種特殊的加密貨幣,其 $\currencyid=0$,即 {\em TON 幣},也稱為 {\em Gram}(參見附錄~\ref{app:coins})。它是工作鏈零的基本加密貨幣。它也用於交易費用和驗證者權益。
原則上,其他工作鏈可能以其他代幣收取交易費用。在這種情況下,應提供一些將這些交易費用自動轉換為 Gram 的智慧合約。
\nxsubpoint \embt(訊息傳遞和價值轉移。) 屬於相同或不同工作鏈的分片鏈可以相互發送{\em 訊息}。雖然允許的訊息的確切形式取決於接收工作鏈和接收帳戶(智慧合約),但有一些通用欄位使跨工作鏈訊息傳遞成為可能。特別是,每個訊息都可以附帶一些{\em 價值},以一定數量的 Gram(TON 幣)和/或其他註冊的加密貨幣的形式,只要它們被接收工作鏈宣告為可接受的加密貨幣。
這種訊息傳遞的最簡單形式是從一個(通常不是智慧合約)帳戶到另一個帳戶的價值轉移。
\nxsubpoint\label{sp:tonvm} \embt(TON 虛擬機。) {\em TON 虛擬機},也縮寫為 {\em TON VM} 或 {\em TVM},是用於在主鏈和基本工作鏈中執行智慧合約程式碼的虛擬機。其他工作鏈可以與 TVM 一起或代替 TVM 使用其他虛擬機。
這裡我們列出了它的一些功能。它們在~\ptref{sp:pec.tvm}、\ptref{sp:tvm.cells} 等處進一步討論。
\begin{itemize}
\item TVM 將所有資料表示為 {\em(TVM)單元}的集合(參見~\ptref{sp:tvm.cells})。每個單元包含最多 128 個資料位元組和最多 4 個對其他單元的引用。作為「一切皆為單元集合」理念(參見~\ptref{sp:everything.is.BoC})的結果,這使 TVM 能夠在必要時處理與 TON 區塊鏈相關的所有資料,包括區塊和區塊鏈全域狀態。
\item TVM 可以處理任意代數資料類型的值(參見~\ptref{sp:pec.tvm}),表示為 TVM 單元的樹或有向無環圖。然而,它對代數資料類型的存在是不可知的;它只是處理單元。
\item TVM 內建支援雜湊映射(參見~\ptref{sp:patricia})。
\item TVM 是一個堆疊機器。其堆疊保存 64 位元整數或單元引用。
\item 支援 64 位元、128 位元和 256 位元運算。所有 $n$ 位元運算操作都有三種形式:用於無符號整數、用於有符號整數和用於模 $2^n$ 的整數(在後一種情況下沒有自動溢位檢查)。
\item TVM 具有從 $n$ 位元到 $m$ 位元的無符號和有符號整數轉換,對於所有 $0\leq m,n\leq 256$,具有溢位檢查。
\item 所有算術運算預設執行溢位檢查,極大地簡化了智慧合約的開發。
\item TVM 具有「乘後移位」和「移位後除」算術運算,中間值以更大的整數類型計算;這簡化了定點運算的實作。
\item TVM 提供對位元字串和位元組字串的支援。
\item 支援某些預定義曲線的 256 位元橢圓曲線密碼學(ECC),包括 Curve25519。
\item 也支援某些橢圓曲線上的 Weil 配對,對於 zk-SNARK 的快速實作很有用。
\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(可設定參數。) TON 區塊鏈的一個重要功能是其許多參數是{\em 可設定的}。這意味著它們是主鏈狀態的一部分,可以透過主鏈中的某些特殊提案/投票/結果交易進行更改,而無需任何硬分叉。更改此類參數將需要收集三分之二的驗證者投票以及超過一半願意參與投票過程的所有其他參與者的投票以支持該提案。
\mysubsection{區塊鏈概論}
\nxsubpoint\label{sp:gen.blkch.def} \embt(一般區塊鏈定義。) 一般來說,任何{\em(真正的)區塊鏈}都是{\em 區塊}的序列,每個區塊 $B$ 包含對前一個區塊的引用 $\blkprev(B)$(通常透過將前一個區塊的雜湊包含在當前區塊的標頭中),以及{\em 交易}的列表。每個交易描述{\em 全域區塊鏈狀態}的某種轉換;區塊中列出的交易依序應用,以從舊狀態計算新狀態,舊狀態是評估前一個區塊後的結果狀態。
\nxsubpoint \embt(與 TON 區塊鏈的相關性。) 回想一下,{\em TON 區塊鏈}不是真正的區塊鏈,而是 2-區塊鏈的集合(即區塊鏈的區塊鏈;參見~\ptref{sp:list.blkch.typ}),因此上述內容不能直接應用於它。然而,我們從這些關於真正區塊鏈的概論開始,以將它們用作我們更複雜構造的構建塊。
\nxsubpoint \embt(區塊鏈實例和區塊鏈類型。) 人們經常使用{\em 區塊鏈}一詞來表示一般的{\em 區塊鏈類型}及其特定的{\em 區塊鏈實例},定義為滿足某些條件的區塊序列。例如,\ptref{sp:gen.blkch.def} 指的是區塊鏈實例。
透過這種方式,區塊鏈類型通常是區塊列表類型 $\Block^*$(即有限序列)的「子類型」,由滿足某些相容性和有效性條件的區塊序列組成:
\begin{equation}
\Blockchain \subset \Block^*
\end{equation}
定義 $\Blockchain$ 的更好方法是說 $\Blockchain$ 是一個{\em 依賴對類型},由對 $(\bbB,v)$ 組成,第一個分量 $\bbB:\Block^*$ 的類型為 $\Block^*$(即區塊列表),第二個分量 $v:\isValidBc(\bbB)$ 是 $\bbB$ 有效性的證明或見證。透過這種方式,
\begin{equation}
\Blockchain\equiv\Sigma_{(\bbB:\Block^*)}\isValidBc(\bbB)
\end{equation}
我們在這裡使用從~\cite{HoTT} 借來的類型依賴和的符號。
\nxsubpoint \embt(依賴類型理論、Coq 和 TL。) 請注意,我們在這裡使用(Martin-L\"of)依賴類型理論,類似於 Coq\footnote{\url{https://coq.inria.fr}} 證明助手中使用的理論。依賴類型理論的簡化版本也用於 {\em TL(類型語言)},\footnote{\url{https://core.telegram.org/mtproto/TL}} 它將用於 TON 區塊鏈的正式規範,以描述所有資料結構的序列化以及區塊、交易等的佈局。
事實上,依賴類型理論提供了證明是什麼的有用形式化,當需要為某個區塊提供無效性證明時,這種形式化證明(或其序列化)可能會派上用場。
\nxsubpoint\label{sp:TL} \embt(TL,或類型語言。) 由於 TL(類型語言)將用於 TON 區塊、交易和網路資料報的正式規範,因此值得簡要討論。
TL 是一種適合描述依賴代數{\em 類型}的語言,允許具有數值(自然數)和類型參數。每個類型透過幾個{\em 建構子}來描述。每個建構子都有一個(人類可讀的)識別符和一個{\em 名稱},即位元字串(預設為 32 位元整數)。除此之外,建構子的定義包含欄位列表及其類型。
建構子和類型定義的集合稱為 {\em TL-方案}。它通常保存在一個或多個帶有後綴 \texttt{.tl} 的檔案中。
TL-方案的一個重要功能是它們確定了一種明確的方式來序列化和反序列化所定義的代數類型的值(或物件)。也就是說,當需要將值序列化為位元組流時,首先序列化用於該值的建構子的名稱。然後是每個欄位的遞迴計算的序列化。
TL 先前版本的描述,適合將任意物件序列化為 32 位元整數序列,可在 \url{https://core.telegram.org/mtproto/TL} 獲得。正在為描述 TON 專案使用的物件序列化而開發稱為 {\em TL-B} 的新版本 TL。這個新版本可以將物件序列化為位元組流甚至位元流(而不僅僅是 32 位元整數),並支援序列化到 TVM 單元樹中(參見~\ptref{sp:tvm.cells})。TL-B 的描述將成為 TON 區塊鏈正式規範的一部分。
\nxsubpoint\label{sp:blk.transf} \embt(區塊和交易作為狀態轉換運算子。) 通常,任何區塊鏈(類型)$\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(區塊序列號。) 區塊鏈中的每個區塊 $B$ 都可以透過其{\em 序列號} $\blkseqno(B)$ 引用,從第一個區塊的零開始,每次傳遞到下一個區塊時遞增一。更正式地說,
\begin{equation}
\blkseqno(B)=\blkseqno\bigl(\blkprev(B)\bigr)+1
\end{equation}
請注意,在存在{\em 分叉}的情況下,序列號不能唯一識別區塊。
\nxsubpoint \embt(區塊雜湊。) 引用區塊 $B$ 的另一種方法是透過其雜湊 $\blkhash(B)$,這實際上是區塊 $B$ 的{\em 標頭}的雜湊(但是,區塊的標頭通常包含依賴於區塊 $B$ 所有內容的雜湊)。假設所使用的雜湊函數沒有碰撞(或至少它們非常不可能),則區塊由其雜湊唯一識別。
\nxsubpoint \embt(雜湊假設。) 在區塊鏈演算法的形式分析中,我們假設所使用的 $k$ 位元雜湊函數 $\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$ 位元序列(即 $k$ 位元數字)的集合(或實際上是類型)。
當然,\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}
然而,這對於證明來說不太方便。如果 \eqref{eq:hash.coll.prec} 在證明中最多使用 $N$ 次,且 $2^{-k}N<\epsilon$ 對於某個小的 $\epsilon$(例如,$\epsilon=10^{-18}$),我們可以像 \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\bigl(\Hash(s)=\Hash(s')|s\neq s'\bigr)$ 當 $p$ 從下方趨近於一時的極限。
\nxsubpoint\label{sp:hash.change} \embt(TON 區塊鏈使用的雜湊。) 我們目前為 TON 區塊鏈使用 256 位元 $\Sha$ 雜湊。如果它被證明比預期的弱,它可以在未來被另一個雜湊函數替換。雜湊函數的選擇是協議的可設定參數,因此可以在沒有硬分叉的情況下更改,如~\ptref{sp:config.param} 中所解釋的。
\mysubsection{區塊鏈狀態、帳戶和雜湊映射}
我們在上面注意到,任何區塊鏈都定義了某個全域狀態,每個區塊和每個交易都定義了該全域狀態的轉換。在這裡,我們描述 TON 區塊鏈使用的全域狀態。
\nxsubpoint \embt(帳戶 ID。) TON 區塊鏈——或至少其主鏈和工作鏈零——使用的基本帳戶 ID 是 256 位元整數,假定為特定橢圓曲線的 256 位元橢圓曲線密碼學(ECC)的公鑰。透過這種方式,
\begin{equation}
\accountid:\Account=\uint_{256}=\st2^{256}
\end{equation}
這裡 $\Account$ 是帳戶{\em 類型},而 $\accountid:\Account$ 是類型 $\Account$ 的特定變數。
其他工作鏈可以使用其他帳戶 ID 格式,256 位元或其他。例如,可以使用 Bitcoin 風格的帳戶 ID,等於 ECC 公鑰的 $\Sha$。
然而,帳戶 ID 的位元長度 $l$ 必須在工作鏈建立期間(在主鏈中)固定,並且必須至少為 64,因為 $\accountid$ 的前 64 位元用於分片和訊息路由。
\nxsubpoint \embt(主要組件:{\em 雜湊映射}。) 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(範例:TON 帳戶餘額。) 一個重要的範例由 TON 帳戶餘額給出。它是一個雜湊映射
\begin{equation}
\vr{balance}:\Account\to\uint_{128}
\end{equation}
將 $\Account=\st2^{256}$ 映射到類型為 $\uint_{128}=\st2^{128}$ 的 Gram(TON 幣)餘額。此雜湊映射的預設值為零,意味著最初(在處理第一個區塊之前)所有帳戶的餘額為零。
\nxsubpoint \embt(範例:智慧合約持久儲存。) 另一個範例由智慧合約持久儲存給出,可以(非常粗略地)表示為雜湊映射
\begin{equation}
\vr{storage}:\st2^{256}\dashrightarrow\st2^{256}
\end{equation}
此雜湊映射的預設值也為零,意味著未初始化的持久儲存單元假定為零。
\nxsubpoint \embt(範例:所有智慧合約的持久儲存。) 由於我們有多個智慧合約,由 $\accountid$ 區分,每個都有其單獨的持久儲存,我們實際上必須有一個雜湊映射
\begin{equation}
\vr{Storage}:\Account\dashrightarrow(\st2^{256}\dashrightarrow\st2^{256})
\end{equation}
將智慧合約的 $\accountid$ 映射到其持久儲存。
\nxsubpoint \embt(雜湊映射類型。) 雜湊映射不僅僅是抽象的(部分定義的)函數 $\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(雜湊映射類型定義為 Patricia 樹。) 邏輯上,可以將 $\Hashmap(n,X)$ 定義為深度為 $n$ 的(不完整的)二元樹,邊標籤為 $0$ 和 $1$,葉子中的值類型為 $X$。描述相同結構的另一種方式是作為長度等於 $n$ 的二進位字串的{\em(按位元)字典樹}。
在實踐中,我們更喜歡使用此字典樹的緊湊表示,透過將每個只有一個子節點的頂點與其父節點壓縮。所得的表示稱為 {\em Patricia 樹}或{\em 二進位基數樹}。現在每個中間頂點恰好有兩個子節點,由兩個非空的二進位字串標記,左子節點以零開頭,右子節點以一開頭。
換句話說,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 樹。) 在處理區塊鏈時,我們希望能夠透過將 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$ 的前綴碼。例如,可以將 0 編碼為 10,將 1 編碼為 11,將字串結尾編碼為 0。\footnote{可以證明,對於具有隨機或連續索引的 Patricia 樹的大約一半邊標籤,此編碼是最佳的。剩餘的邊標籤可能很長(即,幾乎 256 位元長)。因此,邊標籤的近似最佳編碼是對「短」位元字串使用帶前綴 0 的上述碼,並對「長」位元字串編碼 1,然後是包含位元字串~$s$ 的長度 $l=|s|$ 的九個位元,然後是 $s$ 的 $l$ 個位元(其中 $l\geq10$)。}
我們稍後將看到(參見~\ptref{sp:pec.tvm} 和 \ptref{sp:tvm.cells}),這是任意(依賴)代數類型值的遞迴定義雜湊的(稍微調整的)版本。
\nxsubpoint \embt(重新計算 Merkle 樹雜湊。) 這種遞迴定義 $\Hash(h)$ 的方法,稱為{\em Merkle 樹雜湊},其優點是,如果明確儲存 $\Hash(h')$ 與每個節點 $h'$(產生稱為{\em Merkle 樹}的結構,或在我們的情況下,{\em Merkle--Patricia 樹}),則在向雜湊映射新增、從雜湊映射刪除或更改元素時,只需要重新計算最多 $n$ 個雜湊。
透過這種方式,如果透過合適的 Merkle 樹雜湊表示全域區塊鏈狀態,則在每次交易後重新計算此狀態雜湊很容易。
\nxsubpoint\label{sp:merkle.proof} \embt(Merkle 證明。) 在所選雜湊函數 $\Hash$ 的「單射性」假設 \eqref{eq:hash.coll} 下,可以構造一個證明,對於 $\Hash(h)$ 的給定值 $z$,$h:\Hashmap(n,X)$,對於某些 $i:\st2^n$ 和 $x:X$,有 $\hget(h)(i)=x$。這樣的證明將由 Merkle--Patricia 樹中從對應於 $i$ 的葉子到根的路徑組成,並附加此路徑上出現的所有節點的所有兄弟節點的雜湊。
透過這種方式,輕節點\footnote{{\em 輕節點}是不追蹤分片鏈完整狀態的節點;相反,它保留最少的資訊,例如最近幾個區塊的雜湊,並在需要檢查完整狀態的某些部分時依賴從完整節點獲得的資訊。}只知道某個雜湊映射 $h$ 的 $\Hash(h)$ 值(例如,智慧合約持久儲存或全域區塊鏈狀態)可能從完整節點\footnote{{\em 完整節點}是追蹤有關分片鏈的完整最新狀態的節點。}請求不僅是值 $x=h[i]=\hget(h)(i)$,還請求這樣的值以及從已知值 $\Hash(h)$ 開始的 Merkle 證明。然後,在假設 \eqref{eq:hash.coll} 下,輕節點可以自己檢查 $x$ 確實是 $h[i]$ 的正確值。
在某些情況下,客戶端可能想要獲得值 $y=\Hash(x)=\Hash(h[i])$——例如,如果 $x$ 本身非常大(例如,雜湊映射本身)。然後可以提供 $(i,y)$ 的 Merkle 證明。如果 $x$ 也是雜湊映射,則可以從完整節點獲得從 $y=\Hash(x)$ 開始的第二個 Merkle 證明,以提供值 $x[j]=h[i][j]$ 或只是其雜湊。
\nxsubpoint \embt(Merkle 證明對 TON 等多鏈系統的重要性。) 請注意,節點通常不能成為 TON 環境中存在的所有分片鏈的完整節點。它通常只是某些分片鏈的完整節點——例如,包含其自己帳戶、它感興趣的智慧合約的分片鏈,或者該節點已被分配為驗證者的分片鏈。對於其他分片鏈,它必須是輕節點——否則儲存、計算和網路頻寬需求將是令人望而卻步的。這意味著這樣的節點不能直接檢查關於其他分片鏈狀態的斷言;它必須依賴從這些分片鏈的完整節點獲得的 Merkle 證明,這與自己檢查一樣安全,除非 \eqref{eq:hash.coll} 失敗(即,發現雜湊碰撞)。
\nxsubpoint\label{sp:pec.tvm} \embt(TON VM 的特殊性。) TON VM 或 TVM(Telegram 虛擬機),用於在主鏈和工作鏈零中執行智慧合約,與受 EVM(Ethereum 虛擬機)啟發的慣用設計有很大不同:它不僅處理 256 位元整數,而且實際上處理(幾乎)任意的「記錄」、「結構」或「和-積類型」,使其更適合執行以高階(特別是函數式)語言編寫的程式碼。本質上,TVM 使用標記的資料類型,與 Prolog 或 Erlang 實作中使用的資料類型沒有什麼不同。
首先可以想像 TVM 智慧合約的狀態不僅是雜湊映射 $\st2^{256}\to\st2^{256}$ 或 $\Hashmap(256,\st2^{256})$,而是(作為第一步)$\Hashmap(256,X)$,其中 $X$ 是具有多個建構子的類型,使其能夠儲存除 256 位元整數之外的其他資料結構,特別是其他雜湊映射 $\Hashmap(256,X)$。這意味著 TVM(持久或臨時)儲存的單元——或 TVM 智慧合約程式碼中的變數或陣列的元素——可能不僅包含整數,還包含整個新的雜湊映射。當然,這意味著單元不僅包含 256 位元,還包含(例如)8 位元標籤,描述這 256 位元應該如何解譯。
事實上,值不需要精確地為 256 位元。TVM 使用的值格式由原始位元組序列和對其他結構的引用組成,以任意順序混合,在合適的位置插入一些描述符位元組以能夠區分指標和原始資料(例如,字串或整數);參見~\ptref{sp:tvm.cells}。
此原始值格式可用於實作任意和-積代數類型。在這種情況下,值將首先包含一個原始位元組,描述正在使用的「建構子」(從高階語言的角度),然後是其他「欄位」或「建構子參數」,由原始位元組和對其他結構的引用組成,取決於所選的建構子(參見~\ptref{sp:TL})。然而,TVM 不知道建構子及其參數之間的對應關係;位元組和引用的混合由某些描述符位元組明確描述。\footnote{任何 TVM 單元中存在的這兩個描述符位元組僅描述引用的總數和原始位元組的總數;引用保持在一起,在所有原始位元組之前或之後。}
Merkle 樹雜湊擴展到任意這樣的結構:要計算這樣的結構的雜湊,所有引用都遞迴地替換為所引用物件的雜湊,然後計算所得位元組字串(包括描述符位元組)的雜湊。
透過這種方式,\ptref{sp:merkle.patr.hash} 中描述的雜湊映射的 Merkle 樹雜湊只是應用於具有兩個建構子的類型 $\Hashmap(n,X)$ 的任意(依賴)代數資料類型雜湊的特例。\footnote{實際上,$\leaf$ 和 $\node$ 是輔助類型 $\tp{HashmapAux}(n,X)$ 的建構子。類型 $\Hashmap(n,X)$ 具有建構子 $\root$ 和 $\emptyroot$,其中 $\root$ 包含類型 $\tp{HashmapAux}(n,X)$ 的值。}
\nxsubpoint \embt(TON 智慧合約的持久儲存。) TON 智慧合約的持久儲存本質上由其「全域變數」組成,在呼叫智慧合約之間保留。因此,它只是一個「積」、「元組」或「記錄」類型,由正確類型的欄位組成,每個對應一個全域變數。如果全域變數太多,則由於對 TON 單元大小的全域限制,它們無法容納在一個 TON 單元中。在這種情況下,它們被分成幾個記錄並組織成樹,本質上成為「積的積」或「積的積的積」類型,而不僅僅是積類型。
\nxsubpoint\label{sp:tvm.cells} \embt(TVM 單元。) 最終,TON VM 將所有資料保存在 {\em(TVM)單元}的集合中。每個單元首先包含兩個描述符位元組,指示此單元中存在多少個原始資料位元組(最多 128 個)以及存在多少個對其他單元的引用(最多四個)。然後是這些原始資料位元組和引用。每個單元恰好被引用一次,因此我們可以在每個單元中包含對其「父單元」(引用此單元的唯一單元)的引用。然而,此引用不需要是明確的。
透過這種方式,TON 智慧合約的持久資料儲存單元被組織成樹,\footnote{邏輯上;~\ptref{sp:bag.of.cells} 中描述的「單元集合」表示識別所有重複單元,在序列化時將此樹轉換為有向無環圖(dag)。}在智慧合約描述中保留對此樹根的引用。如果必要,從葉子開始遞迴計算整個持久儲存的 Merkle 樹雜湊,然後只需將單元中的所有引用替換為被引用單元的遞迴計算的雜湊,然後計算由此獲得的位元組字串的雜湊。
\nxsubpoint\label{sp:gen.merkle.proof} \embt(任意代數類型值的廣義 Merkle 證明。) 由於 TON VM 透過由(TVM)單元組成的樹表示任意代數類型的值,並且每個單元都有明確定義的(遞迴計算的)Merkle 雜湊,實際上取決於以此單元為根的整個子樹,我們可以為任意代數類型的值(部分)提供「廣義 Merkle 證明」,旨在證明具有已知 Merkle 雜湊的樹的某個子樹採用特定值或具有特定雜湊的值。這概括了 \ptref{sp:merkle.proof} 的方法,其中僅考慮了 $x[i]=y$ 的 Merkle 證明。
\nxsubpoint\label{sp:tvm.data.shard} \embt(TON VM 資料結構中對分片的支援。) 我們剛剛概述了 TON VM 如何在不過於複雜的情況下,在高階智慧合約語言中支援任意(依賴)代數資料類型。然而,大型(或全域)智慧合約的分片需要在 TON VM 層級上的特殊支援。為此,系統中新增了雜湊映射類型的特殊版本,相當於「映射」$\Account\dashrightarrow X$。此「映射」可能看起來等同於 $\Hashmap(m,X)$,其中 $\Account=\st2^m$。然而,當分片拆分為兩個時,或兩個分片合併時,此類雜湊映射會自動拆分為兩個,或合併回來,以便僅保留屬於相應分片的那些鍵。
\nxsubpoint \embt(持久儲存的支付。) TON 區塊鏈的一個值得注意的功能是向智慧合約收取儲存其持久資料(即擴大區塊鏈的總狀態)的費用。它的工作原理如下:
每個區塊宣告兩個費率,以區塊鏈的主要貨幣(通常是 Gram)計價:在持久儲存中保留一個單元的價格,以及在持久儲存的某個單元中保留一個原始位元組的價格。每個帳戶使用的單元和位元組總數的統計資料儲存為其狀態的一部分,因此透過將這些數字乘以區塊標頭中宣告的兩個費率,我們可以計算從帳戶餘額中扣除的用於在前一個區塊和當前區塊之間保留其資料的支付。
然而,並非在每個區塊中對每個帳戶和智慧合約徵收持久儲存使用的費用;相反,最後徵收此費用的區塊的序列號儲存在帳戶資料中,當對帳戶執行任何操作時(例如,價值轉移或智慧合約接收和處理訊息),在執行任何進一步操作之前,從帳戶餘額中扣除自上次此類支付以來所有區塊的儲存使用支付。如果此後帳戶的餘額變為負數,則帳戶被銷毀。
工作鏈可能宣告每個帳戶的一些原始資料位元組數量為「免費」(即不參與持久儲存支付),以使僅保留其一種或兩種加密貨幣餘額的「簡單」帳戶免於這些持續支付。
請注意,如果沒有人向帳戶傳送任何訊息,則不會收取其持久儲存支付,它可以無限期存在。然而,任何人都可以傳送(例如)一個空訊息來銷毀這樣的帳戶。可以向此類訊息的傳送者提供一個小激勵,從要銷毀的帳戶的原始餘額的一部分中收取。然而,我們預期驗證者會免費銷毀此類無力償還的帳戶,只是為了減少全域區塊鏈狀態大小並避免在沒有補償的情況下保留大量資料。
為保留持久資料而收取的支付在分片鏈或主鏈的驗證者之間分配(在後一種情況下與其權益成比例)。
\nxsubpoint\label{sp:loc.glob.smct} \embt(本地和全域智慧合約;智慧合約實例。) 智慧合約通常僅駐留在一個分片中,根據智慧合約的 $\accountid$ 選擇,類似於「普通」帳戶。這通常對大多數應用程式來說已經足夠。然而,一些「高負載」智慧合約可能希望在某個工作鏈的每個分片鏈中都有一個「實例」。為了實現這一點,它們必須將其建立交易傳播到所有分片鏈中,例如,透過將此交易提交到工作鏈 $w$ 的「根」分片鏈 $(w,\emptyset)$\footnote{更昂貴的替代方案是在主鏈中發佈此類「全域」智慧合約。}並支付大額佣金。\footnote{這是一種針對所有分片的「廣播」功能,因此必須相當昂貴。}
此操作有效地在每個分片中建立智慧合約的實例,具有單獨的餘額。最初,建立交易中轉移的餘額只是透過給分片 $(w,s)$ 中的實例 $2^{-|s|}$ 部分的總餘額來分配。當分片拆分為兩個子分片時,所有全域智慧合約實例的餘額都會減半;當兩個分片合併時,餘額會相加。
在某些情況下,拆分/合併全域智慧合約的實例可能涉及(延遲)執行這些智慧合約的特殊方法。預設情況下,餘額如上所述拆分和合併,並且一些特殊的「帳戶索引」雜湊映射也會自動拆分和合併(參見~\ptref{sp:tvm.data.shard})。
\nxsubpoint \embt(限制智慧合約的拆分。) 全域智慧合約可以在建立時限制其拆分深度 $d$,以使持久儲存費用更可預測。這意味著,如果具有 $|s|\geq d$ 的分片鏈 $(w,s)$ 拆分為兩個,則兩個新分片鏈中只有一個繼承智慧合約的實例。此分片鏈是確定性選擇的:每個全域智慧合約都有一些「$\accountid$」,本質上是其建立交易的雜湊,其實例具有相同的 $\accountid$,前 $\leq d$ 位元替換為需要落入正確分片的合適值。此 $\accountid$ 選擇在拆分後哪個分片將繼承智慧合約實例。
\nxsubpoint\label{sp:account.state} \embt(帳戶/智慧合約狀態。) 我們可以總結以上所有內容以得出結論,帳戶或智慧合約狀態由以下組成:
\begin{itemize}
\item 區塊鏈主要貨幣的餘額
\item 區塊鏈其他貨幣的餘額
\item 智慧合約程式碼(或其雜湊)
\item 智慧合約持久資料(或其 Merkle 雜湊)
\item 關於使用的持久儲存單元和原始位元組數量的統計資料
\item 上次(實際上是主鏈區塊編號)收取智慧合約持久儲存支付的時間
\item 從此帳戶轉移貨幣和傳送訊息所需的公鑰(可選;預設等於 $\accountid$ 本身)。在某些情況下,更複雜的簽名檢查程式碼可能位於此處,類似於 Bitcoin 交易輸出所做的;那麼 $\accountid$ 將等於此程式碼的雜湊。
\end{itemize}
我們還需要在帳戶狀態或某個其他帳戶索引的雜湊映射中的某處保留以下資料:
\begin{itemize}
\item 帳戶的輸出訊息佇列(參見~\ptref{sp:out.queue})
\item 最近傳遞的訊息的(雜湊)集合(參見~\ptref{sp:deliver.q})
\end{itemize}
並非所有這些對於每個帳戶都是真正需要的;例如,智慧合約程式碼僅對智慧合約需要,而對「簡單」帳戶則不需要。此外,雖然任何帳戶必須在主要貨幣(例如,基本工作鏈的主鏈和分片鏈的 Gram)中具有非零餘額,但它在其他貨幣中的餘額可能為零。為了避免保留未使用的資料,定義了一個和-積類型(取決於工作鏈)(在工作鏈建立期間),它使用不同的標籤位元組(例如,TL 建構子;參見~\ptref{sp:TL})來區分使用的不同「建構子」。最終,帳戶狀態本身作為 TVM 持久儲存的單元集合保留。
\mysubsection{分片鏈之間的訊息}
TON 區塊鏈的一個重要組件是區塊鏈之間的{\em 訊息系統}。這些區塊鏈可以是同一工作鏈的分片鏈,也可以是不同工作鏈的分片鏈。
\nxsubpoint \embt(訊息、帳戶和交易:系統的鳥瞰圖。) {\em 訊息}從一個帳戶傳送到另一個帳戶。每個{\em 交易}由一個帳戶接收一個訊息、根據某些規則更改其狀態以及生成幾個(可能是一個或零個)新訊息到其他帳戶組成。每個訊息恰好被生成和接收(傳遞)一次。
這意味著訊息在系統中扮演基本角色,與帳戶(智慧合約)的角色相當。從無限分片範式的角度來看(參見~\ptref{sp:ISP}),每個帳戶都駐留在其單獨的「帳戶鏈」中,它能夠影響其他帳戶狀態的唯一方式是透過傳送訊息。
\nxsubpoint\label{sp:actors} \embt(帳戶作為進程或 actor;Actor 模型。) 人們可以將帳戶(和智慧合約)視為「進程」或「actor」,它們能夠處理傳入的訊息、更改其內部狀態並因此生成一些出站訊息。這與所謂的{\em Actor 模型}密切相關,該模型用於 Erlang 等語言(但是,Erlang 中的 actor 通常稱為「進程」)。由於現有 actor 也允許作為處理入站訊息的結果建立新的 actor(即智慧合約),因此與 Actor 模型的對應關係本質上是完整的。
\nxsubpoint \embt(訊息接收者。) 任何訊息都有其{\em 接收者},由{\em 目標工作鏈識別符 $w$}(預設假定與原始分片鏈相同)和{\em 接收者帳戶 $\accountid$} 表徵。$\accountid$ 的確切格式(即位元數)取決於 $w$;然而,分片始終由其前(最高有效)64 位元確定。
\nxsubpoint\label{sp:msg.sender} \embt(訊息傳送者。) 在大多數情況下,訊息有一個{\em 傳送者},再次由 $(w',\accountid')$ 對表徵。如果存在,它位於訊息接收者和訊息值之後。有時,傳送者不重要或它是區塊鏈外部的某人(即不是智慧合約),在這種情況下,此欄位不存在。
請注意,Actor 模型不要求訊息具有隱式傳送者。相反,訊息可能包含對應答請求應傳送到的 Actor 的引用;通常它與傳送者一致。然而,在加密貨幣(拜占庭)環境中,在訊息中有一個明確的不可偽造的傳送者欄位是有用的。
\nxsubpoint \embt(訊息值。) 訊息的另一個重要特徵是其附加的{\em 值},以來源和目標工作鏈都支援的一種或幾種加密貨幣表示。訊息的值在訊息接收者之後的最開始處指示;它本質上是 $(\currencyid,\vr{value})$ 對的列表。
請注意,「簡單」帳戶之間的「簡單」價值轉移只是附加了一些值的空(無操作)訊息。另一方面,稍微複雜一點的訊息正文可能包含簡單的文字或二進位註解(例如,關於支付的目的)。
\nxsubpoint\label{sp:ext.msg} \embt(外部訊息,或「來自無處的訊息」。) 一些訊息「來自無處」進入系統——也就是說,它們不是由駐留在區塊鏈中的帳戶(智慧合約或非智慧合約)生成的。最典型的例子是當使用者想要從她控制的帳戶轉移一些資金到其他帳戶時。在這種情況下,使用者向她自己的帳戶傳送一個「來自無處的訊息」,請求它生成一個訊息到接收帳戶,攜帶指定的值。如果此訊息被正確簽名,她的帳戶接收它並生成所需的出站訊息。
事實上,人們可以將「簡單」帳戶視為具有預定義程式碼的智慧合約的特例。此智慧合約僅接收一種類型的訊息。這樣的入站訊息必須包含作為傳遞(處理)入站訊息的結果要生成的出站訊息列表,以及簽名。智慧合約檢查簽名,如果正確,則生成所需的訊息。
當然,「來自無處的訊息」和正常訊息之間存在差異,因為「來自無處的訊息」不能攜帶值,因此它們本身無法支付其「gas」(即其處理)。相反,它們在甚至被建議包含在新的分片鏈區塊中之前,使用小的 gas 限制進行試探性執行;如果執行失敗(簽名不正確),則「來自無處的訊息」被視為不正確並被丟棄。如果執行在小 gas 限制內沒有失敗,則訊息可能被包含在新的分片鏈區塊中並被完全處理,從接收者的帳戶中收取消耗的 gas(處理能力)的支付。「來自無處的訊息」還可以定義一些交易費用,這些費用從接收者的帳戶中扣除,除了 gas 支付之外,用於重新分配給驗證者。
在這個意義上,「來自無處的訊息」或「外部訊息」扮演其他區塊鏈系統(例如,Bitcoin 和 Ethereum)中使用的交易候選的角色。
\nxsubpoint \embt(日誌訊息,或「通向無處的訊息」。) 類似地,有時可以生成特殊訊息並路由到特定分片鏈,不是為了傳遞給其接收者,而是為了被記錄,以便接收有關該分片的更新的任何人都能輕鬆觀察到。這些記錄的訊息可能在使用者的控制台中輸出,或觸發在鏈下伺服器上執行某些腳本。在這個意義上,它們代表「區塊鏈超級電腦」的外部「輸出」,正如「來自無處的訊息」代表「區塊鏈超級電腦」的外部「輸入」一樣。
\nxsubpoint \embt(與鏈下服務和外部區塊鏈的互動。) 這些外部輸入和輸出訊息可用於與鏈下服務和其他(外部)區塊鏈(例如 Bitcoin 或 Ethereum)互動。人們可以在 TON 區塊鏈內建立與 Bitcoin、Ether 或 Ethereum 區塊鏈中定義的任何 ERC-20 代幣掛鉤的代幣或加密貨幣,並使用由駐留在某些第三方鏈下伺服器上的腳本生成和處理的「來自無處的訊息」和「通向無處的訊息」,來實作 TON 區塊鏈與這些外部區塊鏈之間的必要互動。
\nxsubpoint \embt(訊息正文。) {\em 訊息正文}只是位元組序列,其含義僅由接收工作鏈和/或智慧合約確定。對於使用 TON VM 的區塊鏈,這可能是任何 TVM 單元的序列化,透過 \texttt{Send()} 操作自動生成。這種序列化只需遞迴地將 TON VM 單元中的所有引用替換為所引用的單元即可獲得。最終,出現一個原始位元組字串,通常在前面加上 4 位元組的「訊息類型」或「訊息建構子」,用於選擇接收智慧合約的正確方法。
另一個選項是使用 TL 序列化物件(參見~\ptref{sp:TL})作為訊息正文。這對於不同工作鏈之間的通訊可能特別有用,其中一個或兩個工作鏈不一定使用 TON VM。
\nxsubpoint \embt(Gas 限制和其他工作鏈/VM 特定參數。) 有時訊息需要攜帶有關 gas 限制、gas 價格、交易費用和類似值的資訊,這些資訊取決於接收工作鏈並且僅與接收工作鏈相關,但不一定與原始工作鏈相關。這些參數包含在訊息正文中或之前,有時(取決於工作鏈)帶有指示其存在的特殊 4 位元組前綴(可以由 TL-方案定義;參見~\ptref{sp:TL})。
\nxsubpoint \embt(建立訊息:智慧合約和交易。) 有兩個新訊息的來源。大多數訊息是在智慧合約執行期間建立的(透過 TON VM 中的 \texttt{Send()} 操作),當呼叫某個智慧合約來處理傳入訊息時。或者,訊息可能作為「外部訊息」或「來自無處的訊息」從外部進入(參見~\ptref{sp:ext.msg})。\footnote{以上內容只需對基本工作鏈及其分片鏈字面上為真;其他工作鏈可能提供建立訊息的其他方式。}
\nxsubpoint \embt(傳遞訊息。) 當訊息到達包含其目的帳戶的分片鏈時,\footnote{作為退化情況,此分片鏈可能與原始分片鏈一致——例如,如果我們在尚未拆分的工作鏈內工作。}它被「傳遞」到其目的帳戶。接下來發生的事情取決於工作鏈;從外部角度來看,重要的是這樣的訊息永遠不能從此分片鏈進一步轉發。
對於基本工作鏈的分片鏈,傳遞包括將訊息值(減去任何 gas 支付)新增到接收帳戶的餘額中,並且如果接收帳戶是智慧合約,則可能在之後呼叫接收智慧合約的訊息依賴方法。事實上,智慧合約只有一個入口點來處理所有傳入訊息,它必須透過查看訊息的前幾個位元組(例如,包含 TL 建構子的前四個位元組;參見~\ptref{sp:TL})來區分不同類型的訊息。
\nxsubpoint \embt(訊息的傳遞是一個交易。) 由於訊息的傳遞會更改帳戶或智慧合約的狀態,因此它是接收分片鏈中的特殊{\em 交易},並明確註冊為交易。本質上,{\em 所有\/} TON 區塊鏈交易都包括將一個入站訊息傳遞到其接收帳戶(智慧合約),忽略一些次要的技術細節。
\nxsubpoint \embt(同一智慧合約實例之間的訊息。) 回想一下,智慧合約可能是{\em 本地的}(即,像任何普通帳戶一樣駐留在一個分片鏈中)或{\em 全域的}(即,在所有分片中都有實例,或至少在深度 $d$ 以下的所有分片中都有實例;參見~\ptref{sp:loc.glob.smct})。如果需要,全域智慧合約的實例可以交換特殊訊息以在彼此之間轉移資訊和價值。在這種情況下,(不可偽造的)傳送者 $\accountid$ 變得重要(參見~\ptref{sp:msg.sender})。
\nxsubpoint \embt(向智慧合約的任何實例傳送訊息;萬用字元地址。) 有時訊息(例如,客戶端請求)需要傳遞到全域智慧合約的任何實例,通常是最近的實例(如果有一個與傳送者駐留在同一分片鏈中,則它是明顯的候選者)。一種方法是使用「萬用字元接收者地址」,目的 $\accountid$ 的前 $d$ 位元允許採用任意值。在實踐中,通常將這 $d$ 位元設定為與傳送者的 $\accountid$ 中相同的值。
\nxsubpoint \embt(輸入佇列不存在。) 區塊鏈(通常是分片鏈;有時是主鏈)接收的所有訊息——或者本質上,駐留在某個分片鏈內的「帳戶鏈」接收的所有訊息——都會立即傳遞(即由接收帳戶處理)。因此,不存在「輸入佇列」。相反,如果由於對區塊總大小和 gas 使用的限制而無法處理所有目的為特定分片鏈的訊息,則一些訊息只是留在原始分片鏈的輸出佇列中累積。
\nxsubpoint\label{sp:out.queue} \embt(輸出佇列。) 從無限分片範式的角度來看(參見~\ptref{sp:ISP}),每個帳戶鏈(即每個帳戶)都有自己的輸出佇列,包含它已生成但尚未傳遞給其接收者的所有訊息。當然,帳戶鏈只有虛擬存在;它們被分組為分片鏈,分片鏈有一個輸出「佇列」,由屬於分片鏈的所有帳戶的輸出佇列的聯集組成。
此分片鏈輸出「佇列」僅對其成員訊息施加部分順序。也就是說,在前一個區塊中生成的訊息必須在後續區塊中生成的任何訊息之前傳遞,並且由同一帳戶生成且具有相同目的地的任何訊息必須按其生成順序傳遞。
\nxsubpoint\label{sp:intershard.msgs} \embt(可靠且快速的鏈間訊息傳遞。) 對於像 TON 這樣的可擴展多區塊鏈專案來說,能夠在不同分片鏈之間轉發和傳遞訊息(參見~\ptref{sp:msg.IHR})至關重要,即使系統中有數百萬個分片鏈。訊息應該{\em 可靠地}傳遞(即,訊息不應丟失或傳遞超過一次)且{\em 快速}。TON 區塊鏈透過使用兩種「訊息路由」機制的組合來實現這一目標。
\nxsubpoint\label{sp:hypercube} \embt(超立方體路由:保證傳遞訊息的「慢路徑」。) TON 區塊鏈使用「超立方體路由」作為一種緩慢但安全可靠的方式,將訊息從一個分片鏈傳遞到另一個分片鏈,如有必要,使用幾個中間分片鏈進行中轉。否則,任何給定分片鏈的驗證者將需要追蹤所有其他分片鏈的狀態(輸出佇列),隨著分片鏈總數的增長,這將需要令人望而卻步的計算能力和網路頻寬,從而限制系統的可擴展性。因此,不可能直接從任何分片將訊息傳遞到每個其他分片。相反,每個分片僅「連接」到其 $(w,s)$ 分片識別符(參見~\ptref{sp:shard.ident})中恰好一個十六進位數字不同的分片。透過這種方式,所有分片鏈構成一個「超立方體」圖,訊息沿著此超立方體的邊傳播。
如果訊息被傳送到與當前分片不同的分片,則當前分片識別符的十六進位數字之一(確定性選擇)被目標分片的相應數字替換,所得識別符用作轉發訊息的近似目標。\footnote{這不一定是用於計算超立方體路由下一跳的演算法的最終版本。特別是,十六進位數字可能被 $r$ 位元組替換,其中 $r$ 是可設定參數,不一定等於四。}
超立方體路由的主要優點是,區塊有效性條件意味著建立分片鏈區塊的驗證者必須從「鄰近」分片鏈的輸出佇列收集和處理訊息,否則將失去其權益。透過這種方式,任何訊息都可以預期遲早到達其最終目的地;訊息不會在中轉中丟失或被傳遞兩次。
請注意,超立方體路由會引入一些額外的延遲和費用,因為需要透過幾個中間分片鏈轉發訊息。然而,這些中間分片鏈的數量增長非常緩慢,為分片鏈總數 $N$ 的對數 $\log N$(更準確地說,$\lceil\log_{16}N\rceil-1$)。例如,如果 $N\approx250$,最多有一個中間跳;對於 $N\approx4000$ 個分片鏈,最多兩個。有四個中間跳,我們可以支援多達一百萬個分片鏈。我們認為這是為系統本質上無限的可擴展性付出的非常小的代價。事實上,甚至不需要付出這個代價:
\nxsubpoint\label{sp:instant.hypercube} \embt(即時超立方體路由:訊息的「快路徑」。) TON 區塊鏈的一個新穎功能是它引入了一個「快路徑」,用於將訊息從一個分片鏈轉發到任何其他分片鏈,在大多數情況下允許完全繞過 \ptref{sp:hypercube} 的「慢」超立方體路由,並將訊息傳遞到最終目的分片鏈的下一個區塊中。
想法如下。在「慢」超立方體路由期間,訊息沿著超立方體的邊在(網路中)傳播,但在每個中間頂點被延遲(大約五秒),以便在繼續其旅程之前被提交到相應的分片鏈中。
為了避免不必要的延遲,可以改為沿著超立方體的邊與適當的 Merkle 證明一起轉發訊息,而無需等待將其提交到中間分片鏈。事實上,網路訊息應該從原始分片的「任務組」(參見~\ptref{sp:val.task.grp})的驗證者轉發到目的分片的「任務組」的指定區塊生產者(參見~\ptref{sp:rot.gen.prio});這可能直接完成,而不沿著超立方體的邊前進。當帶有 Merkle 證明的訊息到達目的分片鏈的驗證者(更準確地說,是整理者;參見~\ptref{sp:collators})時,他們可以立即將其提交到新區塊中,而無需等待訊息沿著「慢路徑」完成其旅程。然後,帶有適當 Merkle 證明的傳遞確認沿著超立方體邊傳送回來,它可用於透過提交特殊交易來停止訊息沿著「慢路徑」的傳播。
請注意,這種「即時傳遞」機制並不取代~\ptref{sp:hypercube} 中描述的「慢」但防故障的機制。「慢路徑」仍然需要,因為驗證者不能因丟失或簡單地決定不將「快路徑」訊息提交到其區塊鏈的新區塊中而受到懲罰。\footnote{然而,驗證者有一些激勵盡快這樣做,因為他們將能夠收取與訊息相關的所有尚未在慢路徑上消耗的轉發費用。}
因此,兩種訊息轉發方法並行執行,並且只有在「快」機制成功的證明被提交到中間分片鏈時,「慢」機制才會中止。\footnote{事實上,人們可能暫時或永久完全禁用「即時傳遞」機制,系統將繼續工作,儘管速度較慢。}
\nxsubpoint\label{sp:collect.input.msg} \embt(從鄰近分片鏈的輸出佇列收集輸入訊息。) 當為分片鏈提出新區塊時,鄰近(在 \ptref{sp:hypercube} 的路由超立方體意義上)分片鏈的一些輸出訊息作為「輸入」訊息包含在新區塊中並立即傳遞(即處理)。關於這些鄰居的輸出訊息必須以何種順序處理,有一些規則。本質上,「較舊」的訊息(來自引用較舊主鏈區塊的分片鏈區塊)必須在任何「較新」的訊息之前傳遞;對於來自同一鄰近分片鏈的訊息,必須遵守 \ptref{sp:out.queue} 中描述的輸出佇列的部分順序。
\nxsubpoint\label{sp:out.q.del} \embt(從輸出佇列刪除訊息。) 一旦輸出佇列訊息被觀察到已被鄰近分片鏈傳遞,它就會透過特殊交易明確地從輸出佇列中刪除。
\nxsubpoint\label{sp:deliver.q} \embt(防止訊息的雙重傳遞。) 為了防止從鄰近分片鏈的輸出佇列取出的訊息被雙重傳遞,每個分片鏈(更準確地說,其內部的每個帳戶鏈)將最近傳遞的訊息(或只是它們的雜湊)的集合保留為其狀態的一部分。當觀察到已傳遞的訊息被其原始鄰近分片鏈從輸出佇列中刪除(參見~\ptref{sp:out.q.del})時,它也從最近傳遞的訊息集合中刪除。
\nxsubpoint \embt(轉發目的為其他分片鏈的訊息。) 超立方體路由(參見~\ptref{sp:hypercube})意味著有時出站訊息不是傳遞到包含預期接收者的分片鏈,而是傳遞到位於通往目的地的超立方體路徑上的鄰近分片鏈。在這種情況下,「傳遞」包括將入站訊息移動到出站佇列。這在區塊中明確反映為特殊的{\em 轉發交易},包含訊息本身。本質上,這看起來彷彿訊息已被分片鏈內的某人接收,並因此生成了一個相同的訊息。
\nxsubpoint \embt(轉發和保留訊息的支付。) 轉發交易實際上花費一些 gas(取決於正在轉發的訊息的大小),因此代表此分片鏈的驗證者從正在轉發的訊息的值中扣除 gas 支付。這種轉發支付通常遠小於訊息最終傳遞給其接收者時收取的 gas 支付,即使訊息由於超立方體路由而被轉發多次。此外,只要訊息保留在某個分片鏈的輸出佇列中,它就是分片鏈全域狀態的一部分,因此也可以透過特殊交易收取長期保留全域資料的支付。
\nxsubpoint \embt(往返主鏈的訊息。) 訊息可以直接從任何分片鏈傳送到主鏈,反之亦然。然而,向主鏈傳送訊息和在主鏈中處理訊息的 gas 價格相當高,因此只有在真正必要時才會使用此能力——例如,驗證者存入其權益。在某些情況下,可以為傳送到主鏈的訊息定義最小存款(附加值),只有在接收方認為訊息「有效」時才會返回。
訊息不能自動透過主鏈路由。具有 $\workchainid\neq-1$($-1$ 是指示主鏈的特殊 $\workchainid$)的訊息不能傳遞到主鏈。
原則上,可以在主鏈內建立訊息轉發智慧合約,但使用它的價格將是令人望而卻步的。
\nxsubpoint \embt(同一分片鏈中帳戶之間的訊息。) 在某些情況下,訊息由屬於某個分片鏈的帳戶生成,目的地是同一分片鏈中的另一個帳戶。例如,這發生在尚未拆分為多個分片鏈的新工作鏈中,因為負載是可管理的。
此類訊息可能累積在分片鏈的輸出佇列中,然後在後續區塊中作為傳入訊息處理(為此目的,任何分片都被視為自己的鄰居)。然而,在大多數情況下,可以在原始區塊本身內傳遞這些訊息。
為了實現這一點,對分片鏈區塊中包含的所有交易施加部分順序,並且交易(每個由向某個帳戶傳遞訊息組成)在遵守此部分順序的情況下處理。特別是,允許交易處理相對於此部分順序的前一個交易的某個輸出訊息。
在這種情況下,訊息正文不會被複製兩次。相反,原始交易和處理交易引用訊息的共享副本。
\mysubsection{全域分片鏈狀態。「單元集合」理念。}
現在我們準備描述 TON 區塊鏈的全域狀態,或至少是基本工作鏈的分片鏈的全域狀態。
我們從「高階」或「邏輯」描述開始,它包括說全域狀態是代數類型 $\tp{ShardchainState}$ 的值。
\nxsubpoint\label{sp:shard.state} \embt(分片鏈狀態作為帳戶鏈狀態的集合。) 根據無限分片範式(參見~\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} 是分片鏈全域狀態的良好第一近似,至少從「邏輯」(「高階」)角度來看是這樣。代數類型 $\tp{AccountState}$ 和 $\tp{ShardchainState}$ 的正式描述可以藉助 TL-方案(參見~\ptref{sp:TL})完成,將在別處提供。
\nxsubpoint\label{sp:split.merge.state} \embt(拆分和合併分片鏈狀態。) 請注意,分片鏈狀態 \eqref{eq:simple.shard.st} 的無限分片範式描述顯示了當分片拆分或合併時應如何處理此狀態。事實上,這些狀態轉換變得是雜湊映射的非常簡單的操作。
\nxsubpoint \embt(帳戶鏈狀態。) (虛擬)帳戶鏈狀態只是一個帳戶的狀態,由類型 $\tp{AccountState}$ 描述。通常它具有~\ptref{sp:account.state} 中列出的所有或部分欄位,取決於使用的特定建構子。
\nxsubpoint \embt(全域工作鏈狀態。) 類似於 \eqref{eq:simple.shard.st},我們可以透過相同的公式定義全域{\em 工作鏈}狀態,但 $\accountid$ 允許採用任何值,而不僅僅是屬於一個分片的值。類似於~\ptref{sp:shard.state} 中所做的備註在這種情況下也適用:我們可能想要將此雜湊映射拆分為幾個雜湊映射,我們可能想要新增一些「積分」參數,例如總餘額。
本質上,全域工作鏈狀態{\em 必須}由與分片鏈狀態相同的類型 $\tp{ShardchainState}$ 給出,因為它是我們將獲得的分片鏈狀態,如果該工作鏈的所有現有分片鏈突然合併為一個。
\nxsubpoint\label{sp:bag.of.cells} \embt(低階視角:「單元集合」。) 帳戶鏈或分片鏈狀態也有一個「低階」描述,補充上面給出的「高階」描述。這個描述非常重要,因為事實證明它非常通用,為透過網路表示、儲存、序列化和傳輸幾乎所有 TON 區塊鏈使用的資料(區塊、分片鏈狀態、智慧合約儲存、Merkle 證明等)提供了通用基礎。與此同時,這種通用的「低階」描述,一旦被理解和實現,使我們能夠只專注於「高階」考慮。
回想一下,TVM 透過{\em TVM 單元}或簡稱{\em 單元}的樹來表示任意代數類型的值(例如,\eqref{eq:simple.shard.st} 的 $\tp{ShardchainState}$)(參見~\ptref{sp:tvm.cells} 和~\ptref{sp:TL})。
任何這樣的單元都由兩個{\em 描述符位元組}組成,定義某些旗標和值 $0\leq b\leq 128$(原始位元組的數量)和 $0\leq c\leq 4$(對其他單元的參照數量)。然後是 $b$ 個原始位元組和 $c$ 個單元參照。\footnote{可以證明,如果需要同樣經常地對儲存在單元樹中的所有資料進行 Merkle 證明,則應使用 $b+ch\approx 2(h+r)$ 的單元來最小化平均 Merkle 證明大小,其中 $h=32$ 是雜湊大小(以位元組為單位),$r\approx4$ 是單元參照的「位元組大小」。換句話說,一個單元應該包含兩個參照和幾個原始位元組,或者一個參照和大約 36 個原始位元組,或者根本沒有參照但有 72 個原始位元組。}
單元參照的確切格式取決於實作以及單元是位於 RAM、磁碟、網路封包、區塊中等等。一個有用的抽象模型是想像所有單元都保存在內容定址記憶體中,單元的地址等於其($\Sha$)雜湊。回想一下,單元的(Merkle)雜湊正是透過將對其子單元的參照替換為它們的(遞迴計算的)雜湊並雜湊結果位元組字串來計算的。
透過這種方式,如果我們使用單元雜湊來參照單元(例如,在其他單元的描述中),系統會有所簡化,並且單元的雜湊開始與表示它的位元組字串的雜湊一致。
現在我們看到{\em 任何可由 TVM 表示的物件,包括全域分片鏈狀態,都可以表示為「單元集合」}——即{\em 單元的集合以及對其中一個單元的「根」參照}(例如,透過雜湊)。請注意,重複的單元從此描述中移除(「單元集合」是單元的集合,而不是單元的多重集合),因此抽象樹表示實際上可能變成有向無環圖(dag)表示。
甚至可以將此狀態保存在磁碟上的 $B$-樹或 $B+$-樹中,包含所有相關單元(可能還有一些附加資料,例如子樹高度或參照計數器),按單元雜湊索引。然而,這個想法的天真實作將導致一個智慧合約的狀態分散在磁碟檔案的遙遠部分,這是我們寧願避免的。%
\footnote{更好的實作是將智慧合約的狀態保存為序列化字串(如果它很小),或保存在單獨的 $B$-樹中(如果它很大);然後表示區塊鏈狀態的頂層結構將是一個 $B$-樹,其葉節點允許包含對其他 $B$-樹的參照。}
現在我們將詳細解釋 TON 區塊鏈使用的幾乎所有物件如何表示為「單元集合」,從而證明這種方法的通用性。
\nxsubpoint \embt(分片鏈區塊作為「單元集合」。) 分片鏈區塊本身也可以由代數類型描述,並儲存為「單元集合」。然後,可以簡單地透過以任意順序連接表示「單元集合」中每個單元的位元組字串來獲得區塊的天真二進位表示。這種表示可以改進和最佳化,例如,透過在區塊開頭提供所有單元的偏移列表,並在可能的情況下用此列表中的 32 位元索引替換對其他單元的雜湊參照。然而,人們應該想像一個區塊本質上是一個「單元集合」,而所有其他技術細節只是次要的最佳化和實作問題。
\nxsubpoint\label{sp:obj.update} \embt(物件更新作為「單元集合」。) 想像我們有一個物件的舊版本,表示為「單元集合」,並且我們想要表示同一物件的新版本,假設與前一個版本沒有太大不同。可以簡單地將新狀態表示為另一個具有自己根的「單元集合」,{\em 並從中移除舊版本中出現的所有單元}。剩餘的「單元集合」本質上是物件的{\em 更新}。擁有此物件舊版本和更新的每個人都可以計算新版本,只需聯合兩個單元集合,並移除舊根(減少其參照計數器,如果參照計數器變為零則解除配置該單元)。
\nxsubpoint \embt(帳戶狀態的更新。) 特別地,帳戶狀態的更新,或分片鏈的全域狀態的更新,或任何雜湊映射的更新,都可以使用~\ptref{sp:obj.update} 中描述的想法來表示。這意味著當我們接收到一個新的分片鏈區塊(它是一個「單元集合」)時,我們不僅僅透過它本身來解釋這個「單元集合」,而是首先將它與表示分片鏈先前狀態的「單元集合」聯合。從這個意義上說,每個區塊都可能「包含」區塊鏈的整個狀態。
\nxsubpoint \embt(區塊的更新。) 回想一下,區塊本身就是一個「單元集合」,因此,如果需要編輯區塊,同樣可以將「區塊更新」定義為「單元集合」,在此區塊先前版本的「單元集合」存在下進行解釋。這大致上就是~\ptref{sp:inv.sh.blk.corr} 中討論的「垂直區塊」背後的想法。
\nxsubpoint\label{sp:merkle.as.BoC} \embt(Merkle 證明作為「單元集合」。) 請注意,(廣義的)Merkle 證明——例如,從 $\Hash(x)=h$ 的已知值開始斷言 $x[i]=y$(參見~\ptref{sp:merkle.proof} 和~\ptref{sp:gen.merkle.proof})——也可以表示為「單元集合」。也就是說,只需提供對應於從 $x:\Hashmap(n,X)$ 的根到其所需葉(索引為 $i:\st2^n$,值為 $y:X$)的路徑的單元子集。對不在此路徑上的這些單元的子單元的參照將在此證明中保持「未解析」,由單元雜湊表示。還可以提供同時的 Merkle 證明,比如 $x[i]=y$ 和 $x[i']=y'$,方法是在「單元集合」中包含從 $x$ 的根到對應於索引 $i$ 和 $i'$ 的葉的兩條路徑的聯合上的單元。
\nxsubpoint\label{sp:merkle.query.resp} \embt(Merkle 證明作為全節點的查詢回應。) 本質上,擁有完整分片鏈(或帳戶鏈)狀態副本的全節點可以在輕節點(例如,執行 TON 區塊鏈用戶端輕量版本的網路節點)請求時提供 Merkle 證明,使接收者能夠在沒有外部幫助的情況下執行一些簡單的查詢,僅使用此 Merkle 證明中提供的單元。輕節點可以以序列化格式將其查詢傳送到全節點,並接收帶有 Merkle 證明的正確答案——或者只是 Merkle 證明,因為請求者應該能夠僅使用 Merkle 證明中包含的單元來計算答案。此 Merkle 證明將簡單地由「單元集合」組成,僅包含在執行輕節點查詢時全節點存取的屬於分片鏈狀態的那些單元。這種方法特別可用於執行智慧合約的「取得查詢」(參見~\ptref{sp:tent.exec.get})。
\nxsubpoint\label{sp:aug.upd} \embt(增強更新,或帶有有效性 Merkle 證明的狀態更新。) 回想一下(參見~\ptref{sp:obj.update}),我們可以透過「更新」來描述物件狀態從舊值 $x:X$ 到新值 $x':X$ 的變化,該「更新」只是一個「單元集合」,包含那些位於表示新值 $x'$ 的子樹中但不在表示舊值 $x$ 的子樹中的單元,因為假設接收者擁有舊值 $x$ 及其所有單元的副本。
然而,如果接收者沒有 $x$ 的完整副本,而只知道其(Merkle)雜湊 $h=\Hash(x)$,它將無法檢查更新的有效性(即,更新中所有「懸掛」的單元參照確實參照到 $x$ 的樹中存在的單元)。人們希望擁有「可驗證」的更新,透過舊狀態中所有被參照單元存在性的 Merkle 證明來增強。然後,任何只知道 $h=\Hash(x)$ 的人都能夠檢查更新的有效性,並自己計算新的 $h'=\Hash(x')$。
因為我們的 Merkle 證明本身就是「單元集合」(參見~\ptref{sp:merkle.as.BoC}),可以將這樣的{\em 增強更新}構造為「單元集合」,包含 $x$ 的舊根、它的一些後代以及從 $x$ 的根到它們的路徑,以及 $x'$ 的新根和所有不屬於 $x$ 的後代。
\nxsubpoint \embt(分片鏈區塊中的帳戶狀態更新。) 特別地,分片鏈區塊中的帳戶狀態更新應如~\ptref{sp:aug.upd} 中討論的那樣進行增強。否則,某人可能會提交包含無效狀態更新的區塊,參照到舊狀態中不存在的單元;證明這樣的區塊無效將是有問題的(挑戰者如何證明一個單元{\em 不是}先前狀態的一部分?)。
現在,如果區塊中包含的所有狀態更新都被增強,它們的有效性很容易檢查,它們的無效性也很容易顯示為違反(廣義)Merkle 雜湊的遞迴定義屬性。
\nxsubpoint\label{sp:everything.is.BoC} \embt(「一切皆為單元集合」理念。) 之前的考慮表明,我們需要儲存或傳輸的所有內容,無論是在 TON 區塊鏈中還是在網路中,都可以表示為「單元集合」。這是 TON 區塊鏈設計理念的重要組成部分。一旦解釋了「單元集合」方法並定義了一些「單元集合」的「低階」序列化,就可以簡單地在抽象(相依)代數資料類型的高階上定義一切(區塊格式、分片鏈和帳戶狀態等)。
「一切皆為單元集合」理念的統一效果大大簡化了看似無關的服務的實作;參見~\ptref{sp:ton.smart.pc.supp} 以獲取涉及支付通道的範例。
\nxsubpoint \embt(TON 區塊鏈的區塊「標頭」。) 通常,區塊鏈中的區塊以小標頭開始,包含前一個區塊的雜湊、其建立時間、區塊中包含的所有交易樹的 Merkle 雜湊等等。然後將區塊雜湊定義為此小區塊標頭的雜湊。因為區塊標頭最終取決於區塊中包含的所有資料,所以不能在不改變其雜湊的情況下更改區塊。
在 TON 區塊鏈的區塊使用的「單元集合」方法中,沒有指定的區塊標頭。相反,區塊雜湊被定義為區塊根單元的(Merkle)雜湊。因此,區塊的頂(根)單元可能被視為該區塊的小「標頭」。
然而,根單元可能不包含通常從這種標頭預期的所有資料。本質上,人們希望標頭包含 $\Block$ 資料類型中定義的某些欄位。通常,這些欄位將包含在幾個單元中,包括根單元。這些單元共同構成相關欄位值的「Merkle 證明」。可能會堅持要求區塊在其他任何單元之前,在最開始就包含這些「標頭單元」。然後,只需下載區塊序列化的前幾個位元組,就可以獲得所有「標頭單元」,並了解所有預期的欄位。
\mysubsection{建立和驗證新區塊}\label{sect:validators}
TON 區塊鏈最終由分片鏈和主鏈區塊組成。必須建立、驗證這些區塊並透過網路傳播到所有相關方,系統才能順利正確地運作。
\nxsubpoint\label{sp:validators} \embt(驗證者。) 新區塊由稱為{\em 驗證者}的特殊指定節點建立和驗證。本質上,任何希望成為驗證者的節點都可以成為驗證者,前提是它可以將足夠大的質押(以 TON 幣,即 Grams;參見附錄~\ptref{app:coins})存入主鏈。驗證者因良好的工作而獲得一些「獎勵」,即來自所有交易(訊息)的交易費、儲存費和燃料費,這些交易被提交到新生成的區塊中,以及一些新鑄造的代幣,反映了整個社群對驗證者保持 TON 區塊鏈運作的「感謝」。這筆收入按質押比例分配給所有參與的驗證者。
然而,成為驗證者是一項高度責任。如果驗證者簽署了一個無效的區塊,它可能會受到懲罰,失去部分或全部質押,並被暫時或永久排除在驗證者集合之外。如果驗證者不參與建立區塊,它不會收到與該區塊相關的獎勵份額。如果驗證者長時間放棄建立新區塊,它可能會失去部分質押並被暫停或永久排除在驗證者集合之外。
所有這些都意味著驗證者不是「憑空」獲得金錢。事實上,它必須追蹤所有或部分分片鏈的狀態(每個驗證者負責驗證和建立某個分片鏈子集中的新區塊),執行這些分片鏈中智慧合約請求的所有計算,接收有關其他分片鏈的更新等等。這項活動需要相當大的磁碟空間、計算能力和網路頻寬。
\nxsubpoint \embt(驗證者而非礦工。) 回想一下,TON 區塊鏈使用權益證明方法,而不是比特幣、當前版本的以太坊和大多數其他加密貨幣採用的工作量證明方法。這意味著無法透過提供某些工作量證明(計算大量無用的雜湊)來「挖掘」新區塊並因此獲得一些新代幣。相反,必須成為驗證者並花費計算資源來儲存和處理 TON 區塊鏈請求和資料。簡而言之,{\em 必須成為驗證者才能挖掘新代幣。}在這方面,{\em 驗證者是新的礦工。}
然而,除了成為驗證者之外,還有一些其他方式可以賺取代幣。
\nxsubpoint\label{sp:nominators} \embt(提名者和「礦池」。) 要成為驗證者,通常需要購買和安裝幾台高效能伺服器,並為它們取得良好的網際網路連線。這不像目前挖掘比特幣所需的 ASIC 裝置那麼昂貴。然而,絕對不能在家用電腦上挖掘新的 TON 代幣,更不用說智慧型手機了。
在比特幣、以太坊和其他工作量證明加密貨幣挖礦社群中,有{\em 礦池}的概念,其中許多節點的計算能力不足以單獨挖掘新區塊,它們結合努力並在之後分享獎勵。
權益證明世界中的對應概念是{\em 提名者}。本質上,這是一個節點將其資金借給驗證者以幫助增加其質押;然後驗證者將其獎勵的相應份額(或一些先前商定的分數——比如 50\%)分配給提名者。
透過這種方式,提名者也可以參與「挖礦」並獲得與其願意為此目的存入的金額成正比的一些獎勵。它只收到驗證者獎勵的相應份額的一小部分,因為它只提供「資本」,但不需要購買計算能力、儲存和網路頻寬。
然而,如果驗證者因無效行為而失去其質押,提名者也會失去其質押份額。從這個意義上說,提名者{\em 分擔風險}。它必須明智地選擇其提名的驗證者,否則可能會賠錢。從這個意義上說,提名者做出加權決定並用他們的資金為某些驗證者「投票」。
另一方面,這種提名或借貸系統使人們能夠在不先投資大量 Grams(TON 幣)的情況下成為驗證者。換句話說,它防止那些持有大量 Grams 的人壟斷驗證者的供應。
\nxsubpoint\label{sp:fish} \embt(漁夫:透過指出他人的錯誤來獲得金錢。) 在不成為驗證者的情況下獲得獎勵的另一種方式是成為{\em 漁夫}。本質上,任何節點都可以透過在主鏈中進行小額存款來成為漁夫。然後,它可以使用特殊的主鏈交易來發布先前由驗證者簽署和發布的某些(通常是分片鏈)區塊的(Merkle)無效性證明。如果其他驗證者同意此無效性證明,則違規的驗證者將受到懲罰(失去部分質押),漁夫將獲得一些獎勵(從違規驗證者那裡沒收的代幣的一小部分)。之後,必須按照~\ptref{sp:inv.sh.blk.corr} 中概述的方式更正無效的(分片鏈)區塊。更正無效的主鏈區塊可能涉及在先前提交的主鏈區塊之上建立「垂直」區塊(參見~\ptref{sp:inv.sh.blk.corr});無需建立主鏈的分叉。
通常,漁夫需要至少成為某些分片鏈的全節點,並透過執行至少某些智慧合約的程式碼來花費一些計算資源。雖然漁夫不需要擁有與驗證者一樣多的計算能力,但我們認為成為漁夫的自然候選者是準備處理新區塊但尚未當選為驗證者的準驗證者(例如,因為未能存入足夠大的質押)。
\nxsubpoint\label{sp:collators} \embt(整理者:透過向驗證者建議新區塊來獲得金錢。) 在不成為驗證者的情況下獲得獎勵的另一種方式是成為{\em 整理者}。這是一個節點,它準備並向驗證者建議新的分片鏈區塊候選,並用從該分片鏈和其他(通常是相鄰的)分片鏈的狀態中取得的資料以及適當的 Merkle 證明進行補充(整理)。(例如,當需要從相鄰分片鏈轉發某些訊息時,這是必要的。)然後,驗證者可以輕鬆檢查提議的區塊候選的有效性,而無需下載此或其他分片鏈的完整狀態。
因為驗證者需要提交新的(整理的)區塊候選以獲得一些(「挖礦」)獎勵,所以將獎勵的一部分支付給願意提供合適區塊候選的整理者是有意義的。透過這種方式,驗證者可以透過將監視相鄰分片鏈的狀態外包給整理者來解放自己,而無需親自監視。
然而,我們預計在系統的初始部署階段不會有單獨的指定整理者,因為所有驗證者都能夠為自己充當整理者。
\nxsubpoint \embt(整理者或驗證者:透過包含使用者交易來獲得金錢。) 使用者可以向某些整理者或驗證者開啟小額支付通道,並支付少量代幣以換取在分片鏈中包含他們的交易。
\nxsubpoint\label{sp:global.valid} \embt(全域驗證者集合選舉。) 「全域」驗證者集合每月選舉一次(實際上,每 $2^{19}$ 個主鏈區塊)。此集合提前一個月確定並普遍知曉。
為了成為驗證者,節點必須將一些 TON 幣(Grams)轉入主鏈,然後將它們傳送到特殊智慧合約作為其建議的質押 $s$。與質押一起傳送的另一個參數是 $l\geq 1$,該節點願意接受的相對於最小可能值的最大驗證負載。$l$ 還有一個全域上限(另一個可配置參數)$L$,例如等於 10。
然後,全域驗證者集合由此智慧合約選舉,只需選擇最多 $T$ 個具有最大建議質押的候選人並發布他們的身份。最初,驗證者總數為 $T=100$;我們預計隨著負載的增加,它將增長到 1000。這是一個可配置參數(參見~\ptref{sp:config.param})。
每個驗證者的實際質押計算如下:如果前 $T$ 個提議的質押為 $s_1\geq s_2\geq\cdots\geq s_T$,則第 $i$ 個驗證者的實際質押設定為 $s'_i:=\min(s_i,l_i\cdot s_T)$。透過這種方式,$s'_i/s'_T\leq l_i$,因此第 $i$ 個驗證者獲得的負載不會超過最弱驗證者的 $l_i\leq L$ 倍(因為負載最終與質押成正比)。
然後,當選的驗證者可以撤回其質押的未使用部分 $s_i-s'_i$。不成功的驗證者候選人可以撤回其所有提議的質押。
每個驗證者發布其{\em 公開簽署金鑰},不一定等於質押來源帳戶的公鑰。\footnote{為每次驗證者選舉生成和使用新的金鑰對是有意義的。}
驗證者的質押被凍結,直到他們被選舉的期間結束,以及再多一個月,以防出現新的爭議(即,發現這些驗證者之一簽署的無效區塊)。之後,質押被退回,連同驗證者在此期間處理的交易中鑄造的代幣和費用的份額。
\nxsubpoint\label{sp:val.task.grp} \embt(驗證者「任務組」的選舉。) 整個全域驗證者集合(其中每個驗證者被認為存在的多重性等於其質押——否則驗證者可能會被誘使假設幾個身份並在它們之間分割其質押)僅用於驗證新的主鏈區塊。分片鏈區塊僅由驗證者的特別選定子集驗證,這些子集取自如~\ptref{sp:global.valid} 中所述選擇的全域驗證者集合。
這些驗證者「子集」或「任務組」,為每個分片定義,每小時輪換一次(實際上,每 $2^{10}$ 個主鏈區塊),並且提前一小時就知道,以便每個驗證者知道它需要驗證哪些分片,並可以為此做好準備(例如,透過下載缺失的分片鏈資料)。
用於為每個分片 $(w,s)$ 選擇驗證者任務組的演算法是確定性偽隨機的。它使用驗證者嵌入到每個主鏈區塊中的偽隨機數(透過使用閾值簽章的共識生成)來建立隨機種子,然後例如為每個驗證者計算 $\Hash(\code(w).\code(s).\vr{validator\_id}.\vr{rand\_seed})$。然後驗證者按此雜湊的值排序,並選擇前幾個,以便至少擁有總驗證者質押的 $20/T$ 並至少由 5 個驗證者組成。
此選擇可以由特殊智慧合約完成。在這種情況下,選擇演算法可以輕鬆升級,而無需透過~\ptref{sp:config.param} 中提到的投票機制進行硬分叉。到目前為止提到的所有其他「常數」(例如 $2^{19}$、$2^{10}$、$T$、20 和 5)也是可配置參數。
\nxsubpoint\label{sp:rot.gen.prio} \embt(每個任務組的輪換優先順序。) 根據前一個主鏈區塊的雜湊和(分片鏈)區塊序列號,在分片任務組的成員上施加了一定的「優先」順序。此順序是透過生成和排序一些雜湊來確定的,如上所述。
當需要生成新的分片鏈區塊時,被選擇來建立此區塊的分片任務組驗證者通常是關於此輪換「優先」順序的第一個。如果它未能建立區塊,第二或第三個驗證者可以這樣做。本質上,它們都可以建議其區塊候選,但由具有最高優先級的驗證者建議的候選應該作為拜占庭容錯(BFT)共識協議的結果獲勝。
\nxsubpoint\label{sp:sh.blk.cand.prop} \embt(分片鏈區塊候選的傳播。) 因為分片鏈任務組成員資格提前一小時就知道,他們的成員可以使用那段時間來建立專用的「分片驗證者多播覆蓋網路」,使用 TON 網路的一般機制(參見~\ptref{sect:overlay})。當需要生成新的分片鏈區塊時——通常在最近的主鏈區塊傳播後一到兩秒——每個人都知道誰擁有生成下一個區塊的最高優先級(參見~\ptref{sp:rot.gen.prio})。此驗證者將建立新的整理區塊候選,可以自己建立,也可以在整理者的幫助下建立(參見~\ptref{sp:collators})。驗證者必須檢查(驗證)此區塊候選(特別是如果它是由某個整理者準備的),並用其(驗證者)私鑰簽署它。然後,區塊候選使用預先安排的多播覆蓋網路傳播到任務組的其餘部分(任務組建立其自己的私有覆蓋網路,如~\ptref{sect:overlay} 中所述,然後使用~\ptref{sp:streaming.multicast} 中描述的串流多播協議的版本來傳播區塊候選)。
執行此操作的真正 BFT 方式是使用拜占庭多播協議,例如 Honey Badger BFT~\cite{HoneyBadger} 中使用的協議:透過 $(N,2N/3)$-擦除碼對區塊候選進行編碼,將結果資料的 $1/N$ 直接傳送到組的每個成員,並期望他們將其資料部分直接多播到組的所有其他成員。
然而,執行此操作的更快、更直接的方式(另參見 \ptref{sp:streaming.multicast})是將區塊候選分割為一系列簽署的 1 KB 區塊(「塊」),透過 Reed--Solomon 或噴泉碼(例如 RaptorQ 碼~\cite{RaptorQ} \cite{Raptor})增強其序列,並開始將塊傳輸到「多播網格」中的鄰居(即覆蓋網路),期望他們進一步傳播這些塊。一旦驗證者獲得足夠的塊來從中重建區塊候選,它就會簽署確認收據並透過其鄰居將其傳播到整個組。然後,其鄰居停止向它傳送新塊,但可以繼續傳送這些塊的(原始)簽章,相信此節點可以透過自己應用 Reed--Solomon 或噴泉碼(擁有所有必要的資料)來生成後續塊,將它們與簽章結合,並傳播到尚未準備好的鄰居。
如果「多播網格」(覆蓋網路)在移除所有「壞」節點後保持連線(回想一下,最多允許三分之一的節點以拜占庭方式變壞,即以任意惡意方式行事),則此演算法將盡快傳播區塊候選。
不僅指定的高優先級區塊建立者可以將其區塊候選多播到整個組。優先級第二和第三的驗證者可以開始多播他們的區塊候選,可以立即開始,也可以在未能從最高優先級驗證者接收到區塊候選後開始。然而,通常只有具有最大優先級的區塊候選將由所有(實際上,由任務組的至少三分之二)驗證者簽署並提交為新的分片鏈區塊。
\nxsubpoint \embt(區塊候選的驗證。) 一旦區塊候選被驗證者接收並檢查其發起驗證者的簽章,接收驗證者透過執行其中的所有交易並檢查其結果是否與聲稱的一致來檢查此區塊候選的有效性。從其他區塊鏈匯入的所有訊息必須由整理資料中的適當 Merkle 證明支援,否則區塊候選被視為無效(並且,如果將此證明提交到主鏈,已經簽署此區塊候選的驗證者可能會受到懲罰)。另一方面,如果發現區塊候選有效,接收驗證者會簽署它並將其簽章傳播到組中的其他驗證者,可以透過「網格多播網路」,也可以透過直接網路訊息。
我們想要強調的是,{\em 驗證者不需要存取此分片鏈或相鄰分片鏈的狀態即可檢查(整理的)區塊候選的有效性}。%
\footnote{一個可能的例外是相鄰分片鏈的輸出佇列狀態,需要保證~\ptref{sp:collect.input.msg} 中描述的訊息排序要求,因為在這種情況下 Merkle 證明的大小可能變得令人望而卻步。} 這允許驗證非常快速地進行(無需磁碟存取),並減輕驗證者的計算和儲存負擔(特別是如果他們願意接受外部整理者的服務來建立區塊候選)。
\nxsubpoint\label{sp:new.shardc.blk} \embt(下一個區塊候選的選舉。) 一旦區塊候選收集到任務組中至少三分之二(按質押)的驗證者的有效性簽章,它就有資格作為下一個分片鏈區塊提交。執行 BFT 協議以就選擇的區塊候選(可能提議了不止一個)達成共識,所有「好」驗證者更喜歡此輪具有最高優先級的區塊候選。由於執行此協議,區塊被至少三分之二的驗證者(按質押)的簽章增強。這些簽章不僅證明相關區塊的有效性,而且證明其被 BFT 協議選舉。之後,區塊(沒有整理資料)與這些簽章結合,以確定性方式序列化,並透過網路傳播到所有相關方。
\nxsubpoint \embt(驗證者必須保留他們簽署的區塊。) 在他們的任務組成員資格期間以及之後至少一個小時(或者說 $2^{10}$ 個區塊),驗證者預計會保留他們簽署和提交的區塊。未能向其他驗證者提供已簽署的區塊可能會受到懲罰。
\nxsubpoint \embt(將新分片鏈區塊的標頭和簽章傳播到所有驗證者。) 驗證者使用類似於為每個任務組建立的多播網格網路,將新生成的分片鏈區塊的標頭和簽章傳播到{\em 全域}驗證者集合。
\nxsubpoint\label{sp:new.master.blk} \embt(新主鏈區塊的生成。) 在生成所有(或幾乎所有)新分片鏈區塊之後,可以生成新的主鏈區塊。該過程本質上與分片鏈區塊相同(參見~\ptref{sp:new.shardc.blk}),不同之處在於{\em 所有}驗證者(或至少三分之二的驗證者)必須參與此過程。因為新分片鏈區塊的標頭和簽章被傳播到所有驗證者,每個分片鏈中最新區塊的雜湊可以且必須包含在新的主鏈區塊中。一旦這些雜湊被提交到主鏈區塊中,外部觀察者和其他分片鏈可以認為新的分片鏈區塊已提交且不可變(參見~\ptref{sp:sc.hash.mc})。
\nxsubpoint \embt(驗證者必須保留主鏈的狀態。) 主鏈和分片鏈之間的一個值得注意的區別是,所有驗證者預計會追蹤主鏈狀態,而不依賴整理資料。這很重要,因為驗證者任務組的知識是從主鏈狀態衍生的。
\nxsubpoint \embt(分片鏈區塊並行生成和傳播。) 通常,每個驗證者是幾個分片鏈任務組的成員;它們的數量(因此驗證者的負載)與驗證者的質押大致成正比。這意味著驗證者並行執行新分片鏈區塊生成協議的幾個實例。
\nxsubpoint \embt(減輕區塊保留攻擊。) 因為驗證者總集合在僅看到新分片鏈區塊的標頭和簽章後就將其雜湊插入主鏈,所以有一個很小的概率,生成此區塊的驗證者將串謀並試圖避免完整發布新區塊。這將導致相鄰分片鏈的驗證者無法建立新區塊,因為一旦新區塊的雜湊被提交到主鏈中,他們至少必須知道新區塊的輸出訊息佇列。
為了減輕這種情況,新區塊必須從其他一些驗證者(例如,相鄰分片鏈的任務組聯合的三分之二)收集簽章,證明這些驗證者確實擁有此區塊的副本,並願意在需要時將它們傳送給任何其他驗證者。只有在呈現這些簽章之後,新區塊的雜湊才能被包含在主鏈中。
\nxsubpoint \embt(主鏈區塊的生成晚於分片鏈區塊。) 主鏈區塊大約每五秒生成一次,分片鏈區塊也是如此。然而,雖然所有分片鏈中新區塊的生成基本上同時執行(通常由新主鏈區塊的發布觸發),但新主鏈區塊的生成被刻意延遲,以允許在主鏈中包含新生成的分片鏈區塊的雜湊。
\nxsubpoint\label{sp:slow.valid} \embt(慢速驗證者可能會收到較低的獎勵。) 如果驗證者「慢」,它可能無法驗證新的區塊候選,並且提交新區塊所需的三分之二的簽章可能在沒有其參與的情況下收集到。在這種情況下,它將收到與此區塊相關的較低獎勵份額。
這為驗證者提供了最佳化其硬體、軟體和網路連線的動力,以便盡可能快地處理使用者交易。
然而,如果驗證者在提交區塊之前未能簽署區塊,其簽章可能會包含在接下來的區塊之一中,然後仍會給予此驗證者一部分獎勵(根據自那時以來生成了多少區塊呈指數遞減——例如,如果驗證者遲了 $k$ 個區塊,則為 $0.9^k$)。
\nxsubpoint\label{sp:val.sign.depth} \embt(驗證者簽章的「深度」。) 通常,當驗證者簽署區塊時,簽章僅證明區塊的{\em 相對有效性}:此區塊是有效的,前提是此分片鏈和其他分片鏈中的所有先前區塊都是有效的。驗證者不能因為將提交到先前區塊中的無效資料視為理所當然而受到懲罰。
然而,區塊的驗證者簽章有一個稱為「深度」的整數參數。如果它不為零,則意味著驗證者也斷言指定數量的先前區塊的(相對)有效性。這是「慢」或「暫時離線」驗證者追趕並簽署一些沒有他們簽章就已提交的區塊的方式。然後,仍會給予他們區塊獎勵的一部分(參見~\ptref{sp:slow.valid})。
\nxsubpoint\label{sp:abs.val.from.rel} \embt(驗證者對已簽署的分片鏈區塊的{\em 相對}有效性負責;絕對有效性隨之而來。) 我們想要再次強調,驗證者對分片鏈區塊 $B$ 的簽章僅證明該區塊的{\em 相對}有效性(或者也許還證明 $d$ 個先前區塊的相對有效性,如果簽章具有「深度」$d$,參見~\ptref{sp:val.sign.depth};但這不會對以下討論產生太大影響)。換句話說,驗證者斷言分片鏈的下一個狀態 $s'$ 是透過應用~\ptref{sp:blk.transf} 中描述的區塊評估函數 $\evblock$ 從先前狀態 $s$ 獲得的:
\begin{equation}\label{eq:ev.block.2}
s'=\evblock(B)(s)
\end{equation}
透過這種方式,如果原始狀態 $s$ 被證明是「不正確的」(例如,由於先前區塊之一的無效性),簽署區塊 $B$ 的驗證者不能受到懲罰。漁夫(參見~\ptref{sp:fish})只有在發現{\em 相對}無效的區塊時才應該投訴。整個 PoS 系統努力使每個區塊{\em 相對}有效,而不是{\em 遞迴(或絕對)}有效。但是,請注意,{\em 如果區塊鏈中的所有區塊都是相對有效的,那麼所有區塊和整個區塊鏈都是絕對有效的};這個陳述很容易使用對區塊鏈長度的數學歸納法來證明。透過這種方式,易於驗證的區塊{\em 相對}有效性的斷言一起證明了整個區塊鏈的強得多的{\em 絕對有效性}。
請注意,透過簽署區塊~$B$,驗證者斷言給定原始狀態 $s$,區塊是有效的(即,~\eqref{eq:ev.block.2} 的結果不是指示無法計算下一個狀態的值 $\bot$)。透過這種方式,驗證者必須對在評估~\eqref{eq:ev.block.2} 期間存取的原始狀態的單元執行最小的形式檢查。
例如,假設預期包含從提交到區塊的交易中存取的帳戶的原始餘額的單元結果有零個原始位元組,而不是預期的 8 或 16 個。然後,根本無法從單元中檢索原始餘額,並且在嘗試處理區塊時發生「未處理的例外」。在這種情況下,驗證者不應簽署這樣的區塊,否則將受到懲罰。
\nxsubpoint \embt(簽署主鏈區塊。) 主鏈區塊的情況有所不同:透過簽署主鏈區塊,驗證者不僅斷言其相對有效性,而且還斷言從該驗證者承擔責任的第一個區塊開始的所有先前區塊的相對有效性(但不進一步追溯)。
\nxsubpoint \embt(驗證者總數。) 到目前為止所描述的系統中,要選舉的驗證者總數的上限 $T$(參見~\ptref{sp:global.valid})不能超過,比如說,幾百或一千,因為所有驗證者預計參與 BFT 共識協議以建立每個新的主鏈區塊,並且不清楚這樣的協議是否可以擴展到數千名參與者。更重要的是,主鏈區塊必須收集所有驗證者(按質押)中至少三分之二的簽章,並且這些簽章必須包含在新區塊中(否則系統中的所有其他節點將沒有理由信任新區塊而不自己驗證它)。如果必須在每個主鏈區塊中包含超過,比如說,一千個驗證者簽章,這將意味著每個主鏈區塊中有更多資料,要由所有全節點儲存並透過網路傳播,並且花費更多處理能力來檢查這些簽章(在 PoS 系統中,全節點不需要自己驗證區塊,但他們需要檢查驗證者的簽章)。
雖然將 $T$ 限制為一千個驗證者似乎對於 TON 區塊鏈部署的第一階段來說綽綽有餘,但必須為未來的成長做好準備,當分片鏈總數變得如此之大,以至於幾百個驗證者將不足以處理所有分片鏈。為此,我們引入一個額外的可配置參數 $T'\leq T$(最初等於~$T$),並且只有前 $T'$ 個當選的驗證者(按質押)預計建立和簽署新的主鏈區塊。
\nxsubpoint \embt(系統的去中心化。) 人們可能會懷疑,像 TON 區塊鏈這樣的權益證明系統,依賴於 $T\approx1000$ 個驗證者來建立所有分片鏈和主鏈區塊,必然會變得「過於中心化」,與傳統的工作量證明區塊鏈(如比特幣或以太坊)相反,在那裡每個人(原則上)都可能挖掘新區塊,對礦工總數沒有明確的上限。
然而,流行的工作量證明區塊鏈,例如比特幣和以太坊,目前需要大量的計算能力(高「雜湊率」)才能以不可忽略的成功概率挖掘新區塊。因此,新區塊的挖掘往往集中在幾個大型參與者手中,他們在裝滿專為挖礦最佳化的客製化硬體的資料中心投資了大量資金;以及幾個大型礦池手中,這些礦池集中並協調較大群體的人的努力,這些人無法自己提供足夠的「雜湊率」。
因此,截至 2017 年,超過 75\% 的新以太坊或比特幣區塊是由不到十個礦工產生的。事實上,兩個最大的以太坊礦池一起產生了一半以上的所有新區塊!顯然,這樣的系統比依賴 $T\approx1000$ 個節點來產生新區塊的系統更加中心化。
人們還可能注意到,成為 TON 區塊鏈驗證者所需的投資——即購買硬體(比如,幾台高效能伺服器)和質押(如果需要,可以輕鬆透過提名者池收集;參見~\ptref{sp:nominators})——遠低於成為成功的獨立比特幣或以太坊礦工所需的投資。事實上,~\ptref{sp:global.valid} 的參數 $L$ 將迫使提名者不要加入最大的「礦池」(即積累了最大質押的驗證者),而是尋找目前接受提名者資金的較小驗證者,甚至建立新的驗證者,因為這將允許使用驗證者的——進而也是提名者的——質押的更高比例 $s'_i/s_i$,從而從挖礦中產生更大的獎勵。透過這種方式,TON 權益證明系統實際上{\em 鼓勵}去中心化(建立和使用更多驗證者)並{\em 懲罰}中心化。
\nxsubpoint\label{sp:rel.rel} \embt(區塊的相對可靠性。) 區塊的{\em (相對)可靠性}只是簽署此區塊的所有驗證者的總質押。換句話說,這是如果該區塊被證明無效,某些行為者將失去的金額。如果人們關注的交易轉移的價值低於區塊的可靠性,則可以認為它們足夠安全。從這個意義上說,相對可靠性是外部觀察者可以對特定區塊擁有的信任度量。
請注意,我們談論區塊的{\em 相對}可靠性,因為它是一種保證,即區塊是有效的,{\em 前提是先前的區塊和所有其他被參照的分片鏈區塊都是有效的}(參見~\ptref{sp:abs.val.from.rel})。
區塊的相對可靠性可以在提交後增加——例如,當新增遲到的驗證者簽章時(參見~\ptref{sp:val.sign.depth})。另一方面,如果這些驗證者之一因與其他一些區塊相關的不當行為而失去部分或全部質押,則區塊的相對可靠性可能會{\em 降低}。
\nxsubpoint \embt(「強化」區塊鏈。) 重要的是為驗證者提供激勵,使其盡可能提高區塊的相對可靠性。一種方法是透過為驗證者向其他分片鏈的區塊新增簽章分配少量獎勵。甚至「準」驗證者,他們存入的質押不足以進入按質押計算的前 $T$ 個驗證者並被包含在全域驗證者集合中(參見~\ptref{sp:global.valid}),可能會參與此活動(如果他們同意在選舉失敗後保持其質押凍結而不是撤回它)。這樣的準驗證者可能會兼任漁夫(參見~\ptref{sp:fish}):如果他們無論如何都必須檢查某些區塊的有效性,他們不妨選擇報告無效區塊並收集相關獎勵。
\nxsubpoint\label{sp:rec.rel} \embt(區塊的遞迴可靠性。) 還可以將區塊的{\em 遞迴可靠性}定義為其相對可靠性與其參照的所有區塊(即主鏈區塊、先前的分片鏈區塊以及某些相鄰分片鏈的區塊)的遞迴可靠性的最小值。換句話說,如果區塊被證明無效,無論是因為它本身無效還是因為它依賴的區塊之一無效,那麼至少會有這麼多金額被某人損失。如果真的不確定是否信任區塊中的特定交易,應該計算此區塊的{\em 遞迴}可靠性,而不僅僅是{\em 相對}可靠性。
在計算遞迴可靠性時追溯太遠是沒有意義的,因為如果我們往回看得太遠,我們將看到由質押已經解凍和撤回的驗證者簽署的區塊。無論如何,我們不允許驗證者自動重新考慮那麼舊的區塊(即,如果使用當前的可配置參數值,則是兩個多月前建立的區塊),並從它們開始建立分叉或在「垂直區塊鏈」的幫助下更正它們(參見~\ptref{sp:inv.sh.blk.corr}),即使它們被證明是無效的。我們假設兩個月的期間為檢測和報告任何無效區塊提供了充足的機會,因此如果區塊在此期間未受到質疑,則不太可能受到質疑。
\nxsubpoint \embt(權益證明對輕節點的影響。) TON 區塊鏈使用的權益證明方法的一個重要後果是,TON 區塊鏈的輕節點(執行輕用戶端軟體)不需要下載所有分片鏈甚至主鏈區塊的「標頭」,即可自己檢查全節點作為其查詢答案提供的 Merkle 證明的有效性。
事實上,因為最近的分片鏈區塊雜湊包含在主鏈區塊中,所以全節點可以輕鬆地提供 Merkle 證明,證明給定的分片鏈區塊從主鏈區塊的已知雜湊開始是有效的。接下來,輕節點只需要知道主鏈的第一個區塊(其中宣布了第一組驗證者),該區塊(或至少其雜湊)可能內建在用戶端軟體中,以及之後大約每個月只有一個主鏈區塊,其中宣布了新選舉的驗證者集合,因為該區塊將由先前的驗證者集合簽署。從那時起,它可以獲得幾個最新的主鏈區塊,或者至少獲得它們的標頭和驗證者簽章,並將它們用作檢查全節點提供的 Merkle 證明的基礎。
\mysubsection{分片鏈的拆分和合併}\label{sect:split.merge}
TON 區塊鏈最具特色和獨特的功能之一是它能夠在負載變得過高時自動將分片鏈一分為二,並在負載減少時將它們合併回來(參見~\ptref{sp:dyn.split.merge})。由於其獨特性及其對整個專案可擴展性的重要性,我們必須詳細討論它。
\nxsubpoint \embt(分片配置。) 回想一下,在任何給定時刻,每個工作鏈 $w$ 都被分成一個或幾個分片鏈 $(w,s)$(參見~\ptref{sp:shard.ident})。這些分片鏈可以由二元樹的葉表示,根為 $(w,\emptyset)$,每個非葉節點 $(w,s)$ 有子節點 $(w,s.0)$ 和 $(w,s.1)$。透過這種方式,屬於工作鏈 $w$ 的每個帳戶都被分配到恰好一個分片,並且知道當前分片鏈配置的每個人都可以確定包含帳戶 $\accountid$ 的分片 $(w,s)$:它是唯一的分片,其二進位字串 $s$ 是 $\accountid$ 的前綴。
分片配置——即此{\em 分片二元樹},或給定 $w$ 的所有活動 $(w,s)$ 的集合(對應於分片二元樹的葉)——是主鏈狀態的一部分,並且對追蹤主鏈的每個人都可用。\footnote{實際上,分片配置完全由最後一個主鏈區塊確定;這簡化了對分片配置的存取。}
\nxsubpoint \embt(最新的分片配置和狀態。) 回想一下,最近的分片鏈區塊的雜湊包含在每個主鏈區塊中。這些雜湊組織在分片二元樹中(實際上是樹的集合,每個工作鏈一個)。透過這種方式,每個主鏈區塊都包含最新的分片配置。
\nxsubpoint \embt(宣布和執行分片配置的變更。) 分片配置可以透過兩種方式變更:一個分片 $(w,s)$ 可以被{\em 拆分}為兩個分片 $(w,s.0)$ 和 $(w,s.1)$,或者兩個「兄弟」分片 $(w,s.0)$ 和 $(w,s.1)$ 可以被{\em 合併}為一個分片 $(w,s)$。
這些拆分/合併操作會提前幾個(例如 $2^6$;這是一個可配置參數)區塊宣布,首先在相應分片鏈區塊的「標頭」中,然後在參照這些分片鏈區塊的主鏈區塊中。所有相關方都需要這個提前宣布來為計劃的變更做準備(例如,建立覆蓋多播網路以分發新建立的分片鏈的新區塊,如~\ptref{sect:overlay} 中所討論的)。然後,變更首先提交到分片鏈區塊的(標頭)(在拆分的情況下;對於合併,兩個分片鏈的區塊都應提交變更),然後傳播到主鏈區塊。透過這種方式,主鏈區塊不僅定義了其建立{\em 之前}的最新分片配置,還定義了下一個立即的分片配置。
\nxsubpoint \embt(新分片鏈的驗證者任務組。) 回想一下,每個分片,即每個分片鏈,通常都被分配一個驗證者子集(驗證者任務組),專門用於在相應的分片鏈中建立和驗證新區塊(參見~\ptref{sp:val.task.grp})。這些任務組被選舉一段時間(大約一小時),並提前一段時間(也大約一小時)就知道,並在此期間是不可變的。\footnote{除非某些驗證者因簽署無效區塊而被暫時或永久禁止——然後他們會自動從所有任務組中排除。}
然而,由於拆分/合併操作,實際的分片配置可能在此期間發生變化。必須將任務組分配給新建立的分片。這是按照以下方式完成的:
請注意,任何活動分片 $(w,s)$ 要麼是某個唯一確定的原始分片 $(w,s')$ 的後代,這意味著 $s'$ 是 $s$ 的前綴,要麼它將是原始分片 $(w,s')$ 子樹的根,其中 $s$ 將是每個 $s'$ 的前綴。在第一種情況下,我們只需將原始分片 $(w,s')$ 的任務組用作新分片 $(w,s)$ 的任務組。在後一種情況下,新分片 $(w,s)$ 的任務組將是分片樹中 $(w,s)$ 的所有後代原始分片 $(w,s')$ 的任務組的聯合。
透過這種方式,每個活動分片 $(w,s)$ 都被分配一個明確定義的驗證者子集(任務組)。當分片被拆分時,兩個子分片都從原始分片繼承整個任務組。當兩個分片合併時,它們的任務組也會合併。
任何追蹤主鏈狀態的人都可以為每個活動分片計算驗證者任務組。
\nxsubpoint \embt(在原始任務組責任期間對拆分/合併操作的限制。) 最終,新的分片配置將被考慮在內,並且新的專用驗證者子集(任務組)將自動分配給每個分片。在此之前,必須對拆分/合併操作施加一定的限制;否則,如果原始分片快速拆分為 $2^k$ 個新分片,則原始任務組可能最終同時驗證 $2^k$ 個分片鏈,對於較大的 $k$。
這是透過對活動分片配置與原始分片配置(用於選擇目前負責的驗證者任務組的配置)之間的距離施加限制來實現的。例如,如果 $s'$ 是 $s$ 的前導(即 $s'$ 是二進位字串 $s$ 的前綴),則可能要求從活動分片 $(w,s)$ 到原始分片 $(w,s')$ 的分片樹距離不得超過 3,並且如果 $s'$ 是 $s$ 的後繼(即 $s$ 是 $s'$ 的前綴),則不得超過 2。否則,不允許拆分或合併操作。
粗略地說,對於給定的驗證者任務組集合的責任期間,正在對分片可以拆分(例如三次)或合併(例如兩次)的次數施加限制。除此之外,在透過合併或拆分建立分片後,它不能在一段時間(一些區塊數)內重新配置。
\nxsubpoint\label{sp:split.necess} \embt(確定拆分操作的必要性。) 分片鏈的拆分操作由某些形式條件觸發(例如,如果連續 64 個區塊中分片鏈區塊至少填滿 $90\%$)。這些條件由分片鏈任務組監視。如果滿足這些條件,首先在新分片鏈區塊的標頭中包含「拆分準備」旗標(並傳播到參照此分片鏈區塊的主鏈區塊)。然後,在幾個區塊之後,「拆分提交」旗標包含在分片鏈區塊的標頭中(並傳播到下一個主鏈區塊)。
\nxsubpoint \embt(執行拆分操作。) 在「拆分提交」旗標包含在分片鏈 $(w,s)$ 的區塊 $B$ 中之後,該分片鏈中不能有後續區塊 $B'$。相反,將建立分片鏈 $(w,s.0)$ 和 $(w,s.1)$ 的兩個區塊 $B'_0$ 和 $B'_1$,兩者都參照區塊 $B$ 作為其先前區塊(並且兩者都將在標頭中透過旗標指示分片剛剛被拆分)。下一個主鏈區塊將包含新分片鏈的區塊 $B'_0$ 和 $B'_1$ 的雜湊;不允許包含分片鏈 $(w,s)$ 的新區塊 $B'$ 的雜湊,因為「拆分提交」事件已經提交到先前的主鏈區塊中。
請注意,兩個新分片鏈將由與舊分片鏈相同的驗證者任務組驗證,因此它們將自動擁有其狀態的副本。從無限分片範式的角度來看,狀態拆分操作本身非常簡單(參見~\ptref{sp:split.merge.state})。
\nxsubpoint\label{sp:merge.necess} \embt(確定合併操作的必要性。) 分片合併操作的必要性也由某些形式條件檢測(例如,如果連續 64 個區塊中兄弟分片鏈的兩個區塊的大小總和不超過最大區塊大小的 $60\%$)。這些形式條件還應考慮這些區塊花費的總燃料,並將其與當前區塊燃料限制進行比較,否則區塊可能恰好很小,因為存在一些計算密集型交易阻止包含更多交易。
這些條件由兩個兄弟分片 $(w,s.0)$ 和 $(w,s.1)$ 的驗證者任務組監視。請注意,關於超立方體路由(參見~\ptref{sp:hypercube}),兄弟必然是鄰居,因此任何分片的任務組的驗證者無論如何都會在某種程度上監視兄弟分片。
當滿足這些條件時,驗證者子組中的任何一個都可以透過傳送特殊訊息向另一個建議他們合併。然後,它們結合成一個臨時的「合併任務組」,具有組合成員資格,能夠執行 BFT 共識演算法並在必要時傳播區塊更新和區塊候選。
如果他們就合併的必要性和準備達成共識,「合併準備」旗標被提交到每個分片鏈的某些區塊的標頭中,以及至少三分之二的兄弟任務組驗證者的簽章(並傳播到下一個主鏈區塊,以便每個人都可以為即將到來的重新配置做好準備)。然而,他們繼續為一些預定義數量的區塊建立單獨的分片鏈區塊。
\nxsubpoint \embt(執行合併操作。) 之後,當來自兩個原始任務組聯合的驗證者準備好成為合併分片鏈的驗證者時(這可能涉及從兄弟分片鏈進行狀態轉移和狀態合併操作),他們在其分片鏈的區塊標頭中提交「合併提交」旗標(此事件傳播到下一個主鏈區塊),並停止在單獨的分片鏈中建立新區塊(一旦出現合併提交旗標,就禁止在單獨的分片鏈中建立區塊)。相反,建立合併的分片鏈區塊(由兩個原始任務組的聯合),在其「標頭」中參照其兩個「先前區塊」。這反映在下一個主鏈區塊中,該區塊將包含合併分片鏈的新建立區塊的雜湊。之後,合併的任務組繼續在合併的分片鏈中建立區塊。
\mysubsection{區塊鏈專案的分類}\label{sect:class.blkch}
我們將透過將 TON 區塊鏈與現有和提議的區塊鏈專案進行比較來結束我們對 TON 區塊鏈的簡短討論。然而,在此之前,我們必須引入一個足夠通用的區塊鏈專案分類。基於此分類的特定區塊鏈專案的比較推遲到~\ptref{sect:compare.blkch}。
\nxsubpoint \embt(區塊鏈專案的分類。) 作為第一步,我們為區塊鏈(即區塊鏈專案)建議一些分類標準。任何這樣的分類都有些不完整和膚淺,因為它必須忽略所考慮的專案的一些最具體和獨特的功能。然而,我們認為這是提供至少一個非常粗略和近似的區塊鏈專案領域地圖的必要第一步。
我們考慮的標準列表如下:
\begin{itemize}
\item 單一區塊鏈 vs.\ 多區塊鏈架構
(參見~\ptref{sp:single.multi})
\item 共識演算法:權益證明 vs.\ 工作量證明
(參見~\ptref{sp:pow.pos})
\item 對於權益證明系統,使用的確切區塊生成、驗證和共識演算法(兩個主要選項是 DPOS vs.\ BFT;參見~\ptref{sp:dpos.bft})
\item 對「任意」(圖靈完備)智慧合約的支援
(參見~\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 對分片的原生支援(參見~\ptref{sp:shard.supp})。靜態或動態分片(參見~\ptref{sp:dyn.stat.shard})。
\item 成員區塊鏈之間的互動:鬆耦合和緊耦合系統(參見~\ptref{sp:blkch.interact})
\end{itemize}
\nxsubpoint\label{sp:single.multi} \embt(單一區塊鏈 vs.\ 多區塊鏈專案。) 第一個分類標準是系統中區塊鏈的數量。最古老和最簡單的專案由{\em 單一區塊鏈}組成(簡稱「單鏈專案」);更複雜的專案使用(或者說,計劃使用){\em 多個區塊鏈}(「多鏈專案」)。
單鏈專案通常更簡單且經過更好的測試;它們經受住了時間的考驗。它們的主要缺點是效能低,或者至少是交易吞吐量低,對於通用系統來說,交易吞吐量在十(比特幣)到不到一百\footnote{目前更像是 15。然而,正在計劃一些升級,以使以太坊交易吞吐量增加幾倍。}(以太坊)筆每秒的水平。一些專用系統(例如 Bitshares)能夠每秒處理數萬筆專用交易,代價是要求區塊鏈狀態適合記憶體,並將處理限制為預定義的特殊交易集,然後由用 C++ 等語言編寫的高度最佳化的程式碼執行(這裡沒有 VM)。
多鏈專案承諾每個人都渴望的可擴展性。它們可能支援更大的總狀態和每秒更多的交易,代價是使專案變得更加複雜,並使其實作更具挑戰性。因此,已經執行的多鏈專案很少,但大多數提議的專案都是多鏈的。我們相信未來屬於多鏈專案。
\nxsubpoint\label{sp:pow.pos} \embt(建立和驗證區塊:工作量證明 vs.\ 權益證明。) 另一個重要的區別是用於建立和傳播新區塊、檢查其有效性以及選擇幾個分叉之一(如果出現)的演算法和協議。
兩種最常見的範式是{\em 工作量證明(PoW)}和{\em 權益證明(PoS)}。工作量證明方法通常允許任何節點建立(「挖掘」)新區塊(並獲得與挖掘區塊相關的一些獎勵),如果它幸運地在其他競爭者設法做到這一點之前解決了一個無用的計算問題(通常涉及計算大量雜湊)。在分叉的情況下(例如,如果兩個節點發布兩個有效但不同的區塊來跟隨前一個區塊),最長的分叉獲勝。透過這種方式,區塊鏈不可變性的保證基於生成區塊鏈所花費的{\em 工作}(計算資源)量:任何想要建立此區塊鏈分叉的人都需要重做此工作以建立已提交區塊的替代版本。為此,需要控制超過 $50\%$ 用於建立新區塊的總計算能力,否則替代分叉成為最長分叉的機會將呈指數級降低。
權益證明方法基於某些特殊節點({\em 驗證者})用加密貨幣計價的大額{\em 質押},以斷言他們已經檢查({\em 驗證})了某些區塊並發現它們是正確的。驗證者簽署區塊,並因此獲得一些小額獎勵;然而,如果驗證者被發現簽署了不正確的區塊,並提供了此證明,則其部分或全部質押將被沒收。透過這種方式,區塊鏈的有效性和不可變性保證由驗證者對區塊鏈有效性投入的質押總量給出。
權益證明方法更自然,因為它激勵驗證者(取代 PoW 礦工)執行有用的計算(檢查或建立新區塊所需的,特別是透過執行區塊中列出的所有交易),而不是計算無用的雜湊。透過這種方式,驗證者將購買更適合處理使用者交易的硬體,以獲得與這些交易相關的獎勵,從整個系統的角度來看,這似乎是一項非常有用的投資。
然而,權益證明系統的實作更具挑戰性,因為必須為許多罕見但可能的條件做準備。例如,一些惡意驗證者可能串謀破壞系統以獲取一些利潤(例如,透過更改他們自己的加密貨幣餘額)。這導致一些非平凡的博弈論問題。
簡而言之,權益證明更自然且更有前途,特別是對於多鏈專案(因為如果有許多區塊鏈,工作量證明將需要令人望而卻步的計算資源量),但必須更仔細地思考和實作。大多數目前執行的區塊鏈專案,特別是最古老的專案(例如比特幣和至少原始的以太坊),使用工作量證明。
\nxsubpoint\label{sp:dpos.bft} \embt(權益證明的變體。DPOS vs.\ BFT。) 雖然工作量證明演算法彼此非常相似,主要在挖掘新區塊必須計算的雜湊函數方面有所不同,但權益證明演算法有更多可能性。它們值得有自己的子分類。
本質上,必須回答有關權益證明演算法的以下問題:
\begin{itemize}
\item 誰可以產生(「挖掘」)新區塊——任何全節點,還是只有(相對)小的驗證者子集的成員?(大多數 PoS 系統要求新區塊由幾個指定驗證者之一生成和簽署。)
\item 驗證者是否透過其簽章保證區塊的有效性,還是期望所有全節點自己驗證所有區塊?(可擴展的 PoS 系統必須依賴驗證者簽章,而不是要求所有節點驗證所有區塊鏈的所有區塊。)
\item 下一個區塊鏈區塊是否有一個提前知道的指定產生者,以便沒有其他人可以產生該區塊?
\item 新建立的區塊最初是否僅由一個驗證者(其產生者)簽署,還是必須從一開始就收集大多數驗證者的簽章?
\end{itemize}
雖然根據對這些問題的回答,似乎有 $2^4$ 個可能的 PoS 演算法類別,但實際上的區別歸結為兩種主要的 PoS 方法。事實上,大多數現代 PoS 演算法,設計用於可擴展的多鏈系統,以相同的方式回答前兩個問題:只有驗證者可以產生新區塊,他們保證區塊有效性,而不需要所有全節點自己檢查所有區塊的有效性。
至於最後兩個問題,它們的答案被證明是高度相關的,基本上只留下兩個基本選項:
\begin{itemize}
\item {\em 委託權益證明(DPOS)}:每個區塊都有一個普遍知道的指定產生者;沒有其他人可以產生該區塊;新區塊最初僅由其產生驗證者簽署。
\item {\em 拜占庭容錯(BFT)}PoS 演算法:有一個已知的驗證者子集,其中任何一個都可以建議新區塊;在幾個建議的候選中選擇實際的下一個區塊,該區塊必須在釋放給其他節點之前由大多數驗證者驗證和簽署,這是透過拜占庭容錯共識協議的版本實現的。
\end{itemize}
\nxsubpoint\label{sp:dpos.bft.compare} \embt(DPOS 和 BFT PoS 的比較。) BFT 方法的優點是新產生的區塊{\em 從一開始就}具有大多數驗證者證明其有效性的簽章。另一個優點是,如果大多數驗證者正確執行 BFT 共識協議,根本不會出現分叉。另一方面,BFT 演算法往往相當複雜,需要更多時間讓驗證者子集達成共識。因此,區塊不能太頻繁地生成。這就是為什麼我們預計 TON 區塊鏈(從此分類的角度來看是 BFT 專案)每五秒才產生一個區塊。實際上,這個間隔可能會減少到 2--3 秒(儘管我們不承諾這一點),但如果驗證者分散在全球各地,則不會進一步減少。
DPOS 演算法的優點是相當簡單直接。它可以非常頻繁地生成新區塊——比如說,每兩秒一次,或者甚至每秒一次,\footnote{有些人甚至聲稱 DPOS 區塊生成時間為半秒,如果驗證者分散在幾個大陸,這似乎不現實。} 因為它依賴於提前知道的指定區塊產生者。
然而,DPOS 要求所有節點——或至少所有驗證者——驗證接收到的所有區塊,因為產生和簽署新區塊的驗證者不僅確認此區塊的{\em 相對}有效性,而且還確認它所參照的先前區塊的有效性,以及鏈中更早的所有區塊(可能直到當前驗證者子集的責任期開始)。當前驗證者子集上有一個預定的順序,因此對於每個區塊都有一個指定的產生者(即預期生成該區塊的驗證者);這些指定的產生者以循環方式輪換。透過這種方式,區塊首先僅由其產生驗證者簽署;然後,當下一個區塊被挖掘時,其產生者選擇參照此區塊而不是其前身之一(否則其區塊將位於較短的鏈中,這可能會在未來失去「最長分叉」競爭),下一個區塊的簽章本質上也是對先前區塊的額外簽章。透過這種方式,新區塊逐漸收集更多驗證者的簽章——比如說,在生成接下來的二十個區塊所需的時間內收集二十個簽章。全節點要麼需要等待這二十個簽章,要麼自己驗證區塊,從充分確認的區塊(比如說,往回二十個區塊)開始,這可能不那麼容易。
DPOS 演算法的明顯缺點是,與 BFT 演算法相比,新區塊(以及提交到其中的交易)只有在挖掘了更多二十個區塊之後才能達到相同的信任水平(如~\ptref{sp:rec.rel} 中討論的「遞迴可靠性」),而 BFT 演算法立即提供這種信任水平(比如說,二十個簽章)。另一個缺點是 DPOS 使用「最長分叉獲勝」方法來切換到其他分叉;如果至少有一些產生者在我們感興趣的區塊之後未能產生後續區塊(或者由於網路分區或複雜攻擊,我們未能觀察到這些區塊),這使得分叉相當可能。
我們認為,雖然 BFT 方法實作起來更複雜,並且需要比 DPOS 更長的區塊間隔時間,但它更適合「緊耦合」(參見~\ptref{sp:blkch.interact})多鏈系統,因為其他區塊鏈可以在新區塊中看到已提交的交易(例如,生成針對它們的訊息)後幾乎立即開始行動,而無需等待二十次有效性確認(即接下來的二十個區塊),或等待接下來的六個區塊以確保不會出現分叉並自己驗證新區塊(在可擴展的多鏈系統中,驗證其他區塊鏈的區塊可能變得令人望而卻步)。因此,它們可以在保持高可靠性和可用性的同時實現可擴展性(參見~\ptref{sp:shard.supp})。
另一方面,DPOS 可能是「鬆耦合」多鏈系統的好選擇,其中不需要區塊鏈之間的快速互動——例如,如果每個區塊鏈(「工作鏈」)代表一個單獨的分散式交易所,並且區塊鏈間的互動僅限於罕見的代幣從一個工作鏈轉移到另一個工作鏈(或者說,以接近 $1:1$ 的比率交易駐留在一個工作鏈中的一個山寨幣與另一個)。這實際上是在 BitShares 專案中所做的,該專案非常成功地使用了 DPOS。
總而言之,雖然 DPOS 可以{\em 更快地生成}新區塊並{\em 將交易包含}到其中(區塊之間的間隔更小),但這些交易達到在其他區塊鏈和鏈下應用中使用它們作為「已提交」和「不可變」所需的信任水平{\em 比 BFT 系統慢得多}——比如說,在三十秒內%
\footnote{例如,EOS 是迄今為止提出的最好的 DPOS 專案之一,承諾 45 秒的確認和區塊鏈間互動延遲(參見~\cite{EOSWP},「交易確認」和「鏈間通訊的延遲」部分)。}
而不是五秒。更快的交易{\em 包含}並不意味著更快的交易{\em 提交}。如果需要快速的區塊鏈間互動,這可能會成為一個巨大的問題。在這種情況下,必須放棄 DPOS 並選擇 BFT PoS。
\nxsubpoint\label{sp:smartc.supp} \embt(對交易中圖靈完備程式碼的支援,即本質上任意的智慧合約。) 區塊鏈專案通常在其區塊中收集一些{\em 交易},這些交易以認為有用的方式改變區塊鏈狀態(例如,將一定數量的加密貨幣從一個帳戶轉移到另一個帳戶)。一些區塊鏈專案可能只允許某些特定的預定義類型的交易(例如從一個帳戶到另一個帳戶的價值轉移,前提是提供正確的簽章)。其他專案可能支援交易中某種有限形式的腳本。最後,一些區塊鏈支援在交易中執行任意複雜的程式碼,使系統(至少在原則上)能夠支援任意應用,前提是系統的效能允許。這通常與「圖靈完備虛擬機和腳本語言」(意味著可以用任何其他計算語言編寫的任何程式都可以重新編寫為在區塊鏈內執行)和「智慧合約」(駐留在區塊鏈中的程式)相關聯。
當然,對任意智慧合約的支援使系統真正靈活。另一方面,這種靈活性是有代價的:這些智慧合約的程式碼必須在某個虛擬機上執行,並且每次有人想要建立或驗證區塊時,必須對區塊中的每個交易都這樣做。與預定義和不可變的簡單交易類型集合的情況相比,這減慢了系統的效能,後者可以透過用 C++ 等語言實作其處理來最佳化(而不是某個虛擬機)。
最終,對圖靈完備智慧合約的支援似乎在任何通用區塊鏈專案中都是可取的;否則,區塊鏈專案的設計者必須提前決定他們的區塊鏈將用於哪些應用。事實上,比特幣區塊鏈缺乏對智慧合約的支援是必須建立一個新的區塊鏈專案以太坊的主要原因。
在(異質的;參見~\ptref{sp:blkch.hom.het})多鏈系統中,可以透過在某些區塊鏈(即工作鏈)中支援圖靈完備的智慧合約,並在其他區塊鏈中支援一小組預定義的高度最佳化的交易,來「兩全其美」。
\nxsubpoint\label{sp:class.multichain} \embt(多鏈系統的分類。) 到目前為止,分類對單鏈和多鏈系統都有效。然而,多鏈系統允許更多分類標準,反映系統中不同區塊鏈之間的關係。我們現在討論這些標準。
\nxsubpoint\label{sp:blkch.hom.het} \embt(區塊鏈類型:同質和異質系統。) 在多鏈系統中,所有區塊鏈可能本質上屬於同一類型並具有相同的規則(即使用相同的交易格式、用於執行智慧合約程式碼的相同虛擬機、共享相同的加密貨幣等),並且這種相似性被明確利用,但每個區塊鏈中的資料不同。在這種情況下,我們說系統是{\em 同質的}。否則,不同的區塊鏈(在這種情況下通常稱為{\em 工作鏈})可以有不同的「規則」。然後我們說系統是{\em 異質的}。
\nxsubpoint\label{sp:mixed.het.hom} \embt(混合異質-同質系統。) 有時我們有一個混合系統,其中有幾組區塊鏈的類型或規則,但存在許多具有相同規則的區塊鏈,並且這一事實被明確利用。然後它是一個混合{\em 異質-同質系統}。據我們所知,TON 區塊鏈是這種系統的唯一範例。
\nxsubpoint\label{sp:het.confed} \embt(具有幾個具有相同規則的工作鏈的異質系統,或{\em 聯邦}。) 在某些情況下,具有相同規則的幾個區塊鏈(工作鏈)可以存在於異質系統中,但它們之間的互動與具有不同規則的區塊鏈之間的互動相同(即,它們的相似性沒有被明確利用)。即使它們似乎使用「相同的」加密貨幣,它們實際上使用不同的「山寨幣」(加密貨幣的獨立化身)。有時甚至可以有某些機制以接近 $1:1$ 的比率轉換這些山寨幣。然而,在我們看來,這並不使系統成為同質的;它仍然是異質的。我們說,這種具有相同規則的工作鏈的異質集合是一個{\em 聯邦}。
雖然建立一個允許使用相同規則建立幾個工作鏈(即聯邦)的異質系統似乎是建立可擴展系統的廉價方式,但這種方法也有很多缺點。本質上,如果有人在許多具有相同規則的工作鏈中託管一個大型專案,她不會獲得一個大型專案,而是獲得該專案的許多小實例。這就像擁有一個聊天應用(或遊戲),允許任何聊天(或遊戲)房間中最多有 50 個成員,但透過在必要時建立新房間以容納更多使用者來「擴展」。因此,許多使用者可以參與聊天或遊戲,但我們能說這樣的系統是真正可擴展的嗎?
\nxsubpoint\label{sp:pres.masterch} \embt(主鏈的存在,外部或內部。) 有時,多鏈專案有一個區別的「主鏈」(有時稱為「控制區塊鏈」),例如用於儲存系統的整體配置(所有活動區塊鏈的集合,或者說工作鏈)、當前的驗證者集合(對於權益證明系統)等等。有時其他區塊鏈「綁定」到主鏈,例如透過將其最新區塊的雜湊提交到其中(這也是 TON 區塊鏈所做的)。
在某些情況下,主鏈是{\em 外部的},這意味著它不是專案的一部分,而是某個其他預先存在的區塊鏈,最初與新專案的使用完全無關,並且不知道它。例如,可以嘗試使用以太坊區塊鏈作為外部專案的主鏈,並為此目的將特殊智慧合約發布到以太坊區塊鏈(例如,用於選舉和懲罰驗證者)。
\nxsubpoint\label{sp:shard.supp} \embt(分片支援。) 一些區塊鏈專案(或系統)對{\em 分片}有原生支援,這意味著幾個(必然是同質的;參見~\ptref{sp:blkch.hom.het})區塊鏈被認為是單個(從高階角度來看)虛擬區塊鏈的{\em 分片}。例如,可以使用相同的規則建立 256 個分片區塊鏈(「分片鏈」),並根據其 $\accountid$ 的第一個位元組選擇的恰好一個分片中保留帳戶的狀態。
分片是擴展區塊鏈系統的自然方法,因為如果正確實作,系統中的使用者和智慧合約根本不需要意識到分片的存在。事實上,當負載變得過高時,通常希望向現有的單鏈專案(例如以太坊)新增分片。
擴展的另一種方法是使用如~\ptref{sp:het.confed} 中描述的異質工作鏈的「聯邦」,允許每個使用者在她選擇的一個或幾個工作鏈中保留她的帳戶,並在必要時將資金從她在一個工作鏈中的帳戶轉移到另一個工作鏈,本質上執行 $1:1$ 山寨幣交換操作。這種方法的缺點已經在~\ptref{sp:het.confed} 中討論過。
然而,以快速可靠的方式實作分片並不那麼容易,因為它意味著不同分片鏈之間有大量訊息。例如,如果帳戶在 $N$ 個分片之間均勻分布,並且唯一的交易是從一個帳戶到另一個帳戶的簡單資金轉移,則只有一小部分($1/N$)的所有交易將在單個區塊鏈內執行;幾乎所有($1-1/N$)交易將涉及兩個區塊鏈,需要區塊鏈間通訊。如果我們希望這些交易快速,我們需要一個在分片鏈之間轉移訊息的快速系統。換句話說,區塊鏈專案需要在~\ptref{sp:blkch.interact} 中描述的意義上「緊耦合」。
\nxsubpoint\label{sp:dyn.stat.shard} \embt(動態和靜態分片。) 分片可能是{\em 動態的}(如果在必要時自動建立額外的分片)或{\em 靜態的}(當有預定義數量的分片時,這在最好的情況下只能透過硬分叉來更改)。大多數分片提議是靜態的;TON 區塊鏈使用動態分片(參見~\ptref{sect:split.merge})。
\nxsubpoint\label{sp:blkch.interact} \embt(區塊鏈之間的互動:鬆耦合和緊耦合系統。) 多區塊鏈專案可以根據組成區塊鏈之間支援的互動水平進行分類。
最低水平的支援是不同區塊鏈之間根本沒有任何互動。我們不在這裡考慮這種情況,因為我們寧願說這些區塊鏈不是一個區塊鏈系統的部分,而只是同一區塊鏈協議的單獨實例。
下一個支援水平是缺乏對區塊鏈之間訊息傳遞的任何特定支援,使互動原則上可能,但尷尬。我們稱這樣的系統為「鬆耦合」;在它們中,必須在區塊鏈之間傳送訊息和轉移價值,就好像它們是屬於完全獨立的區塊鏈專案的區塊鏈一樣(例如,比特幣和以太坊;假設兩方想要將保存在比特幣區塊鏈中的一些比特幣交換為保存在以太坊區塊鏈中的以太幣)。換句話說,必須將出站訊息(或其生成交易)包含在源區塊鏈的區塊中。然後她(或其他某方)必須等待足夠的確認(例如,給定數量的後續區塊)以將發起交易視為「已提交」和「不可變」,以便能夠基於其存在執行外部操作。只有這樣,才能提交將訊息中繼到目標區塊鏈的交易(可能連同發起交易的參照和存在性 Merkle 證明)。
如果在轉移訊息之前等待的時間不夠長,或者由於某些其他原因仍然發生分叉,則兩個區塊鏈的聯合狀態被證明是不一致的:訊息被傳遞到第二個區塊鏈中,但從未在(最終選擇的分叉)第一個區塊鏈中生成。
有時透過標準化訊息格式和所有工作鏈區塊中輸入和輸出訊息佇列的位置來新增部分訊息支援(這在異質系統中特別有用)。雖然這在一定程度上促進了訊息傳遞,但從概念上講與前一種情況沒有太大不同,因此這樣的系統仍然是「鬆耦合」的。
相比之下,「緊耦合」系統包括特殊機制以提供所有區塊鏈之間的快速訊息傳遞。所需的行為是能夠在發起區塊鏈的區塊中生成訊息後立即將訊息傳遞到另一個工作鏈。另一方面,「緊耦合」系統也被期望在分叉的情況下保持整體一致性。雖然這兩個要求乍一看似乎是矛盾的,但我們相信 TON 區塊鏈使用的機制(將分片鏈區塊雜湊包含到主鏈區塊中;使用「垂直」區塊鏈來修正無效區塊,參見~\ptref{sp:inv.sh.blk.corr};超立方體路由,參見~\ptref{sp:hypercube};即時超立方體路由,參見~\ptref{sp:instant.hypercube})使其能夠成為「緊耦合」系統,也許是迄今為止唯一的系統。
當然,建立「鬆耦合」系統要簡單得多;然而,快速高效的分片(參見~\ptref{sp:shard.supp})要求系統是「緊耦合」的。
\nxsubpoint\label{sp:blkch.gen} \embt(簡化分類。區塊鏈專案的世代。) 到目前為止我們建議的分類將所有區塊鏈專案分成大量類別。然而,我們使用的分類標準在實踐中恰好是高度相關的。這使我們能夠建議一種簡化的「世代」方法來對區塊鏈專案進行分類,作為對現實的非常粗略的近似,並附有一些範例。尚未實作和部署的專案以{\em 斜體}顯示;世代的最重要特徵以{\bf 粗體}顯示。
\begin{itemize}