實用拜占庭容錯算法的改進研究

唐 宏，劉 雙，酒英豪，賀雨萌，朱 珊

1.重慶郵電大學 通信與信息工程學院，重慶400065

2.重慶郵電大學 移動通信技術重慶市重點實驗室，重慶400065

3.重慶郵電大學 國際學院，重慶400065

隨著比特幣[1]等數字加密貨幣的不斷發展，保障其安全可靠的區塊鏈技術也隨之得到廣泛關注，在很多領域產生深刻影響。區塊鏈[2-3]的本質是一種去中心化的分布式賬本數據庫，它集成了網絡通信、共識算法、密碼學原理、智能合約等技術，具備去中心化、防篡改、透明可溯源的特性。共識算法[4]作為區塊鏈系統的底層核心技術，起到確保系統中的各節點對特定時間內打包的交易順序達成一致，即實現分布式系統各節點數據一致性的作用。

實用拜占庭容錯算法（PBFT）算法[5-6]是聯盟鏈中應用最廣泛的共識算法之一，解決了拜占庭容錯算法效率低的問題。但PBFT仍存在下列不足之處，大大限制了其發展。首先，PBFT三階段通信協議中的后兩階段，節點均需要向系統中的其他所有節點發送消息，導致通信復雜度過高；其次PBFT按照編號順序選取主節點的方式也過于簡單，導致無論是否為拜占庭節點，均具備相等的當選主節點的機會，這極大威脅了系統的安全性與公平性；最后PBFT算法對拜占庭節點缺乏懲罰措施，當主節點被發現為惡意節點時，僅僅依賴視圖切換協議保障共識過程的進行，惡意節點仍存在于系統中，同樣威脅了系統的安全性。

當前已有諸多研究人員從多個方面對PBFT算法提出了改進方案：文獻[7]引入中心化的可信節點驗證新加入系統的節點身份信息，要求系統中的各節點維護一個包含節點信息的記錄表，并將各節點劃分為良性、缺席、惡意三種類型。根據在共識過程中的表現動態更新節點信息表，同時針對節點加入、退出等操作創新性地設計了相關協議，用以解決PBFT算法的動態性問題；文獻[8]為解決PBFT不適用于動態網絡的問題，提出了利用可驗證隨機函數（VRF）選取共識節點的方法，從而使算法滿足節點的動態變化需求，使其適用于動態網絡；文獻[9]從安全性和計算能力兩方面對節點是否可靠這一屬性進行量化處理，根據量化后的數值將節點角色分成四種類型，各類型節點中只有管理節點作為候補主節點，能夠被納入到主節點的選取范圍內，同時為保障系統安全性只有獲得較多選票的候選節點才可以轉為管理節點；文獻[10]針對PBFT 算法缺乏惡意節點懲罰措施的弊端，提出了基于信譽模型的改進拜占庭容錯算法，通過信譽模型評估節點在共識過程中的行為，并從信譽值高的節點中選取主節點，以此提高系統安全性；文獻[11]設置投票機制選取共識節點，并為促進節點積極參與共識過程，設置激勵機制與懲罰機制，從而實現對系統中的節點的管控。以上方案均從不同的角度為改進PBFT提出了創新性設想。文獻[12]通過增設候補集合的方式，解決PBFT算法動態性問題，并改進了視圖切換協議及主節點選舉機制，提高系統效率。

上述已有研究成果針對PBFT 算法存在的相關問題都給出了一些創新性的解決方案，然而考慮問題較為片面，沒有從整體角度出發制定一套完善的節點管控機制。本文對PBFT算法通信復雜度高、主節點選取方式簡單、缺乏節點管控機制的問題進行全面考慮，提出了一種基于節點可靠性評估的改進拜占庭容錯算法（RB-PBFT）。改進算法從評估節點可靠性的維度出發，制定管控機制，貫穿節點整個工作周期。為節點管控制定詳實全面的管理規則。

本文主要貢獻如下：

（1）從節點的基礎配置及共識表現兩個維度分析，計算得到節點的可靠性評分，用以評估各節點的可靠性。選取可靠性評分最高的節點作為主節點，引領本輪共識過程，同時選取可靠性評分高的部分節點組建共識群組參與共識過程，解決PBFT選主不安全及通信復雜度過高的問題。

（2）根據各節點的可靠性評分，將其標記為不同的信任狀態，對不同信任狀態的節點進行分類處理，解決PBFT缺乏節點管控機制的問題。

通過對RB-PBFT 算法進行實驗，分析表明，RBPBFT 在系統的通信復雜度、安全性、公平性、容錯性等方面均有一定提升。

