王啟河

（華北電力大學(xué) 控制與計算機工程學(xué)院，河北 保定 071003）

0 引 言

近2008年中本聰提出一種點對點的電子現(xiàn)金系統(tǒng)即比特幣，使得區(qū)塊鏈底層技術(shù)得到了社會廣泛關(guān)注。區(qū)塊鏈具有不可篡改性、去中心化、安全性高等特點。這些特點使得區(qū)塊鏈技術(shù)在各業(yè)界的應(yīng)用得到迅速發(fā)展。共識算法直接影響區(qū)塊鏈的效率，對共識算法的研究是區(qū)塊鏈技術(shù)的研究熱點之一。

區(qū)塊鏈可以根據(jù)去中心化程度分為公有鏈、聯(lián)盟鏈和私有鏈三種類型。公有鏈去中心化程度最高，其特點是用戶量大、節(jié)點數(shù)較多、且節(jié)點出入系統(tǒng)隨意。公有鏈常用的共識算法為PoW。PoW 計算消耗大，為了爭奪主節(jié)點獎勵會產(chǎn)生不必要的消耗，后續(xù)出現(xiàn)了其他的公有鏈共識算法。私有鏈去中心化程度最低，一般的共識算法為Paxos和Raft等，這些算法記賬效率高于公有鏈和聯(lián)盟鏈，但去中心化程度低，一般是用于私人或一個公司內(nèi)部使用。聯(lián)盟鏈的去中心化程度介于公有鏈和私有鏈之間，一般用于組織聯(lián)盟之間，應(yīng)用范圍較廣。聯(lián)盟鏈的共識機制是BFT 和PBFT。BFT 是1982年由Leslie Lamport等人提出，要求算法能夠在有三分之一惡意節(jié)點的情況下完成共識。原文中僅提出了口信消息型和簽名消息型兩種解決方案，注重理論上的可解，算法復(fù)雜度太高，共識效率太低，不具備實用價值。Miguel Castro 和Barbara Liskov對BFT 改進后提出PBFT算法，成功將BFT算法的復(fù)雜度由指數(shù)級降低到多項式級別，使得拜占庭容錯機制得以在實際實現(xiàn)中變得可行。

PBFT 算法使得聯(lián)盟鏈中的拜占庭將軍問題在實際運用中可行，但算法仍存在主節(jié)點選取隨意，網(wǎng)絡(luò)通信開銷較大，公平性較低等問題。本文針對這些問題，提出一種基于信譽值的PBFT 改進算法，對主節(jié)點的選取方式、達成共識的判斷條件進行改進，優(yōu)化了共識過程，減少了通信量，提高了系統(tǒng)公平性。

1 相關(guān)工作

1.1 實用拜占庭容錯算法

實用拜占庭容錯算法（PBFT）能在有3+1 個節(jié)點的系統(tǒng)中，容忍存在個惡意或故障節(jié)點存在的情況下以多項式級別的通信量完成共識，采用密碼學(xué)相關(guān)技術(shù)確保消息傳遞過程無法被篡改和破壞。在PBFT 算法中所有節(jié)點被分為客戶端節(jié)點，主節(jié)點和備份節(jié)點三種類型，其中主節(jié)點和備份節(jié)點統(tǒng)稱為副本節(jié)點。每一個節(jié)點都有一個編號，每一輪共識稱為一個視圖，視圖編號為。每個視圖都要經(jīng)過請求（request），預(yù)準備（pre-prepare），準備（prepare），確認（commit）和響應(yīng)（reply）五個階段。算法執(zhí)行流程如圖1所示。

圖1 PBFT 算法執(zhí)行流程

具體步驟為：

請求階段：由客戶端節(jié)點發(fā)起提案請求給主節(jié)點，主節(jié)點的編號按照=mod||計算得到，為節(jié)點總數(shù)。提案請求格式為＜request，o，t，c＞，request 包含消息內(nèi)容以及的摘要（），表示執(zhí)行的操作，表示時間戳，表示客戶端C 的標識。

預(yù)準備階段：當(dāng)主節(jié)點收到客戶端的請求并驗證成功后，主節(jié)點向除了自己以外的所有其他節(jié)點發(fā)送預(yù)準備信息。預(yù)準備信息格式為＜＜pre-prepare，v，n，d＞，m＞，為節(jié)點給請求分配的編號，為請求消息的摘要。需要備份節(jié)點給＜pre-prepare，v，n，d＞進行簽名。

