任璽羽，童向榮*，張偉

（1.煙臺大學 計算機與控制工程學院，山東 煙臺 264005；2.山東外國語職業(yè)技術(shù)大學 二級學院，山東 日照 276826）

0 引言

區(qū)塊鏈系統(tǒng)［1］是多中心、防篡改、公開透明、安全可靠、用于存儲交易信息的分布式數(shù)據(jù)庫系統(tǒng)，由系統(tǒng)中所有的節(jié)點共同進行維護。數(shù)據(jù)的存儲通過哈希函數(shù)加密的鏈式區(qū)塊結(jié)構(gòu)［2］，數(shù)據(jù)的產(chǎn)生和更新通過區(qū)塊鏈系統(tǒng)中節(jié)點間的共識過程。區(qū)塊鏈中的數(shù)據(jù)存儲在每一個節(jié)點上，即使有部分節(jié)點發(fā)生故障，可以利用區(qū)塊鏈系統(tǒng)網(wǎng)絡層中的Gossip協(xié)議［3］進行數(shù)據(jù)同步和恢復。

共識算法是區(qū)塊鏈系統(tǒng)中的核心技術(shù)，利用它可以解決分布式系統(tǒng)的一致性問題。起初，分布式計算機領域的共識問題是由Lamp?ort［4］提出在一組可能存在故障節(jié)點，并通過點對點消息通信的獨立處理器網(wǎng)絡中，保證非故障節(jié)點能夠針對特定值達成共識。2008年末，隨著比特幣的提出，拜占庭容錯共識算法逐漸獲得實際的應用，拜占庭將軍問題是區(qū)塊鏈技術(shù)核心思想的根源，對區(qū)塊鏈共識系統(tǒng)的實現(xiàn)有重要影響。

目前，已經(jīng)提出了工作量證明共識（Proof of Work，PoW）［5］、權(quán) 益 證 明（Proof of Stake，PoS）［6］、授權(quán)股份證明（Delegated Proof of Stake，DPoS）［7］、PBFT［8］等共識算法。Saputra等［9-10］提出基于Hashcash的PoW共識算法，系統(tǒng)中的所有節(jié)點為了生成區(qū)塊的資格，必須找到能滿足系統(tǒng)要求的隨機數(shù)，這將大大浪費哈希功率。PoS算法［11］要求每個節(jié)點都根據(jù)自己的利害關(guān)系來尋找隨機數(shù)。為進一步提高共識效率，Bitshares等［12］提出了DPoS 共識算法，此算法是讓所有節(jié)點參與選舉，共同選出一組證人節(jié)點，生成新的區(qū)塊。PoW、PoS和DPoS共識算法，雖然可以容忍拜占庭節(jié)點，但是在生成區(qū)塊的過程中可能會導致分叉。相比之下，對于聯(lián)盟區(qū)塊鏈來說，PBFT共識算法是更理想的共識算法，它能夠保證系統(tǒng)中不會產(chǎn)生分叉行為，還可以容忍一定數(shù)量的拜占庭節(jié)點。

PBFT共識算法有效解決了原拜占庭容錯算法［13］共識效率不高的問題，能夠接受小于1/3的拜占庭節(jié)點。但其通信復雜度會隨著網(wǎng)絡中節(jié)點數(shù)量增加而增加，通信復雜度達到O（N2），系統(tǒng)的擴展性也不夠好。文獻［14］提出了基于PBFT的可伸縮多層共識算法，將節(jié)點分為多層，降低單層PBFT共識的通信量，解決了原PBFT共識算法的可擴展性不足的問題，但忽略了對主節(jié)點的信任度評價。文獻［15］提出了EPBFT共識算法，該算法可以根據(jù)系統(tǒng)所處的網(wǎng)絡環(huán)境采取不同的步驟來達成共識，此算法采用了VRF來選舉共識節(jié)點，能夠適用于動態(tài)的網(wǎng)絡環(huán)境。但在EPBFT中，共識過程接收客戶端請求消息的主節(jié)點可能是拜占庭節(jié)點，造成系統(tǒng)的通信開銷較大。

