吳曉彤，柳平增

（山東農業(yè)大學信息科學與工程學院，山東泰安271018）

0 概述

隨著比特幣等數字加密貨幣的日益普及，區(qū)塊鏈正逐漸成為一種新的去中心化基礎架構和分布式計算范式［1］。目前，區(qū)塊鏈已經引起了政府部門、互聯網企業(yè)和金融機構的廣泛關注和高度重視［2］，其去中心化、公開透明、共同維護、時序性、可編程等特點，除了適合構建可編程的金融系統(tǒng)和貨幣系統(tǒng)之外，還能為中心化機構存在的數據存儲不安全、低效率、高成本等問題提供解決方案［3-5］。共識算法是區(qū)塊鏈技術的核心要素，也是近年來分布式系統(tǒng)研究的熱點，其主要作用是解決拜占庭將軍問題，也是確保分布式系統(tǒng)各節(jié)點數據一致性的關鍵，直接影響著區(qū)塊鏈的交易處理能力、可擴展性和安全性［6-7］。

在目前常用的共識算法中，較為經典的算法有PoW［8］、PoS［9］、Paxos［10］、Raft［11］、PBFT［12］等。不同算法都有各自的特點和優(yōu)勢，其中，實用拜占庭容錯算法（Practical Byzantine Fault Tolerance，PBFT）算法由于能夠解決拜占庭問題且相對高效而被廣泛應用。但由于PBFT 算法通信開銷高，吞吐量和性能較低，且采用的是C/S 架構，不能適應P2P 網絡，無法動態(tài)感知節(jié)點數目的變化［13-14］，因而其應用受到了諸多的限制。許多學者在共識策略［15-17］、一致性協議［18-19］、方法創(chuàng)新［20-21］、區(qū)塊鏈結構［22］等方面對PBFT算法進行了改進，以期使算法具有更高的動態(tài)性和更低的時延。但該算法應用于一些交易量和信息量大的領域時，仍存在共識時延高、動態(tài)性差、吞吐量、性能較低等問題，因此，設計一個低時延、高效率、高吞吐量的共識算法，是亟待解決的問題。

本文針對PBFT 算法存在的不足，提出一種基于備選投票機制的低時延共識算法PBFT，通過引入候補節(jié)點集合和投票選舉機制，降低算法達成共識所需的時延，提高算法的吞吐量和動態(tài)性。

1 實用拜占庭容錯算法

PBFT 算法由CASTRO 和LISKOV 于1999年提出，該算法主要針對系統(tǒng)中存在的作惡節(jié)點向系統(tǒng)中的其他節(jié)點發(fā)送錯誤消息，擾亂整個系統(tǒng)正常運行的問題，從根本上解決了拜占庭問題，并將拜占庭容錯算法復雜度從指數級降低到了多項式級O（N2）。實用拜占庭算法在保證系統(tǒng)安全性和可靠性的前提下提供了（n-1）/3 的容錯性，即允許系統(tǒng)有不多于1/3 的節(jié)點失效或者作惡。

PBFT 共識算法要求節(jié)點共同維護一個狀態(tài)，所有節(jié)點采取的行動一致。因此，需要運行3 類基本協議，即一致性協議、檢查點協議和視圖更換協議。一致性協議主要通過共識過程中的預準備、準備和確認3 個階段來保證全網節(jié)點保存數據的一致性。若在共識過程中主節(jié)點在一段時間內都不能完成客戶端的請求或某節(jié)點檢測出主節(jié)點作惡或宕機，則會觸發(fā)視圖更換協議以更換出現故障的主節(jié)點。周期性地檢查點協議則是將系統(tǒng)中的服務器同步到某一個相同的狀態(tài)，系統(tǒng)會設置一個checkpoint 的時間點，在這個時刻可以定期地處理日志、節(jié)約資源并及時糾正服務器狀態(tài)。

1.1 PBFT 算法的一致性協議

PBFT 算法的一致性協議是該算法的核心部分，能夠保證各節(jié)點數據的一致性。如圖1所示，其中，副本0 是主節(jié)點，副本3 是失效節(jié)點，c 是客戶端。

圖1 PBFT 算法共識過程Fig.1 Consensus process of PBFT algorithm

