基于分組Raft機制的PBFT共識算法改進方案設計

吳宇森 劉伊然 吳沅賽 史庭俊

（揚州大學信息工程學院 江蘇省揚州市 225127）

1 引言

十幾年前隨著比特幣[1]的誕生，區塊鏈和比特幣的概念被越來越多的人知曉。區塊鏈技術[2]本身也因其可溯源、不可篡改的特性而被廣泛研究。聯盟鏈[3]作為區塊鏈2.0 的產物，真正做到了讓區塊鏈和比特幣、以太幣這些虛擬貨幣脫鉤。聯盟鏈由多個組織、機構參與其中，鏈上的數據無法被外部訪問且不可被篡改，數據的安全性得到了極大的保障。在銀行、醫療等領域有著很廣泛的應用價值，而PBFT 作為聯盟鏈的核心共識算法，關系著整個聯盟鏈的效率和安全性[4]，但PBFT 算法本身仍存在隨著節點增加，性能明顯下降以及節點作惡得不到有效監管等問題，因而對PBFT 算法的優化顯然是必不可少的。

2 PBFT、Raft算法簡介及相關研究

2.1 Raft共識算法

Raft[5]共識算法存在節點活躍度不高，故障節點數量較多會影響共識效率的問題。若直接將分組Raft機制應用于PBFT共識算法的優化，會將Raft 算法本身存在的問題帶入到每個小組組內，因而需使用RageRank[6]算法對Raft 算法進行優化，然后再使用優化后的Raft 算法，采用分組機制應用于PBFT 算法中，實現對PBFT 算法的優化。

PageRank 算法最初是被用來衡量谷歌網頁的重要性。在該算法中，一個節點的PR 值是由所有指向它的節點的重要性通過多次遞歸算法得到的，最終得到的PR 值越高代表此節點的重要性越高，因而也可以理解為一個節點的重要性取決于所有指向它的節點的重要性。公式（1）中L(pj)是節點pj的出鏈總數，每個節點初始PR值為1/N，N 是節點總數，是有出鏈到節點pi的所有節點集合，t 為迭代輪數，α 為阻尼系數來解決孤立節點對PR 值分配時的負面，同時起到對PageRank 公式修正的作用，式（1）為PageRank 修正公式：

Raft 算法是由Paxos 算法優化而來，Paxos 算法由于過于復雜，讓大多數人都很難真正去理解，于是有兩位研究者[7]通過對Paxos算法的深入研究，最終提出了更加容易理解，也更容易應用到實際系統當中的Raft 算法。該算法中有三個角色：領導者、跟隨者、候選者。領導者節點負責接收客戶端的請求和日志的同步管理，與跟隨者節點共識后，將請求結果反饋給客戶端，跟隨者節點負責響應領導者節點的日志同步請求，候選者節點是由跟隨者節點在領導者節點宕機時轉變而來，參與新領導者的選舉，若獲得半數投票則成為新的領導者節點，若失敗則轉變回跟隨者節點，每個節點任一時刻都處于這三個狀態之一。Raft 算法為了保證復制日志的一致性，其具體流程如下：

Step1：領導者節點收到客戶端發來的請求。

Step2：領導者節點將收到的命令追加到本地日志，然后并發復制給其它跟隨者節點。

Step3：跟隨者節點將命令寫入到日志中，并反饋確認復制給領導者節點。

Step4：領導者節點收到過半的反饋后，就會提交命令，并返回結果給客戶端。

Step5：最后領導者節點發送讓跟隨者節點提交命令的消息。

2.2 PBFT共識算法

PBFT 算法[8]在1999年被提出，用于解決拜占庭容錯問題。但該算法存在節點活躍度不高，性能隨著節點增加而明顯降低，作惡節點無法被監督并被及時踢出聯盟鏈等問題，于是筆者將采用分組Raft機制來優化PBFT共識算法，將若干節點分為多個組，組內采用基于PageRank 算法優化的Raft 共識算法，組外依然保留PBFT共識算法。

PBFT 算法最大容錯節點數量是（n-1）/3，可以理解為，如果惡意節點的數量為f，正常節點的數量至少是2f+1，才能讓系統正常運轉。假設存在f 個惡意節點以及f 個故障節點這種極端情況，要保證系統依然有至少f+1 個正常節點能讓共識順利達成，因此節點總數至少為3f+1。

PBFT共識算法中包含三個角色，主節點，副本節點，客戶端。主要包含三個階段：預準備階段、準備階段、確認階段，三個階段的流程如下：

Step1：預準備階段：主節點收到客戶端發送來的請求后，驗證其簽名是否正確，若不正確則丟棄，若為正確請求，按順序分配編號n，廣播<,m>消息給其它副本節點。

