王夫森，李志淮，田 娜

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

1 引言

區(qū)塊鏈技術(shù)作為比特幣[1]的底層協(xié)議，具有去中心化、難篡改、允許運行在非許可環(huán)境下的特點。區(qū)塊鏈本質(zhì)是一個去中心化的賬本，有效解決了拜占庭將軍問題[2]，實現(xiàn)了在點對點網(wǎng)絡(luò)中互不信任的節(jié)點通過遵循預(yù)設(shè)的機(jī)制達(dá)成數(shù)據(jù)的最終一致性，從而降低了現(xiàn)實世界的信任成本。

但是，現(xiàn)階段的區(qū)塊鏈技術(shù)仍是不成熟的，面臨著擴(kuò)容困境[3-4]?，F(xiàn)有的解決方案主要歸納為Layer1 層擴(kuò)容和Layer2層擴(kuò)容方案，Layer1擴(kuò)容方案主要包括分片技術(shù)[5]、DAG[6]結(jié)構(gòu)、代理共識協(xié)議、增大區(qū)塊[7]等。Layer2擴(kuò)容方案主要包括側(cè)鏈[8]、狀態(tài)通道[9-10]等。

區(qū)塊鏈分片的概念最早是在文獻(xiàn)[5]中提出，本質(zhì)是一種將計算和存儲分散到對等網(wǎng)絡(luò)的分區(qū)方式，每個節(jié)點只維護(hù)與其分片相關(guān)的信息。分片方案通過切割網(wǎng)絡(luò)中的節(jié)點和交易，以實現(xiàn)每秒處理數(shù)千筆交易的區(qū)塊鏈網(wǎng)絡(luò)。

POW 類共識算法屬于概率性算法，采用最長鏈競爭原則[11]，不適合分片內(nèi)；POS 類共識算法的邏輯是從整體上假定少數(shù)利益不能違背多數(shù)利益，也不適合被分割的分片內(nèi)。目前分片內(nèi)多采用聚合簽名優(yōu)化后的PBFT[12-13]共識算法，是一種被證明的P2P網(wǎng)絡(luò)中實現(xiàn)數(shù)據(jù)最終一致性的確定型共識算法，它允許含有傳遞惡意消息或任意延遲消息的拜占庭節(jié)點，但其比例小于總節(jié)點數(shù)的1/3。

區(qū)塊鏈分片方案盡管提高了區(qū)塊鏈吞吐量，但在采用PBFT共識算法的分片方案中，即使總體拜占庭節(jié)點比例不超過三分之一，單個分片內(nèi)拜占庭節(jié)點比例也可能會超過三分之一，使得這些分片的驗證有效性和可用性受到威脅。

針對分片后單個分片驗證有效性降低的問題，在文獻(xiàn)[5]中，ELASTICO采用增加單個分片中的節(jié)點數(shù)目來降低單個分片失效的概率，通過將單個分片中的節(jié)點數(shù)目增加至600 個來保證單個分片失效的概率低于百萬分之一。在文獻(xiàn)[14-16]中，采用包括RandHound、VSS、VRF、Randao節(jié)點隨機(jī)分配方案提高單個分片的驗證有效性[14-16]。在節(jié)點隨機(jī)分配方案中，節(jié)點不具有自主選擇分片的可能性，將節(jié)點地址、IP地址、公鑰等信息作為輸入進(jìn)行簽名與Hash 計算，將得到的哈希結(jié)果依據(jù)映射關(guān)系分配到既定分片中。在文獻(xiàn)[17]中，通過將礦工節(jié)點運行在TEE環(huán)境中以及通過SGX產(chǎn)生的隨機(jī)數(shù)將節(jié)點分配到既定分片[17]，降低節(jié)點作惡的概率。在文獻(xiàn)[18]中，提出連弩挖礦的方案[18]，每個礦工節(jié)點可以連接多個共識組，通過提高礦工收益的經(jīng)濟(jì)模型來降低礦工節(jié)點作惡的機(jī)率。

