基于平均穩定度的自適應PBFT算法改進

張世政，劉 勇

（網絡體系構建與融合北京市重點實驗室，北京郵電大學信息與通信工程學院，北京 100876）

0 引言

“中本聰”提出的比特幣，成為區塊鏈技術的第一個成功應用的案例，自此，區塊鏈技術開始進入大眾的視野，被人們所熟知。區塊鏈技術是一種特殊的分布式數據庫，它結合了去中心化、信息加密、共識算法等多種技術，具有去中心化、不可篡改、可溯源等特征。按照應用情況，可將其分為公有鏈、聯盟鏈和私有鏈三種。目前，區塊鏈技術已得到極大發展，其應用場景越發廣泛，在諸多領域影響深遠，其在新技術變革中的重要性日漸顯著。

共識算法作為區塊鏈的核心技術之一，影響著其安全性和整體性能。目前應用較為廣泛的共識算法包括工作量證明機制（proof of work，POW）、權益證明機制（proof of stake，POS）、授權權益證明機制（delegated proof of stake， DPOS）和 實 用 拜 占 庭 容 錯 機 制（practical byzantine fault tolerance，PBFT）等，在實際應用中，由于聯盟鏈和私有鏈中的節點只有經過授權才能夠加入到網絡當中，因此具有更高的安全性和實用性，PBFT 共識算法由于能夠有效地解決網絡中的拜占庭將軍問題，保證了網絡可靠性和穩定性，已成為聯盟鏈和私有鏈中應用最廣泛的共識算法之一。 但PBFT 算法的劣勢也極為明顯，在PBFT 共識的過程中，隨著網絡中節點規模的擴大，共識的時延以及通信復雜度急劇上升，從而導致共識效率較低，并且消耗大量的信道資源。PBFT算法缺少節點評估機制，不能靈活地對網絡中的節點進行區分。另外，其輪流當選的視圖切換策略也會影響系統的安全性和共識效率。

對于PBFT 算法的改進工作已有多種方案，但始終缺乏考慮網絡整體情況、自適應的優化措施。為了解決目前PBFT 算法存在的諸多問題，本文旨在設計一種具有一定自適應性的優化算法，結合網絡所有節點的整體情況，從節點評估、自適應共識節點選擇等方面進行創新與改進，提升PBFT算法性能。

1 相關工作

針對PBFT 存在的效率低，時延高的問題，已有多位學者提出了改進措施。例如，文獻［15］提出的基于投票的拜占庭容錯算法，將網絡中的節點劃分為客戶端、從節點和主節點三種不同的職責類型，由主節點進行投票和評分來改變每個節點的類型。文獻［16］提出一種基于特征信任模型的優化實用拜占庭容錯共識算法，它是一種多階段共識算法，通過節點之間的交易來評估節點信任，從而選擇網絡中質量較高的節點來構建共識群。文獻［17］提出基于可靠性評估的改進拜占庭容錯算法，根據評分將節點劃分為誠實、故障、惡意三種狀態，并根據節點可靠性選擇主節點組建共識節點群。上述改進措施均采用依據分數來選擇共識節點的機制，具有一定的優化效果，但在面對惡意節點數量較少甚至沒有惡意節點的系統中，參與共識的節點數量過多，優化效果有限。文獻［18］針對PBFT 算法的改進，根據評分將節點劃分為共識節點、候選節點和預備節點，并規定共識節點數量固定為總節點數量的2 3。但當惡意節點較多時，共識節點集群數量保持不變，共識失敗的概率較高，甚至面臨連續共識失敗的風險。

以上方法都不能根據具體的共識場景自適應地選擇和調整最佳的共識節點集群，針對這種現象，結合聯盟鏈的實際特點，本文提出一種基于平均穩定度的自適應改進PBFT算 法（average stability byzantine fault tolerant algorithm，AS-PBFT），引入平均穩定度的概念，依據平均穩定度控制參與共識的節點，優化PBFT 算法，以此來降低共識時延和通信復雜度，并且能夠一定程度地反映系統的共識情況，及時調整共識節點所占的比例，針對不同的惡意節點情況，選擇最佳的共識節點集群方案，避免連續共識失敗等安全性問題。