Step2：準備階段：副本節點驗證主節點發送的PRE-PERPARE消息，若為正確請求，則向其他節點廣播消息。

Step3：確認階段：節點對收到的PREPARE 消息進行驗證，若非法則丟棄，收到2f+1 個（包含自己）通過驗證的PREPARE 消息，則廣播給其它節點。PBFT共識算法流程圖如圖1所示。

圖1：PBFT共識算法流程圖

2.3 相關研究

近年來對區塊鏈共識機制的研究，主要集中在對PBFT共識算法的研究，黃冬艷等人[9]提出一種基于Raft 集群的拜占庭容錯共識機制，組內用Raft 算法共識，組外采用PBFT 算法共識，提升了共識效率，但是并沒有解決組內成員積極性的問題。陳忠賢等人[10]提出一種基于通信時間分組的PBFT 算法改進方案，基于最短通信時間進行分組，先組內共識再組外共識，提升了共識效率。陳子豪等人[11]提出一種基于K-medoids 的改進PBFT共識機制，通過K-medoids 算法對節點進行分組，先組內共識再組外共識，提升了共識效率。但是這兩個方案仍然沒有解決節點作惡的問題。劉乃安等人[12]提出一種面向區塊鏈驗證節點的聲譽證明共識機制，根據節點的歷史活躍度和信用情況分配聲譽值，提升了節點積極性，一定程度上抵制了節點作惡，但這個方案并沒有解決原始PBFT 算法中存在的通信次數過多而性能不高的問題。

目前對PBFT共識算法的研究往往存在積極性、安全性和性能三者不能同時兼得的問題，本文提出了一種GRBFT（Group Raft Byzantine Fault Tolerance）共識算法。首先對節點進行分組，先組內共識再組外共識，減少了通信次數，大幅提升性能，同時組內采用基于PageRank 算法優化的Raft 共識算法，解決了組內積極性不高的問題，降低了組內故障節點對共識效率的影響，然后引入一個排序節點，將客戶端的每個請求排序好發給所有組長節點，避免了過去單一主節點權利較大，一旦作惡帶來的影響較大的問題，最后每個小組的組內引入監傳節點，有效的抵制組員和組長作惡的問題，提升了系統的安全性。

3 GRBFT共識算法

GRBFT共識算法分為組外共識和組內共識兩個部分，先組內共識，再由各組組長帶著組內共識結果參與組外共識。首先將所有節點，分為K 個組，每個組內包含N 個成員。組內采用基于PageRank 優化的Raft 共識算法，組內成員N ≥3。參與組外共識的節點為每個小組組內選出的組長，組外共識采用PBFT 的共識算法，PBFT 算法中由于總節點數m 對惡意節點數f 要滿足m ≥3f+1 的關系，組外成員K ≥4。

3.1 組內共識

3.1.1 組內共識方案

組內使用PageRank 算法對Raft 共識算法進行優化，每個節點初始PR 值為1/N，N 為節點個數，在一個周期時間T 內，根據組內節點不同的歷史活躍度，通過PageRank 算法多次迭代，等結果收斂后分配節點對應的新的PR 值。領導者節點與跟隨者節點交互期間，每個跟隨者節點回應領導者節點時會附帶自身PR 值，領導者節點收到過半的PR 值便能達成共識，并將該方案作為組內共識方案。由于Raft 算法本身無法抵制作惡節點，筆者將在后續引入組內監傳節點。該方案讓更活躍的節點擁有更高的PR 值，同時提高共識效率，并且比起組內依然實行PBFT 算法，Raft 算法擁有更低的時間復雜度，即使組內成員增加，效率也不會大幅下降。

3.1.2 采用PageRank 修正公式來優化

考慮到組內存在孤立節點的可能性，因而采用PageRank 修正公式，筆者將該公式矩陣化表達，來便于代碼的實現，首先構建一個矩陣M，矩陣其中的任意元素Mij代表節點pj指向節點pi的概率，其分子weightij為節點pj向pi發送請求或回應的總次數，分母L(pj)為節點pj給所有其它節點發送信息的總數，式（2）為元素Mij的公式：

再構建一個列向量Vt，里面存放第t-1 輪迭代后每個節點的PR值PR(pi)，V1中每個節點初始PR 值為1/N，式（3）為Vt的公式：

多次迭代，直到最終收斂，迭代停止，并得到最終迭代結果Vt+1，每個節點最終PR 值PR(pi)存放在里面，其中N 為總節點數，α 為阻尼系數，用來解決出鏈為零的孤立節點問題，式（4）為Vt+1的公式：

由于組長與所有其它組員交互，因而其PR 值PR(pi)組長會過高，為了避免過于中心化的情況，需要對組長的PR 值進行修正，將其自身的PR 值降低為原始PR 值的倍，降低組長作惡的影響，式（5）為修正公式：