1 相關背景介紹

1.1 實用拜占庭容錯共識算法

PBFT 算法于1999 年由Miguel Castro 和Barbara Liskov提出，該算法主要用于解決拜占庭將軍問題，即如何在網絡中存在惡意節點的情況下，確保最終決策的一致性與正確性，PBFT將拜占庭容錯算法的復雜度從指數級降到了多項式級別，是拜占庭容錯算法的首次實現。該算法在保障系統安全可靠的前提下，能夠提供的容錯性，即允許系統中存在不超過1/3的拜占庭節點。

PBFT中參與共識過程的節點被分成主節點（Primary）、備份節點（Backup）兩類，其中主節點負責從客戶端接收請求完成排序，并將相關消息廣播給所有的備份節點，備份節點負責驗證接收到的消息，執行相關操作并將結果返回給客戶端。PBFT的三階段通信協議是算法的核心部分，保障了共識結果的正確性。該三階段協議又稱為一致性協議，是典型的基于投票的共識協議，具體包括預準備（Pre-Prepare）、準備（Prepare）、確認（Commit）三階段，如圖1所示，圖中備份節點3為拜占庭節點。

圖1 PBFT一致性協議執行流程Fig.1 Implementation process of PBFT algorithm conformance protocol

1.2 信譽模型

1.2.1 EigenTrust信譽模型

EigenTrust[13-14]是P2P網絡中廣泛使用的信任度評估模型，以節點i為例，模型中每個節點維護兩個值：（1）根據與其他節點交互歷史得到的局部信任值Cij；（2）整個系統賦予節點i的全局信任值ti。EigenTrust模型計算信任值的過程如下：

（1）計算局部信任值。以節點i為例，根據交互歷史，利用公式（1）對節點j進行評價，計算得到局部信任值Sij，其中Sat(i,j)代表歷史交互中滿意的次數，Unsat(i,j)代表不滿意的次數。

（2）規范化局部信任值。得到Sij后，為防止惡意節點之間相互打高分，威脅系統安全，利用公式（2）對Sij進行標準化處理，得到規范化的局部信任值Cij：

（3）整合局部信任值。采用傳遞信任及多次迭代的思想，使節點i獲得全局視野，利用公式（3）得到全局信任值。其中p是預先信任的節點集合，a是決定預先信任節點集合p中各節點權重的參數。

EigenTrust 信譽模型雖然具備使用簡單、易擴展的優勢，但其過度依賴預先信任節點集合。在EigenTrust信譽模型中，預先信任的節點有很高的地位，其他節點以這些節點為中心，信任這些節點所信任的節點，即使預先信任的節點存在惡意行為，其他節點仍會持續信任該節點。導致即使系統中其他誠實節點從未作惡，但若不在預先信任集合中，也會得不到重視，從而被逐漸邊緣化。這極大威脅了系統的安全性。為解決上述問題，Kurdi 于2015 年提出了HonestPeer 信譽模型，實驗證明HonestPeer信任模型相較于EigenTrust模型能夠實現更高的成功率和更低的錯誤文件下載率。

1.2.2 HonestPeer信譽模型

HonestPeer[15]信任模型旨在解決EigenTrust 模型過度依賴預先信任節點，導致其他誠實節點被邊緣化的問題。在HonestPeer 模型中，誠實節點有最高的地位，如果誠實節點在預先信任的節點集合p中，那么p中各節點在決定其他節點的信任值時仍然有很大影響力；但若誠實節點不在集合p中，p中各節點的影響力就會被減弱，誠實節點會發揮較高的影響力，如公式（4）所示，其中h為誠實節點。

HonestPeer模型允許節點根據以往交易歷史，認證識別誠實節點，并通過判斷誠實節點是否在系統預先信任的節點組中，來降低對預先信任節點的依賴，提高了信任模型的安全性及成功率。

2 RB-PBFT算法設計方案

2.1 算法概述

PBFT 算法要求系統中的所有節點均參與共識，并按照三階段協議完成共識過程，其中完成一次共識，系統中廣播的信息總量過多，導致系統通信復雜度過高效率較差。RB-PBFT 算法全面考慮節點的屬性，利用層次分析法對節點的基礎配置進行處理，得到節點的靜態基礎評分Bj；引入HonestPeer信任模型，根據節點間的交互歷史，得到節點的動態信譽評分Rj；對兩參數進行賦權計算，得到節點的綜合可靠性評分Cj，以此來評估節點的可靠性。

