一種改進的實用拜占庭容錯算法*

谷志峰 張 虎

（河南科技大學軟件學院 洛陽 471003）

1 引言

近年來，數字貨幣愈發流行，對人們的生活產生了很大的影響，而區塊鏈技術是數字貨幣產生的基礎，區塊鏈的本質是去中心化的分布式賬本數據庫，是確保數字貨幣安全可靠的關鍵技術，它需要綜合共識算法、網絡通信、密碼學原理、智能合約等多種技術來進行實現，具有去中心化、防篡改、透明和可追溯性等特點［1~2］。區塊鏈技術被認為是一種具有顛覆傳統行業潛力的新興技術，在金融、物聯網、醫療等領域具有廣闊的應用前景［3~5］。

區塊鏈技術的關鍵是共識算法，共識算法用于解決去中心化分布式互聯網絡中如何判斷區塊數據的正確性和所有權的問題，從而使所有節點達成共識。根據不同的應用場景，共識算法的側重點會有所差異。公共鏈主要使用PoW［6］算法、PoS［7］算法、DPoS［8］算法及其變形算法，而聯盟鏈使用的共識算法主要有Paxos［9］算法、Raft［10］算法和PBFT［11］算法，這些共識算法主要是基于消息傳遞的，其中最典型的是實用拜占庭容錯（PBFT）算法，PBFT 解決了先前拜占庭容錯算法效率低下的問題。當系統中存在（n-1）/3 個錯誤節點時，它仍能保證系統的安全性和可行性，分布式共識也能得到正確的達成。

但現有的PBFT 算法仍有不足之處。在PBFT算法中，選擇主節點的方式是按照節點編號大小依次進行的，這種主節點的選擇方式隨意性較大，并且在選擇主節點后，并未驗證其真偽性，這就使得被選中的主節點極有可能是惡意節點，因此，存在一定的安全隱患。雖然主節點的惡意性會在后續共識過程中被從屬節點識破，并被視圖切換協議推翻，但還是會造成一定程度的損失。另外頻繁的視圖切換也會增加系統開銷并降低系統效率［12］。

針對現有的PBFT 算法主節點選舉方式隨意、不能保證主節點可信性等問題，本文提出一種改進的PBFT 共識算法模型——RPBFT 算法，改進后的算法分兩個階段，第一階段利用Raft算法機制并結合積分策略選取勝利節點集合，第二階段使用PBFT 算法進行主節點的選取，本文RPBFT 算法有效緩解了傳統PBFT算法中因拜占庭節點存在而造成的視圖連續切換問題，降低了通信開銷，提高了共識效率。

2 算法設計

2.1 勝利節點集合選取

針對傳統PBFT算法中主節點選取方法的不足之處，本文在RPBFT 算法中進行了改進，改變了PBFT 算法中主節點輪流坐莊的隨意選取方式，讓主節點從可信程度更高的勝利節點集合中進行選取，從而提高了主節點選取的中靶率，因此本文RPBFT算法的關鍵是勝利節點集合的選取，其選取方法將利用Raft算法并結合積分策略進行［13］，具體如下。

在Raft算法中的每個節點都擁有三個屬性：節點狀態（status）、超時時間（timeout）、當前任期（term）。

1）節點狀態（status）：status 有三個狀態值，即領導者（leader）、跟隨者（follower）、候選者（candidate），其中領導者負責接受客戶的請求，并與跟隨者同步日志。當日志與大多數節點同步時，領導者通知跟隨者提交日志。跟隨者負責將領導者同步的日志進行接收和保存，并提交領導者通知的可以提交的日志，候選者在整個選舉過程中充當的是臨時角色。

節點的這三種狀態的轉化過程如上圖1 所示，即跟隨者僅負責響應來自其他節點的請求，若直到超時，跟隨者仍沒有收到領導者的消息，它將成為候選者并開始領導者的選舉。獲得多數節點選票的候選者將成為新的領導者。在宕機之前，領導者將始終保持領導者的狀態。

圖1 Raft算法節點狀態轉換

2）超時時間（timeout）：超時時間通常指的是心跳超時，心跳是領導者向跟隨者發送一次心跳所需要的時間。一旦這段時間結束，跟隨者會覺得這位領導者已經宕機了，這將開啟一個新的選舉周期。

3）當前任期（term）：Raft 算法將時間分為幾個任期（term），每個任期（term）都是從領導者選舉開始的。領導者被成功選舉后，在整個任期內，領導者將管理整個集群。如果領導者選舉失敗，任期也會隨之結束。

本文RPBFT 算法將在Raft 算法中的每個節點原有屬性的基礎上再添加一個積分（score）屬性，當節點成功執行一次共識，將獲取一定數量積分值，反之將會減去一定數量積分值，積分策略如下：首先每個節點的原始積分為0，當節點成功執行一次共識過程，積分在10 及其以上的節點，其積分累加0.2，積分在5~10之間的節點，其積分累加0.5，積分在0~5 之間的節點，其積分累加1，具體如式（1）所示：

若節點在共識過程中出現錯誤，則積分在10及其以上的節點，其積分減1，積分在5~10 之間的節點，其積分減3，積分在5 以下的節點，積分直接降為0，具體如式（2）所示：