PBFT 算法具體流程如下：

1）客戶端發(fā)起消息請求

客戶端c 向主節(jié)點0 發(fā)送消息請求，格式為：

其中，REQUEST 為消息名稱，o 為請求的具體操作，t 為請求時客戶端追加的時間戳，c 為客戶端標識。

2）預準備階段

主節(jié)點會發(fā)起對應的預準備消息給網絡中的副本節(jié)點，預準備消息包頭結構體定義為：

其中，PRE-PREPARE 為消息名稱，v為視圖編號，d 為信息摘要，n為節(jié)點編號，m 為客戶端發(fā)送的消息。若通過驗證，副本節(jié)點會確認預準備消息進入到準備階段。

3）準備階段

副本節(jié)點i向所有副本節(jié)點發(fā)送準備消息：

若節(jié)點i收到了超過2f+1 個不同共識節(jié)點的PRE-PREPARE 和PREPARE 消息并驗證通過，將進入確認階段。

4）確認階段

進入確認階段后的節(jié)點向其他副本節(jié)點廣播確認消息＜COMMIT，v，n，D（m），i＞，其中，D（m）為副本節(jié)點簽名集合。所有的副本節(jié)點會對接收的廣播消息進行驗證，當節(jié)點i接收到2f+1 個確認消息并滿足相應條件后，則代表式（4）成立，此時每個副本節(jié)點向客戶端發(fā)送回復，進入回復階段。

5）回復階段

當算法進入到回復階段時，共識集合中的節(jié)點i會給一個最終的反饋消息給客戶端，消息格式定義為：

其中，REPLY 為消息名稱，v為視圖編號，t 為時間戳，c 是客戶端，i是節(jié)點編號，r 是節(jié)點i的回復。

若客戶端收到f+1 個相同的REPLY 消息，則說明客戶端發(fā)起的請求已經達成全網共識。

1.2 PBFT 算法的視圖切換協議

若某個副本節(jié)點i檢測出主節(jié)點拜占庭錯誤或者宕機時，則啟動視圖切換協議，將視圖編號v變更為v+1，同時不再接受除檢查點（checkpoint）、視圖切換（view-change）和新視圖（new-view）外的其他消息請求。

此時，副本節(jié)點i會向其他節(jié)點廣播視圖更換消息：

其中，VIEW-CHANGE 為消息名稱，v為視圖編號，n是檢查點編號，C是檢查點消息集合，i是節(jié)點編號，P是當前副本節(jié)點未完成請求的PRE-PREPARE和PREPARE 消息集合。

通過公式p=vmod |R|計算得到主節(jié)點p（R為主節(jié)點的編號），當主節(jié)點p收到2f個來自其他副本節(jié)點的有效的視圖更換消息后，節(jié)點p向其他副本節(jié)點廣播新視圖消息＜NEW-VIEW，v+1，V，O＞，其中，V 是節(jié)點接收到的視圖更換消息，O 為主節(jié)點重新發(fā)起的未完成的預準備消息。當副本節(jié)點收到主節(jié)點的新視圖消息后，若驗證通過，進入v+1 視圖開始O中的預準備處理流程。

1.3 PBFT 算法的優(yōu)點與不足

實用拜占庭算法PBFT 是解決拜占庭將軍問題的算法，能夠針對性地解決共識當中出現的拜占庭問題，同時算法允許不超過1/3 的作惡節(jié)點存在，在節(jié)點數適中的情況下可以高效地完成共識。對于一些以企業(yè)、政府為代表的聯盟鏈來說，PBFT 共識算法是較好的選擇，但是該算法在目前的區(qū)塊鏈技術中仍然存在以下不足：

1）視圖切換協議的不足

在主節(jié)點出現拜占庭節(jié)點的情景下，實用拜占庭共識算法PBFT 必須進行算法的視圖切換，但是，算法在視圖切換過程中，對于當前區(qū)塊鏈中已有的簽名區(qū)塊的數量，即區(qū)塊高度的變量沒有加以考慮，這樣就會使得在共識超時情況下視圖切換效率低下，直接導致算法在實際情況中的網絡通信開銷加大，增加了系統(tǒng)的數據交換開銷，同時也失去了視圖切換時的隨機性，這對于算法性能是有影響的。