針對以上問題，為了選取更可靠的主節(jié)點，根據(jù)節(jié)點的交互歷史，選取信任評估值較高且一直穩(wěn)定的節(jié)點，優(yōu)先作為共識過程的主節(jié)點，提高系統(tǒng)的可靠性。為了解決系統(tǒng)中通信量過大的問題，對系統(tǒng)中的節(jié)點進行分層和分組共識，以主節(jié)點為初始中心，以距離為標準進行聚類分組，因此組內(nèi)節(jié)點數(shù)量較少。原PBFT共識算法通過節(jié)點全網(wǎng)廣播來達成一致，將會大幅度消耗系統(tǒng)中的通信資源。改進后進行組內(nèi)廣播，降低了通信量，保證總體通信量遠低于原PBFT共識算法。

本文的主要貢獻如下：

（1） 為了使共識算法能夠應用到大規(guī)模的網(wǎng)絡系統(tǒng)中，引入了雙層PBFT系統(tǒng)模型，利用聚類方法將系統(tǒng)中的節(jié)點進行分層分組，減少通信復雜度，提高系統(tǒng)的靈活性；

（2） 在小組共識前，改進了主節(jié)點的選取。利用節(jié)點信任評估模型，依據(jù)節(jié)點在系統(tǒng)中的歷史行為進行評估，選取信任值最高的節(jié)點作為共識小組的主節(jié)點，提高系統(tǒng)的效率和可靠性；

（3） 通過分析，改進算法的通信復雜度小于原PBFT算法的通信復雜度O（N2）。通過實驗驗證，該改進的算法優(yōu)于基線算法。

1 相關(guān)工作

近年來，隨著區(qū)塊鏈的快速發(fā)展，根據(jù)去中心化的程度可以把區(qū)塊鏈分為公有鏈、聯(lián)盟鏈和私有鏈［16］。這三種區(qū)塊鏈都有各自的共識算法，公有鏈共識可以分為PoW共識、PoS共識、基于PoW共識和PoS共識的改進，例如POA共識［17］、POSV共識［18］等。聯(lián)盟鏈共識總體可以分為兩類：拜占庭容錯共識和非拜占庭容錯共識，非拜占庭容錯共識又稱作故障容錯類共識，指的是在系統(tǒng)發(fā)生宕機問題時，能夠保障系統(tǒng)的可靠性，但當出現(xiàn)不誠實的節(jié)點時，無法保證區(qū)塊鏈系統(tǒng)的可靠性，例如PAXOS 共識［19］、RAFT 共識［20］；拜占庭容錯共識是指節(jié)點對廣播的信息進行偽造并惡意響應，但系統(tǒng)中能夠允許存在一定數(shù)量的不誠實節(jié)點，例如PBFT共識。私有鏈和其他兩種鏈不同，只用于組織內(nèi)部，大部分采用PBFT、RAFT等共識。

聯(lián)盟鏈可以用于多個組織或機構(gòu)之間的合作，有利于信息共享，比較符合當下的發(fā)展趨勢。對于聯(lián)盟區(qū)塊鏈來說，PBFT共識算法是更加理想的共識算法，容忍一定數(shù)量的拜占庭節(jié)點，它通過核心三階段的共識過程可以保證網(wǎng)絡中節(jié)點的一致性，通過超時檢測和視圖變更協(xié)議保證了系統(tǒng)的活性，通過節(jié)點交互過程簽名消息確保了系統(tǒng)的安全性。但原始PBFT共識算法也存在一定的缺陷，比如不適用節(jié)點數(shù)量較大的網(wǎng)絡、無法識別系統(tǒng)中的拜占庭節(jié)點等。在共識過程中，只要收到超過一定數(shù)量的回復消息就認為是達成共識等。由于區(qū)塊鏈技術(shù)的快速發(fā)展，眾多學者也針對PBFT算法出現(xiàn)的問題進行了研究，為推進此算法的廣泛應用做出了貢獻。

對PBFT共識算法的改進主要是在改進共識結(jié)構(gòu)和解決通信復雜度過高兩方面。在改進共識結(jié)構(gòu)方面，文獻［21］通過改進C4.5提高節(jié)點分類的準確度，引入積分機制，有效緩解了在節(jié)點數(shù)量規(guī)模較大的情況，原PBFT共識算法共識效率低下的問題。文獻［22］提出了一種可以任意擴展的分布式模型，把PBFT共識算法和P2P信任計算模型相結(jié)合，能夠提高系統(tǒng)的容錯率和可信度。

