基于角色管理的實用拜占庭容錯共識算法*

李 騰，程 哲，賈東立，賈耀清

(河北工程大學信息與電氣工程學院,河北 邯鄲 056038)

1 引言

隨著計算機和網絡的發展，計算機系統提供的服務和功能越來越多地被人們使用。近年來，隨著比特幣[1]的巨大成功，出現了一種新的分布式系統應用“區塊鏈”并受到了高度重視。主流的分類方法將區塊鏈分為3類:公有鏈、聯盟鏈和私有鏈[2]。不同類型的區塊鏈對節點數量和工作要求都不一樣，但都需要保證節點的一致性。對共識算法的研究由此而生，不同類型的共識算法逐漸出現，比如適用于公有鏈的工作量證明POW(Proof-Of-Work)算法[3]和股權權益證明POS(Proof Of Stake)算法，適用于聯盟鏈的實用拜占庭容錯算法PBFT(Practical Byzantine Fault Tolerance)共識算法[4]，適用于私有鏈的Raft共識算法等。

拜占庭容錯源自于古羅馬拜占庭將軍問題[5]。如何在存在惡意節點的網絡系統中，保證系統的穩定運行以及信息的一致性、完整性和安全性，正是拜占庭將軍模型在去中心化網絡和分布式系統中所反映的問題，也是區塊鏈中共識算法所需要解決的問題。

為解決拜占庭容錯問題，20世紀80年代，Lamport等[6]提出了著名的拜占庭容錯BFT(Byzantine Fault Tolerance)共識算法。BFT共識算法中節點之間相互發送消息進行數據的傳遞和同步，另外還需要額外的時鐘同步機制支持，算法的復雜度也是隨著節點增加呈指數級增大。BFT 算法由于需要展示其理論上的可行性而缺乏實用性，但是其提供的思路在解決拜占庭問題上是一種創新，減少了POW算法大量的資源消耗。

1999年，基于BFT共識算法，Castro等[4]提出了實用性拜占庭容錯PBFT共識算法，由拜占庭容錯帶來的系統開銷被大幅度降低。PBFT共識算法是一類狀態機拜占庭系統，其要求共同維護一個狀態，所有節點采取的行動一致。因為各個節點達成共識是在同一時刻決定的，不用等待確認以保證當前區塊所在的鏈是最長鏈，所以采用PBFT共識算法的區塊鏈不會像POW算法那樣存在鏈分叉，保持了系統的活性[7]。

目前PBFT共識算法還存在很多不足。對于P2P[8]網絡來說，節點應該相互通信而不是客戶端請求直接發送到主節點。而且由于PBFT共識算法采用C/S架構[9]，節點在加入時系統不能及時回應，無法正確回應處理請求。主節點的選舉是按照編號輪流選取，選舉方式比較隨意，對主節點的可靠性沒有進行驗證，因此很有可能選舉出惡意節點，盡管惡意節點可以在視圖變更時被推翻，但頻繁地更換主節點和視圖變更會導致大量資源的浪費，并降低系統效率。主節點選舉完成之后，因為網絡等原因會導致各個節點的狀態不一致[10]，需要完善的同步數據過程。共識過程通信開銷較大，需要進行優化和改進。

2 PBFT共識算法流程

隨著網絡技術的發展，對PBFT共識算法的改進研究明顯增多，例如，無主節點排序的HQ(Hybrid Quorum)算法[11]、基于投機的Zyzzyva 算法[12]和以主節點切換為代價進行優化的spining 算法[13]等。而在針對區塊鏈應用場景進行優化方面，主要有POS與PBFT 結合的Tendermint[14]和DPOS(Delegated Proof Of Stake)[15]與PBFT結合的dBFT(delegated Byzantine Fault Tolerance)[16]算法等。 通過以上分析發現，區塊鏈共識算法及其變種都是基于PBFT共識算法的，所以本文選取PBFT 共識算法作為研究對象。