由上述文獻(xiàn)可知，目前國內(nèi)外關(guān)于分片方案的研究很多，各從不同方面對單個分片的驗證有效性進(jìn)行了分析。但是，目前關(guān)于分片驗證有效性的研究側(cè)重點集中在對分片驗證有效性的定性分析，缺乏對分片失效概率與拜占庭節(jié)點比例、分片內(nèi)節(jié)點數(shù)目之間量化關(guān)系的分析，以及對分片驗證失效后的進(jìn)一步處理。本文量化了影響分片驗證有效性的各變量之間的關(guān)系，計算出單個分片失效的概率以及全部分片都不失效的概率。本文提出的多輪驗證方案，通過連續(xù)多輪PBFT驗證，確保分片內(nèi)的交易得到更高概率的確認(rèn)。通過實驗數(shù)據(jù)可以表明，多輪驗證方案在提升分片規(guī)模的同時，確保單個分片的驗證有效性，實現(xiàn)分片方案下區(qū)塊鏈整體TPS（Transaction Per Second）的顯著提高。

2 問題描述與分析

2.1 問題描述

分片方案力圖通過并行處理提高區(qū)塊鏈TPS，但也可能因為分片內(nèi)驗證有效性明顯降低，達(dá)不到預(yù)期吞吐量，產(chǎn)生分片規(guī)模與分片內(nèi)驗證有效性的矛盾。

針對分片中采用PBFT 共識的方案，假設(shè)在未分片之前，總節(jié)點數(shù)目為n，拜占庭節(jié)點數(shù)為b，拜占庭節(jié)點數(shù)所占比例為f，則f=b n(0 ≤f＜1/3)。現(xiàn)假定將n個節(jié)點均勻分配到k個分片中，假設(shè)每個分片內(nèi)的節(jié)點數(shù)是L，則L=n k；每個分片中的拜占庭節(jié)點比例為，其中i(1 ≤i≤k)表示分片編號。將節(jié)點分配到k個分片中后，自然存在拜占庭節(jié)點分配不均，可能出現(xiàn)≥1/3 的問題，如圖1所示。

圖1 分片可能導(dǎo)致拜占庭節(jié)點在片內(nèi)聚集

圖1 描述了經(jīng)過分片后存在一定概率使得片內(nèi)拜占庭節(jié)點比例超過1/3。在圖1中，經(jīng)過節(jié)點分配后1號分片和3號分片中拜占庭節(jié)點數(shù)超過1/3，導(dǎo)致分片內(nèi)無法達(dá)成共識。

2.2 節(jié)將對單個分片失效的概率P與f、L的關(guān)系進(jìn)行量化，2.3節(jié)中將對所有分片都正常工作的概率Pr與f、L、k之間的關(guān)系進(jìn)行量化。

2.2 單個分片失效概率的分析

假設(shè)在未進(jìn)行分片之前，區(qū)塊鏈中的拜占庭節(jié)點比例為f(0 ≤f＜1/3)，L表示一個分片中節(jié)點的數(shù)量。對于L中的每一個節(jié)點在進(jìn)行共識的時候都會依據(jù)自己的身份進(jìn)行驗證，拜占庭或者非拜占庭身份。

令X=，其中Xi表示第i個節(jié)點表現(xiàn)出了拜占庭身份，X表示當(dāng)前片中拜占庭節(jié)點總個數(shù)。由于Xi只能表現(xiàn)出拜占庭節(jié)點身份或者非拜占庭節(jié)點身份，且這兩個身份之間相互獨立，所以X服從Binomial(L,X,f)的二項分布，當(dāng)X≥L/3時，分片失效。如公式（1）所示：

2.2.1 分片內(nèi)節(jié)點數(shù)與分片驗證有效性的關(guān)系

根據(jù)公式（1），設(shè)置f=[0.1,0.2,0.3]，改變L的值，用Python模擬研究L對P的影響情況。如表1所示。

表1 分片內(nèi)節(jié)點數(shù)L 對單分片失效概率P 的影響

根據(jù)表1，在拜占庭節(jié)點比例f不變時，單個分片失效的概率隨著分片中節(jié)點數(shù)目的增大而減小；當(dāng)f=0.3，L=60 時，單個分片失效的概率超過0.3；即使L=600，單個分片失效的概率在f=0.3 時仍大于0.04，這仍是一個不可接受的值，并且分片內(nèi)節(jié)點數(shù)目過多限制了分片規(guī)模。當(dāng)分片內(nèi)節(jié)點數(shù)目L不變時，在f=0.3的較高拜占庭比例下，單個分片的驗證有效性迅速降低。

2.2.2 拜占庭節(jié)點比例與單個分片驗證有效性的關(guān)系

