基于防預測分組的PBFT 算法改進方案*

周昌慧 劉萬里 梁 峰 李榮臻 徐 雷

（1.南京理工大學計算機與工程學院 南京 210094）

（2.南京市中西醫結合醫院 南京 210014）

（3.連云港市廣播電視臺 連云港 222000）

1 引言

區塊鏈這一概念起源于中本聰提出的比特幣［1］，其本質是在對等網絡中基于密碼學構建去中心化的分布式數據庫［2］。利用區塊鏈所具有的防篡改、可追溯、鏈上信息透明公開的特點，網絡中的對等節點之間互相信任，一致行動，保證了在分布式場景下的鏈上數據一致可靠。近些年對于區塊鏈的相關技術的研究愈發火熱。2020 年12 月，中國信息通信研究院發布了《區塊鏈白皮書（2020年）》針對區塊鏈的生態和發展做出了系統性的全景觀望。隨著廣大研究者的不懈鉆研，逐漸發掘出了區塊鏈更多的潛力，并擴展出醫療、教育、供應鏈、物聯網等非金融領域的應用可能［3］。

區塊鏈的核心技術中，哈希算法保證了鏈上數據不可篡改，分布式存儲實現了去中心化，密碼學保證了電子貨幣和個人資產的安全，共識算法解決分布式一致性問題［4］。其中，共識算法是當下區塊鏈研究的熱點。針對不同的分布式應用場景，共識算法需要滿足不同的可擴展性、共識效率、數據一致性、分區容錯性的需求［5］。研究者基于去中心化程度，將區塊鏈分為公有鏈、私有鏈和聯盟鏈。在公有鏈中，為滿足高去中心化需求，共識算法主要以證明機制為主［6］。在私有鏈和聯盟鏈中，節點身份相對較為可靠［7］，因此共識算法的關注點在于鏈上數據的一致性和網絡的健壯性。目前在區塊鏈領域得到廣泛應用的共識算法主要有工作量證明算法（proof of work，PoW）［1］、權益證明算法（proof of stake，PoS）［8］、委任權益證明算法（delegated proof of work，DPoS）［9］和實用拜占庭容錯算法（practical Byzantine fault tolerance，PBFT）［10］以及基于上述幾種算法的混合算法。

2 相關工作

PBFT算法是當前區塊鏈領域中解決分布式系統下的拜占庭將軍問題的主要算法之一，并且可以實際應用在吞吐量較小的分布式系統中，比如在Hyperledger Fabric 項目中被采用［11］。該算法通過三個階段的節點通信，其中包括兩次全網絡的廣播通信，算法的復雜度為節點規模的指數級，所以隨著網絡中的節點數量的增長，算法的共識效率快速下降，并且通信開銷大幅增長。

針對PBFT 算法的局限性，研究人員試圖通過優化共識流程，提高算法在大規模分布式系統下的表現。一種被普遍接受的思路是將網絡分組，將一個大規模問題轉化成多個并行小規模問題。文獻［12］提出了一種基于Raft集群的改進PBFT算法—RBFT。文獻［13］提出了一種基于距離的改進PBFT 算法—DS_PBFT。文獻［14］提出了一種基于通信時間分組的改進PBFT算法—GBFT。

多數結果表明，針對大規模分布式系統，網絡分組確實能夠減小通信開銷，提高共識效率。但是網絡分組的解決方案隱含了一個問題，即共識階段由于參與共識的節點數量急劇減少所導致的分布式系統的拜占庭容錯能力的大幅下降。拜占庭將軍問題（Byzantine failures），是由Pease 和Leslie Lamport提出的點對點通信網絡中的基本問題［15～16］。特別是在分組結果或分組規則被獲知的情況下，該問題的危害性會被放大，攻擊者能夠以一個更小的代價癱瘓整個分布式系統。

本文測試了基于網絡分組的兩階段PBFT 算法，采用固定網絡分組的方式模擬網絡分組結果被攻擊者獲知的情況。模擬結果表示，在最壞情況下，攻擊者針對性地使其中的兩個節點下線便可以癱瘓共識網絡，而PBFT 算法該網絡規模下應該能夠提供四個拜占庭節點的容錯能力，可以看出分組結果被獲知或是被預測將帶來極大的安全隱患。

為解決上述問題，分組算法應具備抗預測能力，主要通過以下特性實現：

1）隨機性，分組算法中引入隨機數或隨機性算法。

2）不相干性，分組結果相互獨立，多次分組之間互不影響。

3）局部性，只有少部分節點知道全網分組結果，大部分節點只知道局部分組結果。

基于上述思考，本文提出了一種抗預測分組算法，并證明該算法具備上述特性。本文將該分組算法結合前文的兩階段PBFT 改進算法，實現了一種基于抗預測分組的PBFT 改進算法—RS-PBFT 算法。仿真實驗結果表示，該算法在具有比PBFT 算法更高的共識效率和吞吐量的同時極大程度地保留了PBFT算法的拜占庭容錯能力。

3 RS-PBFT算法模型

3.1 抗預測分組算法

基于該算法需要具備局部性的考慮，抗預測分組算法的思路是由主節點進行分組，將剩余節點分為小組主節點和共識節點，主節點告知小組主節點所在小組的共識節點成員，并提供簽名作為證明，然后由小組主節點向共識節點轉發，這樣保證了除了主節點以外的其余節點均只知道局部的分組信息。

抗預測分組算法的流程如圖1。

PBFT 算法中的主節點選取基于透明的規則，即當前視圖編號對節點規模取模得到主節點的序號，這種方式在存在拜占庭節點的網絡環境下會產生安全隱患。抗預測分組算法的主節點選取方法參考Raft算法，通過三種身份、隨機過期時間、獲取選票、心跳維持狀態等機制保證主節點選取具備隨機性和健壯性。