在解決通信復雜度方面，文獻［23］對具有PBFT共識的Hyperledger fabric v0.6的性能進行了評估，此共識算法能夠為系統(tǒng)貢獻較大的吞吐量，但隨著節(jié)點數(shù)量的增加，系統(tǒng)的性能會有下降趨勢。文獻［24］提出了積分機制來解決通信復雜度過高的問題，通過節(jié)點積分來選取共識節(jié)點，來降低通信開銷。文獻［25］提出了G-PBFT，利用固定物聯(lián)網(wǎng)設備的地理信息達成共識，減少了驗證和記錄交易的開銷。本節(jié)將簡要介紹已有的相關(guān)工作。

1.1 拜占庭將軍問題

目前，大多數(shù)專家學者所研究的共識問題主要包括兩種，算法共識和決策共識。這兩種共識問題最初來源于拜占庭將軍問題，區(qū)塊鏈系統(tǒng)共識的基礎也是拜占庭將軍問題。

拜占庭將軍問題是指在拜占庭帝國里的將軍率領他們各自的軍隊對敵方的城池進行圍攻，由于軍隊相隔較遠，每個將軍只能控制自己的軍隊，要想商榷一個合理的作戰(zhàn)計劃并達成共識，只能通過信使傳送消息給其他的將軍。但將軍中可能存在叛徒，他們在傳遞消息的過程中，試圖傳播錯誤的行動計劃，來欺騙其他忠誠的將軍。拜占庭將軍問題即找到一個可行的算法，當存在少數(shù)叛徒的情況下，忠誠的將軍們?nèi)阅軌蜻_成共識。

1.2 PBFT共識算法

PBFT共識算法能夠應用于異步網(wǎng)絡［26］環(huán)境，是在聯(lián)盟鏈中采用最多的共識算法，該算法允許存在拜占庭節(jié)點，但不能識別拜占庭節(jié)點，只要系統(tǒng)收到超過一半的回復消息即達成共識。

PBFT共識算法是一種基于狀態(tài)即復制的容錯算法［27］，它可以提供不超過（n-1）/3故障的容錯保證。為了保護分布式系統(tǒng)免受惡意用戶的攻擊［28］，共識過程中節(jié)點的角色劃分有三種，包括客戶端、主節(jié)點和副本節(jié)點。PBFT共識算法核心是由一致性協(xié)議、檢查點協(xié)議和視圖變更協(xié)議組成。網(wǎng)絡系統(tǒng)在正常運行的情況下，只執(zhí)行一致性協(xié)議和檢查點協(xié)議。當主節(jié)點出錯或者系統(tǒng)運行緩慢的情況下，會進行視圖更換協(xié)議，以維持系統(tǒng)能夠繼續(xù)響應客戶端的請求。

1.2.1 一致性協(xié)議

一致性協(xié)議將系統(tǒng)中的共識節(jié)點劃分為主節(jié)點和副本節(jié)點。主節(jié)點對客戶端發(fā)出的請求進行排序；副本節(jié)點按照主節(jié)點提供的順序執(zhí)行請求。所有的節(jié)點都在相同的配置下工作，這個配置信息稱為視圖（view），每更換一次主節(jié)點，視圖就會隨之變化。

1.2.2 檢查點協(xié)議

檢查點協(xié)議用于從日志中安全地丟棄消息，并幫助落后的節(jié)點同步最新的狀態(tài)。在一致性協(xié)議中，系統(tǒng)每執(zhí)行一個請求，節(jié)點都需要記錄日志。如果日志不能及時清理，就會導致系統(tǒng)資源被大量日志所占用，影響系統(tǒng)的性能，即可用性。另一方面，由于拜占庭節(jié)點的存在，一致性協(xié)議并不能保證每一個節(jié)點都執(zhí)行了相同的請求，不同節(jié)點狀態(tài)可能不一致。因此，設置周期性的檢查點協(xié)議，可以將系統(tǒng)中的節(jié)點同步到某一個相同狀態(tài)。

1.2.3 視圖變更協(xié)議

主節(jié)點對客戶端發(fā)出的請求消息不進行響應或主節(jié)點向所有共識節(jié)點廣播不一致的預準備消息時，視圖變更協(xié)議（view change）可以幫助系統(tǒng)繼續(xù)正常工作。視圖變更協(xié)議一共包含viewchange、view-change-ack和new-view三個階段。