3.1.3 組內引入監傳節點

基于PageRank 算法優化的Raft 共識算法雖然可以通過降低故障節點或者不活躍節點的PR 值來減少它們對共識效率的影響，但對于該組組長與組員的作惡不能起到很好的抵制作用，因而需要在每個小組里增加一個絕對公正的監傳節點，讓組長和組員間通過監傳節點當中間人傳遞彼此的信息，由于監傳節點不參與共識投票，只是作為信息傳遞的中轉站，可以做到公正，還可以通過驗證組員和組長發送的信息，來找出作惡節點，并發起投票踢出。

組長會一直給監傳節點發送自己的心跳，表明自己沒有宕機，監傳節點如果能收到組長的心跳，也會給組員發送自己的心跳，如果監傳節點接收不到組長的心跳，將發起換屆選舉，組內將選出新的組長，新的組長由當前PR 值最高的組員擔任。

由于監傳節點為了保證公正，不參與共識投票且不擁有PR 值，所以在計算PR 值時，忽略監傳節點的存在，組長與組員通過監傳節點來通信分配到的PR 值等同于組長與組員直接通信分配得到的PR 值。監傳節點每隔一個周期時間T，就會根據組員和組長過去的表現，通過PageRank 算法給組長和組員分配新的PR 值，并對組長PR 值進行修正。每個成員初試PR 值均為1/N，N 為組員成員數量，包含組長，不包含監傳節點。組內共識流程圖如圖2所示。

圖2：組內共識流程圖

若監傳節點發現組長作惡，將向所有組員發起，其中evidence 為判定組長作惡的證據，n 為作惡消息的編號，組員會驗證收到的消息，消息驗證無誤后，投票給監傳節點，監傳節點若收到組員過半投票，則踢出該組組長，并且將該組長的PR 值，根據每個組員PR 值占所有組員PR 值的比例分配給每個組員，并由此時PR 值最高的組員擔任組長。

如圖3所示，若監傳節點發現組員作惡，將向組長和其它組員發起，其中evidence 為判定組員作惡的證據，n 為作惡消息的編號，組員和組長對該消息進行驗證，消息驗證無誤后，投票給監傳節點，監傳節點若收到過半投票，則踢出該組員，并且將該組員的PR 值，根據每個成員PR 值占該組非作惡成員總PR 值的比重，來分配給每個組員。

圖3：監傳節點踢出作惡節點流程

3.2 組外共識

3.2.1 排序節點的引入

引入一個公正的排序節點，僅負責驗證客戶端請求簽名是否正確和對客戶端發來的請求進行編號排序。由于其不參與共識投票，主要負責請求的排序，因而可以做到公正。排序節點將客戶端發來的請求排序好發給組長節點。

3.2.2 組長的選取

由于每個小組內遵循的是Raft 共識算法，初次組長的選取遵循Raft 領導節點選取機制，后續若監傳節點發現組長宕機或作惡，將由組員里當前PR 值最高的組員擔任新的組長。

3.2.3 組外共識方案

如圖4所示，組長間的共識遵循PBFT共識算法。首先組長們會將排序節點發來的請求通過監傳節點發給組員，組員們會對請求回應并在回應中附帶自身當前PR 值的數值，每個組員的回應會先傳給監傳節點，監傳節點收到的有效返回的信息中包含的PR 值的累計數值加上組長的PR 值過半后，便會把收到的結果反饋給組長，組長驗證無誤后，會按照PBFT共識算法的流程，先進入準備階段，廣播PREPARE 消息，收到2f+1 個組長(包含自己)發送來的PREPARE 消息，則進入確認階段，廣播COMMIT 消息，收到2f+1 個組長(包含自己)發送來的COMMIT 消息，則發送REPLY給客戶端，并發送數據提交給組內監傳節點，客戶端收到f+1 個REPLY，則共識達成。

圖4：組外共識流程

3.3 GRBFT共識算法的流程

Step1：客戶端給排序節點發送請求。

Step2：排序節點驗證簽名無誤后，給請求分配編號n，廣播<,m>消息給所有組長節點。

Step3：組長節點對排序節點發送的PRE-PERPARE 消息進行驗證，若為正確請求，則廣播消息給監傳節點。

Step4：監傳節點將消息轉發給組員，讓組員進行復制，組員們會將對請求的回應發送給監傳節點，并在回應中附帶自身當前PR 值的數值。

Step5：監傳節點收到的有效返回的信息中包含的PR 值的累計數值加上組長的PR 值過半后，便會把收到的結果反饋給組長。

Step6：監傳節點每隔一段周期時間T，就會根據組員和組長過去的表現，通過PageRank 算法給組長和組員分配新的PR 值，并對組長PR 值進行修正。