在PBFT共識算法中，客戶端是請求的發送端，主節點負責接收請求，并且按照順序對請求排序，從節點主要負責檢查從主節點發來的請求，并通過超時機制檢測主節點是否出錯，發生出錯時觸發視圖更換協議。PBFT共識算法流程如圖1所示。其中，Node0為主節點，Node3為出錯節點。

Figure 1 Flow chart of PBFT consensus algorithm圖1 PBFT共識算法流程

PBFT共識算法流程分為5個階段，每個階段的工作方式和作用分別介紹如下：

(1)請求階段(Request)：客戶端c產生交易數據并向主節點發送處理交易的請求消息〈REQUEST,m,t,c〉，其中,t是時間戳，m是需要共識的內容。請求階段的主要作用是將需要共識的消息傳遞到主節點。

(2)預準備階段(Pre-prepare)：主節點收到請求后為需要共識的內容m分配序號，然后向所有從節點廣播預準備消息〈〈PRE-PREPARE,v,N,d〉,m〉，其中,v是視圖編號，N表示消息m的序號，d是請求消息m的摘要。視圖編號v、消息序號N和摘要d是節點收到預準備消息后要檢查的內容。預準備階段完成了共識內容的序號分配和從主節點傳遞到所有從節點的工作。

(3)準備階段(Prepare)：編號為i的從節點收到預準備消息后，首先對消息的簽名、消息序號N和摘要d進行驗證。若驗證通過，則將向所有從節點廣播準備消息〈PREPARE,v,N,d,i〉。當節點收到2f+1(f表示PBFT共識算法可容忍的錯誤節點數量)個從不同從節點發送的與預準備消息一致的準備消息后，準備階段完成。準備階段完成對預準備階段和準備階段收到的視圖編號、共識內容m分配的序號和消息內容的驗證任務。

(4)確認階段(Commit):從節點完成準備階段后進入確認階段。從節點i向所有節點廣播確認消息〈COMMIT,v,N,D(m),i〉,其中D(m)是對消息m的驗證簽名。從節點在收到確認消息后會檢查消息簽名和視圖編號是否一致，若檢查通過并接收到2f+1個與預準備消息一致的確認消息，則確認階段完成。這一階段的作用是確保所有節點對本地確認的請求的序號達成一致。

(5)回復階段(Replay):回復階段的作用是將共識成功信息發送給客戶端。回復消息格式為〈REPLAY,v,c,i,r〉，其中r是請求的執行結果。

對PBFT共識算法流程分析可知，算法存在著以下不足：

(1) 客戶端只向主節點發送請求，當請求過多時容易造成主節點過載，可靠性降低，系統運行消耗增加，而且這種方式也不適合區塊鏈的點對點網絡。

(2) 主節點選取比較隨意，無法保證節點的可靠性，如果連續選取惡意節點作為主節點，則會極大地增加系統消耗，降低系統的穩定性和可靠性；選擇主節點后沒有完備的數據同步過程，節點之間的數據無法更好地達成一致。

(3) 算法擴展性差，沒有完善的節點加入或退出機制。節點加入或退出時，系統需要重新啟動，開銷較大。如果系統中的節點更換頻率較大，將會大大降低系統的可用性。

(4) 共識過程網絡消耗較大，網絡中節點數較多時通信非常頻繁，容易造成網絡擁堵，影響請求正確執行。

3 RPBFT共識算法設計

3.1 算法主要思想

基于角色控制的拜占庭容錯RPBFT (Role management-based Practical Byzantine Fault Tolerant)共識算法將網絡中的節點分為3種類型的角色，分別是管理者(Manager)、候選者(Candidate)和普通節點(Normal)，通過選舉機制和獎勵機制對節點的角色類型進行轉換和管理，以達到提高效率、增加可靠性和動態性的目的。針對PBFT共識算法中存在的不足，本文主要在以下幾個方面進行了改進：

(1) 為更好地適應點對點網絡，改變客戶端單點提交請求到主節點的方案，而是向所有節點發送帶有時間戳和簽名信息的交易數據。