系統(tǒng)正常運行的情況下，客戶端將請求消息發(fā)送給主節(jié)點，然后，由主節(jié)點將請求消息廣播給其他副本節(jié)點，進行一個視圖view。但當接收請求消息的主節(jié)點出錯或者不響應消息時，此時就會進行視圖更換操作，采用輪換法選擇主節(jié)點，視圖編號為view+1，進入下一個共識過程。

1.3 PBFT共識算法共識過程

在主節(jié)點沒有故障的情況下，PBFT共識算法一次完整的共識過程需要經(jīng)歷請求（re?quest）、預準備（pre-prepare）、準備（prepare）、確認（commit）和回復（reply）五個階段［29］，其中預準備階段、準備階段、提交階段是共識過程中的核心三階段。

請求階段：客戶端發(fā)送請求消息給主節(jié)點，附帶時間戳等信息。時間戳可以保證該請求不會重復執(zhí)行。根據(jù)時間戳t，能夠辨別操作的執(zhí)行順序。

預準備階段：主節(jié)點響應客戶端發(fā)出的請求，驗證通過，給該請求消息分配編號，然后，把預準備消息廣播給其他的副本節(jié)點。

準備階段：節(jié)點接收到來自主節(jié)點的預準備消息進行驗證其有效性，如果驗證通過，則向其他節(jié)點廣播準備消息。

確認階段：當節(jié)點接收到至少2f（f為拜占庭節(jié)點的數(shù)量）個準備消息，驗證通過后，向全網(wǎng)廣播確認消息。副本節(jié)點將確認消息發(fā)送給其余副本節(jié)點。當系統(tǒng)中節(jié)點接收到2f+1個有效的確認消息后，就可以向客戶端發(fā)送回復消息。

回復階段：副本節(jié)點執(zhí)行完上述操作，副本節(jié)點向客戶端發(fā)送回復消息，當客戶端接收到2f+1個獨立的返回結(jié)果，就認為達成共識。

2 問題描述與基本定義

本節(jié)對改進的PBFT共識算法做了描述，介紹了節(jié)點信任度評估模型中的相關(guān)定義。

2.1 問題描述

為了解決節(jié)點數(shù)量規(guī)模較大的問題，并選取可信的節(jié)點作為主節(jié)點參與共識過程，提出了基于信任評估模型的雙層PBFT系統(tǒng)，如圖1所示。第一層有一個主節(jié)點和q個副本節(jié)點組成了一個共識小組，第二層一共有Z個節(jié)點。經(jīng)過對節(jié)點的信任評估，選取信任值最高的節(jié)點作為共識小組中的主節(jié)點，避免故意不響應消息或響應錯誤消息的節(jié)點作為主節(jié)點，可以提高系統(tǒng)的安全性和可靠性。經(jīng)過信任評估選出可信的主節(jié)點作為初始化的聚類中心節(jié)點。

2.2 節(jié)點的信任度評估

為了選出信任度值高的節(jié)點作為主節(jié)點，對節(jié)點的信任度進行評估，以此提高系統(tǒng)的安全性和可靠性。系統(tǒng)中不同的節(jié)點有不同行為，某些節(jié)點積極主動參與共識過程，能夠及時對系統(tǒng)的消息做出應答；亦存在一些惡意節(jié)點，不對系統(tǒng)發(fā)出的消息做出應答或響應錯誤消息。對節(jié)點進行評估主要分為兩方面，一是對節(jié)點的靜態(tài)評價，通過對節(jié)點在系統(tǒng)中發(fā)生的歷史共識行為和共識參與程度進行評價，二對節(jié)點的動態(tài)評價，通過共識過程中節(jié)點之間的交互行為進行評價。

定義1 節(jié)點信任度。節(jié)點i的信任度評估模型為

其中，Trusti表示節(jié)點i當前的信任度值。信任度值由對節(jié)點i的靜態(tài)評價和對節(jié)點i的動態(tài)評價兩部分共同組成。TSi是節(jié)點i的歷史共識行為和參與度來對其進行評價，即節(jié)點i的靜態(tài)評價。TDti是節(jié)點i和其他節(jié)點之間的交互行為進行評價，即節(jié)點i的動態(tài)評價。α和β分別是靜態(tài)評價和動態(tài)評價所對應的權(quán)重。