由于PBFT 算法僅僅按照編號順序選取主節點，選取主節點的方式過于簡單。且一旦發現主節點為拜占庭節點，也只是依賴視圖切換協議，更換主節點繼續完成本輪共識過程。作惡的主節點依然留在系統中，且未受到任何懲罰，仍擁有與其他誠實節點均等當選主節點的機會，這難以保障系統的安全性及公平性。RB-PBFT算法根據降序排列的節點Cj，選取主節點并組建共識群組。等待本輪共識結束后更新節點Rj標記各節點的信任狀態，根據節點不同的信任狀態，設置節點管控機制。增加誠實節點入選共識群組的概率，減少惡意節點入選共識群組的概率。以此來解決系統安全性及公平性問題。

2.2 節點基礎配置評分機制

考慮到節點基礎配置越高，作惡成本也越高；同等條件下，高配置的節點較低配置的節點，傳輸信息的速度更快，效率更高。因此應將節點的基礎配置納入到評估節點可靠性的考慮范圍內。在節點初入網絡時，根據節點的基礎配置，從影響交易處理速度的CPU 內核數量、計算機內存容量及硬盤容量大小這三方面進行評估。計算節點基礎配置評分的步驟如下：

（1）由于各參數的單位不同，為了方便統一計算，利用歸一化公式（5）對參數進行標準化處理，得到標準化后的數值。其中Xp為實際值，Xb為標準化處理后的數值。

（2）利用層次分析法，根據三方面參數的重要性分級構造判別矩陣，得到符合重要性排名的權重向量。

（3）根據權重向量及標準化處理后的數值，為各參數進行權重賦值，得到節點的基礎評分Bj。

2.3 節點信譽評分機制

引入HonestPeer 信譽模型監測節點行為。首先初始化各節點的全局信譽值；選取共識群組成員，等待本輪共識結束后，更新各節點的信譽值，同時根據更新后的信譽值將節點標記成不同信任狀態，以便后續制定節點管控機制。下面為具體介紹：

假設系統中的總節點數為N，將所有節點的本地初始信譽值設為0.5，根據公式（6）計算節點的初始化Cj。此處將初始信譽值設為0.5是根據后續計算各節點的可靠性評分Cj時，為了使Cj一直滿足(0＜Cj＜1)條件，如果初始信譽值設置得過小，各節點Cj差距不大，不便于實驗觀察；如果Cj設置得過大，又難以滿足(0＜Cj＜1)條件，同樣不利于實驗分析。得到Cj后，對其進行降序排列，選取Cj最高的節點作為主節點，并按降序Cj選取不同比例a(0＜a＜1)的節點構建共識群組，參與共識過程。選取的比例一定要保證共識組中成員數量始終大于2f+1（f為系統中拜占庭節點的數量）。

待本輪共識結束后允許共識群組中各節點之間根據交互歷史進行互評。共識組中節點i對同處于共識群組中的節點j根據共識過程中節點j的具體表現，標記節點j的信任狀態。標記節點信任狀態分類的條件如表1所示。當節點j與i之間正常傳遞信息，且j向i發送的信息內容，與i收到的來自其他大多數節點的發送的信息內容一致時，i即可判定j在本輪共識中的行為正常，將j標注為誠實節點；當j未在規定時間內向i發送信息，或i向j發送信息后，j聲稱未收到來自i的信息，則節點i判定j的行為異常，但此時不能確定j的信任狀態，可能是惡意節點作惡也可能只是節點出現宕機故障。先將其標注為故障節點，一旦之后發現j出現惡意行為，將其信任標注改為惡意；當j向i發送信息，但i發現該信息內容，與其收到的來自其他大多數節點發送的信息內容不一致時，i判定j的行為異常，將其標注為惡意節點。節點i根據對節點j的信任標注，更新本地信任矩陣，得到更新后的Rj，從而計算得到更新后的Cj，重新構建共識群組中的成員。

表1 節點行為及信任狀態分類表Table 1 Node behavior and trust status classification

對于非共識群組成員（即未能參與共識過程的節點）RB-PBFT 算法允許其根據以往交互歷史即以往印象對其他同處于非共識群組的成員進行評分，評分與標記規則與上述共識群體中各節點互評標記的規則一致。

2.4 節點管控機制

根據各節點的不同信任狀態，制定管控機制，對節點進行分類處理：當節點j被標注為誠實狀態時，節點i對j打+1 分，根據公式（4），誠實節點j的信任值Rj將持續增加；當節點j被標注為故障狀態，計算節點i對j的局部信任值時，節點i對j打0分，使得故障節點的全局信任值維持不變，觀察后續行為，做出相應處理；當節點j被標注為惡意狀態，改進HonestPeer 模型，計算節點i對j的局部信任值時，允許i對j打-1分，節點j的全局信任值將持續減少。

