基于通信時間分組的PBFT算法改進*

陳忠賢 李秦偉，2 羅婧雯

（1.貴州大學計算機科學與技術學院 貴陽 550025）（2.貴州省公共大數據重點實驗室 貴陽 550025）

1 引言

共識問題是計算機科學領域的經典問題，最早出現是在20個世紀80年代，Pease和Leslie Lamport對拜占庭將軍問題進行了形式化的描述和分析［1～2］。自中本聰提出比特幣以來［3］，共識成為了區塊鏈系統中其中一個新的研究熱點［4～5］，目前，區塊鏈中主流的共識算法包括有工作量證明（PoW）［6］、股 權 證 明（PoS）［7～8］、委 任 權 益 證 明（DPoS）［9］、實用拜占庭容錯算法（PBFT）［10］。工作量證明的思想最早來源于哈佛大學教授Cynthia Dwok［11］，其目的是為了通過郵件發送方計算一定難度的數學難題來增加垃圾郵件發送者的成本，從而解決垃圾郵件問題。在比特幣系統中，PoW主要應用在數字貨幣系統中，旨在通過算力證明來獲得一個區塊的記賬權，從而換取獲得比特獎勵的機會，這造成了為提高哈希計算而不斷優化的挖礦設備的浪費和大量的電力資源的消耗。PoS彌補了PoW的不足，使用股權機制來代替算力證明完成記賬節點的選取。目前，有Peercoin、NTX、Blackcoin使用了基于PoS思想的共識算法，但PoS也存在這樣一些問題：某些節點擁有大量的區塊鏈資產且長期持有，這就可能造成股份分配不均，從而造成擁有大部分股權的節點壟斷出塊。2014年，雷恩（Larry Ren）提出PosV共識算法［12］，Slimcoin提出了PoB共識算法［13］。PosV與PoB算法既解決了PoW的能源消耗問題又規避了PoS的風險問題。DPoS對PoS中心化進行了適當妥協［6］，有效解決了PoW的純碎依靠算力以及PoS的首富賬戶的寡頭壟斷問題。但是DPoS對于惡意拜占庭節點的處理存在諸多困難。PBFT算法能容忍1/3的拜占庭節點，在性能上有著較好的表現，但三階段的大量消息廣播侵占有限帶寬從而影響執行的效率。中國區塊鏈社區NEO提出了一種改進的拜占庭容錯算法DBFT［14］，該算法是一個PBFT與PoS算法的有機結合，首先根據節點的權益來選出一些記賬人，然后記賬人之間通過PBFT算法來達成共識。

上述常用的共識算法中，PoW和PoS是目前公有鏈［15］普遍采用的算法，PoW與PoS可拓展性良好，因為新加入的節點只要能提供算力證明或權益證明即可，但是兩者的吞吐量以及交易速度等眾多性能瓶頸使得很多應用場景被限制。不論是PoW、PoS、DPoS亦或是其衍生算法，它們的共識機制都是依賴于代幣的，但國家法律法規不支持使用代幣。相比之下，PBFT實用拜占庭容錯算法更適合作為服務平臺來搭建區塊鏈應用。

1.1 相關工作

PBFT算法主要解決了缺少可信的中央節點和可信任的通道的情況下，分布在網絡中的各個節點如何達成共識的問題。PBFT是由Miguel Castro和Barbara Liskov在1999年的OSD199會議上提出來的，它改進了拜占庭算法效率不高的問題，將算法復雜度由指數級降低到多項式級，使得拜占庭容錯算法在實際系統應用中變得可行［6］。PBFT算法容錯模型為3f+1，即當存在f個錯誤節點時，總節點數n≥3f+1時，拜占庭將軍問題可以被解決，其容錯性為33%。但PBFT也存在這樣的問題：要實現節點之間的協商狀態一致，需要經過三階段（預準備階段、準備階段、確認階段）的節點間通信，其中有兩次全網全節點廣播，大量的消息廣播非常占用通信資源。其次，從PBFT算法流程可知，傳統的PBFT算法針對的是靜態網絡結構。該算法中節點數目的增多可以增強系統的容錯性，但PBFT算法不能夠動態的感知節點的加入或者退出，那么就無法根據拜占庭節點數量和總結點數量進行動態變化，這無疑是浪費了新加入節點的資源。