2）區(qū)塊鏈共識節(jié)點動態(tài)性支持不夠

在區(qū)塊鏈分布式系統(tǒng)中，所有共識節(jié)點的行為通常都是隨機的、動態(tài)的，在區(qū)塊鏈網絡中有加入也有退出。原始的實用拜占庭容錯算法，在最初設計時主要是為了解決拜占庭將軍問題，對于節(jié)點動態(tài)變化的問題并沒有考慮得很周到，因此，算法無法支持節(jié)點動態(tài)加入或退出網絡，這樣容易導致在節(jié)點出現變化后無法快速進行處理，以及拜占庭的節(jié)點無法及時替換的問題。

2 PBFT 算法改進

針對原始PBFT 算法的不足，本文提出一種低時延的共識算法IPBFT。首先增設候補集合節(jié)點，用于選舉產生新的備用主節(jié)點，并對視圖切換協議進行優(yōu)化，在提高共識效率的同時實現節(jié)點的動態(tài)增刪；然后將算法的主節(jié)點選取方式改進為投票選舉機制，優(yōu)化主節(jié)點選取機制，在提高視圖切換效率的基礎上同時減少拜占庭節(jié)點的數量，從而提高系統(tǒng)效率。

2.1 改進思路與符號表示

本文按照圖2所示的優(yōu)化流程對PBFT 算法進行改進。

圖2 PBFT 算法優(yōu)化流程Fig.2 Optimization procedure of PBFT algorithm

1）以R1表示共識集合，以R2表示候補集合，定義R1集合為：

其中，R1表示共識集合總節(jié)點數，f表示共識結合中最多的拜占庭錯誤節(jié)點數。R1的節(jié)點數量根據實際應用系統(tǒng)中錯誤節(jié)點的數量而定。

候補集合中包括了從共識集合中出現拜占庭錯誤的替換節(jié)點和區(qū)塊鏈系統(tǒng)中新加入的節(jié)點，在算法中，定義R2集合為：

同理，R2的節(jié)點數量根據實際應用系統(tǒng)中錯誤節(jié)點的數量而定。

2）當首次共識開始時定義一個值v1，與視圖編號v不同，v1用于視圖切換時主節(jié)點的選取，其初始值設置為：

其中，v是首次共識的視圖編號數值，且每當視圖成功切換一次，v1都相應的增加1，表示視圖已切換。

3）當主節(jié)點發(fā)生拜占庭錯誤時，考慮到主節(jié)點選取的隨機性和惡意節(jié)點的不可重復性，IPBFT 算法在主節(jié)點選取的定義中增加了一個區(qū)塊高度參數h，計算公式為：

為提高視圖切換的效率，規(guī)定主節(jié)點的選取在候補集合中進行，因此，主節(jié)點p的選取與R2有關。該公式結合投票選舉的機制避免了拜占庭節(jié)點重復當選為主節(jié)點，同時公式的隨機性也能夠更好地使算法支持節(jié)點的動態(tài)性。

2.2 具體改進

對PBFT 算法的改進包括增設候補集合和加入投票選舉機制兩個方面。

1）通過增設候補集合以實現節(jié)點的動態(tài)變化。

（1）將所有的節(jié)點分為兩個節(jié)點集合：一個是共識節(jié)點集合，集合功能為參加區(qū)塊鏈中的共識過程；另一個是候補節(jié)點集合，若共識集合中主節(jié)點拜占庭或有節(jié)點退出，則由候補集合中選出的信任節(jié)點替換上，在實現節(jié)點動態(tài)替換的同時減小替換所需的時延。共識集合中的拜占庭錯誤節(jié)點，也將會被淘汰進入到候補節(jié)點集合中，信任節(jié)點的選取方式使用的是基于投票的選舉機制。

（2）優(yōu)化視圖切換協議以簡化共識過程。