根據(jù)公式（1），設(shè)定L=600 的情況下，研究不同數(shù)值的拜占庭節(jié)點比例f對于單個分片失效概率P的影響。如表2所示。

表2 拜占庭節(jié)點比例f 對單分片失效概率P 的影響

根據(jù)表2，當(dāng)L=600，f≤0.25 時，單個分片失效的概率很小。隨著f不斷接近1/3，單分片失效的概率出現(xiàn)指數(shù)類型增長，這將使得該分片幾乎失去了驗證有效性，難以達(dá)成驗證共識。單個分片的驗證有效性成為了影響整個區(qū)塊鏈TPS的瓶頸。

2.3 所有分片都正常工作的概率的分析

在進(jìn)行分片的區(qū)塊鏈中，區(qū)塊鏈的整體TPS受限于單個分片的驗證有效性。在分片后，若想提升區(qū)塊鏈的并行驗證能力，需要保證每個分片內(nèi)的驗證有效性。

下面計算分析分片之后所有分片都能正常工作的概率。假設(shè)：

區(qū)塊鏈中總節(jié)點數(shù)目為n；拜占庭節(jié)點比例為f(0 ≤f＜1/3)；每個分片中的節(jié)點數(shù)目為L；分片規(guī)模為k；分片后第i個分片中的拜占庭節(jié)點比例為fi′，節(jié)點進(jìn)入到任意分片概率相同。若想保證所有分片不失效，需要保證每個分片內(nèi)的拜占庭節(jié)點的比例fi′＜1/3，為了追求結(jié)果的準(zhǔn)確性，采用窮舉遍歷的方法，列舉出所有滿足分片都不失效的情況，如公式（2）所示。其中對于公式（2）有兩個限定條件，分別為公式（3）、（4）。

在公式（3）中，i1表示第1 個分片內(nèi)可能的拜占庭節(jié)點數(shù)目；i2表示第2 個分片內(nèi)可能的拜占庭節(jié)點數(shù)目；ij表示第j(1 ≤j≤k)個分片內(nèi)可能的拜占庭節(jié)點數(shù)目；所有滿足公式（3）的序列均被放入到集合B中。

對于公式（4），借鑒貪心算法思想，若保證每個分片都能正常運行，每個分片中保持分片驗證有效性的同時盡可能多地容納拜占庭節(jié)點。假設(shè)前k-1 個分片中在保證不失效的情況下盡可能多地存儲了拜占庭節(jié)點數(shù)，則第k個分片中可能的拜占庭節(jié)點數(shù)目分為兩種情況：一種是拜占庭節(jié)點數(shù)目已經(jīng)都分配到前k-1 個分片中，那么第k個分片中的拜占庭節(jié)點數(shù)目為0。另一種情況是前面k-1 個分片盡管盡可能多地分配了拜占庭節(jié)點，但仍有剩余，則剩下的拜占庭節(jié)點全部分配到第k個分片中。故第k個分片中的拜占庭節(jié)點的取值為0之間的較大值。

由于Pr的值受分片個數(shù)k、拜占庭比例f、分片內(nèi)節(jié)點數(shù)L的影響，采用控制變量的方法，分別研究f、L、k對Pr的影響。

2.3.1 分片內(nèi)節(jié)點數(shù)與所有分片都不失效的關(guān)系

根據(jù)上述2.2.1小節(jié)的分析，總結(jié)出分片內(nèi)節(jié)點數(shù)L會對分片的驗證有效性造成影響。探究L與Pr的關(guān)系，需要控制分片個數(shù)和拜占庭節(jié)點比例不變。本文主要研究高拜占庭節(jié)點比例下分片的失效概率，故選取f=0.3；分片個數(shù)k=4 是保證分片規(guī)模有效的合理有效值，固定這兩個值可準(zhǔn)確地研究有效分片規(guī)模與高拜占庭比例下分片內(nèi)節(jié)點數(shù)L對所有分片都不失效的概率值Pr影響。圖2 是基于公式（2）～（4）模擬k=4，f=0.3，分片中節(jié)點數(shù)目L對所有分片都不失效的概率影響圖。

圖2 L 對于Pr 的影響

圖2顯示，增加分片內(nèi)的節(jié)點數(shù)在一定程度上能提高分片不失效的概率，但所有分片不失效的概率依然很低，且隨著不斷增加分片內(nèi)節(jié)點數(shù)，Pr增大的幅度也在減小，僅增大分片中的節(jié)點數(shù)目在f=0.3 的較高拜占庭比例下仍無法解決分片失效率高的問題。