(2) 將網絡中的節點分為3種角色。普通節點服從管理者的安排，只負責完成交易。候選者不僅要服從管理者對交易內容進行分析，而且還要監督管理者的行為。管理者出現惡意行為時，將被降級為普通節點，候選者開始選舉管理者的過程。管理者的主要職責是負責接收客戶端的請求，同時對這些消息進行排序，分配編號，再向網絡中廣播請求消息。3種角色的節點在一定條件下可以相互轉換，為新節點加入或退出提供了保證，提高了系統的可擴展性。

(3) 增加選舉過程和獎勵機制。用2種機制對節點的角色分配進行管理。候選者是系統網絡重要組成部分。獎勵機制下，所有節點每完成一次交易，都對其信用積分累計加一。當信用積分滿足一定條件的時候，普通節點升級成為候選者，管理者是通過候選者之間的選舉產生的。2種機制確保管理者節點具有最高的信用積分和最大交易序列號，降低了隨意選取主節點帶來的風險，提高了系統安全性。

(4) 增加數據同步及驗證過程，在管理者選舉完成之后進行數據同步，并且副本節點在同步過程中對主節點和數據進行驗證，驗證沒有問題，說明管理者可靠，然后開始新的共識過程。

(5) 改進共識算法通信過程，去掉確認階段。在去掉確認階段的情況下，需要保證共識過程中發生視圖變更后系統節點狀態的一致性。本文使用交易序列號和區塊高度來判定區塊狀態，舍棄視圖這個概念，發生視圖變更時通過重新選舉來保證一致性。發生網絡擁堵或節點惡意行為導致需要視圖變更時，系統進入重新選舉的過程，以此來消除系統可能面臨的不一致性。

3.2 算法流程

系統初始化時，選取節點編號較小的2f+1個節點作為初始候選者。然后進行選舉過程選出管理者，管理者通過發送數據塊和序列號與所有節點進行數據同步達到狀態一致，即存儲數據、最大序列號和區塊高度等信息完全一致。采用密碼技術保證數據傳遞過程中的完整性和安全性，定義Si為消息簽名，Di為消息摘要。節點初始化完成之后系統開始認證(Authentication)和提交(Submit)2個階段的共識過程。

RPBFT共識算法流程如圖2所示，各階段具體過程描述如下:

Figure 2 Flow chart of RPBFT consensus algorithm圖2 RPBFT共識算法流程

客戶端c廣播請求到所有節點，共識節點收到請求后驗證交易簽名并將驗證成功的交易數據存儲在自己的內存中。

(1)認證階段(Authentication):管理者收到請求后為交易數據分配序號N，然后向所有節點廣播認證消息〈〈AUTHENTICATION,cp,N,Si,Di〉,data〉，其中,cp(credit points)是節點信用積分值，data是需要共識的交易數據。從節點i∈{0,1,…,|R|-1}(|R|為節點總數)在接收到認證消息時會對消息序號N、信用積分cp、簽名和摘要進行檢驗，如果同意認證消息，則進入提交階段，如果不同意，則對管理者產生質疑，廣播重新選舉消息。

(2)提交階段(Submit):進入提交階段后，所有從節點向除自己以外的節點廣播提交消息〈SUBMIT,N,Si,Di,i〉。節點收到提交消息后對消息序號N、信用積分cp、簽名和摘要進行檢驗，認證成功將認證消息和提交消息寫入消息日志。節點收到2f+1個來自不同從節點且與認證消息一致的提交消息時，提交階段完成。如果在一定的時間內沒有收集到足夠多的消息，則認定此交易過程失效，發起重新選舉過程。

當節點完成提交階段后向管理者發送已完成消息，管理者收到來自2f+1個不同節點的完成消息時，對客戶端進行回復。

3.3 獎勵機制

