基于PBFT 算法的分片技術的研究?

王旭東 符精晶 王 赟

（1.江蘇大學計算機科學與通信工程學院 鎮江 212013）（2.沙洲職業工學院電子信息工程系 張家港 215600）

1 引言

比特幣［1］作為有史以來最成功的加密貨幣［2］，是一種突破和顛覆性的創新，其底層的區塊鏈技術在分布式共識領域備受技術人員和研究者的關注。區塊鏈（blockchain）是一種由對等網絡以分散的方式保存且無法篡改［3］的分布式賬本，其最初的目的是為了實現像比特幣這樣的數字資產而設計的，由于區塊鏈技術擁有的巨大的潛力為現有業務能力的突破提供了新的可能性，故區塊鏈技術在能源貿易，農業［4］，物聯網（IoT）［5］等領域被廣泛應用。

在區塊鏈系統中當眾多節點試圖將一個區塊添加到主鏈中時，就需要一種達成一致性協議算法來確定哪個區塊才能被添加到主鏈中，這個算法被稱為共識算法，共識算法具有非常重要的意義，它決定了要添加的數據的正確性、試圖添加該區塊的節點的可信度以及確保了區塊鏈系統中分散的節點之間的一致性，高效的共識算法可實現更高的精度、更高的安全性、更好的性能和擴展性等，常見的共識算法有工作量證明（PoW）［1］，權益證明（PoS）［6］和實用拜占庭容錯（PBFT）［7］等。

目前區塊鏈的發展還處于最初階段，面臨著很多問題［8］，其中擴展性［9］問題亟待解決，分片技術是迄今為止被認為最能夠解決區塊鏈系統擴展性的最實用的解決方案，它通過將網絡劃分為不同的分片能夠使系統的處理、存儲和計算可以并行進行，從而減少通信、數據存儲和計算等資源開銷，同時保持去中心化和安全性，國內外許多專家針對分片提出了諸多解決方案，下面將進行分別的介紹。

Elastico［10］是一種無許可的分片協議，在Elastico 中節點首先需要解決一個用于確定共識委員會PoW 謎題，確定共識委員會后，該委員會負責對分片的共識結果作出最終決定，在Elastico 中每達成一輪共識，委員會就會重組一次，這種頻繁的操作會降低交易執行的效率；OmniLedger［11］是在Elastico的基礎上提出的一種分片協議，OmniLedger數據結構塊采用了DAG，并使用了結合RndHound 和Algorand 的公共隨機協議來進行分片，但Omniledger的缺點是共識過程中牽扯到跨分片交易時通信開銷過大；RapidChain［12］是一種基于PBF 算法分片的公共區塊鏈協議，RapidChain 通過減少每筆交易的數據交換量，并使用快速的跨分片驗證技術，使交易不需要大范圍傳播，但是RapidChain 是采用PBF算法達成共識，依然沒能解決通信開銷大的問題；Monoxide［13］是一個橫向擴展的區塊鏈，它提出了異步共識區，線性擴展了區塊鏈系統，但依然沒能解決通信開銷的問題；Zilliqa［14］是以Pow 為共識算法的區塊鏈分片技術，Zilliqa 通過處理不同分片中的交易來改進吞吐量，但是Zilliqa中的節點需要存儲整個區塊鏈網絡中的數據，阻礙了系統的擴展；Harmony 是一個具有多個分片鏈結構的方案，它可以同時處理交易和存儲數據，但該分片協議可擴展性較差，還有很大的研究空間。

2 準備知識

2.1 實用拜占庭容錯算法

PBFT 是一種經過改進的BFT 算法，經過改進，PBFT在異步環境下比BFT的響應時間降低了一個數量級，并能夠容忍異步系統中故障節點引起的一致性問題。與PoW 相比，PBFT 的工作原理中沒有計算任務，因此，它將共識的復雜性降低到多項式水平，并且顯著降低了能耗。

圖1 PBFT算法的共識過程

在PBFT的每個視圖中，當主節點收到請求時，它會根據一個三階段的協議向前移動：預準備、準備和提交。在預準備階段，當主節點收到請求序列時，主節點按順序將請求序列發送給其他副本節點，副本節點在收到請求序列后，檢查其有效性，并將其添加到其本地日志中，并向其副本節點發送一條消息，以顯示它已經收到了提議并識別了它。然后，副本節點進入準備階段，副本節點成功收集2f+1反饋消息（f表示故障節點數量）時，將啟動提交階段。最后，主節點收集到2f+1 條提交消息后，就可以確保提案已經由足夠的副本節點完成記錄，可以執行反饋操作，并向客戶端發送回復。

為了確保主節點不出現故障，PBFT 設計了一種稱為視圖更換的協議，如果備份節點發現主節點有惡意行為或停止工作，那么它會獨立地宣布要將主節點更改為下一個節點的提議，如果2f+1副本發現主節點的異常，將確認更改視圖，由下一個主節點接管。