利用Raft 算法，每個節點都會擁有一個積分值，根據節點的積分值從大到小的順序對節點進行排序，形成初始節點集合｛n1，n2，…，ni｝，其中i表示節點的編號，編號的最大值為系統節點的總數N，根據實用拜占庭算法共識原理，節點中的拜占庭節點的最大容忍數為（N-1）/3，所以系統節點中合法節點的最小數目應為（2N+1）/3，因此，可以從初始節點集合中按順序選出（2N+1）/3 個節點作為勝利節點集合｛c1，c2，…，cj｝，其中j表示勝利節點的編號，j的最大值為（2N+1）/3，這樣本文算法的第二階段中主節點的選取可以從可信度更高的勝利節點集合中進行選擇，從而優化了傳統PBFT 算法中主節點選取的盲目和隨意性問題。

2.2 共識過程

勝利節點集合確定之后，本文RPBFT 算法將借助PBFT算法的一致性協議算法思想使系統中節點達成共識，具體過程如圖2所示。

圖2 PBFT算法共識過程

圖中節點0 表示主節點，節點1 和節點2 表示普通節點，節點3表示拜占庭節點，節點0的傳統選舉方式是p=v mod n，其中v 表示視圖編號，n 表示節點數量，本文RPBFT算法中節點0首先將從算法第一階段中選取的勝利節點集合中選取，然后再參與一致性協議算法，具體流程如下：

1）請求階段：客戶端c 向節點0 發送內容為的請求消息。其中ts 是時間戳，ms 是需要共識的內容。該階段主要用于將需要共識的消息傳遞給主節點。

2）預準備階段：主節點收到請求后，將分配一個序號給需要共識的內容ms，然后向所有普通節點廣播預準備消息<，ms>，其中vi是視圖號，sn 是消息ms 的序號，bf是請求消息ms的簡要，普通節點收到預準備消息后，要對消息序號sn 和簡要bf 進行檢查。在該階段主要完成兩個工作：一是為共識內容分配序號，二是主節點將消息傳輸給其他節點。

3）準備階段：編號為i的節點首先會對收到的預準備消息的消息簽名、消息序號sn 和摘要bf 進行驗證，如果驗證通過，則將向所有普通節點廣播內容為的準備消息，當2f+1 個不同節點接收到與預準備消息一致的準備消息時，準備階段完成。該階段的任務是：驗證在預準備階段和準備階段接收的視圖編號、分配給共識內容ms的序號和消息內容。

4）確認階段：節點在準備階段完成后，進入確認階段。節點i將向所有節點發送一條確認消息，其中D（ms）是消息ms 的驗證簽名。接收到確認消息后，節點將對消息簽名和視圖號的一致性進行檢查。當檢查通過并接收到2f+1個與預準備消息一致的確認消息時，確認階段完成。

5）響應階段：該階段用于向客戶端發送共識成功消息。其中rs 是請求的最終執行結果［14］。

3 虛擬仿真測試

3.1 實驗設置

本文在Win7 系統下，利用實驗室局域網內6臺計算機和VMware虛擬機平臺（Linux CenterOS系統），簡易模擬30 個區塊鏈節點，虛擬節點IP 地址如表1所示。

表1 實驗節點

實驗環境配置如表2所示。

表2 實驗設備配置和開發環境

本文利用Java 語言編寫了PBFT 算法程序，然后利用Raft算法思想并結合積分策略對PBFT算法進行優化，得到本文算法RPBFT 算法，本文利用開源測試工具OpenSTA 軟件對這兩種算法的數據吞吐量和共識時延進行測試，并對測試結果進行分析，分析表明RPBFT 算法在數據吞吐量以及共識時延上都有所改進。

3.2 數據吞吐量測試

吞吐量是指單位時間內交易完成的數量。它是衡量共識算法性能的重要指標。吞吐量的大小顯示了系統負載承受、事務處理或交易請求的能力。通常用TPS表示，TPS公式為

其中，?t為出塊所用的時間，T?t為出塊時間內完成的交易數量［12］。

由于吞吐量的大小與節點的數量有關［15］，因此本文測試將在共識節點數量分別為5、10、15、20、25、30 個的情況下，對各算法的吞吐量進行測試，并將測試數據導入Origin 分析軟件進行分析，繪制出兩種算法的吞吐量對比圖，如圖3所示。

圖3 數據吞吐量對比圖

從圖3 中可以看出，隨著節點數量的增加，兩種算法的吞吐量都有所下降，但RPBFT 算法的吞吐量仍高于原始PBFT算法。

3.3 共識時延測試

共識時延表示交易提交和寫入之間的時間差，即完成一次共識所需的時間。它是衡量共識算法運行效率的重要指標。較低的共識延遲使交易能夠快速確認，使得區塊鏈更加安全和實用［12］。用公式可以表示為

其中Tdelay為一次交易所需要的時間，Tc為確認交易執行成功的時間，Tp為交易產生的時間。兩種算法的共識時延對比如圖4所示。

圖4 共識時延對比圖

從圖4 中可以看出，隨著節點數量的增加，兩種算法的共識時延都有所增加，但本文算法RPBFT具有更低的共識時延。

4 結語

傳統的PBFT 共識算法中主節點選取比較隨意，節點的可靠性無法得到保證，本文針對PBFT算法中主節點選舉隨意的問題提出了一種改進策略，該策略以PBFT算法為基礎，優化了PBFT算法中主節點的選舉方法，將PBFT 算法中主節點輪流坐莊的選舉方法改為從本文算法選出的勝利節點中進行選取，從而縮小了主節點的選取范圍，經實驗證明，改進后的算法數據吞吐量較傳統PBFT 算法有很大的提高，而共識時延較傳統PBFT 算法有所降低。