狀態分片中交易過載處理的節點競選方案

秦文慧，李志淮，馬洪程

大連海事大學 信息科學技術學院，遼寧 大連 116002

區塊鏈本質上是一個去中心化的賬本，是一種融合了密碼學技術、分布式數據庫、計算機網絡、共識算法等計算機技術的新型應用模式[1]。2021年6月，工信部發布文件指出：區塊鏈成為建設制造強國和網絡強國，發展數字經濟，實現國家治理體系和治理能力現代化的重要支撐。在各種政策和環境的激勵下，區塊鏈技術研究得到大力支持。然而，目前區塊鏈基礎設施無法滿足大規模應用的需求，其中限制區塊鏈技術大規模落地的一個重要因素就是區塊鏈的性能問題。

為了使區塊鏈能夠更好地適應實際需求，必須增強其可擴展性[2]。區塊鏈擴容[3]是區塊鏈亟待突破的核心技術之一，通過提升可擴展性，從而提升交易吞吐量。目前已有的擴容解決方案包括側鏈[4]、分片技術[5]、DAG（directed acyclic graph）技術等[6]。

分片是目前最有效的實現高性能而不降低去中心化程度的區塊鏈擴容方案。分片的思想是“分而治之”，在區塊鏈系統中，分片是指將事務和存儲劃分為不同的分組，每個分組并行處理交易，從而提升區塊鏈的性能[7]。分片包括網絡分片、交易分片、狀態分片等，其中狀態分片難度最大，狀態分片在網絡分片和交易分片的基礎上，不僅將交易處理并行化，且因每個分片只存儲與本分片交易相關的狀態信息，能夠減少存儲冗余。狀態分片可以從本質上突破區塊鏈的容量瓶頸[8]。

從理論上看，區塊鏈分片可以有效提高網絡的整體性能，但是由于交易根據一定規則隨機分配，難以被預先規劃，某個分片內極有可能因為交易量過大而發生交易擁堵。目前應用狀態分片技術的區塊鏈項目，尚未專門討論狀態分片后可能帶來的交易過載的處理問題。此外，區塊鏈中的驗證節點，即共識節點的性能實際上存在較大的差異，而在目前主流方案中的驗證節點分配時，沒有考慮節點交易驗證能力的差異。嚴重時，整個區塊鏈網絡的交易吞吐量也會因單個分片交易驗證擁堵而受到影響[9-10]。

綜上所述，本文針對區塊鏈狀態分片交易過載問題進行預研究，提出了一種狀態約束下分片內交易過載處理的多輪驗證節點競選方案。方案考慮到狀態分片約束下，節點不能隨意調度到其他分片，將分片內的交易驗證分為多輪，在不同輪次中優化節點競選策略，進行區塊鏈分片內的交易過載優化處理，當分片內交易過載時，分配性能高的節點進行下一輪的驗證。實驗表明，本文方案可以有效提升交易過載分片的交易驗證率，減少分片交易擁堵的現象，提升區塊鏈分片性能。

1 問題的提出與研究

1.1 分片模型中的過載

1.1.1 分片中的交易分配和分布特點

分片理論上能夠提升整個系統層面的性能，但是單個分片仍然可能存在單點過熱問題，即在具有分片的區塊鏈系統中，為了避免雙花攻擊[11]，交易往往按發送地址隨機分配到各個分片中，再次分配還是會分配到特定的分片，造成單個分片內部交易量過載，從而使得分片發生擁堵并且產生大量的交易成本。分片技術只是通過并行的方式實現了整體性能提升，但各分片本質上是小型的區塊鏈系統，其性能并沒有實質的提升，因此若在單個分片內存在過多交易，分片仍會發生擁堵，并且如果此分片內長期擁堵，所產生的交易成本也會遠高于其他分片。分片交易過載如圖1所示。

由圖1可以看到，區塊鏈網絡中的交易進行隨機分配后，可能會出現分片2與其他分片未驗證交易數差距過大的現象。如果3個分片中節點處理能力恰好與1號分片中的交易數對應，此時2號分片可能會因為未驗證交易數過多造成交易過載。

1.1.2 交易過載的概率

假設區塊鏈系統中有ks個分片，未驗證交易集合Tx={T1,T2,…,Tn}。由于區塊鏈中的交易是根據交易發送方的地址隨機分配到分片中的，可以將交易分配的過程視為n次獨立重復的伯努利試驗，每個未驗證的交易被分配到某一特定分片的概率為1/k。用X表示n重伯努利試驗中，新交易被分配到某一特定分片的次數，則X的取值可以是0,1,…,n，隨機變量X的離散概率服從二項分布。

假設單個分片中驗證節點Nsv數目保持均勻恒定并且每一輪可驗證交易的最大數量為Tmax，可以通過式（1）計算出單個分片分配的交易數為Tmax的概率，其中n為區塊鏈系統中的未驗證交易數，x為分配到某一分片的未驗證交易數。