2.2 聚合簽名

聚合簽名［15］是一種用于消息身份驗證和數據完整性驗證的安全技術，通過將一組數字簽名組合成一個單一的數字簽名，可用作大量數據的完整性證明。聚合簽名通過把多個簽名進行聚合，節省了通信和存儲空間，在聚合簽名驗證過程中只有當整個簽名集都有效時，聚合簽名的驗證才會輸出肯定的結果，如果在集合中有一個錯誤的簽名，則表示所涉及數據的完整性無效。下面對聚合簽名做簡單驗證，對于橢圓曲線上的兩個點X，Y 和x，y 以及原點G：

聚合簽名有諸多優點，對于驗證者來講，聚合簽名可以提升交易的驗證速度并節省了通信和存儲空間，且無法通過聚合簽名推導出參與方的公鑰和簽名的信息，可用于提高鏈上數據的隱私性。

3 分片失效概率分析

本章通過對節點數對分片失效概率的分析、分片節點數對分片均不失效的分析來驗證導致分片有效性降低的原因。

3.1 節點數對分片失效概率的分析

根據式（4），設置初始參數值f=[0.1,0.2,0.3]，通過改變M 的值模擬研究M 對P的影響情況，如表1所示。

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

根據表1，在f 不變時，隨著分片中節點數目的增多，分片失效的概率顯著降低，在M不變時，隨著f 增大分片失效概率越高，對于整個區塊鏈系統而言，單個分片失效概率大于0.03已經是一個較高的數值了。

3.2 分片節點數對分片均不失效的分析

假設拜占庭節點比例為f(0 ≤f≤1/3) ，每個分片中節點數為M，分片個數為k，若想保證所有分片不失效，需要保證每個分片內的拜占庭節點的比例f<1/3，為了追求結果的準確性，采用窮舉遍歷的方法，如式（5）所示，式（6）和式（7）是式（5）的兩個限定條件。

在探究M 與Pr 的關系時，為了研究高拜占庭節點比例下分片的失效概率，選取f=0.3，分片個數k=4，固定這兩個值可準確地研究有效分片規模與高拜占庭比例下，分片內節點數M對所有分片都不失效的概率值Pr 影響，圖2 是基于式（5），M 對P 的影響圖。

圖2 M對P的影響

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

4 分片內共識方案實現

為了解決以上問題，本文通過動態權值分配方法優化一致性hash 算法，解決節點分配的不均衡性，在此基礎上實現基于PBFT 共識算法利用聚合簽名技術改進動態實用拜占庭算法（DPBFT）。

4.1 節點隨機性分配

在對節點進行隨機劃分時，采用一致性哈希算法［16］進行劃分，但是在系統中每一個節點都存在差異，故本文通過動態權值分配的方法對一致性hash算法進行優化以支持動態權重，首先對權值進行計算，步驟如下：

1）節點負載

假設有n 個節點，分片數目為m，對于每個節點i，CPU 利用率是內核模式和空閑模式下CPU（t）時間之和的比值，采用以下公式計算：

節 點 閑 置 內 存 為METfree（t），節 點 總 內 存 為METtotal（t），主機內存利用率（MEM（t））為

網絡利用率（NET（t））是節點在時間間隔t 內接收和發送的字節之和與網絡帶寬NETband（t）的比值，當一個節點加入集群時，可以使用以下公式計算網絡利用率：

通過上面的計算，我們使用以下公式計算系統中節點i的負載Load：

其中λ1=0.3，λ2=0.3，λ3=0.4。

2）節點誠信值

共識完成率反映了節點在區塊鏈中總體的完成程度，其可通過共識完成率γ表示，如式（12）計算：

式（12）中，s 為節點成功完成的共識次數，a 為調節常數，n為節點參與共識次數。

交易影響率用于表示交易對節點的影響程度，交易影響率可用交易影響函數f（x）計算，如式（13）：

節點交互程度是指節點在區塊鏈系統中的參與共識的程度，節點交互程度用交互影響函數表示，交互影響函數可采用式（14）計算：

其中，η?( ]0.5,1 用來控制活躍度比重，a為次數調節因子，n為共識次數。

則節點信用可采用式（15）計算：

其中Cinit為節點信任值初值，E 為行為評價影響因子。

3）節點完成速率可用式（16）計算：

其中，V0表示原始數值，Vmin和Vmax分別為節點完成速率的最大和最小值。

那么節點s的當前權重Ws為

經過多次實驗驗證，當ω1=0.3，ω2=0.3，ω3=0.4時最為合適。