2.3.2 拜占庭比例與所有分片都不失效的關(guān)系

根據(jù)2.2.2小節(jié)分析，得出拜占庭節(jié)點比例對于分片驗證有效性的影響很大，參考文獻(xiàn)[14]，單個分片內(nèi)節(jié)點數(shù)適中為宜，故單個分片內(nèi)的節(jié)點數(shù)設(shè)定為L=180，根據(jù)公式（2）～（4），計算在n=720,L=180,k=4 時，不同的拜占庭節(jié)點比例f與所有分片都正常工作的概率Pr的關(guān)系，如圖3所示。

圖3 f 對Pr 的影響

依據(jù)圖3，當(dāng)每個分片中的節(jié)點數(shù)目固定時，所有分片正常工作的概率隨著拜占庭節(jié)點比例的增大而減小。當(dāng)拜占庭節(jié)點比例f=0.25 時，所有分片正常工作的概率為0.034；當(dāng)拜占庭節(jié)點比例f=0.3 時，所有分片正常工作的概率為0.015。較高拜占庭節(jié)點比例對分片驗證有效性影響較大。

2.3.3 分片規(guī)模與所有分片都不失效的關(guān)系

根據(jù)公式，計算在L=180，f=0.3 時，不同的分片規(guī)模k對所有分片都不失效的概率的影響。結(jié)果如圖4所示。

圖4 k 對Pr 的影響

在區(qū)塊鏈分片中，增加分片規(guī)模會使得系統(tǒng)的吞吐量線性增加，但分片規(guī)模的增加會使得分片的驗證有效性降低。當(dāng)k=3 時，所有分片正常工作的概率為0.022 3，而當(dāng)分片規(guī)模k=10 時，所有分片全部正常工作的概率低于0.005，此時分片已基本失去了驗證有效性。

3 多輪共識方案設(shè)計

通過第2 章量化影響分片驗證有效性的各變量之間的關(guān)系，數(shù)據(jù)表明當(dāng)拜占庭節(jié)點比例f較高時，擴(kuò)大分片規(guī)模k，分片內(nèi)驗證有效性P降低。當(dāng)拜占庭節(jié)點比例f越接近于1/3，單個分片失效的概率P越高，所有分片都不失效的概率Pr也就越小，單個分片的驗證有效性將成為提高區(qū)塊鏈TPS的關(guān)鍵，擴(kuò)大分片規(guī)模則又是解決當(dāng)前區(qū)塊鏈擴(kuò)容瓶頸的重要方法。在這樣一個難兩全的環(huán)境下，本文提出多輪PBFT共識驗證的方案，通過擴(kuò)大分片規(guī)模，并降低分片驗證失效率，力圖使區(qū)塊鏈整體TPS顯著提高。

多輪驗證方案的主要思想為當(dāng)一筆交易根據(jù)映射規(guī)則被分配到一個既定的分片后，由此分片中的所有節(jié)點對分片中的交易進(jìn)行共識驗證。如果共識驗證成功，則將交易打包進(jìn)區(qū)塊。如果交易驗證超時未得到有效共識，可依據(jù)節(jié)點的隨機(jī)分配算法重新分配一組新的節(jié)點到該分片，對此交易進(jìn)行新一輪共識驗證。

在拜占庭節(jié)點比例較高的情況下，如果連續(xù)經(jīng)過T次都沒有達(dá)成共識，將選擇放棄該筆交易，犧牲交易的可用性，同時要求放棄一筆交易的概率ε＜10-7。

對于輪數(shù)T的上限，在3.1節(jié)中給出。對于節(jié)點隨機(jī)分配算法，在3.2節(jié)中描述。

3.1 多輪輪數(shù)的選擇

3.1.1 拜占庭節(jié)點合謀的概率

在拜占庭節(jié)點比例比較高的情況下，可能在某個分片內(nèi)拜占庭節(jié)點占據(jù)大多數(shù)，且相互串通，進(jìn)行合謀攻擊。此時，盡管主節(jié)點收集到足夠多的消息，但是這些確認(rèn)消息是拜占庭節(jié)點之間串通合謀發(fā)送給主節(jié)點的，使得最終達(dá)成錯誤的共識。