定義2 節(jié)點i的靜態(tài)信任度值。根據(jù)節(jié)點在共識過程中的歷史行為來進行計算，可以表示為

其中，Bi是節(jié)點i在共識過程中的歷史行為因子，Pi是節(jié)點i在共識過程中的歷史參與程度因子，γ和θ是各自所對應的權(quán)重。

定義3 歷史行為因子。節(jié)點i的歷史行為對其信任值的影響程度。節(jié)點i歷史行為因子，可以表示為

其中，Ris表示為節(jié)點i在曾經(jīng)的共識過程中表現(xiàn)出誠實行為的次數(shù)。Rif表示為節(jié)點i在共識過程中有惡意行為的次數(shù)。φ和?是對應的權(quán)重，φ+?=1。Ri表示節(jié)點i曾參加共識過程的次數(shù)，Ri=Ris+Rif。由此公式可以看出，節(jié)點做出誠實行為的次數(shù)越多，對增加節(jié)點信任度值的影響越大。

定義4 節(jié)點參與程度。評價節(jié)點是否積極參與共識，表示為

其中，R表示為節(jié)點參與過共識過程的總次數(shù)。Ri表示節(jié)點i參與過共識過程的次數(shù)。

定義5 節(jié)點i的動態(tài)評價。節(jié)點之間相互進行評價。節(jié)點i的動態(tài)評價可以表示為

其中，節(jié)點i和節(jié)點j是兩個不同的節(jié)點（i≠j），N表示系統(tǒng)中節(jié)點的總數(shù)，t表示客戶端發(fā)出請求消息的請求周期，l表示在周期t內(nèi)的共識次數(shù)，m是第m次共識，是在第m次共識中，節(jié)點j和節(jié)點i進行交互后，對節(jié)點i的評分。f(m)表示為時間衰減因子，可以表示為

其中，f(m)的值大小代表共識次數(shù)與當前的共識輪次的遠近，與當前共識輪次距離越遠，時間衰減較大，對節(jié)點的動態(tài)評價影響越小。

基于節(jié)點信任評估模型，根據(jù)節(jié)點以往的行為對其進行信任度評估，并更新節(jié)點的信任度。選取信任度值高的節(jié)點作為共識過程的主節(jié)點，保證共識順利進行，使網(wǎng)絡環(huán)境的可靠性得到提升。

3 改進的PBFT共識算法

通過上述對原始PBFT共識算法共識過程的描述，可以看出系統(tǒng)對網(wǎng)絡節(jié)點之間的通信要求較多，導致通信復雜度較大。在準備階段和確認階段，需要進行兩次全網(wǎng)通信，才能保證達成共識，通信的復雜度為O（N2）。在節(jié)點數(shù)量較少的網(wǎng)絡中，原始PBFT算法在延遲、資源需求等方面尚能體現(xiàn)較好的性能，但當系統(tǒng)中節(jié)點規(guī)模較大，其通信的復雜度是系統(tǒng)不能承受的。因此，對原算法進行改進，使其能應用到較大規(guī)模的網(wǎng)絡系統(tǒng)中，提高系統(tǒng)安全性。假設所研究的區(qū)塊鏈網(wǎng)絡中節(jié)點數(shù)個數(shù)為N（N≥4，N∈N+）。

基于無線網(wǎng)絡定位技術(shù)，可以獲取對象的空間位置信息，并將其投影到二維空間中，獲得節(jié)點的無線網(wǎng)絡坐標（Wireless Network Coor?dinates，WNC），節(jié)點 i的坐標表示為（xi，yi），節(jié)點 i，j之間的距離表示為 d（i，j）：

通過改進的K-means算法對網(wǎng)絡中的節(jié)點進行聚類，并采用信任度評估模型選取信任度較高的前n位節(jié)點來作為初始的中心節(jié)點，然后形成n個共識小組，經(jīng)過信任度評估，選取可靠的節(jié)點作為各共識小組的主節(jié)點，如圖2所示。

4 共識協(xié)議