①IPBFT 算法對視圖切換協議進行了優(yōu)化，當主節(jié)點發(fā)生拜占庭錯誤時，算法會丟棄未完成的共識提案歷史信息，重新選取主節(jié)點，并提醒客戶端發(fā)送與未完成提案相同的請求，然后進行共識。由于視圖切換后會丟棄未完成的消息提案重新開始共識，一方面可以省去新主節(jié)點向其余節(jié)點廣播新視圖消息NEW-VIEW、收集之前未完成的預準備和準備消息的共識過程，可減少一部分網絡開銷，另一方面還能保證主節(jié)點廣播的消息順序正確。

②視圖切換完成后，將共識節(jié)點所處的視圖編號v初始化為0，v1數值增加1，從而保證即使出現視圖切換，消息依然能在保證視圖編號一致的基礎上進行廣播共識而不影響候補集合進行下一個備用主節(jié)點的選取。

③共識過程中確認階段的作用，一方面是為了保證視圖消息順序和視圖編號一致，另一方面是防止主節(jié)點出錯而導致產生的集群狀態(tài)不一致。IPBFT 算法首先可以保證在視圖切換完成后，所有共識節(jié)點所處的視圖編號和收到廣播的消息順序一致，其次可保證新的主節(jié)點為候補集合中節(jié)點所信任的非作惡節(jié)點，作惡的概率非常小。在這樣的雙重保障下，IPBFT 算法可以優(yōu)化掉確認階段的共識過程，共識過程由三階段共識變成了兩階段，從而優(yōu)化掉確認階段的通信，提高整個共識達成的效率，減少系統(tǒng)的通信開銷。IPBFT算法的共識過程如圖3所示。其中，4 表示候補集合選舉出的信任節(jié)點，等待視圖切換時將拜占庭節(jié)點替換下來，除此之外不做任何操作。

圖3 IPBFT 共識過程Fig.3 Consensus process of IPBFT algorithm

2）加入投票選舉機制。

（1）投票選舉整體思想及原理

IPBFT 共識算法使用基于投票的選舉機制作為主節(jié)點的選取方式，在共識集合中，當主節(jié)點出現拜占庭錯誤或有節(jié)點退出時，算法將共識集合中的相應節(jié)點替換掉，使用候補集合中通過選舉機制產生的新節(jié)點作為候補節(jié)點補增到共識集合節(jié)點中。

為提高節(jié)點替換的效率，候補集合的選舉和共識集合的共識同時進行，即在共識集合正常運行的情況下，候補集合先將下一次視圖切換所需要的信任節(jié)點選舉出來，當共識集合的主節(jié)點出現錯誤時不再進行傳統(tǒng)的視圖切換過程，而是直接對備用的主節(jié)點進行替換，從而減少視圖切換時的通信次數。

節(jié)點替換完成后，在候補集合內再進行下一次的節(jié)點選舉，替換下來的拜占庭節(jié)點也會一直處于候補集合中，并且被選舉為主節(jié)點的概率極低；同時，當有節(jié)點進入時，首先進入候補集合，節(jié)點進入或退出時算法會增加或刪除他的投票權。投票選舉原理如圖4所示。

圖4 投票選舉原理Fig.4 Voting principle

IPBFT 算法首先實現候補集合與共識集合的聯動同步過程，當共識集合的共識過程發(fā)生視圖切換時，通過消息的廣播，同步地通知到候補集合，其次候補集合將廣播投票選舉的消息，用于共識集合中節(jié)點的動態(tài)替換。

（2）投票選舉流程分析

步驟1候補集合的節(jié)點保持與共識集合的心跳，當共識集合中的主節(jié)點出現拜占庭錯誤或有節(jié)點退出時，立即在候補集合內廣播節(jié)點替換的消息，將選舉好的信任節(jié)點替換到共識集合，在視圖切換完成后進行下一次選舉行為。

步驟2通過P=（h+v1）mod|R1|選出下一個節(jié)點候選人，參與選舉的節(jié)點向其他所有節(jié)點發(fā)出參與選舉的消息，同時通知集合中所有節(jié)點，自己將參與選舉；如果該節(jié)點非當前共識集合中所需要的節(jié)點，則該節(jié)點自動放棄，重新選舉下一個節(jié)點候選人。

步驟3在所有的節(jié)點收到該通知消息后，如果同意，則會選舉該節(jié)點作為獲選人；如果不同意，則可以反對，同時也能投票給本身節(jié)點；如果一個參選節(jié)點同意票選的數量大于或者等于R2/2+1 個，則成功獲得稱為獲選人資格。