若想在某個分片內(nèi)進(jìn)行合謀攻擊，則要求此分片中至少含有(2×L)/3+1 個拜占庭節(jié)點且進(jìn)行合謀，但這是比較困難的。假設(shè)當(dāng)該分片中的拜占庭節(jié)點數(shù)目大于(2×L)/3，則串通在一起進(jìn)行合謀。X表示分配到該分片中的節(jié)點總數(shù)，L表示分片內(nèi)節(jié)點數(shù)。X符合Binomial(L,X,f)的二項分布。如公式（5）所示：

根據(jù)公式（5）運用python模擬計算出在不同的拜占庭比例f和單個分片內(nèi)不同的節(jié)點數(shù)目L下，該分片中的拜占庭節(jié)點發(fā)生合謀的概率，見表3。

表3 單個分片中拜占庭節(jié)點間合謀的概率

根據(jù)表3 發(fā)現(xiàn)，即使當(dāng)f=0.333，若保證單個分片中的節(jié)點數(shù)目超過60 個，該分片中的拜占庭節(jié)點達(dá)成合謀的概率β也會低于4×10-8。

3.1.2 拜占庭節(jié)點比例和分片內(nèi)節(jié)點數(shù)對輪數(shù)的影響

在拜占庭節(jié)點比例低的情況下，共識可以在較少的輪數(shù)t(1 ≤t＜T)內(nèi)結(jié)束。在4.1節(jié)實驗中會得出在不同拜占庭比例下達(dá)成一輪共識的最少次數(shù)、最多次數(shù)和平均次數(shù)。最大共識次數(shù)T的取值范圍需要根據(jù)拜占庭節(jié)點不合作的概率和合謀的概率確定。T的下限是當(dāng)拜占庭節(jié)點合謀的概率小于10-7時的取值，T的上限是拜占庭節(jié)點不合作的概率低于10-7時的取值。保證最終共識超時的概率低于10-7時，計算出在不同的拜占庭比例f和分片中不同的節(jié)點數(shù)目L下，輪數(shù)T的取值范圍，如表4 所示。表5 分析了在L=60，不同輪數(shù)下，不同拜占庭節(jié)點比例與共識超時概率的關(guān)系。

表4 輪數(shù)T 在不同f 和L 下的取值范圍

表5 共識超時概率

通過表4 發(fā)現(xiàn)，隨著分片內(nèi)節(jié)點數(shù)的增多，對輪數(shù)影響不大。表5表明f=0.3 時，需要更多的輪數(shù)來保證可用性。

3.2 節(jié)點隨機(jī)分配算法

當(dāng)出現(xiàn)共識過程超時的情況時，需要對分片中的節(jié)點進(jìn)行新一輪的分配，節(jié)點隨機(jī)分配算法需要盡可能滿足具有比較高的隨機(jī)性和不可預(yù)測的特點?；诖耍x用VRF（Verifiable Random Function）作為節(jié)點隨機(jī)分配算法的隨機(jī)函數(shù)。VRF 隨機(jī)函數(shù)具有很好的隨機(jī)性和不可預(yù)測的特性。

在區(qū)塊鏈中，每個節(jié)點都具有節(jié)點地址和一對公私鑰。在需要進(jìn)行重新分配節(jié)點時，節(jié)點i將輸入m通過數(shù)字簽名和哈希函數(shù)映射為固定長度的輸出H[SIGi(m)]，即m→H[SIGi(m)]，其中m可以是節(jié)點的IP 地址或者是節(jié)點公鑰。對于任何輸入m，不同的調(diào)用節(jié)點i生成的數(shù)字簽名SIGi(m)是確定且唯一的；而對于不同輸入，哈希函數(shù)H的輸出具有隨機(jī)性，符合隨機(jī)性的特點。

為保證不可預(yù)測性，需要為VRF 隨機(jī)函數(shù)提供一個隨機(jī)的且不斷變化的種子。在本文的VRF 函數(shù)中，引入一個隨機(jī)的、不斷更新的種子參數(shù)G(h)，G(h)=H(Bh-1,Sk)，其中h為第h個區(qū)塊，Bh-1為上一區(qū)塊的哈希值。要求每個參與節(jié)點都需要和網(wǎng)絡(luò)中的兩個鄰居節(jié)點互換一個數(shù)字，Sk為每個參與的節(jié)點從鄰居節(jié)點獲得的數(shù)字集合?？梢钥闯?，G(h)在每一輪都會發(fā)生變化，且與交易本身無關(guān)。當(dāng)G(h-1)是隨機(jī)的，則G(h)也是隨機(jī)的。因此惡意節(jié)點無法通過改變交易集去影響下一個種子的生成。符合所要求的不可預(yù)測性。