針對基于信任評估模型的雙層PBFT系統(tǒng)，提出一個新的共識協(xié)議，其中第一層的副本節(jié)點表示為，上標1表示的是層號，下標i表示副本節(jié)點索引。通過對節(jié)點歷史行為進行信任度評估選取的可靠的主節(jié)點，作為相應的第二層副本（）節(jié)點的主節(jié)點，一個主節(jié)點和它相應的副本節(jié)點一起，形成一個共識組，共同組成樹狀的拓撲結(jié)構(gòu)，并假設第一層節(jié)點能夠順利達成共識。

當每個共識小組達成共識，組內(nèi)節(jié)點會給此小組的主節(jié)點發(fā)送消息，而不是對客戶端進行回復。對應的主節(jié)點收集回復消息，并代表共識小組將其發(fā)送給客戶端，如圖3所示。當網(wǎng)絡結(jié)構(gòu)發(fā)生改變的時候，進行更新操作。

4.1 客戶端

客戶端c開始發(fā)送一個請求消息R=給主節(jié)點。其中，o表示操作，t是時間戳，時間戳按照時間順序排列，越往后時間戳的值越大。請求消息被送到副本節(jié)點，副本節(jié)點的標識從先前回復的視圖號中提取。在接收請求時，主節(jié)點廣播消息使用下面所述的協(xié)議。

所有共識小組的主節(jié)點直接向客戶端發(fā)送回復消息。其中，v是當前視圖號，i是副本節(jié)點，r是執(zhí)行結(jié)果，rc是相關(guān)證書，GP描述副本節(jié)點的分配情況。

假設第一層有q個副本節(jié)點，第二層有Z-n個副本節(jié)點，在共識組中錯誤副本節(jié)點的數(shù)量是fw（區(qū)別于f）。如果主節(jié)點收到了來自同一共識組的有效回復fw+1，則該共識組就達成了共識。當超過一半的共識小組給出相同的應答時，就認為達成共識。客戶端只接受來自共識組主節(jié)點的結(jié)果，要保證至少有一半是一致的。

4.2 第一層共識協(xié)議

第一層的共識過程，如圖4所示。首先，客戶端c向主節(jié)點發(fā)送請求消息R=，并對該請求和客戶端的身份進行驗證。驗證通過，主節(jié)點將序列號α賦給R，然后向其他節(jié)點廣播預準備消息進入預準備階段。當其他副本節(jié)點接收到預準備消息，如果同意主節(jié)點分配給該請求的序列號，進入準備階段。其中d為R的摘要（上標是為了區(qū)分第一層的pre-prepare1預準備和第二層的pre-prepare2預準備）。

第一層中的副本節(jié)點接受來自主節(jié)點的pre-preparel消息，然后副本節(jié)點廣播準備消息<，Voteti>，其中 Voteti是節(jié)點i在區(qū)塊中投出的贊成票，Votefi表示反對票。收到的預準備消息和準備消息將寫入消息日志。在同一時刻，可能會有多個節(jié)點在進行這個過程，節(jié)點有可能接收到其他節(jié)點發(fā)送的prepare消息，當前節(jié)點會驗證這些消息和自己發(fā)出的prepare消息的d，α，v，Voteti是否一致。在一定時間范圍內(nèi)，某節(jié)點收到2f+1（超過2f）個其他節(jié)點的prepare消息，表示prepare階段已經(jīng)完成。

對于準備好的副本節(jié)點，它們會廣播確認消息<< commitl，d，α，i，v>，voteSeti>，如果當前節(jié)點（包括主節(jié)點）收到2f+1來自其他共識節(jié)點的commitl消息，同時將該消息寫入本地消息日志中，驗證通過，表示共識達成。其中，voteSeti表示節(jié)點i的投票集合。

副本節(jié)點會將回復消息發(fā)送給它們小組的組長，即第一層的主節(jié)點。副本節(jié)點暫停執(zhí)行，并在第二層啟動另一輪協(xié)議。主節(jié)點通過檢查超過一半的組成員回復一致的reply1消息（包括它自己）來確認這個組成員已經(jīng)達成一致。每個共識小組的組長收集reply1并形成一個回復證書rcl（reply-certificate）。

共識過程完成后，主節(jié)點用對客戶端進行回復。

4.3 識別拜占庭節(jié)點