準備階段：當(dāng)其他節(jié)點收到驗證成功的預(yù)準備信息后，向包括自己在內(nèi)的節(jié)點發(fā)送準備信息，并把預(yù)準備信息寫入日志。準備信息格式為＜prepare，v，n，d，i＞，表示當(dāng)前節(jié)點的編號。且節(jié)點要對＜prepare，v，n，d，i＞進行簽名。

確認階段：當(dāng)節(jié)點收到2+1 條驗證成功的準備信息（包括請求和預(yù)準備信息）后，節(jié)點向所有節(jié)點發(fā)送確認信息。確認信息格式為＜commit，v，n，d，i＞，節(jié)點需要對＜commit，v，n，d，i＞簽名。

響應(yīng)階段：當(dāng)節(jié)點收到2+1 條驗證成功的確認信息后，節(jié)點向客戶端發(fā)送一條響應(yīng)信息。響應(yīng)信息格式為：＜reply，v，t，c，i，r＞，為請求操作結(jié)果。當(dāng)客戶端收到+1 條相同的響應(yīng)信息后表示客戶端的請求達成共識。

1.2 PBFT 算法相關(guān)改進研究

目前對PBFT 的改進方向有兩種：一是減少參加共識的節(jié)點數(shù)量，即每輪只選取一部分節(jié)點進行公示，達到減少通信量的目的；二是優(yōu)化共識過程，通過改進共識過程或增加節(jié)點評判機制，減少不必要的通信，達到增加共識效率的目的。

在減少參加共識的節(jié)點數(shù)量改進方面：文獻[13]提出一種VPBFT 算法。引入投票機制，將節(jié)點分為投票者、管理者、候選人、普通用戶四類，每種節(jié)點有不同權(quán)限，這樣做的本質(zhì)是減少參加共識過程節(jié)點的數(shù)量。文獻[14]提出一種基于網(wǎng)絡(luò)自聚的NAC-PBFT 算法，文獻[15]也提出一種K-PBFT類聚算法，兩種算法核心思想都是將節(jié)點分組，每個分組內(nèi)共識后由骨干節(jié)點再進行公示，在有大量節(jié)點的情況下減少通信量。此種類聚算法本質(zhì)上是分組類聚減少每次共識的節(jié)點數(shù)量。文獻[16]提出一種基于樹形網(wǎng)絡(luò)拓撲圖的共識算法，通過對全網(wǎng)共識任務(wù)進行拆分，減小任務(wù)的整體規(guī)模。以上的四類算法都是通過減少參與共識過程的節(jié)點來達到減少通信量的目的。通過聚類分組或以其他分組結(jié)構(gòu)（如樹形網(wǎng)絡(luò)拓撲）的方式分組進行公示，最后達到全局共識。此類算法適用于節(jié)點數(shù)目較多的情況，若節(jié)點數(shù)太少優(yōu)勢不明顯。

在優(yōu)化共識過程方面：文獻[17]提出一種IPBFT 算法，將節(jié)點分為協(xié)商節(jié)點和執(zhí)行節(jié)點，引入節(jié)點的自證機制，使得在長期共識過程中的共識效率提高，是一種優(yōu)化共識過程的算法。文獻[18]提出一種基于時間權(quán)重的PBFT 算法。算法給每個節(jié)點賦予一個時間權(quán)重，存在時間越長權(quán)重越大，對共識影響越大。對主節(jié)點選取算法根據(jù)權(quán)重選取，優(yōu)化共識流程，提高系統(tǒng)安全性。文獻[19]提出一種E-PBFT 算法，通過優(yōu)化主節(jié)點選舉方式以及優(yōu)化共識流程對算法進行改進，減少算法的通信量。文獻[20]提出一種PBFT 改進算法，通過對交易分類為平等交易和不平等交易，只對錯誤交易進行公示，減少共識次數(shù)來增加區(qū)塊鏈共識的效率且增加了算法的可擴展性。文獻[21]提出一種RB-PBFT 算法，引入信譽模型和節(jié)點的可信度評估，對惡意節(jié)點有懲罰機制。RBPBFT算法通過信譽值排名來決定哪些節(jié)點進入下一輪共識，減少參與共識節(jié)點數(shù)目。以上幾類算法的核心思想都是增加信譽值或者其他方式，對PBFT 算法流程進行改進，達到減少通信量和提高算法公平性的目的。

通過對以上算法的研究，本文提出一種改進的PBFT 算法，算法引入一種更合理的信譽機制，提高算法的公平性。同時，改進算對共識流程進行優(yōu)化，優(yōu)化部分不必要的通信，減少共識所需要的通信量。

2 改進算法

2.1 算法思想概述