2 AS-PBFT算法

2.1 AS-PBFT算法概述

聯盟鏈是由多個組織或機構參與的區塊鏈，通常情況下，每個節點都有與之對應的實際機構或組織，故在實際的應用場景中，節點產生作惡行為的概率是不同的，會有一部分穩定性強的節點，也會存在相對穩定性較差的節點。基于這種實際情況，本文提出了一種改進方案，其整體結構如圖1所示。

圖1 AS-PBFT算法整體結構

基于聯盟鏈的實際特點，本文提出的算法主要分為基于歷史表現評估機制、自適應共識比例控制機制和優化的一致性交互協議三部分。首先對所有節點增設穩定系數，共識開始后，由主節點按照基于歷史表現的穩定性評估機制，計算所有節點當前的穩定系數，此系數可以反應當前節點的穩定性。此后，本文引入整體穩定度的概念，通過自適應共識比例控制模塊，計算當前系統的整體穩定度，根據計算結果，調整共識比例。共識集群確定以后，采用優化的一致性協議進行共識節點之間的信息交互，確定共識結果，標記作惡節點，完成共識。在存在惡意節點的區塊鏈系統中，通過上述機制，便可根據網絡中惡意節點的實際情況，進行評估優化，提高共識效率。

2.2 基于歷史表現評估機制

為了解決PBFT 算法無法對節點進行評估的問題，提出了基于歷史表現的穩定性評估機制。首先為所有節點增設穩定系數，在系統開始共識前，將每個節點的穩定系數初始化為50，并規定其下限為0，上限為100。增設共識狀態表，此表格記錄系統中每個節點近三次共識的狀態，節點共識狀態包括穩定、出錯和沒有參加共識三種，分別用0、1、2 表示，每一輪共識結束后，都將更新該表以及時反應節點的最新狀態，對節點穩定系數的調整如表1所示。

表1 穩定系數調整

系統根據共識狀態表來判斷每個節點的歷史狀態，并將前三輪按照2∶1∶1 的比例進行權值分配，按照穩定系數的調整規則，計算對應三次的系數調整結果并進行累加，成為節點新的系數調整值。通過這種穩定系數調整機制，可以反映出節點的歷史狀態，從而對一個節點的穩定系數做出綜合評估，削弱隨機性帶來的影響，更容易區分出惡化概率較高的節點，提升算法的穩定性和安全性。并且給沒有參與共識的節點進行緩慢的加分，保證共識節點集群的動態性。

2.3 自適應共識比例控制

針對PBFT 算法隨著節點數量的增多，共識時延上升明顯的問題，提出自適應共識比例控制機制，動態調整參與共識的節點所占的比例。基于評估機制中設置的穩定系數，本文引入平均穩定度的概念，即網絡中所有節點的平均穩定系數，計算方法如公式（1）所示，其中，A為第輪共識的平均穩定度，S代表節點第輪的穩定系數，ΔS代表節點第輪穩定系數的調整，代表總節點數。

由公式（1）計算每輪共識的平均穩定度，并且規定50 ≤A≤100，基于得到的當前整體的平均穩定度，采用公式（2）計算下一輪參與共識的節點數目，其中為計算所得的共識節點數量。

根據公式（2）可以得出，當平均穩定度為初始狀態的50 時，全部節點都將參與共識，平均穩定度到達上限100時，計算得到的共識節點所占比例為2 3，并且按照規定，數量下限應該大于總節點數量的2 3，從而通過判斷進行適當調整。由此可以得出結論，在網絡中作惡節點較少，或者沒有作惡節點時，共識節點的數目經過幾輪調整以后，將會趨于總節點的2 3，并且在確定共識節點之前，先會將節點按照穩定系數進行降序排列，從而使得選取的節點都是穩定系數高的。

在本文提出的優化方案中，由于減少了共識節點的數量，故在惡意節點較多的情況下存在共識失敗的可能性，控制機制在面對共識失敗的情況下，會將所有節點的穩定系數減20，則平均穩定度A下降20，進而通過公式（2）計算得到的下一輪共識節點的數量就會增加，對共識失敗的消息進行重新共識，降低共識失敗的概率。此后，再通過評估機制進行慢恢復，避免連續失敗的情況發生。