信用積分cp是衡量節點可信任程度的指標，節點成功完成交易任務數量越多，信用積分值越高，所有節點根據信用積分值cp的不同分為不同角色。初始狀態下所有節點cp值為0，選舉管理者之后每次完成管理者分配的交易任務即提交階段完成，cp值加1并且記錄在自己的日志中。由于網絡延遲或節點惡意行為導致節點無法完成任務，節點需要接受降級懲罰。管理者發生故障時，信用積分清除到初始狀態，并將角色類型變為普通節點，管理者自身發起重新選舉過程；候選者發生故障時，信用積分清除到初始狀態，并降級成為普通節點。

信用積分在選舉管理者和推選候選者中具有重要的作用。在選舉過程中，候選者通過發起投票選舉出信用積分最大的候選者，當選者升級成為管理者，然后進行數據同步和驗證。候選者是共識節點的主要部分，是保證系統可靠性和穩定性的重要力量。候選者的數量要占系統節點數量的大多數，假設算法可容錯節點數量為f，則候選者的數量至少需要2f，確保即使在有f個候選者出現錯誤時，候選者數量依然可以代表系統的決策。候選者數量的保證，也可以在選舉管理者時更加公平，避免惡意操縱候選者選舉出惡意管理者帶來的危險。在數據同步驗證過程中，管理者統計由不同節點發送來的信用積分值并選擇2f個信用積分較高的從節點分配為候選者。

為避免在短時間內通過大量交易刷信用積分的惡意行為，在管理者內部設立一個閾值K，當在一定時間內來自同一個節點的交易數量大于或等于K時，管理者認為該節點具有惡意行為，將該節點降級為普通節點并清除其信用積分。

3.4 選舉過程

管理者的選舉依據最大信用積分原則，選出候選者中信用積分(cp)最大即擁有最多完成交易記錄的節點作為管理者。系統在沒有管理者或管理者出錯的情況下發起選舉。

節點收到選舉消息后，判斷自己的角色，候選者首先將自己的cp值記錄下來，然后對照存儲的候選者列表將自己的cp值發送給所有候選者。候選者在收到所有候選者cp值后進行比較，如果cp值小于自己存儲的值，則什么也不做；如果cp值與自己所存儲的值相等，則比較節點編號，將節點編號較小的節點和cp值存入內存中；如果cp值大于存儲的值，則清除原來存儲，更換為較大的cp值。當cp值比較完成之后，將更新后的cp值及其節點編號廣播給所有候選者，候選者如果收到了f+1個來自不同候選者的內容一致的投票消息，則更新自己的存儲，給消息中的目標節點發送確認消息。候選者收到至少f+1個來自不同候選者發送的確認消息后升級成為管理者。

管理者在發生錯誤或由于網絡原因導致出現不一致性時，將被降級為普通節點，然后由候選者發起新一輪的投票，投票過程與上述相同。

管理者選擇完成之后，為使各節點保持狀態一致并進一步驗證管理者是否為惡意節點，需要管理者發起數據同步和驗證過程。具體過程如下：

管理者發送同步數據請求消息，消息格式為〈SYN-REQUEST,cp,Si,i〉，其他節點收到請求消息后，對比自己cp值，如果沒有異議，則向管理者回復確認同步消息，消息格式為〈SYN- COMMIT,Si,i〉；如果產生質疑則向所有節點廣播否定同步消息，并發起重新選舉過程。

在管理者收到2f+1個不同節點發送的確認同步消息后，進入數據同步階段，發送數據同步消息〈〈SYN-DATA,cp,Si,i〉,data〉。節點收到同步數據消息后，更新自己的備份數據區塊，向其他節點廣播同步成功消息，當節點收到2f+1個來自不同節點的對數據同步消息的同步成功消息后，數據同步和驗證過程完成。選舉和數據同步驗證過程如圖3所示。

Figure 3 Schematic diagram of election process and data synchronization圖3 選舉過程和數據同步示意圖

3.5 節點加入和退出

本文將共識節點分為3種角色，每種角色有自己的職責。普通節點在系統網絡中只負責對交易的處理和轉發，對候選者和管理者的狀態不產生影響，這樣有利于節點以普通節點的身份動態地加入系統網絡。