2.5 節點可靠性評分計算機制

根據靜態的基礎評分及動態更新的信任值計算節點的可靠性評分，評估節點可靠性，要為兩個參數賦予不同的權重比例K1、K2。雖然節點的基礎配置會加快信息傳遞速度，提高系統性能，但為了抵御惡意節點成員聚集起來利用高配置設備進行攻擊，節點的基礎配置評分占比不應過高。因而相較于基礎配置，節點在共識過程中的動態可信度在評估節點可靠性方面，應占較高比重，即權重參數滿足(K1＜K2)。根據公式（6）計算節點的可靠性評分。

計算得到節點更新后的Rj，利用公式（6）更新節點的Cj，當惡意節點j的可靠性評分小于未參與共識過程的其他備份節點的可靠性評分時，節點j將被踢出共識節點組，不能繼續參與共識過程。從未參與共識的其他備份節點中隨機選取可靠性評分高于節點j的某個節點，取代j在共識組中的位置，參與共識過程。從而減少共識組中惡意節點的數目，提高共識過程及系統的安全性及公平性。

3 實驗及理論分析

3.1 可靠性分析

安全性即各誠實節點能否對廣播的事件結果達成一致性共識，并將正確結果成功輸出。若成功輸出正確結果，則認為系統安全性較高。在PBFT 算法中，主節點是依靠公式（7）進行計算，式中P為選取的主節點編號、V為當前視圖編號、R為系統中的節點數目。可以看出根據取模運算，實際上就是按照順序編號選取主節點，這使得拜占庭節點和誠實節點擁有相等的被選為主節點的機會，這種選主方式極大地威脅了系統的安全性。

在RB-PBFT 算法中，引入了共識群組的概念。綜合評估節點的基礎配置及共識表現，得出節點動態的可靠性評分，根據降序排列的可靠性評分，選取評分高的成員進入共識組。其中可靠性評分主要被節點信譽值影響，信譽值是節點間互評的結果，代表了節點之間的信任關系，節點作惡的概率與信譽值成反比關系。即高信譽值的節點作惡可能性低。由于共識組中的成員均是信譽值較高的節點，因此系統的安全性會得到提高。同時RB-PBFT 設置了節點管控機制，一旦節點被發現存在惡意行為，其可靠性評分將會隨之降低，當評分低于非共識群組中的某節點評分時，該作惡節點將會被踢出共識組，系統安全性得到進一步保障。

實驗所需硬件配置如表2所示，利用實驗室不同基礎配置的電腦搭建聯盟鏈環境，使用docker容器技術模擬多個實驗所需的虛擬節點。

表2 實驗配置信息Table 2 Experiment configuration information

假設當前網絡中共有20 個節點，即每臺電腦利用docker容器模擬4個節點。首先根據各節點的基礎配置計算基礎評分，設置每個節點的初始信任值為0.5，得到初始化的節點可靠性評分。選取可靠性評分排在前a%的節點入選共識群組，即參與共識的節點數目為aN，未參與公式過程的節點數目為(1-a)N。當a=0.5 時，根據PBFT算法容錯性，設置共識組內拜占庭節點數目為3，進行20輪共識。為了防止惡意節點通過高配置硬件設備作惡，節點在共識組中的表現影響力應超過基礎配置，因此取基礎配置賦權參數K1=0.3，信譽賦權參數K2=0.7。記錄共識組內惡意節點可靠性評分如圖2所示，新加入共識組的誠實節點可靠性評分如圖3 所示，組內惡意節點數如圖4所示。

圖2 惡意節點可靠性評分Fig.2 Malicious node reliability score

圖3 誠實節點可靠性評分Fig.3 Honest node reliability score

圖4 共識組中惡意節點數目Fig.4 Number of malicious nodes in consensus group

可見，隨著共識輪數的增加，共識組內惡意節點的可靠性評分隨之下降，誠實節點的可靠性評分隨之增加。當惡意節點的可靠性評分小于非共識組中某節點評分時，該節點將被取代共識組成員位置；同時共識組內惡意節點的數目隨著組內成員動態變化而減少，最終為0。圖中出現共識次數增加而惡意節點數維持不變的情況是當惡意節點僅做出故障節點行為使得信任值保持不變或該節點的可靠性評分仍大于候補節點的情況，但惡意節點數總體仍保持減少的趨勢。