步驟4為避免選舉算法出現特定情況下的惡性循環(huán)選舉而最終影響選舉的進度，算法規(guī)定了每個參選節(jié)點不同的唯一超時值。既然超時值是唯一的，那么所有的參選節(jié)點發(fā)起投票的行為將會成為順序發(fā)起的行為，這樣能有效地避免出現所有節(jié)點都得票不通過半的情況，節(jié)點分先后，最終會有一個唯一的節(jié)點獲得獲選人資格，并作為代表被放入到共識集合節(jié)點中，此時投票選舉結束。IPBFT 算法選舉流程如圖5所示。

圖5 IPBFT 算法選舉流程Fig.5 Voting mechanism procedure of IPBFT algorithm

當投票結束時，會出現兩種情況：1）若參與選舉的節(jié)點中有節(jié)點得到超過半數的投票，則節(jié)點當選成為新一輪共識的主節(jié)點；2）若參與選舉的節(jié)點都沒有得到足夠的票數，則視為本次選舉失敗，選舉失敗的節(jié)點返回候補集合中，此時v1數值加1，重新選取參與選舉的主節(jié)點，發(fā)起進行新一輪的選舉。

2.3 IPBFT 算法流程

IPBFT 算法的整體流程如圖6所示。

圖6 IPBFT 算法流程Fig.6 Procedure of IPBFT algorithm

根據上述算法的設計過程，給出IPBFT 算法的共識過程，如下所示：

算法1IPBFT 算法

輸入交易請求

輸出共識結果

1.主節(jié)點選舉成功，視圖編號初始化，v1的值增加1。

2.客戶端發(fā)向主節(jié)點P送請求。//請求階段

3.主節(jié)點進行廣播預備消息。//預準備階段

4.1.副本節(jié)點對主節(jié)點和接收到的提案消息進行驗證，若主節(jié)點拜占庭錯誤，則進入視圖切換流程，轉到步驟1。

4.2.若提案消息驗證通過則進入準備階段，否則丟棄消息重新共識，轉到步驟2。

5.1.副本節(jié)點進入到準備階段，廣播準備消息，當節(jié)點i收到超過2f+1 個不同共識節(jié)點的準備消息并驗證通過，則回復共識達成信息給客戶端。

5.2.否則進行視圖切換或丟棄消息重新共識，轉到1。//準備階段

6.客戶端在收到了f+1 個回復信息后，認為系統(tǒng)達成了共識，共識結束。

2.4 IPBFT 算法分析

為滿足實際場景中的應用，同時滿足算法高共識效率的要求，IPBFT 算法是基于部分同步狀態(tài)的基礎上進行應用的，即節(jié)點發(fā)出的消息，雖然會有延遲，但是最終會到達目標節(jié)點。這是由于本文算法確保了每一個節(jié)點都有不同的超時值，在允許一定延遲的情況下，達成節(jié)點間的共識，保證了節(jié)點共識的效率。例如當主節(jié)點的發(fā)送時間超過了此超時值，即視為主節(jié)點出錯，此時執(zhí)行IPBFT 算法的視圖切換協議，進行后續(xù)的過程。結合候補集合以及備選投票機制，IPBFT 共識算法中存在以下優(yōu)點：

1）算法將共識的過程從普通的三階段優(yōu)化為兩階段，在達成共識的基礎上縮短了共識所需的時延和通信次數，極大地降低了系統(tǒng)的網絡開銷，共識的效率較原始PBFT 算法相比有明顯提高。

2）當共識集合中出現主節(jié)點i拜占庭錯誤時，會使用候補集合中選舉的信任節(jié)點進行替換，這樣可以避免進行主節(jié)點的更換時出現多余網絡通信的現象，而且還能使節(jié)點可以動態(tài)地增刪，同時也避免了拜占庭錯誤節(jié)點i被第2 次或者多次的重復選為主節(jié)點，導致視圖不斷切換和系統(tǒng)的共識性能波動下降的情況。