4 實驗驗證與結(jié)果分析

為驗證本文方法確實能夠降低單個分片失效的概率，且多輪對交易的延遲確認(rèn)不會使得總體TPS 降低。實驗以ELASTICO為基礎(chǔ)進(jìn)行，增加了多輪方案和節(jié)點的隨機(jī)分配方法，選用Linux 作為實驗平臺，以Go 語言作為開發(fā)語言，以Docker和Goland作為開發(fā)工具，在每臺服務(wù)器的不同端口模擬不同的節(jié)點，實驗數(shù)據(jù)用MATLAB進(jìn)行繪制。

4.1 實驗設(shè)置

4.1.1 實驗環(huán)境設(shè)定

本文所設(shè)計的多輪方案，在使用之前需要設(shè)定下列條件：

（1）節(jié)點可以動態(tài)加入和退出，假設(shè)在分片期間總節(jié)點數(shù)目保持均勻恒定。

（2）區(qū)塊鏈中節(jié)點的位置和網(wǎng)絡(luò)情況會影響達(dá)成共識的效率，實驗在局域網(wǎng)內(nèi)進(jìn)行，P2P 網(wǎng)絡(luò)中各個節(jié)點之間通信良好，延遲在可控范圍內(nèi)。

（3）在每一輪共識中，節(jié)點是否誠實是可變的，即非拜占庭節(jié)點有可能在下一輪中變?yōu)榘菡纪ス?jié)點。

4.1.2 實驗參數(shù)設(shè)置與實驗流程

本文設(shè)計兩個對比實驗，隨著拜占庭比例的變化，觀察對比首個區(qū)塊鏈分片方案ELASTICO、采用節(jié)點隨機(jī)分配算法并取得較好效果的Omniledger方案、多輪方案的單個分片的失效概率和平均TPS 的表現(xiàn)情況。在實驗時，為了更能體現(xiàn)單一變量對結(jié)果的影響，需要對一些實驗參數(shù)進(jìn)行設(shè)定，如下：

（1）總節(jié)點數(shù)目n=600；

（2）每個分片中的節(jié)點數(shù)L=60；

（3）拜占庭比例的取值為f=[0.1，0.15，0.2，0.25，0.28，0.3]；

（4）輪數(shù)T的值取為在f=0.3,L=60,ε＜10-7條件下的最多輪數(shù)。如圖5所示。

圖5 共識次數(shù)與拜占庭節(jié)點比例的關(guān)系

在圖5中，分別統(tǒng)計了在多輪方案中上述條件下輪數(shù)的最多、最少和平均情況。當(dāng)0 ≤f＜0.15 時，最多輪數(shù)、最少輪數(shù)、平均輪數(shù)均可在一輪內(nèi)結(jié)束；當(dāng)0.15 ≤f＜0.25 時，最多輪數(shù)的值在增大，但平均輪數(shù)和最少輪數(shù)仍可在一輪內(nèi)結(jié)束。當(dāng)0.25 ≤f≤0.3 時，最多輪數(shù)出現(xiàn)指數(shù)增長的趨勢，平均輪數(shù)穩(wěn)定在兩輪，最少輪數(shù)仍可在一輪內(nèi)結(jié)束。

實驗樣本：實驗以局域網(wǎng)內(nèi)10 臺服務(wù)器的不同端口號模擬600個節(jié)點；在3.1.1小節(jié)的計算中，保證L＞60時合謀的概率即女巫攻擊成功的概率β＜4×10-8，故設(shè)定每個分片中的節(jié)點數(shù)為60。

實驗中采用對收到消息不進(jìn)行轉(zhuǎn)發(fā)，來模擬拜占庭節(jié)點的行為：即拜占庭節(jié)點雖然收到了消息，但是不向主節(jié)點以及其他共識節(jié)點進(jìn)行反饋。基本實驗流程如圖6所示。

圖6 多輪方案處理一筆交易流程

4.2 實驗結(jié)果與分析