1.2 改進方案

針對上一節提出的PBFT算法的不足，并根據文獻［16］，提出基于時間分組的GBFT算法，該算法主要從以下幾個方面進行了優化。

1）根據節點之間的通信時間分組分層進行共識。

GBFT算法的實現通過分組、選舉、以及分層進行共識。基于最短通信時間，將區塊鏈所有副本節點進行分組，每個組都有一個組長節點。首先各個組分別在組內進行三階段的共識，組內共識依然嚴格遵循3f+1的原則，當組內各個節點收到的來自同一組不同節點的消息數為2f+1，即可進入下一階段。在組內共識完成后，各組組長節點根據收到的消息執行全局共識，全局共識的執行過程和組內共識基本一致，最終由率先收到滿足共識條件的組長節點更新區塊鏈。

GBFT算法的改進主要是通過減少節點之間的消息數來進行改進，組內共識與全局共識依然遵循3f+1的容錯模型，在效率提升的同時，也保證了安全性。

2）動態感知節點的加入和離開，資源利用最大化。

通過節點探測可以實時根據在線節點數目，調整分組的組數和組員數量。為每個節點設立的評分表可以動態刪除共識表現差的節點。

2 GBFT算法的設計與實現

2.1 算法定義

1）GBFT算法分為組內共識與全局組長節點之間的共識，令組Gj中最大能容忍惡意節點的數量為f1，令全局組長節點中最大能容忍惡意節點的數量為f2，wj表示組Gj的組員個數，G表示所有組長節點的數目，則有：

2）根據視圖編號v、當前區塊高度h以及參與共識的節點總數n，可計算出主節點P，即：

2.2 分組

2.2.1 最優分組

只考慮平均時延的情況下，使用共識過程中的交互消息數計算出最優分組。

主節點發起提案ConsensusProposal發送消息數：

組內準備GroupedPrepare與組內確認Grouped-Commit發送消息數：

wj表示組Gj的組員個數，G為組數。

全局共識GlobalPrepare與GlobalCommit階段共發送消息數：

由式（4）、（5）、（6）相加整理得到：

s為方差，由式（7）可看出，當s=0時，即平均分組時，MGBFT可以得到最小值。所以得到：

式（8）兩邊同時對G求導得到：

由式（9）可知，當n與G滿足=0時，MGBFT最小，即所發送的消息數最少。

2.2.2 節點探測階段

假設在整個區塊鏈網絡最初啟動時，全網節點都處于孤立節點狀態。首先給區塊鏈網絡內所有在線的參與共識的副本節點編號，用｛1，2，3…n｝表示各個副本節點的ID，參與共識算法的記賬代表節點從ID號最小的節點開始，向比自己ID號大的節點發送探測消息＜DET ECT，status，self，t1＞，sel f包含節點自身信息，包括IP地址等信息，st at us字段有兩個不同的狀態，1表示請求計算通信時間的信息，2表示對請求信息的響應。t1為發送消息時區塊鏈網絡上的時間。其余共識節點在收到來自Ri的探測消息后，以區塊鏈網絡時間為標準，記錄收到消息的時間t2，計算Ri與Rj之間的通信時間Tij=t2-t1，之后回復消息給相應的共識節點Ri，消 息 格 式 為＜D ET ECT-REP LY，status，self，Tij，t1＞，此時status置為2，表示對收到的消息進行回復。同樣的Ri也會根據來自Rj的探測回復消息計算出Ti'j=t2-t1，Ri根據自己計算出的與來自Ri計算的Tij計算Ri與Rj平均通信時間=(Ti'j+Tij)/2，并將計算出來的記錄在由共識節點組成的鄰接表中。

等待節點Ri完成自己的鄰接表后，向Ri之前的i-1個節點以及下一個節點Ri+1發送消息＜C OM M U N IC AT IO N-T IM E，sel f，sch ed ule＞，schedule表示由Ri更新后的通信時間鄰接表，前i-1個已經完成節點探測的節點根據后續節點發送的消息，更新各自的鄰接表，下一個節點Ri+1除了保存由上一個節點Ri發送的鄰接表，還要向比自己ID號小的節點發送探測消息，也就是重復Ri節點的操作，直到節點Rn-1完成探測并將更新后的鄰接表廣播，則區塊鏈網絡內已經建立一個由各個節點組成的通信時間表。