如果單個分片中的未驗證交易數超過該分片中當前輪次節點可驗證交易的最大數量Tmax，驗證節點在短時間內無法完成驗證，該分片就會交易擁堵。可以運用式（2）計算出單個分片中交易數超出Tmax的概率。

根據式（2），設置n=1 000，ks=10，用Python模擬計算出當交易數為1 000，分片個數為10時，單個分片交易過載的概率。表1列舉了分片內的交易數Tmax=[120,130,140,150]與其對應發生過載的概率。

表1 單個分片交易數分配過載的概率Table 1 Probability of single sharding transaction number distribution overload

根據表1可以發現，當交易數為1 000，分片個數為10時，單個分片交易數超過120的概率約為0.22，此時該分片的交易數已經比各分片平均分配交易多出20%。以以太坊為例，分析分片交易過載對區塊鏈系統的影響。根據以太坊瀏覽器提供的相關數據，統計以太坊2021年10月28日至11月9日的每日交易筆數，如圖2所示。

圖2 中，橫坐標表示日期，縱坐標表示相對應的交易量。平均24小時鏈上交易數約為100萬筆。根據以太坊網絡中的分片個數為64個，平均分配交易到各個分片，每個分片分到的交易數約為15 600筆。如果其中一個分片中的交易數比平均分配多出20%，則該分片比其他分片多出3 120筆交易。分析可知，隨著網絡中交易數的增多，各分片所分配交易數之間的差距會越來越大。區塊鏈分片時無法保證各個分片內節點處理能力均衡。隨機分配交易具有很大的概率，導致部分分片未驗證交易過載。

1.2 相關解決方法與分析

目前的分片方案一般采用隨機方式分配節點和交易，然而區塊鏈網絡中的節點因設備、網絡環境等因素的不同，存在較大的性能差異。隨機分配節點會導致各個分片的整體性能差異較大，隨機分配交易又可能因性能較差的分片分得較多的交易負載而產生擁堵，導致整個區塊鏈系統交易處理能力下降。目前，區塊鏈分片交易過載的問題尚未在全球公有鏈中得到有效解決。

研究人員提出了OmniLedger[12]、NEAR[13]和以太坊[14-15]等狀態分片協議，利用分片技術將網絡中的節點和交易進行劃分，各個分片并行處理交易，提高了區塊鏈系統的交易處理能力。OmniLedger分片方案根據隨機協議選擇驗證者分組，利用RandHound協議保證分配過程的安全性。該分片方案實現了狀態分片，降低了節點的存儲和啟動開銷，但是并沒有考慮節點交易驗證能力差異，無法處理分片內交易過載。與以太坊不同，NEAR協議是單條區塊鏈，而各個分片植根于其上。像傳統的區塊鏈一樣，每個區塊都包含所有分片的所有交易，但是此數據并不存在于單個物理區塊中。應對過量的交易，該分片方案采用延遲的交易處理方式，如果交易重新分配時仍指向同一個分片，該分片方案無力處理。以太坊市值高達25 400億元，是規模僅次于比特幣的區塊鏈項目。以太坊2.0使用信標鏈進行節點分配，大大提高了區塊鏈網絡的性能，同時也面對著很多新的挑戰。以太坊2.0嘗試在信標鏈上部署負載均衡合約，當某個分片中出現交易擁堵時，通過調用合約將負載轉移到其他分片。該方案目前還未在項目中實際應用，其穩定性仍需進一步研究。

1.3 無狀態驗證的局限

針對區塊鏈分片隨機分配交易機制產生的難以預知的區塊鏈分片交易過載問題，文獻[16]提出了一種基于節點驗證能力積分的區塊鏈分片負載的多輪驗證方案。此方案根據各分片的剩余負載，將驗證能力高的節點再分配到高負載的分片進行后續的驗證，減少單個分片交易擁堵的情況。但是此方案沒有考慮狀態分片約束下，節點不能隨意競選的問題。

狀態分片中每個分片只存儲所負責分片中的狀態，因此在下一次節點重新分配時，新節點加入分片之前必須等待同步完該分片中的狀態信息后才可以加入分片并提供算力，否則將無法保證數據的連貫性，從而影響交易驗證的有效性。而狀態信息的同步需要消耗大量的時間，因此若頻繁地在分片之間進行節點的輪換，會極大地增加系統的延遲，從而影響系統的活性。因此，僅考慮無狀態驗證，節點隨意跨分片間調度是不可行的。

根據上述分析可知，在前期較少的關于交易過載處理的分片方案中存在無狀態驗證的局限。故本文針對以上問題進行分析及預研究，在跨分片節點調度外提出了一種狀態約束下交易過載處理的多輪節點競選方案。