節點加入后處于無管理者狀態，發起對管理者的搜尋(Searching)過程。系統中的其它節點將告知其當前管理者的消息，當收到來自不同節點的2f+1個節點一致信息后，該節點與當前管理者建立聯系，然后進入工作狀態，如圖4所示。

Figure 4 Schematic diagram of adding new nodes圖4 新節點加入示意圖

候選者或者普通節點退出時，向所有節點廣播退出請求，管理者收到請求之后向除退出請求節點外的所有節點發送確認消息；管理者退出時，向所有節點廣播退出請求并將降級為普通節點，同時啟動選舉過程。選舉過程完畢之后由新當選的管理者發送確認消息。其它節點收到確認消息后查看是否與退出請求一致，如果一致則向退出請求節點發送退出回復消息。退出節點收到f+1個來自不同節點的退出回復消息時，節點退出成功，停止參與節點共識過程。

4 實驗分析

本文是在PBFT共識算法的基礎上提出的RPBFT共識算法，對通信開銷、時延、動態性、可靠性和容錯性方面進行了改進和優化。本節在配置為Iitel I5-337U處理器、8 GB內存、256 GHz固態硬盤的Windows 10系統中，通過Java多線程機制模擬網絡中的共識節點通信過程。同時與PBFT共識算法進行比較，以此驗證改進算法的有效性和可用性。

4.1 通信開銷

PBFT共識算法的通信開銷主要在預準備、準備、確認和視圖更換過程中；RPBFT共識算法的通信開銷主要在認證、提交2個階段和選舉、數據同步過程。

假設系統共識節點個數為n。PBFT共識算法預準備階段主節點發送預準備消息給所有從節點需要通信的次數為(n-1)。準備階段從節點之間相互通信所需通信次數為(n-1)2。確認階段每個節點向除自己以外的節點發送消息，所需通信次數為n(n-1)。即PBFT共識算法共識過程共需通信次數為2n(n-1)。視圖變更過程中，從節點廣播視圖變更消息所需通信次數為(n-1)2。主節點收到視圖變更消息后廣播確認消息所需通信次數為(n-1)。若出現視圖變更的概率為p，則總共通信次數為：

Q=2n(n-1)+pn(n-1)

(1)

RPBFT共識過程沒有錯誤發生時，2階段的通信次數為n(n-1)。當系統節點出錯或因網絡導致超時，進行選舉過程，候選者將自己的節點信息發送至其他候選者，這一階段共需的通信次數為4(n-1)2/9。候選者收到其它節點信息并進行比較之后，將更新信息發送至其他候選者，該過程通信次數為4(n-1)2/9。管理者發送同步數據請求，該過程通信次數為(n-1)。節點驗證成功發送確認同步過程的通信次數為(n-1)。確認同步完畢之后，管理者向其它節點發起數據更新的通信次數為(n-1)。由此分析可知，總共通信次數為:

(2)

假設網絡環境相同，則每次通信對網絡的消耗相同。2種算法通信次數比值W如式(3)所示：

(3)

由式(3)可以得出，當p=0時，W的值恒等于2，此時RPBFT共識算法的通信效率是PBFT共識算法的一半；當p=1時，W的值趨近于1，此時2種算法的網絡通信次數相等；當p<1時，W的值恒大于1，而且p的值越小，W的值越趨近于2。這說明在需要視圖變更情況出現較少時，RPBFT共識算法的共識過程通信開銷接近于PBFT共識算法的一半。多次實驗結果表明，在運行穩定的區塊鏈環境中，系統發生視圖變更的概率很小，所以RPBFT共識算法的通信開銷會減少將近一半，有效降低了系統在共識過程中的通信開銷。

4.2 時延測試

共識時延作為衡量共識算法的重要指標，在區塊鏈中表示交易從發起到完成的時間差。較低的時延使得區塊鏈的可用性和安全性更高。在同樣的網絡環境下，RPBFT共識算法通信次數更少，降低了共識延時。測試共識延時的計算方法如式(4)所示：