算法中，為每個節點設置評分，初始評分設置為0分。

2.2.3 平均時延估計

各個共識節點Ri根據鄰接表的值，計算出平均通信時延。平均時延的估計，是為了在后續分組中，將分散的節點分為多個通信時間基本一致的組。根據計算出的平均時延，各個節點分別統計在平均時延以內的節點編號數量di、節點編號Ri和通信時間，并根據通信時間升序。

2.2.4 分組形成階段

根據公式計算出的主節點P在給定的共識時間間隔Δtc，發起一輪新的共識。由主節點啟動快速分組協議，按照以下五個步驟進行分組。

步驟1：根據全網共識節點的數目計算出最優分組的組數G和最佳組員人數W，G和W的值由上一節介紹的最優分組中式（6）決定。

步驟2：凡是滿足di≥W的節點為擬組長節點（擬組長節點是尚未組建成功的節點，若成功組建則成為組長節點），各個擬組長節點開始根據鄰接表選取組員，將選取的節點添加到分組向量表chosen中，向選擇的組員節點發送消息＜Q UI C KG R OU P，sel f，fl ag，ID＞σi，self包含節點自身信息，包括IP地址，節點編號等，fla g置1表示組長節點。選取組員滿足以下幾個規則。

規則1：di最小的擬組長節點Ri為第一組G1的組長節點首先選取組員，若多個節點的di相同，則由ID號最小的節點優先分組。

規則2：Ri將通信時間在以內的前W-1個的節點選為組員，被選取的節點不再參與下一輪的選取。

規則3：若共識節點Ri的鄰接表里在平均通訊時延以內的節點不足W-1個，則依次順延至下一個擬組長節點。

規則4：若根據規則3遍歷整個擬組長節點，仍不能組建組員通信時間在以內且人數為W的組，則Ri根據鄰接表選取通信時間為前W-1個節點作為組員。

步驟3：組員節點收到QUICK-GROUP后，解密驗證，看到組長節點發送的消息fla g的值為1，表示組長節點在選舉組員，立即根據self的值作出回復，向組長節點回復消息＜GROUPRE P L Y，self，flag，ID＞σi，fl ag置0表示為非組長節點。

分組的最終結果是形成以組長節點為中心的多個圓簇，每個組長節點負責維護組內成員。

圖2 分組形成過程

2.2.5 重新分組

每次共識的發起都有一定的時間間隔，共識的時間間隔根據區塊鏈網絡內的交易數據來決定，但并不是每次共識都會發起一次分組協議。重新分組主要考慮以下幾個方面。

1）拜占庭節點增多

每個組設立一個拜占庭區，通過組內共識，組內每個節點都可以知道哪些節點為拜占庭節點，將拜占庭節點添加至拜占庭區，當某一組的拜占庭區的節點數目多于f1，則認為這個組宕機，這個組的所有節點不再參與到組內共識與全局共識當中，組內非拜占庭節點向區塊鏈網絡內其他節點廣播宕機消息＜DOWN-ME S S AG E，sel f＞σi，其余節點根據監測到的消息將宕機的整個組的組員添加至拜占庭區，當拜占庭區的組數大于f2時，則需重新進行分組。

如果某一個組Gj的組長節點為拜占庭節點，而Gj組的拜占庭區的節點數目少于f1，Gj組仍可以繼續參與共識，此時由除拜占庭節點外評分最高的節點擔任組長節點，若分數相同，則取ID號最小的節點擔任，并向其余組長節點廣播變更消息＜GROUP-C HA N G E，self，chosen＞σi，這里chosen僅為Gj組的組員向量表。

2）節點的加入

當有新的節點加入共識，新加入節點需要向全網發送探測消息，在收到新節點的探測消息后向新節點發送通信時間鄰接表sch edule，新加入節點根據節點探測階段所描述的方法計算平均通信時延以及更新鄰接表schedule，并將新的鄰接表廣播至全網。每次當有新的節點加入，則由主節點發起新一輪的快速分組協議。

