秦文慧，李志淮，馬洪程

大連海事大學 信息科學技術(shù)學院，遼寧 大連 116002

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

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

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

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

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

1 問題的提出與研究

1.1 分片模型中的過載

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

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

由圖1可以看到，區(qū)塊鏈網(wǎng)絡(luò)中的交易進行隨機分配后，可能會出現(xiàn)分片2與其他分片未驗證交易數(shù)差距過大的現(xiàn)象。如果3個分片中節(jié)點處理能力恰好與1號分片中的交易數(shù)對應(yīng)，此時2號分片可能會因為未驗證交易數(shù)過多造成交易過載。

1.1.2 交易過載的概率

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

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

如果單個分片中的未驗證交易數(shù)超過該分片中當前輪次節(jié)點可驗證交易的最大數(shù)量Tmax，驗證節(jié)點在短時間內(nèi)無法完成驗證，該分片就會交易擁堵?？梢赃\用式（2）計算出單個分片中交易數(shù)超出Tmax的概率。

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

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

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

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

1.2 相關(guān)解決方法與分析

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

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

1.3 無狀態(tài)驗證的局限

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

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

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

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

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

2.1 分片的多輪驗證模型

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 節(jié)點綜合積分機制

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

2.2.1 節(jié)點共識表現(xiàn)評估

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

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

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

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

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

2.2.2 節(jié)點通信能力評估

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

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

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

2.2.3 節(jié)點綜合性能評估

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

其中，Ri(x)表示節(jié)點i的共識表現(xiàn)積分，Pi表示節(jié)點的通信能力積分，β是指標的權(quán)重參數(shù)，可根據(jù)具體情況設(shè)定合理的值?？紤]到?jīng)]有可靠傳輸?shù)谋Ｕ?，負載的優(yōu)化是無意義的。因此要嚴格杜絕通信能力強，但是共識表現(xiàn)差的節(jié)點作為驗證節(jié)點，可適當調(diào)整β的值。

2.3 交易負載計算模型

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

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

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

2.4 節(jié)點競選策略

2.4.1 節(jié)點狀態(tài)轉(zhuǎn)移機制

狀態(tài)分片中活躍節(jié)點的角色是動態(tài)轉(zhuǎn)變的，本文根據(jù)網(wǎng)絡(luò)中的節(jié)點不同的狀態(tài)，將節(jié)點劃分為全局候選節(jié)點、待同步狀態(tài)節(jié)點、分片內(nèi)就緒節(jié)點、分片內(nèi)共識節(jié)點和局外節(jié)點。處于不同狀態(tài)的節(jié)點對應(yīng)不同的行為。

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

（1）狀態(tài)分片后被分配到指定分片并等待加入分片進行工作的節(jié)點。

（2）后續(xù)新加入系統(tǒng)的節(jié)點。

（3）部分節(jié)點因為網(wǎng)絡(luò)問題掉線重連，可能會丟失部分狀態(tài)，同樣需要先同步信息后再參與共識流程。

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

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

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

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

2.4.2 可驗證的隨機分配算法

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

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

（1）狀態(tài)分片交易依據(jù)相應(yīng)規(guī)則被分配到分片中，通過VRF算法隨機分配節(jié)點到各個分片。

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

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

由于VRF的不可預(yù)測性、可驗證和無偏倚的特性優(yōu)勢，節(jié)點的分配無法預(yù)測，可以高效、安全且隨機地分配節(jié)點，保證了分片的驗證有效性和系統(tǒng)安全性。

2.4.3 狀態(tài)分片約束下的節(jié)點競選策略

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

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

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

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

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

（4）每輪驗證結(jié)束后，根據(jù)節(jié)點的共識表現(xiàn)更新節(jié)點分值，共識節(jié)點組按照分值進行排序，分值最低的節(jié)點進行末位淘汰，作為本輪轉(zhuǎn)出當前分片的節(jié)點，按照最新分值轉(zhuǎn)入全局候選節(jié)點序列的相應(yīng)位置。

（5）若檢測出節(jié)點作惡，則將節(jié)點轉(zhuǎn)入局外節(jié)點，使其失去加入分片內(nèi)參與驗證工作的資格。

節(jié)點競選的詳細流程如圖7所示。

3 實驗設(shè)計與結(jié)果分析

3.1 實驗基本設(shè)置

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

本文設(shè)計的狀態(tài)分片內(nèi)的交易過載多輪節(jié)點競選方案在實驗室環(huán)境下進行，需要設(shè)置以下假設(shè)條件：

（1）分片期間總節(jié)點數(shù)目保持均勻恒定。

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

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

3.2 分片規(guī)模及有效性分析

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

3.2.1 通信量與分片內(nèi)共識節(jié)點數(shù)目的關(guān)系分析

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

其中，B為網(wǎng)絡(luò)帶寬的最小值，Nsv為分片內(nèi)共識節(jié)點的數(shù)目，HashSize為轉(zhuǎn)發(fā)哈希的大?。ü潭?2 Byte），a為普通節(jié)點投票產(chǎn)生主節(jié)點所產(chǎn)生的通信量。BlockSize為打包的一個區(qū)塊的大小，其計算公式如下所示：

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

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

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

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

本文為了控制整個過程中所產(chǎn)生的通信量占用百分比為網(wǎng)絡(luò)帶寬的30%到40%，通過仿真計算得出共識節(jié)點應(yīng)該控制在10到19個的范圍內(nèi)。

3.2.2 單個分片內(nèi)不同拜占庭節(jié)點比例的概率分析

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

根據(jù)公式運用Python模擬計算出單個分片內(nèi)不同拜占庭節(jié)點比例的概率如圖9所示。

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

3.2.3 不同共識節(jié)點數(shù)目導致共識失效的概率分析

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

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

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

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

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

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

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

3.3 交易驗證輪數(shù)的研究

3.3.1 多輪輪數(shù)與驗證成功概率的關(guān)系

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

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

根據(jù)公式模擬出分片內(nèi)不同共識節(jié)點數(shù)下，輪數(shù)x對交易驗證成功率P的影響，如圖12所示。

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

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

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

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

3.3.2 輪數(shù)實驗

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

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

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

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

表3共識超時Table 3 Consensus timeout

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

3.4 交易驗證率對比實驗

區(qū)塊鏈系統(tǒng)的交易驗證率指的是在一段時間內(nèi)被成功驗證交易數(shù)目占總交易數(shù)目的比重，在相同時間內(nèi)，系統(tǒng)內(nèi)節(jié)點驗證的交易數(shù)目越多，則該系統(tǒng)的交易驗證率越高，其性能越高。本實驗?zāi)康氖球炞C本文方案可以有效提高系統(tǒng)的交易驗證率。

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

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

3.5 交易吞吐量對比實驗

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

其中，Δt表示一筆交易從發(fā)起到寫入?yún)^(qū)塊的時間間隔，Transactions表示在Δt時間內(nèi)寫入?yún)^(qū)塊的交易總數(shù)。為了驗證本文方案可以提高算法的吞吐量，在實驗室環(huán)境中，根據(jù)公式計算本文方案、MRPV分片方案以及OmniLedger三種方案在不同共識節(jié)點規(guī)模下的TPS。

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

4 總結(jié)

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

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

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