非主節點在收到主節點宣告身份之后，會生成一個分組投票地圖，為每個節點隨機生成一個數字，然后發送給主節點。主節點會維護一個分組投票統計的數據結構用于緩存其他節點發來的分組投票地圖，然后接受其他節點的投票信息，主節點自身不參與投票。主節點在收到超過全網三分之二節點的投票信息之后會根據投票結果得出分組，并告知小組主節點自身小組內的成員組成，小組主節點再轉發給小組內的其他成員。

抗預測分組算法具備隨機性、不相干性和局部性。主節點的選舉基于隨機過期時間，每個節點成為主節點的可能性相同，選舉結果具備隨機性。主節點不參與分組投票，分組投票由全網節點參與，基于多個隨機數地圖加和產生，分組結果具備隨機性。每次分組結果僅依賴于本輪收集到的隨機數地圖，不受其他參數和環境影響，具備不相干性。除了主節點之外的節點僅知道自身分組的情況，沒有其他分組的節點規模和節點身份的信息，具備局部性。進行多次模擬實驗記錄分組情況，得到的結果也滿足隨機性和不相干性。

3.2 RS-PBFT算法

RS-PBFT 算法是將抗預測分組算法與兩階段PBFT 改進算法結合，需要考慮拜占庭網絡中節點可能做出的異常行為，對抗預測分組算法的流程進行修改。

在主節點選舉過程中，拜占庭節點可能私自設置一個極小的喚醒時間，保證自己成為主節點，這樣不僅能夠知道全網的分組結果，更給系統帶來極大的安全隱患。RS-PBFT 算法在主節點選舉階段加入水線，將選舉階段開始之后固定間隔的一個時間作為水線，對于水線時間之前的請求選票行為不作回應。

在主節點選舉過程中，拜占庭節點可能偽造當選信息欺騙其他節點，擾亂正常的選舉過程，形成系統內部“分裂”的結果。RS-PBFT 算法在投票階段加入節點簽名信息，主節點在廣播當選信息時需要帶上獲得的全部選票信息及節點的簽名信息，其他節點只有驗證過該節點的正當選票數量達標才承認其主節點的身份，否則不作回應。

在分組投票過程中，拜占庭節點可能為自己和同謀分配一個極大值，保證自己和同謀成為小組主節點，多個拜占庭節點成為小組主節點會增加共識結果被操縱的可能性。RS-PBFT 算法在接受投票地圖的時候設置一個閾值，對于超過閾值的數做0處理。

在節點通信過程中，拜占庭節點可能利用歷史信息或偽造信息來混亂網絡的正常運作。RS-PBFT 算法在進行關鍵性階段的通信時，會進行報文的摘要和簽名的驗證，并且將通信結果寫入日志。

4 仿真與實驗分析

下面從通信開銷、共識時延、容錯能力三個方面對RS-PBFT 算法進行測試分析，實驗環境為64位Windows10 操作系統，8 核CPU，8GB 運行內存，通過多進程加端口映射的方式模擬P2P節點網絡，測試代碼開發環境為GoLang1.15+Goland2021.2.3。

4.1 通信開銷

假設系統內節點個數為n，PBFT 算法進行單次共識所需要的通信次數為

假設系統內分組數目為G，每個分組內的節點個數為g，RS-PBFT 算法進行單次共識所需要的通信次數為

RS-PBFT 算法進行一次節點分組需要的通信次數為

當n=13，G=3 時，RS-PBFT算法進行單次共識所需的通信次數約為PBFT 算法的35%，進行一次分組所需的通信次數是進行單次共識的56%，綜合來看在通信開銷方面具備很大優勢。并且隨著n增長，RS-PBFT 算法的通信次數的漲幅會比PBFT小。

4.2 共識時延

以PBFT算法為對照，以系統內節點個數n=13為起點，每次增加4 個節點，通過多組實驗進行RS-PBFT 算法的共識時延測試，在此定義共識時延為發送請求到收到回復之間的間隔。測試結果如圖2所示，可以看出RS-PBFT算法的共識效率較PBFT算法有明顯提升。

圖2 RS-PBFT與PBFT共識時延對比折線圖

4.3 容錯能力

此處測試RS-PBFT 算法在面對攻擊者隨機攻擊使節點下線時的抵抗能力，以系統內節點個數n=13，G=3 為網絡參數，使用RS-PBFT 算法進行多輪共識，每輪共識之前隨機使一個節點下線，測試指標為不能夠完成共識的輪次。測試結果如圖3 所示。最后得到平均結果為3.952 輪，而PBFT 算法的結果為5輪，說明RS-PBFT算法較好地保留了PBFT算法的容錯能力。

圖3 RS-PBFT容錯能力測試折線圖

5 結語

區塊鏈共識算法中的PBFT算法由于共識流程中大量的消息廣播表現出通信開銷大、共識效率低下的問題。針對這一問題，研究者普遍認可通過網絡分片的方式提升算法的性能。但分組會帶來拜占庭容錯能力下降的問題，特別是在節點分組結果被預測的情況下，攻擊者能夠以更小的代價使網絡失去共識能力。本文提出具備隨機性、不相關性和局部性的抗預測分組算法，并考慮拜占庭節點行為做出抗拜占庭算法改進，將其與兩階段PBFT 改進算法結合提出RS-PBFT 算法。經過分析和實驗表明，RS-PBFT 算法在解決了通信開銷大和共識效率低下的問題，并且在容錯能力上較好地保留了PBFT算法的性能。