2 分片多輪驗證模型的交易過載處理

本文在現有區塊鏈分片基礎上，提出了狀態分片約束下交易過載處理的多輪節點競選方案。一輪驗證后，通過節點綜合積分方法更準確地評價節點，計算剩余的未確認交易數量并判斷剩余負載，通過節點競選策略有效地組織節點進行交易驗證，以縮短區塊鏈交易確認時間，使得節點篩選更快收斂，實施均衡化處理，提高區塊鏈交易處理能力。

2.1 分片的多輪驗證模型

通過上述分析可以發現，區塊鏈狀態分片中，交易通常按照一定的規則被隨機分配到各個分片，且再次分配還是會被分配到特定分片，存在單個分片交易過載的問題。此外，區塊鏈系統的交易負載具有滯后性，即無法預先獲得各分片的交易負載對此進行處理。目前一些主流的分片項目并沒有針對分片的交易過載問題提出切實可行的解決方案。

針對單個分片內拜占庭節點比例過高導致單個分片失效概率增大的問題，多輪PBFT驗證（multiple rounds of PBFT verification，MRPV）方案[17]被提出。連續多輪進行交易驗證，當各個分片開始對分片內的交易進行驗證時，即為第一輪驗證，當分片中產生一個區塊后，即為一輪結束。本文基于此方案提出狀態分片交易過載處理的多輪PBFT驗證方案，利用多輪PBFT機制在每輪驗證后獲取到分片內的交易負載，通過調整分片內輪次間不同性能的驗證節點，來處理狀態分片內交易過載的問題，提升區塊鏈系統的TPS（transaction per second）。

如圖3所示，第t時隙，分片的狀態為SS(t)，待驗證的交易集合為Tx(t)，分片內共識節點組表示為Vsv(Nsv=||Vsv)。在第t時隙，共識驗證節點組Vsv利用當前狀態SS(t)對當前交易集合Tx(t)進行第1輪共識驗證，記為Vsv(t,1)[SS(t),Tx(t)]。

若交易在第t時隙被驗證成功，則將交易打包上鏈，并更新狀態。第t時隙結束后，若Tx(t)中仍存在未經驗證的交易，則重新選取共識節點對此批交易，在第t+1時隙進行第2輪的驗證，如過程①所示，記為Vsv(t+1,2)[SS(t),Tx(t)]。若仍未驗證成功，則繼續重新選取共識節點進行第3輪驗證，如過程②所示，記為Vsv(t+2,3)[SS(t),Tx(t)]，直至達到輪數上限放棄交易。

多輪方案中不同輪次可能對應多個共識組，分別處理不同的交易。若交易集合Tx(t)在第t時隙被確認，則將交易打包上鏈，并在第t+1時隙將分片狀態更新為SS(t+1)。第t+1時隙又將有新的交易集合Tx(t+1)等待被處理，選取新的共識節點組對此批交易進行第一次驗證，記為Vsv(t+1,1)[SS(t+1),Tx(t+1)]。隨著輪數增多，每一時隙的交易驗證延遲會帶來更多的負載。

狀態分片交易過載處理的多輪驗證方案的具體過程如下：

（1）將節點隨機分配到各個分片，再將交易根據映射規則隨機分配到各個分片，然后初始化交易處理的輪次。

（2）待同步節點首先進行狀態同步，并根據節點狀態同步的快慢測評其通信能力。待同步節點完成狀態同步后可以進入分片內并獲得參與共識驗證的資格，通過VRF隨機函數選出共識節點。

（3）由分片內的共識節點集合Vsv對分配到該分片的全部交易進行共識驗證，超過2/3共識節點達成一致則驗證成功，將該組交易打包到區塊。通過節點綜合積分機制更新共識節點的分值，并進行交易負載的計算，判斷是否有未驗證交易。若分片內交易過載，則通過節點競選策略選取通信能力高的節點進行下一輪的驗證，更快地處理交易。

（4）若分片未達到共識，則扣除共識節點的分值，通過節點競選策略分配共識表現較好的驗證節點進行下一輪的驗證。

（5）若連續T輪過后仍未達成有效共識，則選擇放棄該筆交易。通過犧牲交易的可用性，保全系統的總體性能。

需注意，在步驟（3）中，達成共識的分片同樣需要重新分配共識節點，一方面，如果分片內交易過載，需分配綜合性能強的節點進行驗證，提高分片的處理能力。另一方面，如果不進行節點重新分配，分片中的節點一直處于同一分片中，會導致如下兩個問題：一是分片中的拜占庭節點會因為一次偶然的分配而一直留在正常工作的分片中，其共識表現分值無法被扣除，拜占庭節點身份無法體現，不利于系統整體的穩定。二是隨著驗證輪數的增加，同一分片中的節點熟悉彼此后，可能會為謀求更大的利益，互相勾結攻擊分片，影響系統的安全性。