單個分片失效的概率受分片規(guī)模和區(qū)塊鏈中拜占庭節(jié)點比例的影響。實驗1 模擬以n=600,L=60,T=7 為條件，隨著f的不斷變化，觀察ELASTICO 方案、Omniledger 方案、多輪方案與單個分片驗證有效性的關(guān)系。實驗結(jié)果分別如圖7所示。

圖7 不同拜占庭比例下兩種方案中單個分片失效概率

在實驗1中，當(dāng)f＜0.15 時，三種方案在單個分片失效的概率上都很低；當(dāng)0.15 ≤f＜0.25 時，ELASTICO 方案出現(xiàn)了失效概率增大的情況，Omniledger 方案和多輪方案表現(xiàn)仍然良好；當(dāng)0.25 ≤f≤0.3 時，ELASTICO方案的單分片失效的概率值出現(xiàn)了指數(shù)型增長，Omniledger方案的單分片失效概率值出現(xiàn)了小幅增長，這是由于在Omniledger 中節(jié)點隨機(jī)分配算法盡管在一定程度上可降低分片失效的概率，但是無法根本解決較高拜占庭比例下拜占庭節(jié)點聚集的問題；多輪中單個分片失效的概率值盡管也出現(xiàn)了增長，但在f=0.3 情況下值依然較小，這是因為在某個分片中連續(xù)多輪拜占庭節(jié)點發(fā)生累次聚集的概率極小，因此更能保證單個分片的驗證有效性。

本文的目的是保證分片驗證有效性的同時，顯著提高分片規(guī)模，確保整體區(qū)塊鏈TPS 提升，故實驗2 模擬以n=600,L=60,T=7 為條件，隨著f的不斷變化，調(diào)整拜占庭節(jié)點數(shù)目，觀察ELASTICO 方案、Omniledger方案和多輪方案TPS的表現(xiàn)情況。結(jié)果如圖8所示。

圖8 不同拜占庭節(jié)點比例下兩種方案TPS表現(xiàn)情況

在實驗2中，隨著拜占庭節(jié)點比例的不斷增大，三種方案的TPS值均在降低。當(dāng)0.1 ≤f≤0.15 時，ELASTICO方案和Omniledger方案的平均TPS比多輪方案稍高；當(dāng)0.15 ＜f≤0.2 時，三種方案TPS 值差距很??；當(dāng)0.2 ＜f≤0.3，ELASTICO 的TPS 急劇下降，Omniledger 方案的TPS 也在迅速下降，但整體TPS 較ELASTICO 稍優(yōu)，多輪方案盡管也出現(xiàn)了下降，但下降幅度稍緩，且整體TPS均優(yōu)于前兩種方案。

在多輪PBFT 共識驗證算法中，在吞吐量方面，T輪共識驗證雖然使得單個分片的交易確認(rèn)得到延遲，但保證了單個分片具有更高的驗證有效性；同時，因分片的個數(shù)已增至M(M?k)，平均共識驗證輪數(shù)為t，總體區(qū)塊鏈TPS提高M(jìn)/t倍。在保證單個分片中的節(jié)點數(shù)目不低于60 時，可使得單個分片中的拜占庭節(jié)點達(dá)成合謀攻擊的概率低至4×10-8。兩個實驗綜合表明：減少分片內(nèi)節(jié)點數(shù)、擴(kuò)大分片規(guī)模、增加輪數(shù)驗證，比分片規(guī)模較小、分片內(nèi)節(jié)點數(shù)較多的單輪驗證方案，總體驗證有效性更好、區(qū)塊鏈TPS更高。

5 總結(jié)

本文針對分片規(guī)模與分片內(nèi)驗證有效性的矛盾：“在分片內(nèi)采用PBFT共識算法時，因擴(kuò)大分片規(guī)模，使分片內(nèi)驗證有效性降低”提出多輪PBFT共識驗證方案，找到輪數(shù)的一個合理取值，并通過實驗數(shù)據(jù)進(jìn)行對比分析，確認(rèn)了多輪方案能夠在保持分片驗證有效性的同時，提高區(qū)塊鏈總體TPS。

分片技術(shù)作為解決區(qū)塊鏈擴(kuò)容問題的關(guān)鍵技術(shù)，受到越來越多項目和學(xué)者的關(guān)注，因此本文對于區(qū)塊鏈分片的多輪驗證研究很有后續(xù)參考價值。進(jìn)一步，分片內(nèi)的多輪共識驗證方法，還可以改進(jìn)，以抵抗分片內(nèi)的合謀攻擊。