3.2 公平性分析

PBFT中，若發現主節點存在惡意行為，算法僅依靠視圖切換協議，切換當前視圖更換本輪共識的主節點，以保證共識過程。作惡的主節點仍然存在于系統中，且沒有受到任何懲罰，下次當選主節點的概率依然與其他誠實節點相等，這對于誠實節點是不公平的，導致系統公平性較差。

RB-PBFT 算法則通過引入信譽模型的方法，允許共識群組中的各節點之間根據在共識過程中的表現進行互評；非共識組中各節點根據以往交互歷史進行互評。標記節點的信任狀態，設置節點管控機制。一旦節點被標記為惡意節點，其信譽值將隨之降低，導致可靠性評分隨之減少，將可能被移除共識組無法參與共識過程；而非共識組中的誠實節點，可靠性評分會隨其誠實行為而增加，將有機會進入共識群組參與共識過程。簡而言之，誠實節點會因其誠實行為而獲得獎勵；惡意節點會因其惡意行為受到懲罰。這種機制極大地提高了系統公平性。

3.3 通信復雜度分析

通信復雜度即完成一次共識，系統中廣播的信息總數，過高的通信復雜度會影響系統的效率。PBFT算法、RB-PBFT算法及文獻[12]的IPBFT算法完成一輪共識，系統所需廣播的消息數目對比如表3所示。

表3 不同算法通信量對比Table 3 Comparison of traffic volume of different algorithms

根據表3 列舉的各算法通信量，分別取a=0.5、a=0.25，繪制各算法廣播通信量對比圖5、圖6。由于IPBFT算法通信量表達式中P為視圖切換的概率，為方便觀察數據，設置系統拜占庭節點數f=0，則P=0。

圖5 a=0.5 時各算法通信量對比Fig.5 Traffic volume comparison of each algorithm when a=0.5

從圖5 及圖6 可以看出在a=0.5 及a=0.25，設定系統中不存在惡意節點的情況下，PBFT 算法及IPBFT算法均高于RB-PBFT 算法，且在RB-PBFT 算法中，通信量與參數a的取值成正比關系，a的取值減小，系統中廣播的消息數量也隨之減少。因此本算法提出的選取可靠性評分較高的部分節點參與共識的方案能夠有效地減少系統中廣播的通信量，降低系統復雜度，提高效率。

圖6 a=0.25 時各算法通信量對比Fig.6 Traffic volume comparison of each algorithm when a=0.25

3.4 容錯性分析

容錯性指的是系統中最多能容納的惡意節點數，PBFT中為保證順利完成共識，系統僅支持容錯性，而RB-PBFT系統中將節點劃分到不同的群組：共識群組及非共識群組，使得系統容錯性達到+(1-a)N，只有當a=1 時，兩算法的容錯性才相等，即全部節點均參與共識；而參數比例參數a是滿足a≤1 的條件，即RB-PBFT算法最壞的情況的容錯性與PBFT算法相同，因此本算法的容錯性優于PBFT算法，兩算法性能對比如表4所示。

表4 算法性能對比Table 4 Comparison of algorithm performance

4 結束語

本文針對原始PBFT 算法通信復雜度高、主節點選取簡單、缺乏節點管控機制的弊端，提出了一種基于節點可靠性評估的改進拜占庭容錯算法（RB-PBFT）。RB-PBFT從節點的基礎配置及信任狀態兩方面評估節點可靠性，首先計算節點的基礎評分，接著引入Honest-Peer 信任模型，根據節點在共識過程中的行為，標記節點的信任狀態，允許共識組中各節點根據歷史交互信息進行互評，非共識組中的各節點根據以往交互印象進行互評，得到節點動態變化的信任值，最后對這兩個參數進行賦值權重，綜合計算節點的可靠性評分。標記節點信任狀態，設置節點管控機制。最終惡意節點的可靠性評分將隨著共識次數的增加而逐漸減少，誠實節點的可靠性評分將不斷增加。實驗表明RB-PBFT算法能夠提高共識過程的安全性及公平性，減少系統通信復雜度，同時在系統容錯性方面也有良好表現。

本算法引入了信用模型，增加了計算可靠性的步驟，相較于原始PBFT 算法，進行共識時，增大了計算量。因此在傳遞相同數目信息，進行相同輪次共識時，RB-PBFT 算法的運行時間及傳輸時延略高于PBFT 算法。接下來將研究如何盡可能低的降低時間損耗，減小對算法運行效率的影響。