PBFT 算法中每一輪共識中所有節(jié)點的影響力都相同，這樣對于誠實節(jié)點來說是不公平的。在實際情況中，故障節(jié)點和作惡節(jié)點對于共識的貢獻是零甚至是在破壞共識，所以共識成功的節(jié)點應(yīng)該在下一輪的共識中更有影響力。本文提出一種PBFT 的改進算法，對每個節(jié)點增加一個信譽值。信譽值會隨著節(jié)點的行為變化，信譽值的大小就是節(jié)點在共識過程中影響力的大小。隨著共識輪次的增加，系統(tǒng)中故障節(jié)點和惡意節(jié)點影響力變小，誠實節(jié)點影響力變大。

2.2 信譽值調(diào)節(jié)機制

節(jié)點的信譽值情況由節(jié)點在本地進行維護。每經(jīng)過一輪共識，各個節(jié)點根據(jù)接收到的數(shù)據(jù)確認情況更新信譽值。誠實節(jié)點信譽值會得到提升，故障節(jié)點和惡意節(jié)點信譽值會不同程度的降低。節(jié)點按照表1分為誠實節(jié)點、故障節(jié)點、惡意節(jié)點三種節(jié)點類型。高信譽值節(jié)點也可能會在某一輪共識中作惡，懲罰方案是信譽值越高，作惡懲罰越大。

表1 節(jié)點分類表

假設(shè)共有個節(jié)點，一輪共識后有個誠實節(jié)點，個故障節(jié)點，個惡意節(jié)點（++=）

故障節(jié)點信譽值更新公式：

其中表示第個故障節(jié)點更新后的值，表示第個故障節(jié)點更新前的值，為故障節(jié)點更新系數(shù)。1≤≤，0 ＜＜1。

故障節(jié)點信譽值降低值總和：

惡意節(jié)點信譽值更新公式：

其中表示第個惡意節(jié)點更新后的值，表示第個惡意節(jié)點更新前的值，為無效響應(yīng)節(jié)點更新系數(shù)。1≤≤，0 ＜＜1。

惡意節(jié)點信譽值降低值總和：

所有非誠實節(jié)點信譽值降低總和為：

誠實節(jié)點信譽值更新公式為：

其中w表示第個有效響應(yīng)節(jié)點更新后的值，w表示第個惡意節(jié)點更新前的值。

2.3 主節(jié)點選取算法

PBFT 算法中主節(jié)點選取方式是客戶端節(jié)點根據(jù)視圖編號計算得出，對節(jié)點本質(zhì)上沒有任何篩選，通過視圖轉(zhuǎn)換協(xié)議解決惡意節(jié)點或故障節(jié)點成為主節(jié)點的問題會影響共識效率。本文主節(jié)點選取算法為：

根據(jù)節(jié)點信譽值序列w篩選出信譽值大于主節(jié)點最低值的所有節(jié)點，節(jié)點編號和信譽值分別存入備選主節(jié)點編號序列c和備選主節(jié)點信譽值序列b中，1≤≤，為備選節(jié)點總數(shù)。

根據(jù)式（7）算出主節(jié)點備選序列的累積和序列，1≤≤+1。

隨機生成一個隨機數(shù)，0 ＜＜s+1。

遍歷序列b，若滿足b＜＜b，則編號為c的節(jié)點成為主節(jié)點。

所有節(jié)點在驗證視圖更換請求時，需要驗證客戶端節(jié)點所請求的主節(jié)點的信譽值是否大于，若大于則可以接受，若小于則拒絕。

2.4 算法流程

PBFT 算法的確認階段是統(tǒng)計系統(tǒng)中大部分（大于等于2+1）節(jié)點已經(jīng)共識成功，但又將結(jié)果廣播于所有節(jié)點，所有節(jié)點又進行一次統(tǒng)計工作才將結(jié)果響應(yīng)給客戶端。兩次廣播導(dǎo)致算法通信復(fù)雜度較高。在改進算法中，節(jié)點對于數(shù)據(jù)的驗證和確認只在第一個廣播階段完成，第二個階段更新節(jié)點信譽值。改進算法的五個階段為：預(yù)提案階段（preproposal）、提案階段（proposal）、數(shù)據(jù)確認階段（data-commit）、信譽值更新階段（reputation-update）、響應(yīng)階段（reply）?；谛抛u值的PBFT 算法消息發(fā)送過程如圖2所示。

圖2 基于信譽值的PBFT 算法消息發(fā)送過程

