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

谷志峰 張 虎

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

1 引言

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

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

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

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

2 算法設計

2.1 勝利節(jié)點集合選取

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

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

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

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

圖1 Raft算法節(jié)點狀態(tài)轉換

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

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

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

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

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

2.2 共識過程

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

圖2 PBFT算法共識過程

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

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

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

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

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

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

3 虛擬仿真測試

3.1 實驗設置

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

表1 實驗節(jié)點

實驗環(huán)境配置如表2所示。

表2 實驗設備配置和開發(fā)環(huán)境

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

3.2 數(shù)據(jù)吞吐量測試

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

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

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

圖3 數(shù)據(jù)吞吐量對比圖

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

3.3 共識時延測試

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

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

圖4 共識時延對比圖

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

4 結語

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