3）當出現視圖切換時，候補集合會將選好的信任節(jié)點替換到共識集合，同時共識集合的拜占庭錯誤節(jié)點也會替換到候補集合，如此替換下去，將會減少共識集合中的拜占庭節(jié)點數量，這樣能夠有效降低系統(tǒng)共識過程中的視圖切換的概率，減小共識開銷，保持系統(tǒng)的高效運行。

3 實驗與結果分析

本文在算法的測試環(huán)節(jié)，使用基于docker 的容器技術，將區(qū)塊鏈共識節(jié)點的運行配置和代碼都裝載在docker 虛擬容器中，系統(tǒng)對每個容器的資源分配內容為2 GB，節(jié)點的代碼在容器中運行分配的CPU 的資源分配為5%，同時內存給每個節(jié)點運行時的內存的分配也為5%左右，使容器能夠發(fā)揮其優(yōu)點。所有的虛擬區(qū)塊鏈節(jié)點的運行會相對獨立，同時運行具有隔離性，實驗環(huán)境信息如表1所示。

表1 實驗環(huán)境信息Table 1 Experimental environment information

3.1 IPBFT 算法共識時延實驗

共識時延是指從交易提交到交易完成之間所消耗的時間，是衡量共識算法運行速度的重要指標，較低的共識時延可使交易可以快速得到確認，區(qū)塊鏈安全性更高，同時也能變得更為實用。測試的共識時延為區(qū)塊完成一次共識過程的時間，用公式定義時延為：

其中，Tcomplete表示區(qū)塊確認完成的時間，Tsubmit表示提案開始的時間。

為驗證IPBFT 算法在實際應用中低時延的特點，對IPBFT 算法與原始PBFT 算法進行對比。在每次進行信息交易時進行一次節(jié)點的動態(tài)替換，用來模擬例如共識過程中節(jié)點替換的現象，同時保證7 個共識節(jié)點，測試在相同出塊間隔內，系統(tǒng)發(fā)送1 000 條交易量下的對照實驗，實驗測試30 次，實驗結果如圖7所示?？梢钥闯?，在同一個網絡環(huán)境中，以節(jié)點數量相同且傳輸的交易信息數據大小相同為前提，IPBFT 算法由于增設了候補集合，省去了大部分視圖切換和更換節(jié)點產生的信息收集的過程，且省去了確認階段，所需的共識時延要低于原始PBFT算法。單次共識所需的平均時延僅為380 ms 左右，證明在實際應用中，即使需要在短時間內處理大量的信息，且加上網絡請求和數據傳輸的時延，整個系統(tǒng)的時延情況也能有良好的表現。

圖7 共識時延對比Fig.7 Consensus delay comparison

3.2 IPBFT 算法吞吐量性能實驗

吞吐量指的是在單位時間內完成的交易的數量，一般用TPS 來表示，TPS 公式為：

其中，Δt為出塊所用的時間，TΔt為出塊時間內完成的交易數量。

對上述的兩種算法進行吞吐量的對比實驗。由于吞吐量的大小與交易量及節(jié)點的數量有關，因此本次實驗將分為兩組獨立的實驗。

實驗1將兩種算法的共識節(jié)點數量固定為7 個，對各算法在相同出塊間隔內，系統(tǒng)分別發(fā)送1 000、1 500、2 000、2 500、3 000、3 500、40 00 條交易量下的吞吐量進行30 次測試，將這30 次的結果取平均值作為實驗的結果，如圖8所示?？梢钥闯觯S著交易量的逐漸增多，在節(jié)點的處理能力范圍內，每種算法的吞吐量也會隨之增加。但當交易量超過3 000 條，此時的交易請求超過了節(jié)點的處理能力范圍，導致了線程的堵塞，吞吐量呈下降趨勢。但從總體來看，IPBFT 算法的吞吐量仍高于原始PBFT 算法。

圖8 不同交易量下吞吐量對比Fig.8 Throughput comparison under different transaction volumes

實驗2將每種算法的交易量固定為1 000 條，對各算法在共識節(jié)點數量分別為4、7、10、13、16、19、22、25 個情況下的吞吐量進行30 次測試，將這30 次的結果取平均值作為實驗的結果，如圖9所示?？梢钥闯?，隨著節(jié)點數量的增多，兩種算法的吞吐量都呈下降趨勢，但IPBFT 算法的吞吐量仍高于原始的算法。

