提升分片規模和有效性的多輪PBFT驗證方案

王夫森，李志淮，田 娜

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

1 引言

區塊鏈技術作為比特幣[1]的底層協議，具有去中心化、難篡改、允許運行在非許可環境下的特點。區塊鏈本質是一個去中心化的賬本，有效解決了拜占庭將軍問題[2]，實現了在點對點網絡中互不信任的節點通過遵循預設的機制達成數據的最終一致性，從而降低了現實世界的信任成本。

但是，現階段的區塊鏈技術仍是不成熟的，面臨著擴容困境[3-4]。現有的解決方案主要歸納為Layer1 層擴容和Layer2層擴容方案，Layer1擴容方案主要包括分片技術[5]、DAG[6]結構、代理共識協議、增大區塊[7]等。Layer2擴容方案主要包括側鏈[8]、狀態通道[9-10]等。

區塊鏈分片的概念最早是在文獻[5]中提出，本質是一種將計算和存儲分散到對等網絡的分區方式，每個節點只維護與其分片相關的信息。分片方案通過切割網絡中的節點和交易，以實現每秒處理數千筆交易的區塊鏈網絡。

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

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

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

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

2 問題描述與分析

2.1 問題描述

分片方案力圖通過并行處理提高區塊鏈TPS，但也可能因為分片內驗證有效性明顯降低，達不到預期吞吐量，產生分片規模與分片內驗證有效性的矛盾。

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

圖1 分片可能導致拜占庭節點在片內聚集

圖1 描述了經過分片后存在一定概率使得片內拜占庭節點比例超過1/3。在圖1中，經過節點分配后1號分片和3號分片中拜占庭節點數超過1/3，導致分片內無法達成共識。

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

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

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

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

2.2.1 分片內節點數與分片驗證有效性的關系

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

表1 分片內節點數L 對單分片失效概率P 的影響

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

2.2.2 拜占庭節點比例與單個分片驗證有效性的關系

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

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

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

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

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

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

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

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

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

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

2.3.1 分片內節點數與所有分片都不失效的關系

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

圖2 L 對于Pr 的影響

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

2.3.2 拜占庭比例與所有分片都不失效的關系

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

圖3 f 對Pr 的影響

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

2.3.3 分片規模與所有分片都不失效的關系

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

圖4 k 對Pr 的影響

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

3 多輪共識方案設計

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

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

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

對于輪數T的上限，在3.1節中給出。對于節點隨機分配算法，在3.2節中描述。

3.1 多輪輪數的選擇

3.1.1 拜占庭節點合謀的概率

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

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

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

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

根據表3 發現，即使當f=0.333，若保證單個分片中的節點數目超過60 個，該分片中的拜占庭節點達成合謀的概率β也會低于4×10-8。

3.1.2 拜占庭節點比例和分片內節點數對輪數的影響

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

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

表5 共識超時概率

通過表4 發現，隨著分片內節點數的增多，對輪數影響不大。表5表明f=0.3 時，需要更多的輪數來保證可用性。

3.2 節點隨機分配算法

當出現共識過程超時的情況時，需要對分片中的節點進行新一輪的分配，節點隨機分配算法需要盡可能滿足具有比較高的隨機性和不可預測的特點。基于此，選用VRF（Verifiable Random Function）作為節點隨機分配算法的隨機函數。VRF 隨機函數具有很好的隨機性和不可預測的特性。

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

為保證不可預測性，需要為VRF 隨機函數提供一個隨機的且不斷變化的種子。在本文的VRF 函數中，引入一個隨機的、不斷更新的種子參數G(h)，G(h)=H(Bh-1,Sk)，其中h為第h個區塊，Bh-1為上一區塊的哈希值。要求每個參與節點都需要和網絡中的兩個鄰居節點互換一個數字，Sk為每個參與的節點從鄰居節點獲得的數字集合。可以看出，G(h)在每一輪都會發生變化，且與交易本身無關。當G(h-1)是隨機的，則G(h)也是隨機的。因此惡意節點無法通過改變交易集去影響下一個種子的生成。符合所要求的不可預測性。

4 實驗驗證與結果分析

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

4.1 實驗設置

4.1.1 實驗環境設定

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

（1）節點可以動態加入和退出，假設在分片期間總節點數目保持均勻恒定。

（2）區塊鏈中節點的位置和網絡情況會影響達成共識的效率，實驗在局域網內進行，P2P 網絡中各個節點之間通信良好，延遲在可控范圍內。

（3）在每一輪共識中，節點是否誠實是可變的，即非拜占庭節點有可能在下一輪中變為拜占庭節點。

4.1.2 實驗參數設置與實驗流程

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

（1）總節點數目n=600；

（2）每個分片中的節點數L=60；

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

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

圖5 共識次數與拜占庭節點比例的關系

在圖5中，分別統計了在多輪方案中上述條件下輪數的最多、最少和平均情況。當0 ≤f＜0.15 時，最多輪數、最少輪數、平均輪數均可在一輪內結束；當0.15 ≤f＜0.25 時，最多輪數的值在增大，但平均輪數和最少輪數仍可在一輪內結束。當0.25 ≤f≤0.3 時，最多輪數出現指數增長的趨勢，平均輪數穩定在兩輪，最少輪數仍可在一輪內結束。

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

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

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

4.2 實驗結果與分析

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

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

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

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

圖8 不同拜占庭節點比例下兩種方案TPS表現情況

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

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

5 總結

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

分片技術作為解決區塊鏈擴容問題的關鍵技術，受到越來越多項目和學者的關注，因此本文對于區塊鏈分片的多輪驗證研究很有后續參考價值。進一步，分片內的多輪共識驗證方法，還可以改進，以抵抗分片內的合謀攻擊。