通過本文提出的共識節點選擇機制，能夠保證絕大多數情況下，參與共識的節點是穩定性強的節點，穩定性較差的節點則會逐漸剔除出共識集群。因此，在惡意節點數量較少的情況下，共識失敗的概率很低，共識節點數量趨于總節點數量的2 3，而在惡意節點數量較多的情況下，也能自適應地對共識節點集群進行控制，避免連續共識失敗。因此，本文中的共識比例控制機制可以針對不同情況進行自適應的動態調整，以得到最優的共識節點群，提高共識效率。

2.4 優化一致性協議

2.4.1 優化視圖切換策略

對于傳統的PBFT 算法的一致性交互協議，在進行視圖切換時是按照公式（3）進行新的主節點選擇的。

其中代表新選擇的主節點的編號，代表上一次主節點的編號，為總的節點數量。可以看出，傳統的一致性協議的視圖切換是一種輪流當選的方式，對于存在惡意節點的系統中，這種選舉方式是極其隨意的，并且也會面臨著多個惡意節點連續當選為新的主節點的風險。

針對這個問題，結合本算法提出的基于歷史表現的節點評估機制，對一致性協議的視圖切換策略進行改進，在共識過程中需要進行視圖切換的時候，將每個節點的穩定系數作為主要參考指標，將節點的歷史表現考慮進來，按照穩定系數降序的順序，進行新的主節點的選擇。利用這種視圖切換策略，可以有效地降低惡意節點當選為主節點的概率，減少視圖切換的頻率與次數，進一步提高算法的共識效率。

2.4.2 惡意節點篩選策略

為維護系統的共識狀態表，向評估機制提供穩定系數調整的參考依據，故在改進后的一致性交互協議中，對有惡意行為的節點進行篩選和記錄。

（1）本文為每個節點增設共識集群表，記錄當前共識過程中，參與共識的節點的編號集合。該表在每輪共識開始之前，由主節點根據基于歷史表現的評估機制和共識比例控制機制進行更新和調整，主節點在Pre-prepare 階段將該表添加至Pre-prepare 消息中，分發給每個節點，節點根據共識集群表確定后續的消息廣播和接收的節點范圍。

（2）在全廣播消息交互階段，每個節點需要收到2+1 條一致消息才能認為投票通過，進而在投票過程中，記錄收到的不一致消息的來源節點編號，在回復階段，將該消息一起發送給共識信息的請求端。

（3）共識請求端節點驗證共識成功以后，將收到的惡意節點集合進行取并集處理，得到本輪篩選出的惡意節點集合，將其發送給主節點，由主節點根據該集合對所有節點穩定系數進行調整。

3 實驗及結果分析

本文基于Java 語言構建一個多節點區塊鏈系統，分別對PBFT 算法和本文提出的AS-PBFT算法進行實現和驗證，記錄分析AS-PBFT 算法在共識過程中的變化情況，從共識時延和通信量方面與PBFT 算法進行比較，并且對本算法的自適應性進行實驗驗證分析。

3.1 AS-PBFT算法共識過程分析

本文提出了基于平均穩定度來控制共識節點比例的優化思想，為貼近聯盟鏈中節點的實際場景，設定系統中節點作惡的概率不同，選擇1 3 的節點設置其作惡概率為80%，再取1 3的節點規定其作惡概率為50%，另外的節點作惡概率為10%，并且每一輪惡意節點的總數不變。因此，在惡意節點數量較少的情況下，共識失敗的概率很低。選定總節點數為16，作惡節點數為4，其前十次共識過程中，系統的平均穩定度和共識節點數的變化如圖2所示。

圖2 平均穩定度和共識節點數量變化

根據圖2可知，第一輪平均穩定度為初始值50，所有節點都參與共識，隨著共識過程的進行，基于歷史表現的評估機制對所有節點的穩定系數進行評估，平均穩定度逐步上升，進而參與共識的節點數量呈下降趨勢，最終數量穩定在11 個節點。另外，惡意節點數量不同，對平均穩定度增長速率會產生影響，如圖3 所示，在惡意節點數量較少的情況下，其數量越少，平均穩定度上升越快，共識節點數量達到下限的時間就越短。