圖9 不同節(jié)點數量下吞吐量對比Fig.9 Throughput comparison under different numbers of nodes

綜上，IPBFT 算法具有更高的吞吐量，能夠在相同時間內處理更多的交易事務，使區(qū)塊鏈溯源系統(tǒng)具有更高的共識效率。

3.3 IPBFT 算法共識通信次數實驗

為了驗證IPBFT 算法的通信次數，對兩種算法在共識過程的通信次數進行實驗對比。為便于理解，首先計算IPBFT 算法和原始PBFT 算法的通信次數。

1）原始PBFT 算法通信次數

由于原始PBFT 算法中需要經過三階段的共識過程和視圖切換過程，假設共識節(jié)點數量為n，那么共識過程中的預準備階段需要主節(jié)點將消息發(fā)送給所有副本節(jié)點，所需通信次數為（n-1）次。準備階段中副本節(jié)點間互相通信，需要（n-1）2次通信次數。而確認階段每個節(jié)點需要向除自己外的節(jié)點發(fā)送消息，所需通信次數為n（n-1）次。綜上，共識過程的總通信次數N為：

在視圖切換過程中，每個副本節(jié)點需要廣播視圖變更消息，需要（n-1）2通信次數；接著主節(jié)點發(fā)送新視圖消息給所有副本節(jié)點，消耗（n-1）次通信次數；考慮到系統(tǒng)發(fā)生視圖切換存在著一定概率。因此，視圖切換過程的總通信次數M為：

其中，z為出現視圖切換的概率（0≤z≤1），z會隨著節(jié)點數量的增加而增長。綜上，原始PBFT 算法所需要的總通信次數C為：

2）IPBFT 算法通信次數

IPBFT 算法由于共識階段省去了確認階段，所需通信次數為n（n-1）次；優(yōu)化視圖切換協議省去了主節(jié)點廣播新視圖消息的環(huán)節(jié)，且主節(jié)點的選取是在候補集合中進行，由于候補集合節(jié)點數量為（n-1）/3，因此所需要的通信次數為z｛［（n-1）/3］-1｝2次。綜上，IPBFT 算法的總通信次數C為：

3）通信次數對比

將兩種算法的通信次數進行對比，在沒有出現視圖切換的情況下，兩個算法通信次數比值為：

由上式可知，算法在沒有出現視圖切換的情況下IPBFT 的通信次數為原始PBFT 算法的一半，極大地減少了系統(tǒng)的網絡通信開銷。

在視圖出現切換時，2 個算法通信次數比值為：

將n取不同的節(jié)點數量，z取從0 到1 的所有情況，得到如圖10所示的圖形化界面。

圖10 通信次數比值三維曲面圖Fig.10 Three dimensional surface graph of communication degree ratio

由圖10 可以看出：隨著節(jié)點的增加，在視圖切換概率取不同值的情況下，通信次數比值Q都高于2，即IPBFT 算法的通信次數將始終低于原始PBFT算法通信次數的一半，且隨著概率z的逐漸升高，兩個算法的通信次數比值也越來越大，證明了IPBFT 算法在共識切換所需的通信次數要遠小于原始算法。

這里解釋兩個特殊情況：

（1）當共識集合節(jié)點數為4 時，候補集合中的節(jié)點數量為1，此時該節(jié)點就是下一次視圖切換的主節(jié)點，因此，不需要進行選舉過程，IPBFT 算法視圖切換所需的通信次數為0，此時比值Q為3 并達到了最大值。但此時出現視圖切換的概率為100%，在實際應用中一個可行的區(qū)塊鏈系統(tǒng)不允許視圖切換概率大于50%的情況發(fā)生，所以，此情況下比值Q雖然較大，但是沒有實用價值。

（2）當z為0 時，由于沒有出現視圖切換過程，所以無論節(jié)點數量是多少，通信次數的比值Q一致保持在2。

總而言之，IPBFT 算法在通信次數最多的情況下也僅僅為原始PBFT 算法的一半。在實際情況中，算法所處的聯盟鏈出現節(jié)點拜占庭的概率非常低，即出現視圖切換的概率非常低，所以IPBFT 算法的通信次數可以長時間保持在原始PBFT 算法通信次數的50%。