多輪驗證的流程圖如圖4所示。

2.2 節點綜合積分機制

本文在現有區塊鏈分片的基礎上，提出了節點綜合積分機制。文獻[18]通過節點處理交易能力來進行節點積分，本文考慮到實際網絡中的影響因素，根據節點的共識表現和節點的通信能力兩個指標來評估節點性能，并且為每個指標都設置一個指標權重占比，然后再根據這些指標數據，計算分數，綜合權衡兩個指標。在下一輪節點重新分配時，遵循基于節點積分的分配算法，選取綜合積分高的節點進入下一輪共識，解決區塊鏈系統分片內剩余負載不均衡的問題，提高系統的交易吞吐量。

2.2.1 節點共識表現評估

節點在共識過程中的表現是降低選中拜占庭節點參與共識的重要指標，同時也是區塊鏈中節點提供資源和服務可靠性的評價因素。通過對區塊鏈網絡中節點行為信息的收集、評價、量化、更新，從而達到利用節點的可靠性評估對其行為進行規范和限制的目的。在區塊鏈網絡通信中，選擇共識表現好的節點參與驗證，在一定程度上可以保證區塊鏈網絡的可靠性。因此，節點共識表現評價機制須體現多粒度、動態更新的特點，同時符合人類社會信任評價中“信任積累緩慢，信任迅速消減”的特性，即信任的增加是緩慢的，信任的衰減是迅速的。如果只是根據節點每次的共識結果對其積分進行累加，會太過于片面，可能會導致一些惡意節點故意通過節點通信能力來累積分值，從而得到參與驗證的機會，這樣會對系統的性能造成比較大的負面影響。

基于此，本文引入了基于時間的信任衰減函數以及節點信任積分的動態更新策略，來提升區塊鏈網絡的可靠性和安全性。隨著時間的推移，節點成功參與兩次共識之間相差的時間越長，共識積分的占比會越小。共識積分的衰減函數如式（3）所示：

式（3）中，Ti表示隨著時間的推移，節點的共識表現分值的衰減程度；tnew表示節點當前共識發生的時間；tpre表示節點上次共識發生的時間。|tnew-tpre|值越大，Ti就越小。當節點長時間不在線，或者出現網絡故障，導致節點參加兩次共識時間的間隔比較長，則衰減程度就會相應增大。根據節點的投票信息與最終的共識結果是否一致來判斷節點是否成功參與共識。

節點共識分值Ri(x)的具體計算方式如式（4）所示。如果投票信息與最終的共識結果一致，則節點的可靠值是結合時間衰減函數進行累加。若共識成功則加1分。若不一致或者檢測到驗證節點作惡，則表明此節點為惡意，共識分值減10分。如果節點超時沒有進行響應，表明此節點可能是因為網絡故障造成超時，但是也有可能節點是惡意不回應，此時的積分不會直接降為初始值，而是將積分值減5分。

式（4）中，x表示節點i參與共識的次數，Ri(x)表示節點i參與x次共識后的積分，Ri(x)的初始值Ri(0)設為0，Ti表示節點i的共識表現隨時間的衰減程度。

2.2.2 節點通信能力評估

在區塊鏈真實網絡中，區塊鏈節點具有異構性，主要表現在節點的驗證能力、存儲能力、通信能力的差異[19]。一筆交易信息要快速可靠地傳輸給網絡中的其他節點，需要重點考慮節點通信能力，本文中節點的通信能力評測是在狀態同步過程中進行的。本文對節點的通信時間和通信效率進行研究，將節點的硬件性能作為通信影響因子來量化節點的通信能力。

節點由于硬件配置的異構性導致其在區塊鏈通信過程中的傳輸能力存在差異。文獻[2]通過CPU內核數n、CPU頻率C、內存容量M、磁盤I/O速率D、網絡帶寬T等指標來計算一個節點的硬件性能。本文的積分重點在節點對共識的貢獻力度，因此主要考慮節點的CPU處理頻率、內存大小以及CPU利用率和內存利用率。通信能力Pi的量化公式如下：

其中，Ci代表節點i的CPU處理頻率，n表示CPU內核數，Mi表示節點i的內存大小，Uc表示節點的CPU利用率，Um表示節點的內存利用率。

2.2.3 節點綜合性能評估

節點的綜合性能MergeScore評估計算方式如式（6）所示：

其中，Ri(x)表示節點i的共識表現積分，Pi表示節點的通信能力積分，β是指標的權重參數，可根據具體情況設定合理的值。考慮到沒有可靠傳輸的保障，負載的優化是無意義的。因此要嚴格杜絕通信能力強，但是共識表現差的節點作為驗證節點，可適當調整β的值。

2.3 交易負載計算模型