2.3 共識

我們定義主節點作為一次共識的發起者，如同比特幣網絡中，通過調節難度控制出塊時間為10min，我們可以根據區塊鏈網絡的交易數量，調控主節點發起一次共識的時間間隔。在整個區塊鏈網絡中，所有的共識節點都有可能是最終的記賬節點，所以不僅參與共識也要保存區塊鏈數據。當收到交易數據，所有共識節點驗證交易合法性，將通過驗證的交易數據添加至自己的內存中并根據前一區塊的哈希索引、版本號、區塊高度等信息構造一個候選區塊，并廣播至其他共識節點，不合法則直接丟棄，這確保了只有有效的交易才能在區塊鏈網絡中傳播。

1）主節點P向所有副本節點發起共識提案，消息格式為＜C O NSE N S US-P RO P OSA L，v，n，h，d，self＞σi，b l ock，t1＞，v為當前視圖編號，n為在當前視圖編號下主節點分配的序列號，h為當前區塊的高度，block為請求的區塊信息，d為block的摘要，t1為時間戳，目的是為了計算通信時延，不斷更新鄰接表。

其余的副本節點收到來自P的共識提案后，驗證簽名、檢查提案、h的值、n的值是否在水線范圍內。若為真，則進入組內共識階段。若發現提案為假或在超過共識間隔時間后仍未發起共識提案，備份節點懷疑主節點失效，則進行視圖變更。詳細的變更細節在文章的后續做出介紹。

5）與全局準備階段一致，組長節點間互發確認消 息＜GL OB A L-C O M MIT，v，n，h，d，self，t1＞σi，當組長節點中的任意一個在收到來自2f2+1個其他組長的相同確認消息后，即認為共識達成，可以發布來自主節點提案的區塊block。

6）其余節點根據最新的區塊，將自己內存中的與區塊block中相同的交易刪除，同時開始構造新的區塊，準備下一輪的共識。

算法中，產生區塊的節點評分score加1分，若主節點被副本節點懷疑，引發視圖變更，若變更成功，則主節點score減2分，該備份節點score加1分。

整個算法的共識過成如圖3所示。

圖3 GBFT算法流程

2.3.1 鄰接表更新

鄰接表建立之后并不是一成不變的，除了節點的加入和退出需要變更鄰接表外，組內共識和全局共識動態更新部分的鄰接表的通信時間。

組內共識以及全局共識的消息都包含時間戳，根據節點探測一節介紹的通信時間的計算方法，每次收到共識階段內的消息后自動計算傳播時間并記錄，待一輪共識完成后，將所有收集到的消息的通信時間累加并取平均值，將計算出的值填入鄰接表的對應位置。

2.3.2 組長節點的輪換

我們為每個共識節點都設置了評分score，在GBFT算法中，根據評分建立一個忠誠度表1。

表1 忠誠度計算方法

每個節點計算出各自的忠誠度c：

c的計算是綜合了score與擔任組長次數t的結果，平衡每個節點成為組長節點的幾率，避免分數高的節點長期擔任組長。α與β為調節系數。c的值最高的成為下一輪次的組長節點。

2.3.3 視圖變更

當備份節點懷疑主節點或者在共識間隔時間Δtc后仍未發起新的共識，則由懷疑主節點的備份節點或隨機選取的備份節點發起視圖變更消息，具體的變更流程如下。

1）令新的視圖vnew=vold+1，假設由備份節點Ri向全網發送視圖變更消息＜V IEW-C H A N GE，vold，vnew，h，Ri＞σi。

2）其余備份節點收到視圖變更消息后，驗證消息的簽名、vold以及h的值是否為真，若為真，則拒絕主節點的共識提案并向全網廣播視圖變更確認 消 息＜V IE W-CH A N GE-C ON FIR M，vold，vnew，h＞σi。

3）任何一個節點如果收到來自其他（2n-1）/3條圖變更確認消息后，視圖變更得到確認，新的視圖編號變為vnew。新的主節點開始下一輪的共識提案。

3 實驗模擬與分析

3.1 實驗設計