經過上述對分片權重的計算，我們使用一致性哈希算法來獲取系統中所有節點的動態權值Ws，并將節點的動態權重值作為哈希值，映射到哈希空間中，然后利用一致性哈希算法來確保節點與哈希空間動態權值之間的對應關系，并用哈希表進行記錄，最后通過跳躍查找算法對節點的所有權重進行索引查找然后隨機分配，跳躍查找算法如下所示：

4.2 PBFT共識算法改進

選擇生成元定義為P∈G1，Q∈G2，定義雙線性映射為e：G1×G1→G2，散列函數為H0、H1、H2、HDV。

1）利用當下的視圖計算Pv=vP，得到系統參數Params=｛G1，G2，e，q，P，Q，Pv，H0，H1，H2，HDV｝。

2）用戶ui選擇隨機值xi∈Zq*計算Pi=xiP，Qi=H1（IDi||Pi），Di=vQi生成用戶的私鑰Si=（Di，xi）。

3）用戶ui執行以下過程：ri∈Zq，計算Ri=riP，hi=H0（IDi||mi||Pi||Ri），T=H2（Pv）。

4）若要驗證u對m的簽名σi=（Vi，Ri）的有效性，計算hi=H0（IDi||mi||Pi||Ri），Qi=H1（IDi||Pi），T=H2（Pv），并驗證下列等式是否成立：

為了說明上述論述是正確的，下面給出了單個簽名驗證過程和聚合簽名驗證過程的正確性的證明過程。

u 對m 的簽名σi=（Vi，Rn）證明單個簽名驗證過程是正確的過程如下：

對上述問題進行正確性驗證之后，改進的共識算法DPBFT的共識過程如下。

1）令H：{0,1}*→G1是一個哈希函數，T/B 是一個交易。 發送者使用私鑰sk 計算哈希值h=H((T/B)||v)，計算的簽名為σ=hsk，節點附上發送者簽名的數據向全網廣播；

2）聚合簽名者通過給定的公鑰pk，交易T/B，簽名σ=hsk，計算哈希函數值h=H((T/B)||v)，驗證為真，則接受，反之放棄。聚合簽名者通過聚合簽名算法得到的聚合集表示為U={u1,u2,…,un}，收集到的簽名為σ，消息集為T/B={(T/B)1,(T/B)2,…,(T/B)n}，則聚合簽名為

3）主節點在經過時間t 后，發送σi>給副本節點；

4）副本節點i在收到消息后，檢查其有效性，并添加到本地日志中，并發送σi>給其他副本節點，以顯示已經收到了提議；

5 實驗測試結果與分析

本文將分別從系統容錯性、交易吞吐量，交易延遲三個方面對改進后的DPBFT 與Omniledger 兩個方案進行對比，實驗平臺為Hyperledger Fabric，實驗中通過對節點收到消息后延遲處理與發送模擬拜占庭節點的行為。

5.1 系統容錯性測試

在系統容錯性實驗中，主要統計Omniledger和DPBFT 兩種方案在不同的拜占庭節點數目下的出塊時間，在實驗室中我們將拜占庭節點個數逐次增加至超過節點總數的1/3。

由圖3 可以看出，隨著拜占庭節點數目的增多Omniledger 和DPBFT 兩種方案的出塊時間都在增加，但DPBFT 方案的增加幅度比較小，相比而言DPBFT方案更優。

圖3 分片內拜占庭節點數目對出塊時間影響

5.2 交易吞吐量測試

交易吞吐量測試過程中，只改變拜占庭節點比例，其他參數均保持保持不變，對比DPBFT 和Omniledger兩種方案的交易吞吐量，結果如圖4所示。

圖4 不同拜占庭節點比例對TPS的影響

根據圖4 所示，隨著拜占庭節點比例的增大，兩種方案的TPS均在降低，但是DPBFT方案下降幅度稍緩，DPBFT方案較優。

5.3 交易延遲測試

在系統對拜占庭節點比例容忍范圍內，通過改變分片個數，對DPBFT 和Omnildger 兩種方案的交易延遲進行測試，結果如圖5所示。

圖5 分片數量對交易延遲的影響

根據圖5 所示，隨著區塊鏈系統中分片數量不斷增加，DPBFT方案和Omniledger方案交易延遲都在增加，但DPBFT 方案具有更低的交易延遲，DPBFT方案更優。

經過上述實驗分析可知，DPBFT共識算法提高了系統容錯性和交易吞吐量并降低了交易延遲，保證區塊鏈系統分片后的系統效率，使該改進后的共識算法能夠應用于更多去中心化場景。

6 結語

擴展性是區塊鏈系統面臨的一大問題，受到越來越多的專家的關注，本文針對區塊鏈分片以及分片內達成一致性的的問題進行研究，提出了DPBFT共識算法，在保證分片數據的可信性前提下有效地提升了系統容錯性、交易吞吐量并降低了交易延遲。