區塊鏈系統中的交易根據交易發送方的地址隨機分配到各個分片，因此無法保證交易數量均勻分配。本文方案引入多輪驗證的思想，分片中的節點在每一輪達成共識打包交易出塊后，計算本輪分片內剩余交易負載，剩余負載進入下一輪與新交易一起打包處理，根據分片內的剩余負載來選取已有節點在不同輪次之間均衡使用。本文的每一輪待處理的交易負載包括上一輪次分片內的剩余負載和當前輪次的交易負載兩部分，由式（7）計算：

其中，shardLi(t)為分片i在第t輪的交易負載值，Counti(T(t-1))為該分片上一輪交易驗證后的剩余負載，即未確認交易數，Counti(T(t))表示該分片第t輪新提交的交易數。分片的交易負載與輪次的關系如圖5所示。

需注意，不同輪次對應不同的共識組，且每一輪次可能對應多個共識組。第i輪的剩余負載作延后處理，后續輪次的驗證一定是對未確認交易的重復驗證。

2.4 節點競選策略

2.4.1 節點狀態轉移機制

狀態分片中活躍節點的角色是動態轉變的，本文根據網絡中的節點不同的狀態，將節點劃分為全局候選節點、待同步狀態節點、分片內就緒節點、分片內共識節點和局外節點。處于不同狀態的節點對應不同的行為。

待同步狀態節點由于沒有存儲當前分片的狀態信息，需要先進行狀態同步，即同步節點所在分片的賬本信息后才有資格參與交易的驗證。此外，通過節點狀態同步的快慢來測定節點的通信能力。以下三種情況的節點統稱為待同步狀態節點：

（1）狀態分片后被分配到指定分片并等待加入分片進行工作的節點。

（2）后續新加入系統的節點。

（3）部分節點因為網絡問題掉線重連，可能會丟失部分狀態，同樣需要先同步信息后再參與共識流程。

狀態同步后的節點會進入分片內，獲取參與交易驗證的資格，轉換為分片內就緒節點。每一輪通過節點競選策略選出共識節點集合進行交易的驗證。

在完成一輪驗證并進行積分核算后，共識節點集合按照分值進行排序，并將排名末位的節點淘汰轉入全局候選節點隊列，進入靜默期靜默一段時間等待進入待同步狀態節點。

全局候選節點隊列依據分值按序排列，等待加入分片進行工作，后續可依據輪次通過隨機算法選中進入到分片內的待同步節點集合。

分片內的就緒節點需要監督共識節點進行共識驗證，若通過欺詐性證明檢測出共識節點作惡，例如節點隨意篡改轉發信息、丟棄信息、破壞網絡資源等，則進行舉報，將作惡節點轉入分片外的局外節點集合，剝奪其進入分片內參與驗證的資格，并對提交了欺詐性證明的就緒節點進行獎勵。節點狀態轉換流程如圖6所示。

2.4.2 可驗證的隨機分配算法

VRF（verifiable random function）是可驗證的隨機函數，是結合了哈希函數與非對稱加密的應用算法。通過隨機輸入一個數值，得到一個任意的輸出，且該輸出的結果，可以通過零知識證明來驗證其正確性。

本文基于以下三種情況采用可驗證的隨機分配算法VRF進行節點的分配：

（1）狀態分片交易依據相應規則被分配到分片中，通過VRF算法隨機分配節點到各個分片。

（2）每一輪次通過VRF算法從就緒節點中重新選取驗證節點，以此來保證節點分配時較高的隨機性、不可預測性和可驗證性。

（3）全局待分配同步節點需要通過VRF算法，依據當前輪次隨機選中進入分片內待同步狀態節點集合，以此保證其在不同時刻進入不同的分片。

由于VRF的不可預測性、可驗證和無偏倚的特性優勢，節點的分配無法預測，可以高效、安全且隨機地分配節點，保證了分片的驗證有效性和系統安全性。

2.4.3 狀態分片約束下的節點競選策略

針對第1章的分析，本文提出了一種適應于狀態分片約束下的多輪PBFT驗證的節點競選方案。利用分片內節點能力的差異，每一輪驗證結束后通過更新共識節點組，對交易過載的分片進行快速調整處理，同時可以降低分片內的拜占庭節點比例，有效提高驗證效率。

方案進行節點競選的具體步驟如下：

（1）每輪交易驗證完成后，根據節點綜合積分機制進行節點積分核算。

（2）打包交易成功出塊后，計算本輪剩余交易負載，下一輪次再結合新分配的交易根據交易負載計算模型計算出本輪的交易負載。

（3）節點競選首先借助VRF隨機算法，從分片內的節點Ns中隨機選出一半節點，以此保證一定的隨機性和公平性。再選取前端分值最高的Nsv個共識節點進入下一輪驗證。

