基于平均穩(wěn)定度的自適應PBFT算法改進

張世政，劉 勇

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

0 引言

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

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

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

1 相關工作

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

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

2 AS-PBFT算法

2.1 AS-PBFT算法概述

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

圖1 AS-PBFT算法整體結構

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

2.2 基于歷史表現(xiàn)評估機制

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

表1 穩(wěn)定系數(shù)調(diào)整

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

2.3 自適應共識比例控制

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

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

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

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

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

2.4 優(yōu)化一致性協(xié)議

2.4.1 優(yōu)化視圖切換策略

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

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

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

2.4.2 惡意節(jié)點篩選策略

為維護系統(tǒng)的共識狀態(tài)表，向評估機制提供穩(wěn)定系數(shù)調(diào)整的參考依據(jù)，故在改進后的一致性交互協(xié)議中，對有惡意行為的節(jié)點進行篩選和記錄。

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

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

（3）共識請求端節(jié)點驗證共識成功以后，將收到的惡意節(jié)點集合進行取并集處理，得到本輪篩選出的惡意節(jié)點集合，將其發(fā)送給主節(jié)點，由主節(jié)點根據(jù)該集合對所有節(jié)點穩(wěn)定系數(shù)進行調(diào)整。

3 實驗及結果分析

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

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

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

圖2 平均穩(wěn)定度和共識節(jié)點數(shù)量變化

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

圖3 不同數(shù)量作惡節(jié)點下平均穩(wěn)定度變化情況

3.2 共識時延

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

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

3.3 通信開銷

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

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

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

3.4 自適應分析

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

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

圖6 分數(shù)選擇機制和平均穩(wěn)定度選擇機制共識時延對比

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

圖7 固定比例機制和平均穩(wěn)定度機制共識失敗次數(shù)對比

4 結語

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

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