Step7：組長對監傳節點發來的消息進行驗證，驗證無誤后，便進入準備階段，廣播給其它組長節點。

Step8：組長們會對收到的PREPARE 消息進行驗證，若非法則丟棄，收到2f+1 個（包含自己）通過驗證的PREPARE 消息，則向其他組長節點廣播。

Step9：組長們會對收到的COMMIT 消息進行驗證，若非法則丟棄，收到2f+1 個（包含自己）通過驗證的COMMIT 消息，則發送REPLY 給客戶端，并發送數據提交給組內監傳節點，監傳節點發送數據提交給每個組員。

Step10：客戶端收到f+1 個組長發來的REPLY 信息，則共識達成。

4 實驗與分析

4.1 實驗環境

實驗環境選用的宿主機系統為Window10，處理器為AMD R5 2600，宿主機內存為16g，測試平臺軟件的開發環境為ubuntu20.04/Golang1.16。

4.2 最大可容忍惡意節點數比較

筆者通過比較兩個算法最大可容忍惡意節點數來區分哪一個算法擁有更好的安全性，可以容忍更多的惡意節點，首先筆者設GRBFT 算法中每個組的節點數均為5，然后模擬實驗，觀察兩個算法，在隨著節點數量的增加下，最大可容忍惡意節點數的變化情況，實驗結果如圖5所示。

圖5：兩個算法最大可容忍惡意節點數對比

從圖5 中筆者可以看出隨著節點數量的增加，GRBFT 算法比起PBFT 算法總是可以容忍更多的惡意節點數，因而GRBFT 算法有著更好的安全性。

4.3 吞吐量比較

吞吐量指系統每秒鐘處理的事務的數量，吞吐量越高代表著系統單位時間能處理的事務就越多，性能就越好。

吞吐量可以很好的反應一個系統的性能，用來衡量兩個算法對系統的影響是非常合適的，筆者在不同節點數下都會進行10 次模擬實驗，把10 次實驗中的平均值作為該節點數下的吞吐量，實驗結果如圖6所示。

圖6：PBFT 與GRBFT 吞吐量比對圖

從圖6 中可以看出，GRBFT 算法比起PBFT 算法，在不同節點數量下，均擁有更高的吞吐量，且隨著節點數量的增加，PBFT算法的吞吐量已經下降到1000 以下，而GRBFT 算法依然能保持著較高的吞吐量，因而GRBFT 算法有著更好的吞吐性能。

4.4 共識時延比較

共識時延指請求從客戶端發出到最終全網共識所需的時間，共識時延越小代表著消息被全網共識所需時間越短，同時也代表著性能越優異，共識時延用來評估兩個算法對系統處理消息的快慢非常的合適，在不同節點數下筆者通過10 次模擬實驗，將平均值作為不同節點數下的共識時延數值，實驗結果如圖7所示。

圖7：PBFT 與GRBFT共識時延比對圖

從圖7 中可以看出，GRBFT 算法比起PBFT 算法，擁有更低的共識時延，且隨著節點增加，GRBFT 算法的共識時延增長的幅度也比PBFT 算法小很多，既代表著有著更快的對請求消息的處理速度，也能反應出GRBFT 算法有著更好的性能，比起PBFT 算法可以更好的提升聯盟鏈的共識效率。

5 結束語

本文針對實用拜占庭容錯算法（PBFT）中存在節點活躍度不高，節點數量增加，通信次數過多導致的效率低下，作惡節點無法被監督并被及時踢出聯盟鏈的問題進行了研究，提出了GRBFT 算法。將PBFT 原本的全員互相共識，改為了組內共識和組外共識，組內采用基于PageRank 算法的Raft 共識算法，根據組內成員不同的活躍度，給予不同的PR 值，將收到超過半數節點同意算達成共識，改為收到超過半數的PR 值便算共識達成，有效降低了故障節點對共識效率的影響，并在每個組內增加了監傳節點，作為組長和組員傳遞信息的中間人，在當中間人幫它們傳遞信息的同時，也監督著該組組長和組員是否作惡，對于作惡的節點，取證并發起投票踢出，組外新增了排序節點取代主節點給所有組長們發送PRE-PERPARE消息，一定程度上防范了主節點作惡，組長們代表著組內的意見實行PBFT共識算法。通過模擬實驗，筆者發現GRBFT 算法比起PBFT 算法最大可容忍更多的惡意節點，擁有更高的吞吐量以及更低的共識時延，并且在隨著節點數增加的同時，依然保持著較高的性能。監督節點與排序節點的引入，一定程度上也提升了系統的安全性。未來也依然會對共識優化做進一步的研究，努力去做到能在保證性能不降低的同時，安全性進一步提高。