預(yù)提案階段：客戶端節(jié)點通過主節(jié)點選取算法得到主節(jié)點編號，向主節(jié)點發(fā)送一條提案請求消息。預(yù)提案請求格式為＜pre-proposal，o，t，c，j＞，其中表示請求的操作，表示時間戳，為客戶端C 的標識，為主節(jié)點編號。preproposal 中包含請求消息以及消息摘要（m），且客戶端需要對預(yù)提案請求進行簽名。

提案階段：當(dāng)主節(jié)點收到預(yù)提案請求后，驗證客戶端請求是否合法，檢驗客戶端節(jié)點提供的信譽值序列與節(jié)點本地保存的信譽值序列是否一致以及主節(jié)點的信譽值是否大于。驗證通過后主節(jié)點為提案編一個序號，然后向除了自己以外的其余節(jié)點發(fā)送一條提案信息。提案信息格式為＜＜proposal，n，j，d（m）＞，m＞，且需要對＜proposal，n，j，d＞進行簽名。

數(shù)據(jù)確認階段：當(dāng)副本節(jié)點收到提案信息后（主節(jié)點完成預(yù)提案階段后直接到數(shù)據(jù)確認階段），驗證提案信息的合法性，同時對請求數(shù)據(jù)進行驗證。若通過則先將提案信息內(nèi)容記錄到日志，然后向所有節(jié)點發(fā)送一條數(shù)據(jù)確認信息。數(shù)據(jù)確認信息格式為：＜data-commit，n，j，d（m），i＞，為當(dāng)前節(jié)點編號。且需要對＜data-commit，n，j，d（m），i＞簽名。

信譽值更新階段：當(dāng)副本節(jié)點收到一條數(shù)據(jù)確認信息后，先對信息進行合法性驗證。節(jié)點進入此階段后啟用一個計時器，設(shè)置一個此階段的最大等待時間，在此階段內(nèi)接收到的數(shù)據(jù)確認信息進行下一步分類，此時間段之外的節(jié)點直接認定為故障節(jié)點。計時結(jié)束后，副本節(jié)點需要記錄所接收到數(shù)據(jù)確認信息的來源，完成節(jié)點分類序列。計時結(jié)束后，向主節(jié)點發(fā)送一條信譽情況＜reputation，＜p，i，n，j＞＞，副本節(jié)點需要對＜p，i，n，j＞進行簽名。主節(jié)點需要將各個節(jié)點的信譽消息匯總成信譽消息矩陣PI，PI 由主節(jié)點所接受到的所有信譽情況信息組成。然后向其余節(jié)點發(fā)送一條信譽更新信息＜reputation-update，PI，n，j＞，主節(jié)點需要對此消息簽名。此階段轉(zhuǎn)發(fā)過程如圖3所示。

圖3 信譽消息轉(zhuǎn)播示意圖

其中，分類序列中值為1 表示對應(yīng)節(jié)點為誠實節(jié)點。為表示一般情況，用表示不確定值。

響應(yīng)階段：當(dāng)副本節(jié)點收到信譽更新信息后，先對信息進行合法性驗證，然后根據(jù)信息中的信譽消息矩陣PI 進行計算得到共識結(jié)果以及得到共識過程中各個節(jié)點的分類情況，根據(jù)分類情況按信譽機制對各個節(jié)點信譽值進行更新。此后，副本節(jié)點向客戶端發(fā)送一條響應(yīng)信息＜reply，t，c，i，j，w，r＞，為驗證結(jié)果，為更新后的信譽值序列。當(dāng)客戶端節(jié)點收到相同響應(yīng)信息對應(yīng)節(jié)點信譽值累積和大于+1 時，表示共識完成。

3 算法分析

3.1 一致性分析

算法的一致性主要是需要所有誠實節(jié)點對數(shù)據(jù)共識結(jié)果以及對各節(jié)點的信譽值的更新結(jié)果保持一致，信譽值在共識過程中起到判斷條件的作用，不同信譽值序列可能會出現(xiàn)不同的結(jié)果。本算法是在每一輪共識結(jié)束后，需要保持最終一致性。每一輪算法經(jīng)歷兩次共識。第一次是在數(shù)據(jù)確認階段，完成對數(shù)據(jù)的共識。各節(jié)點并沒有在此時就直接認定此數(shù)據(jù)能通過，而是在進行各節(jié)點的行為統(tǒng)計，為后面的信譽值更新做準備。第二次共識是在信譽值更新階段，完成各節(jié)點信譽值更新的共識。