（4）每輪驗證結束后，根據節點的共識表現更新節點分值，共識節點組按照分值進行排序，分值最低的節點進行末位淘汰，作為本輪轉出當前分片的節點，按照最新分值轉入全局候選節點序列的相應位置。

（5）若檢測出節點作惡，則將節點轉入局外節點，使其失去加入分片內參與驗證工作的資格。

節點競選的詳細流程如圖7所示。

3 實驗設計與結果分析

3.1 實驗基本設置

為驗證本文提出的狀態分片內的交易過載多輪節點競選方案的可用性和有效性，對本方案進行分片規模與有效性分析和交易驗證輪數的研究，并將本方案與未進行交易過載處理的MRPV方案進行對比實驗，觀察兩種方案在交易驗證率、系統吞吐量方面的性能。實驗設置總節點數為1 000，每100個節點為1個分片，設置共識節點數為10。節點的共識表現初始分值為100分，節點通信能力初始分值為60～100分。

本文設計的狀態分片內的交易過載多輪節點競選方案在實驗室環境下進行，需要設置以下假設條件：

（1）分片期間總節點數目保持均勻恒定。

（2）本實驗所設置的交易均不屬于跨分片交易。

（3）本實驗的節點屬性可變，即本輪誠實的節點，下一輪可變成拜占庭節點。

3.2 分片規模及有效性分析

在本文的多輪PBFT驗證方案中，由于每一輪共識時間較短，且狀態分片中的待同步節點還需同步每一輪共識后產生的區塊，增加了分片內的通信量，本節將分析共識節點的數目，在降低分片內通信開銷的同時，保證每個分片內的驗證有效性。

3.2.1 通信量與分片內共識節點數目的關系分析

在真實區塊鏈網絡中，考慮到每個節點的實際網絡的帶寬可能并不一致，因此網絡中的通信量會有一定的限制。由于PBFT共識機制中驗證節點增多，分片內的通信復雜度也會顯著增加。本文將選取盡量少的驗證節點進行共識，降低通信開銷成本。為了滿足系統的活性，節點的網絡帶寬必須足以讓整個網絡能同時進行上一區塊的廣播驗證，客戶端發布待驗證交易、主節點共識以及普通節點投票幾項工作。本文將滿足網絡主節點所需的最低網絡帶寬抽象為式（8）：

其中，B為網絡帶寬的最小值，Nsv為分片內共識節點的數目，HashSize為轉發哈希的大小（固定32 Byte），a為普通節點投票產生主節點所產生的通信量。BlockSize為打包的一個區塊的大小，其計算公式如下所示：

式（9）中，HeaderSize為區塊頭的大小，txSize為一條交易信息的大小。

式（10）中，TxCount為一個區塊打包的交易數量，TPS為每秒可打包的交易數量，TD為上一區塊進入主節點共識的時刻與本輪進入主節點共識階段的時間差。

式（11）中，CP為一致性協議產生的通信量，p為prepare階段節點廣播的確認消息的大小，c為commit階段各節點廣播的確認消息的大小。

通過式（11）可以看出，網絡中最小帶寬取決于分片內共識節點的數量Nsv。若僅僅將Nsv設置過小，雖然通信量較低，但是這將導致嚴重的中心化以及安全性問題，這與本文分片規模設置的初衷不符。分片內共識節點的數量Nsv如果設置過大，將會使得網絡中的通信量過大，從而造成網絡擁堵。其中節點數量帶來的通信量占網絡帶寬比如圖8所示。

本文為了控制整個過程中所產生的通信量占用百分比為網絡帶寬的30%到40%，通過仿真計算得出共識節點應該控制在10到19個的范圍內。

3.2.2 單個分片內不同拜占庭節點比例的概率分析

設置系統總節點數N為1 000，單個分片內節點數Ns為100，系統內拜占庭節點比例為1/3。X1表示單個分片內節點數Ns中拜占庭節點的數量，X1服從超幾何分布，記為X1～H(Ns,N×Pn,N)，系統中總的拜占庭節點比例Pn為1/3。系統進行節點分配時，可看作從系統N個節點中為每個分片選取Ns個節點，則在分片內拜占庭節點數量為K1時，分片內拜占庭節點比例Ps在不同點的取值概率P1如式（12）所示：

根據公式運用Python模擬計算出單個分片內不同拜占庭節點比例的概率如圖9所示。

由圖9可知，當系統內總拜占庭節點比例Pn為1/3時，單個分片內拜占庭節點比例Ps在[0，0.2]范圍內的概率之和為1.50E-3；在[0.2，0.45]范圍內的概率為0.99，其中，當Ps等于0.33時的概率最大；在[0.45，1]范圍內的概率之和為7.02E-3。可以發現單個分片拜占庭節點比例在[0.2，0.45]范圍內的概率較大。經驗算，P1的概率總和近似為1。