DelayTime=TSubmit-TAuthentication

(4)

其中，TSubmit為區塊完成共識確認的時間，TAuthentication為認證階段開始時間。固定交易數量為10個，在容錯節點數量不超過1的前提下，分別取4,5,6,7,8,9,10個節點進行3組對照實驗。對每組節點進行多次測試取平均值，得出2種算法在相同條件下的共識延時對比，如圖5所示。

Figure 5 Consensus delay comparison between two algorithms圖5 2種算法共識延時對比

由圖5可知，RPBFT共識算法的時延明顯低于PBFT共識算法的，而且隨著節點數量的增加，2種算法時延差距也會變大。

4.3 動態性

PBFT共識算法采用靜態請求響應模式，當節點加入或退出時需要重新啟動系統和數據同步過程。RPBFT共識算法將整個網絡的節點分為3種不同的角色，并通過一定的機制控制角色之間的轉換。其中，候選者是系統的關鍵節點，候選者負責選舉管理者，并且候選者數量需要保證為系統節點數量的大多數。節點加入時增加了尋找管理者的過程，節點退出時增加了退出確認過程，2個過程使系統可以感知節點加入或退出，相應地調整候選者的數量，并保證系統的可靠性和穩定性。

由此可見，RPBFT共識算法能夠在節點加入或退出時動態調整各個角色數量，避免了系統重啟的過程，減少了節點加入或退出時帶來的網絡資源消耗。

4.4 安全性

假設系統中有n個節點，每個節點出錯的概率為q,交易次數為M。在PBFT共識算法下主節點由式(5)計算得出：

P=vmodn

(5)

節點出錯后視圖編號變更為v+1，通過式(5)選擇主節點。假設在M次交易過程中每次出錯的節點均為當前主節點編號加一的節點，此時視圖變更后選擇的主節點為上一個視圖的出錯節點，系統處于高風險。由此可知PBFT共識算法在最壞的情況下有q的概率處于高風險環境中。

在RPBFT共識算法進行M次交易之后最壞的情況是有f個節點連續M次無法正常工作，每次出錯重新更換管理者，并將原管理者降級為普通節點。則此時存在2f-M個節點處于全部成功完成交易的狀態，信用積分為M；存在M個節點處于積分不為零的狀態。管理者就是從這2f個節點中選擇信用積分最高的節點，即選擇原來出錯節點的概率為零。對比之下，RPBFT共識算法在增加系統安全性方面有所改進。

為驗證系統在管理者行為出錯下的行為，實驗中設置管理者線程在系統運行10 s之后關閉。結果表明，RPBFT共識算法檢測到管理者失效后重新選舉管理者，并且與所有從節點進行數據同步，數據同步過程中從節點對新管理者進行檢測，保證了管理者的可靠性。接著開始新的共識過程。而且在整個過程中參與選舉和驗證的可信節點數量超過了2f，保證了系統(n-1)/3的容錯性。

實驗表明,RPBFT共識算法減少了系統開銷，縮短了共識延時，增加了算法的動態性，并且與PBFT共識算法一樣能夠保證分布式系統運行的一致性和安全性，證明了該算法的有效性和可靠性。

5 結束語

本文對在區塊鏈中應用廣泛的PBFT共識算法進行深入研究，并提出了一種基于PBFT共識算法的改進算法RPBFT共識算法。RPBFT共識算法動態管理節點的3種角色，使得節點可自由加入或者退出；對管理者的選擇方式加以改進，選舉出來的節點更為可信；選舉完成之后的數據同步和驗證過程，在驗證管理者的可信性的同時，保證了節點的一致性；優化的共識過程更加適應區塊鏈的網絡環境，并減少了消耗，加快了共識速度。但是，RPBFT共識算法依然存在不足，如何進一步降低網絡通信量，在保證通信效率的前提下提高容錯性，在將來需要進一步深入研究。