在信譽值更新階段最后各個節(jié)點會收到來自主節(jié)點發(fā)送來的信譽消息矩陣PI，為了便于說明，假設(shè)系統(tǒng)3f+1 個節(jié)點中節(jié)點編號1 至2+1 的2+1 個節(jié)點為誠實節(jié)點，節(jié)點編號2+2 至3+1 的個節(jié)點可能是故障節(jié)點或惡意節(jié)點。對于一次成功的共識來說，各節(jié)點收到的信譽消息矩陣如表2所示。其中共識結(jié)果中第行第列的值為1 表示編號為的節(jié)點在數(shù)據(jù)確認階段收到節(jié)點的數(shù)據(jù)確認消息，為0 則表示未收到數(shù)據(jù)確認消息，為了表示情況的一般性，用表示不確定，即值為時值可能為0 或1。

表2 信譽消息矩陣

對于誠實節(jié)點來說，在一次成功的共識中該節(jié)點一定能接收到其他誠實節(jié)點的確認信息，所以編號為1 至2+1 的節(jié)點之間的值一定都為1。對于編號為2+2 至3+1 的節(jié)點，其余節(jié)點不確定是否能收到確認信息，且主節(jié)點不一定能收到該節(jié)點的信譽情況消息，所以涉及這些節(jié)點通信的值都為不確定。當(dāng)各節(jié)點收到此消息矩陣時，便可以通過此矩陣得到共識結(jié)果以及對于信譽值的更新結(jié)果。顯然，只要各個節(jié)點所收到的信譽消息矩陣一致，最終各節(jié)點對信譽值的更新結(jié)果和對數(shù)據(jù)的共識結(jié)果都是一致的。

3.2 通信量分析

通信量就是在一輪共識過程中，系統(tǒng)各節(jié)點之間通信次數(shù)之和。本算法中通信量與原PBFT 算法不同的地方主要是在信譽值更新階段。在個節(jié)點的系統(tǒng)中，原PBFT 算法在準備階段和確認階段進行了兩次全體廣播，而改進算法只在數(shù)據(jù)確認階段進行一次全體廣播以及在信譽值更新階段進一次主節(jié)點轉(zhuǎn)播，所以改進算法通信減少量為一次全體廣播的次通信減去一次主節(jié)點轉(zhuǎn)播的2（-1）次通信，即本文算法通信量為（2-2）-（-2（-1））=+-2。

本文改進PBFT 算法的通信復(fù)雜度還是（）量級，但通信量大約減少了一半。原PBFT 算法，文獻[21]提出的RB-PBFT 算法以及本文改進PBFT 算法通信量對比如表3所示。其中RB-PBFT 算法中的為該算法中每次篩選節(jié)點參與共識的節(jié)點的比例。RB-PBFT 算法是通過減少參與共識的節(jié)點數(shù)來減少通信量，與取值有關(guān)。

表3 算法通信量對比

3.3 公平性分析

本文算法與現(xiàn)有的引入信譽機制的RB-PBFT 算法相比，在公平性上也有一定的提升。RB-PBFT 算法是通過給節(jié)點信譽值排名，然后取信譽值排名靠前的一部分參加共識，這樣做雖然避免了一部分惡意節(jié)點的作惡，但這屬于一刀切策略。對于一些節(jié)點，可能只是因為網(wǎng)絡(luò)延遲等原因在某次共識后導(dǎo)致信譽值靠后，結(jié)果被踢出系統(tǒng)。對于一個公平的系統(tǒng)來說，共識過程應(yīng)該是所有節(jié)點都能參與共識，只是信譽值不同的節(jié)點對共識的影響不同，改進算法很好地做到了這一點。

原PBFT、RB-PBFT 算法和本文改進算法公平性對比如表4所示。

表4 各算法公平性對比表

4 結(jié) 論

本文針對PBFT 共識機制通信量高，主節(jié)點選取未篩選以及對各節(jié)點在共識過程中行為缺乏賞罰機制等問題，在PBFT 算法基礎(chǔ)上引入信譽值機制。通過信譽機制的引入，對各節(jié)點在每一輪共識的行為進行評判，逐漸減小故障節(jié)點和惡意節(jié)點對共識結(jié)果的影響，通過對信譽值更新達到對節(jié)點進行賞罰的目的。在選取主節(jié)點時，從信譽值達到條件的節(jié)點中篩選，減少了新的主節(jié)點仍是非誠實節(jié)點的可能性。信譽機制的引入也提高了算法的公平性。此外，改進算法還對共識流程進行了優(yōu)化，在保證一致性和安全性的同時降低了每輪共識的通信量。改進算法與原PBFT 算法相比，會產(chǎn)生更多關(guān)于維護節(jié)點信譽值時所產(chǎn)生的計算上和內(nèi)存空間上的消耗，如何減少這些消耗是接下來的進一步研究方向。