3.2.3 不同共識節點數目導致共識失效的概率分析

假設分片內共識節點數量為Nsv，分片內共識節點組中拜占庭節點比例為Psv,X2表示選取的Nsv個共識節點中拜占庭節點的數量，則X2服從超幾何分布，X2～H(Nsv,Ns×Ps,Ns)。Psv在不同共識節點數取值的概率P2如式（13）所示：

單個分片內節點數Ns中拜占庭節點的數量X1和共識組中拜占庭節點的數量X2所有情況下分片失效的概率取值之和Psum如式（14）所示。經驗算，Psum的總和近似為1。當共識節點組中拜占庭節點比例超過1/3時，共識節點組會無法達成共識，導致共識失效。當分片內共識節點數量Nsv不同時，共識節點中拜占庭節點所占的比例Psv也不同，從而導致節點共識失效的概率不同。共識失效的概率Pfailure如式（15）所示。

根據式（15）運用Python進行模擬計算，當分片內拜占庭節點比例Ps在[0.2，0.45]范圍內，共識節點的數目在[10，19]范圍內，不同共識節點數目導致共識失效的概率如圖10所示。

根據圖10可知，共識失效的概率隨著分片內拜占庭節點比例Ps的增大而增大。而共識節點數量和共識失效概率存在振蕩的情況。

選取分片內拜占庭節點比例Ps出現概率最高的值0.33，共識節點的數目在{10，19}范圍內，不同共識節點數目導致共識失效的概率如圖11所示。

根據圖11可得知，隨著共識節點數量的增加，共識失效的概率呈現總體上升的趨勢，并產生周期長度為3的振蕩，因此Nsv的節點數量可按3i+C來選定范圍。其中，C是常數0、1、2，i取正整數。

綜上分析，本文將分片內共識節點數Nsv取值定為[10，13，16]，在降低通信開銷的同時，保證了分片內PBFT共識的驗證有效性。

3.3 交易驗證輪數的研究

3.3.1 多輪輪數與驗證成功概率的關系

本方案中設置一筆交易被驗證失敗的次數高于某一限定值后就放棄該筆交易。對輪數上限的設置關系到系統整體的性能，若輪數上限設置過低，會導致大量交易被放棄，系統的交易驗證率降低。若輪數上限設置過高，又會影響到交易的處理延遲，導致過多交易擁堵，對系統的負荷帶來壓力。下面將詳細分析對于驗證輪數的設置。

根據以上分析，當分片內拜占庭節點比例較高時，共識失效概率依舊不可忽視，威脅系統的安全性。因此本文通過多輪驗證以有限地犧牲交易的可用性，保全系統的性能。多輪驗證中，一筆交易進行x輪驗證直到被驗證成功才被打包到區塊上，用X表示多輪的驗證次數，假設交易在第x輪被成功驗證，則前x-1輪次均驗證失敗，那么X近似服從幾何分布，記為X～GE(p)，其中p為驗證成功的概率，pfailure表示交易驗證失敗的概率，則p=1-pfailure。交易驗證成功的概率P如式（16）所示：

根據公式模擬出分片內不同共識節點數下，輪數x對交易驗證成功率P的影響，如圖12所示。

根據圖12可以看出，隨著輪數的加大，一筆交易在k輪內被驗證成功的概率也在增大。而隨著共識節點數目的增加，交易成功率會隨之降低，需要更多的輪數來保證其可用性。

此外，根據公式模擬出分片內不同拜占庭節點比例，輪數x對交易驗證成功率P的影響，如圖13所示。

根據圖13可知，當分片內拜占庭節點比例Ps不變時，隨著交易驗證輪數的增加，交易共識成功率會逐漸增大。當分片內拜占庭節點比例低于0.3時，大多數交易在1到4輪有很大的概率共識成功。當分片內拜占庭節點比例為0.3時，經過4輪驗證，交易驗證成功的概率就可以達到99%。當分片內拜占庭節點比例為出現概率最高的值0.33時，在交易驗證輪數為8時，交易驗證成功的概率達到了99%。當交易輪數達到14時，即使在分片內拜占庭節點比例為0.45的情況下，交易驗證成功率也達到了99%。

綜上所述，多輪驗證方案相較于傳統的單輪驗證方法，交易驗證成功率大幅提高，證明多輪方法達到了以犧牲交易的可用性提升系統性能的目的。

3.3.2 輪數實驗

實驗環境設置分片內節點數Ns為100，每個節點完成同步后隨機對應60～100的通信分值，并給其設置100分的共識表現初始值。取分片內拜占庭節點比例Ps出現概率最高的值0.33，共投放10萬筆交易。根據第3.2節分析，共識節點數目Nsv取值范圍[10，13，16]。每輪根據共識節點的表現更新其共識表現分值。通過實驗計算本文方案中每輪的交易成功率，如表2所示。