在共識過程中，設置了投票機制。如果系統(tǒng)在t1之前沒有達成共識，每個共識節(jié)點會在區(qū)塊上廣播自己的投票，然后廣播收到的投票集合。假設，節(jié)點i是共識過程中的一個拜占庭節(jié)點，當它發(fā)送一個<，voteti>消息發(fā)送給共識節(jié)點j，但一個<，votefi>消息發(fā)送給共識節(jié)點k。然后在共識節(jié)點j和k發(fā)送的 commit1消息中，可以看到 Voteti∈VoteSetj而Votefi∈VoteSetk，所以每個共識節(jié)點可以通過比較它從其他共識節(jié)點接收到的commit1消息來識別拜占庭節(jié)點。

4.4 第二層協(xié)議

信任度值較高的節(jié)點被選為主節(jié)點，主節(jié)點會把新的預準備消息廣播給副本節(jié)點，實現(xiàn)了另一輪PBFT協(xié)議。當再次提交請求時，所有的共識小組成員以4.2節(jié)中類似的方式回復主節(jié)點。主節(jié)點在同一共識組中廣播一個類似于給副本節(jié)點，其中 ccl是 commit-certificate1、v、α 和 R 來自前一個進程。如果滿足第一層協(xié)議中所述條件，共識小組中的副本節(jié)點將會接受該請求。

在收到有效的pre-prepare2消息時，共識小組中收到預準備消息的副本節(jié)點，會廣播消息給同一共識組中的所有其他副本節(jié)點。在prepare2階段，每個副本節(jié)點收集2fw消息，其中包含匹配的序列號α、視圖v和請求R。與接收到的pre-prepare2消息一起，它形成一個定額準備證書certificate2，表示此副本節(jié)點已準備好請求。

準備好的副本節(jié)點和共識小組的主節(jié)點廣播并收集具有相同視圖、序列和摘要的commit2消息。這些commit2形成commit-certificate2。然后副本節(jié)點執(zhí)行已提交的消息。執(zhí)行后，所有小組成員向其組長（小組的主節(jié)點）回復結(jié)果，組長以第一層中類似的方式向客戶端回復結(jié)果。

4.5 共識小組間共識

共識小組中的主節(jié)點代表第二層中所有節(jié)點進行小組間的共識，共識過程有準備階段、確認階段兩個階段。

共識小組的主節(jié)點向其他共識小組的主節(jié)點發(fā)送準備消息。當其接收到2f個準備消息，并驗證通過就會進入確認階段。各個共識小組的主節(jié)點向其他共識小組的主節(jié)點發(fā)送確認消息。當各個共識小組的主節(jié)點都收到了至少2f+1個正確的確認消息，表示共識小組之間達成共識。

5 PBFT和T-PBFT通信次數(shù)分析

在原PBFT共識算法中，準備階段和確認階段都需要進行全網(wǎng)廣播通信，在這個過程中每個節(jié)點需要通信N?1次，完成一輪共識所需要的通信次數(shù)為2N（N?1），當節(jié)點數(shù)量很大，將給通信網(wǎng)絡帶來較大的負擔。

設系統(tǒng)中參與共識過程的節(jié)點個數(shù)為N，第二層共有Z個節(jié)點。第一層節(jié)點個數(shù)為N?Z（N?Z≥4），Z較大時，可忽略不計。因此，將重點對第二層中通信次數(shù)進行分析。二層中總節(jié)點數(shù)為Z（N≈Z），把Z個節(jié)點分為n個共識小組，假設每個小組內(nèi)節(jié)點數(shù)量為，共識算法所需的通信次數(shù)具體分析如下，如表1所示。

6 實驗分析

為了評估改進共識算法的性能，基于Java編程語言對T-PBFT和PBFT的共識流程進行了仿真模擬。實驗環(huán)境為Intel Xeon Gold 6148 CPU@ 2.40 GHz 2.39 GHz（2個處理器）和16 GB內(nèi)存操作系統(tǒng)為64位Win10。實驗結(jié)果用Matlab對數(shù)據(jù)進行了處理。實驗分別測試了總節(jié)點N為40、50、60、70、80、90兩種共識算法的耗時和吞吐量。為了減少實驗誤差，實驗重復進行了10次最終取平均值。本節(jié)從通信開銷、共識過程的耗時和吞吐量三方面對兩種算法進行對比。

6.1 通信開銷分析