本算法的基礎是分布式系統，即需要在多個節點下運行，為模擬出大量的分布式節點的計算，有如下設計。

1）共識節點：以進程來模擬共識節點，共識節點的端口號分布在10001～20000之間，共識節點是整個系統的關鍵，負責交易和區塊的共識確認。

2）交易產生節點：以進程來模擬交易節點，一個進程一個交易節點，每個進程擁有不同的的端口號，端口號分布在20001～30000之間，交易節點主要負責交易數據的模擬，以最快的速度生產交易信息并發送給共識節點。

3）由于共識節點是在同一局域網下一臺或多臺電腦上進行模擬，為了更好地驗證算法的有效性，用隨機函數事先生成一個n×n的對稱矩陣模擬通信延遲時間。

4）整個區塊鏈系統采用Python語言編寫，搭建了Linux操作系統環境，用腳本語言開啟多個進程。本實驗以PBFT算法作為對照，分別對99個、216個、336個、420個、512個節點進行改進共識算法GBFT的時間測試。實驗中，各個進程依次開啟，開始執行GBFT算法。針對不同數量的共識節點，我們各測試10次，取10次的平均值來作為最后的結果。

3.2 運行效率分析

GBFT設計的目的就是為了提高區塊鏈系統運行的效率。以PBFT算法作為對照，分別對99個、130個、176個、216個、273個、350個節點進行PBFT算法、GBFT算法的時間測試。測試結果如圖4所示。

圖4 不同節點數PBFT與GBFT共識時間折線圖

從圖4知隨著共識體系中節點數量不斷的增加，GBFT的效率提升越明顯。

3.3 吞吐量

區塊鏈應用中對于吞吐量的定義是：

其中，Δt為交易發出到區塊確認的時間，即出塊時間，transacti on為Δt時間段內打包進區塊的交易數。

實驗對PBFT算法以及GBFT算法，統計1000條交易所花費的共識時間，根據式（11），計算出吞吐量，如圖5是PBFT算法與GBFT算法的吞吐量折線圖。

圖5 PBFT與GBFT吞吐量折線圖

從吞吐量折線圖可知，PBFT算法與GBFT算法的吞吐量與參與共識的節點數成反比，節點越多，吞吐量越低。但在相同節點數量的情況下GBFT算法的吞吐量是遠高于PBFT算法的。

3.4 安全性分析

1）主節點的選取根據視圖編號和區塊高度計算所得，而組長節點的選取根據最小ID號，兩者的選取都具有隨機性和公平性。

2）由主節點P發起的快速分組并不是說全網的副本節點全部由主節點安排分組，而是根據節點探測階段所統計的通信時間以及隨機ID號進行分組，這個組要獲得最大利益就會根據鄰接表選擇通信時間最短的成為組員，這樣不僅可以防止主節點成為拜占庭節點后安排最差的分組，而且可以提高節點間的通信時間。

3）GBFT共識算法的實質是將PBFT算法分解為組內共識與全局共識兩個階段，共識協議和試圖更換的核心并沒有改變，依然嚴格遵循3f+1的模型。

4）每個組設立拜占庭區，且每個節點都獨立監聽其余節點的狀態，根據最大容仍失效節點的數目動態調整算法，當拜占庭節點數大于f個，則觸發重新分組協議。

5）信用評分協議與組長更換協議使得各個節點成為組長節點的機會均等，滿足區塊鏈去中心以及節點間對等的特性。

4 結語

針對區塊鏈共識算法中的實用拜占庭容錯算法表現出的由于大量的消息廣播造成的通信資源浪費和效率低下問題，提出基于通信時間分組分層算法。在分組形成前，采用節點探測獲知共識節點的“地理位置”——構建一個通信時間對稱矩陣，根據通信時間對稱矩陣將節點分成多個以組長節點為中心，平均通信時延為半徑的圓。在組保持階段，根據節點的行為進行信用評分與組長更換，使得所有節點成為組長節點的概率盡可能均等。整個共識算法可以通過節點探測動態感知新加入節點，拜占庭區的設立感知失效節點，從而確定是自適應調整共識還是調整分組結構。仿真表明，本文算法很好地解決了PBFT算大的通信資源消耗和效率低下問題。