圖3 不同數量作惡節點下平均穩定度變化情況

3.2 共識時延

共識時延為算法開始進行一輪共識到共識結束所消耗的時間，反應了共識算法的效率。本文分別對PBFT算法和AS-PBFT算法的共識時延進行評估，在惡意節點為(- 1) 3 的情況下，對不同節點數分別進行多次實驗，計算其進行十輪共識以后單次共識消耗時間的平均值，對比結果如圖4 所示。隨著共識節點數量的增加，兩種算法的共識時延都呈上升趨勢，但相較于PBFT 算法，本算法參與共識的節點數量趨于總節點數量的2 3，并且發生視圖切換的概率小很多，因此，在不同節點數量的情況下，共識時延均明顯減小。

圖4 PBFT和AS-PBFT算法共識時延對比

3.3 通信開銷

通信開銷是指完成單次共識所需要通信的次數，分別對PBFT和AS-PBFT算法，在惡意節點為(- 1) 3 的情況下進行多次實驗比較，計算其第十輪共識以后的單次通信量的平均值。兩種算法的通信開銷如圖5所示。

圖5 PBFT和AS-PBFT算法通信開銷對比

本文對視圖切換時主節點的選擇策略做了優化，將視圖切換的概率大大降低，減少了因視圖切換造成的通信開銷。并且，根據共識比例控制機制，減少了參與共識的節點數量，故其單次共識的通信量明顯降低。

3.4 自適應分析

本文提出的AS-PBFT 算法，能夠根據作惡節點的數量和共識情況進行自適應調整，故設置兩組不同作惡節點數量的實驗，進行對比分析。

（1）將系統中的惡意節點數量設置為0，模擬沒有節點作惡的情況，與常見改進方法中所采用的分數選擇機制來選擇共識節點的方式進行多次實驗對比，記錄其平均共識時延。在沒有節點作惡的情況下，最終所有節點的穩定系數都將達到上限100，若采用分數選擇機制選擇節點，全部節點都將符合要求參與共識，與傳統的PBFT 算法類似，AS-PBFT 算法會根據公式（2），將共識節點的數量維持在總節點數量的2 3 左右。如圖6 所示，本文提出的基于平均穩定度選擇機制的共識時延更低，更加適用于沒有作惡節點的情況。

圖6 分數選擇機制和平均穩定度選擇機制共識時延對比

（2）設置系統中惡意節點的數量為(- 1) 3，因減少了參與共識的節點數量，故當惡意節點數量較多時，便有可能產生接收到的一致性投票數量達不到2f+1 的情況，從而導致無法成功完成共識，此時就需要重新對該信息進行操作。在這種情況下，將基于平均穩定度選擇機制和常用的改進方案中采用的固定前2 3 比例節點作為共識節點的機制進行對比，對其分別進行100 輪共識， 并進行多次實驗，求得失敗次數的平均值，如圖7 所示。因ASPBFT 算法采用基于平均穩定度的控制機制，逐步降低其共識節點比例，并且一旦出現共識失敗的現象，會立刻降低系統的平均穩定度，增加共識節點數量，以降低失敗概率，故其失敗次數明顯小于采用固定前2 3節點作為共識節點的方式，并且避免了連續共識失敗的可能，增強了系統的安全性。因此AS-PBFT 共識算法具有更強的自適應性。

圖7 固定比例機制和平均穩定度機制共識失敗次數對比

4 結語

本文提出AS-PBFT 共識算法，采用根據系統整體穩定度來動態調整共識節點比例的思想，來增強共識過程的動態性和自適應性，并且依據基于歷史表現的評估機制和優化的一致性協議來解決PBFT 算法存在的諸多問題，提高共識效率、降低通信開銷的同時，也能根據惡意節點的實際情況動態選擇最優的共識節點集群。

AS-PBFT 算法提出基于平均穩定度控制的思想，具有一定的自適應性，但在惡意節點較多的情況下，其共識效率仍有待提高，在后續工作中，將針對該情況進行優化，在保證共識失敗率的情況下，進一步提升共識效率。