表2每輪的共識成功率Table 2 Success rate of each round

由表2可見，隨著共識節點數的增加，交易驗證率減少。當Nsv=10時，第4輪交易驗證率就已接近99%。隨著輪數的加大，交易在k輪內被驗證成功的概率也在增大。當輪數為6時，對一筆交易驗證成功的概率達到了99%，表明系統能以較低的處理延遲確保更高的驗證成功率且更快收斂。

此外，在保證最終共識超時的概率低于10-7時，計算出分片中不同的共識節點數目Nsv下，輪數T與共識超時概率的關系，如表3所示。

表3共識超時Table 3 Consensus timeout

由表3可見，當分片失效概率小于10-7時，此時的多輪輪數Tmax=8。本文方案將多輪輪數上限定為8輪，即對同一筆交易進行8輪共識驗證仍沒得到統一驗證結果，就放棄這筆交易。

3.4 交易驗證率對比實驗

區塊鏈系統的交易驗證率指的是在一段時間內被成功驗證交易數目占總交易數目的比重，在相同時間內，系統內節點驗證的交易數目越多，則該系統的交易驗證率越高，其性能越高。本實驗目的是驗證本文方案可以有效提高系統的交易驗證率。

本實驗的研究目標是證明本文方案能夠有效地提升系統的交易驗證率。設定總節點數目為1 000，分片數目為10。初始時將節點隨機分配到各分片，統計各分片的交易驗證情況，分別計算本文方案和MRPV分片方案以及OmniLedger方案中每輪驗證完成后各分片的交易驗證率。交易驗證率對比結果如圖14所示。

實驗結果如圖14，隨著時隙的增加，三種方案的交易驗證率均不斷提升。本文方案與MRPV方案由于采用了多輪驗證，通過連續多輪次的交易驗證，對之前未確認的交易重新驗證，保證了交易的最終確認，最終的交易驗證率均趨近100%。而OmniLedger方案由于設定一筆交易在一次驗證失敗后將直接丟棄該筆交易，交易驗證率僅可達到90%。通過對比分析本文方案和MRPV方案兩種多輪模擬系統，可以看出本文方案在第8輪交易驗證率就已達到99.99%，而MRPV方案的交易驗證成功率在第15輪才達到99.99%。

3.5 交易吞吐量對比實驗

交易吞吐量代表系統單位時間內處理事務或交易的能力，是衡量系統性能的重要指標，一般用TPS表示系統吞吐量，計算公式如式（17）所示：

其中，Δt表示一筆交易從發起到寫入區塊的時間間隔，Transactions表示在Δt時間內寫入區塊的交易總數。為了驗證本文方案可以提高算法的吞吐量，在實驗室環境中，根據公式計算本文方案、MRPV分片方案以及OmniLedger三種方案在不同共識節點規模下的TPS。

由圖15可以看出，本文方案的平均TPS優于沒有進行交易過載處理的MRPV和OmniLedger方案，且在任意拜占庭節點比例下，這種優勢都比較明顯。主要原因有三點：一是本文方案根據剩余負載在輪次間競選性能高的節點進行交易過載處理；二是減少單個分片內參與驗證的節點數量，提高了共識達成的速度；三是本文方案能夠通過節點綜合積分機制，將拜占庭節點淘汰，使得拜占庭節點參與交易驗證的機會降低，提高系統的穩定性以及交易處理的效率。綜上所述，本文方案體現出了更高的平均TPS，能夠滿足更大規模的系統實現。

4 總結

本文針對區塊鏈狀態分片內的交易過載問題，提出了一種狀態分片約束下的多輪節點競選驗證方案。本文方案將分片內的交易驗證分為多輪，在每輪驗證完成后根據節點的通信能力和節點共識表現進行綜合積分核算，并計算分片內的交易負載，確認分片的交易過載情況，進而在下一輪驗證中增強分片的處理能力；通過利用節點競選策略對分片內的節點在不同輪次之間均衡使用，實現狀態分片內交易過載處理，在犧牲延遲來保證安全性的前提下，提高系統的性能。

通過實驗驗證，本文方案提出的狀態分片多輪節點任務競選方案可以有效處理分片內交易過載，提升分片內的交易驗證率，提升整體TPS。但是本文方案存在一定局限性，由于考慮到狀態分片的約束，節點不能在分片間隨意調度。目前實現了分片內部的已有節點在不同輪次間均衡使用，對狀態分片約束下分片間的負載均衡和信標鏈上負載均衡的實現還在探索中，可在后續的研究中改進和優化。

此外，本文基于大連海事大學區塊鏈實驗室團隊成員陳靜、段培培、高冬雪、厚香瑩、王冬雪、馬洪程等同學的共同基礎研究。