PBFT和T-PBFT兩種共識算法的通信次數(shù)比值C，n為共識小組的數(shù)量，如圖5所示。PBFT共識算法是通過節(jié)點進行全網(wǎng)廣播，進行信息的傳遞，將會大幅度消耗系統(tǒng)中通信資源。通信開銷作為算法效率的指標之一，通過對兩種算法對比，驗證改進算法可以提高共識效率，減少通信資源的浪費。

經(jīng)過分析可得，節(jié)點總數(shù)為N，沒有對節(jié)點進行分組時，兩種算法的通信次數(shù)是相同的。當節(jié)點總數(shù)不變，共識小組數(shù)量增加，每個共識小組內(nèi)的節(jié)點數(shù)量減少，T-PBFT共識算法能夠在小范圍內(nèi)達成共識，與原PBFT共識算法相比可以有效地減少系統(tǒng)中的通信次數(shù)。當分組數(shù)量達到最大，共識小組數(shù)量增多，同時要進行組內(nèi)和小組之間的共識，會導致通信次數(shù)增多。當共識小組達到和節(jié)點總數(shù)一致時，與原PBFT共識算法通信次數(shù)將會再次達到一致。但從整體來說，T-PBFT共識算法所需的通信次數(shù)要小于原PBFT共識算法。

6.2 共識過程耗時分析

共識過程的耗時是指從共識過程開始到共識過程完全結(jié)束所需要的時間。為了對比兩種共識算法的共識耗時，進行了10次的獨立對比實驗，對改進的共識算法和原始的PBFT共識算法單次共識的耗時進行了記錄，如圖6所示。

從圖中可以看出，通過10次重復實驗計算出PBFT單次共識的平均耗時為591.6 ms，改進共識算法單次共識的耗時為447.2 ms。通過實驗可以看出，改進的共識算法的單次共識耗時比原始的PBFT共識算法提升了25%。

6.3 吞吐量分析

吞吐量是指在該系統(tǒng)中單位時間內(nèi)處理交易的數(shù)量，系統(tǒng)處理交易的能力高低取決于吞吐量的大小，吞吐量越大說明處理交易的的能力越高，反之亦然。吞吐量計算公式如下：

其中，transactionsΔt是系統(tǒng)在共識過程中處理交易的數(shù)量，time是系統(tǒng)處理交易所需要的時間。兩種算法的對比方案，在相同的網(wǎng)絡測試環(huán)境中，節(jié)點個數(shù)分別設置40、50、60、70、80、90六組數(shù)據(jù)進行對比。

原PBFT共識算法，系統(tǒng)中的吞吐量受節(jié)點數(shù)量影響較大。改進的共識算法，將系統(tǒng)中節(jié)點劃分為n個共識組，首先在共識組內(nèi)進行共識，然后再由共識小組的主節(jié)點之間進行共識組間的共識，僅需要n個共識小組中的主節(jié)點參與，有效減少了通信的開銷，要優(yōu)于原共識算法中的吞吐量。在節(jié)點數(shù)量較大的情況下，與原算法相比也會有較高的吞吐量，如圖7所示。

7 結(jié)論

本文針對原PBFT共識算法存在的問題，提出了基于信任度評估模型的PBFT共識算法。在第一層的共識過程中，可以根據(jù)節(jié)點收到的投票結(jié)果，識別出拜占庭節(jié)點，減少了共識過程中惡意節(jié)點作惡的行為。根據(jù)系統(tǒng)中節(jié)點的歷史行為，利用信任評估模型分別從節(jié)點動態(tài)行為和靜態(tài)行為兩方面進行評估，選取可靠節(jié)點作為第二層共識小組的主節(jié)點，防止共識中的主節(jié)點是惡意節(jié)點，這有利于減少系統(tǒng)的通信開銷。通過實驗驗證了該改進算法的有效性，在網(wǎng)絡穩(wěn)定的情況下，可以以較少的通信量達成共識。對PBFT共識算法的不斷改進和優(yōu)化，能夠使其應用在各大聯(lián)盟鏈平臺。

此改進的共識算法存在一定的不足之處，劃分共識小組的組內(nèi)成員數(shù)量在某范圍內(nèi)，效率能達到最高。在未來工作中，將對其繼續(xù)研究，并對信任評估模型進一步完善，提高系統(tǒng)的安全性。