IPBFT 算法與原始PBFT 算法的通信次數對比結果如圖11所示?？梢钥闯?，實驗結果可以很好地驗證上述的結論，隨著節(jié)點數量的增加，原始PBFT算法的通信次數呈大幅度增長，而IPBFT 算法的通信次數明顯低于原始PBFT 的通信次數，且增長略顯平穩(wěn)。

圖11 不同節(jié)點數量下共識通信次數對比Fig.11 Comparison of consensus communication times under different numbers of nodes

3.4 IPBFT 算法節(jié)點選舉性能實驗

由于IPBFT 算法中加入了選舉機制，在此對候補集合中選舉的性能進行實驗分析，測試在不同節(jié)點數量下，候補集合在開始進行選舉，到主節(jié)點替換完成所需要的時間。實驗測試30 次，并取平均值作為結果，如圖12所示。

圖12 選舉機制性能測試結果Fig.12 Performance test result of election mechanism

由圖12 可以看出：隨著候補集合中節(jié)點數量的增加，選舉所需要的時間也會隨之增多。但總體而言，候補集合中節(jié)點選舉所需的時間能夠保持在可接受的范圍內，所花費的網絡開銷占整個系統(tǒng)開銷的比重也微乎其微。實驗證明，由于增設了候補集合并采取基于投票的選舉機制，IPBFT 算法能夠以更高的效率和更低的時延進行主節(jié)點的替換，而不影響系統(tǒng)整體的共識過程。

3.5 IPBFT 算法效率實驗

效率測試實驗是為了測試在系統(tǒng)運行一段時間后，整個共識集合中拜占庭節(jié)點的數量。實驗將IPBFT 算法和原始PBFT 算法進行對比，首先將2 個算法的共識節(jié)點數量初始化為10 個，共識節(jié)點中的拜占庭節(jié)點數為3 個。IPBFT 算法的候補集合節(jié)點數量設置為3 個，候補集合的拜占庭節(jié)點數為0 個。實驗記錄出現視圖切換時各集合中拜占庭節(jié)點的數量，實驗結果如圖13所示。

圖13 選舉機制效率測試結果Fig.13 Efficiency test result of election mechanism

由圖13 可以看出：當實驗發(fā)生3 次共識的視圖切換時，IPBFT 算法共識集合的拜占庭節(jié)點數從3 個減少到0 個，候補集合中的拜占庭節(jié)點數從0 個增加到3 個；而原始的PBFT 算法，不管視圖如何切換，共識節(jié)點中的拜占庭節(jié)點總數都沒有發(fā)生任何變化。

在這種情況下，原始PBFT 算法拜占庭節(jié)點數的數量是不變的，那么發(fā)生視圖切換的概率也會一直不變，系統(tǒng)的運行狀態(tài)并不能達到最優(yōu)。而IPBFT算法共識集合中拜占庭節(jié)點的數量會隨著視圖切換的次數不斷下降，直到整個共識集合中沒有拜占庭節(jié)點，此時系統(tǒng)會保持高效運行。由此可見，當系統(tǒng)運行一段時間后，IPBFT 算法的共識效率會比原始的PBFT 算法的效率高得多。

4 結束語

本文改進傳統(tǒng)的PBFT 共識算法，提出一種低時延的共識算法IPBFT。通過增設候補節(jié)點集合，在視圖切換協議上進行優(yōu)化，使算法的共識過程簡化為兩階段，減少了達成共識的時延。此外，采取基于備選投票機制作為主節(jié)點選取的方式，在共識節(jié)點進行共識的同時完成候補節(jié)點的選舉，不僅減少了視圖切換過程的節(jié)點通信次數，而且還能支持節(jié)點的動態(tài)變化。實驗結果證明了IPBFT 算法的有效性及其低時延、高吞吐量、高共識效率的優(yōu)點，同時能夠較好地支持節(jié)點動態(tài)的加入或退出。下一步將在不影響算法效率的基礎上把拜占庭節(jié)點的容錯性提升到（n-1）/2，使IPBFT 算法能夠適應更大規(guī)模的公有鏈。