基于備選投票機制的低時延PBFT改進(jìn)研究

吳曉彤，柳平增

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

0 概述

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

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

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

1 實用拜占庭容錯算法

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

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

1.1 PBFT 算法的一致性協(xié)議

PBFT 算法的一致性協(xié)議是該算法的核心部分，能夠保證各節(jié)點數(shù)據(jù)的一致性。如圖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 為客戶端標(biāo)識。

2）預(yù)準(zhǔn)備階段

主節(jié)點會發(fā)起對應(yīng)的預(yù)準(zhǔn)備消息給網(wǎng)絡(luò)中的副本節(jié)點，預(yù)準(zhǔn)備消息包頭結(jié)構(gòu)體定義為：

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

3）準(zhǔn)備階段

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

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

4）確認(rèn)階段

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

5）回復(fù)階段

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

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

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

1.2 PBFT 算法的視圖切換協(xié)議

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

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

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

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

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

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

1）視圖切換協(xié)議的不足

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

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

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

2 PBFT 算法改進(jìn)

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

2.1 改進(jìn)思路與符號表示

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

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

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

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

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

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

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

其中，v是首次共識的視圖編號數(shù)值，且每當(dāng)視圖成功切換一次，v1都相應(yīng)的增加1，表示視圖已切換。

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

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

2.2 具體改進(jìn)

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

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

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

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

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

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

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

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

2）加入投票選舉機制。

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

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

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

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

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

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

（2）投票選舉流程分析

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

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

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

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

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

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

2.3 IPBFT 算法流程

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

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

根據(jù)上述算法的設(shè)計過程，給出IPBFT 算法的共識過程，如下所示：

算法1IPBFT 算法

輸入交易請求

輸出共識結(jié)果

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

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

3.主節(jié)點進(jìn)行廣播預(yù)備消息。//預(yù)準(zhǔn)備階段

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

4.2.若提案消息驗證通過則進(jìn)入準(zhǔn)備階段，否則丟棄消息重新共識，轉(zhuǎn)到步驟2。

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

5.2.否則進(jìn)行視圖切換或丟棄消息重新共識，轉(zhuǎn)到1。//準(zhǔn)備階段

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

2.4 IPBFT 算法分析

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

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

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

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

3 實驗與結(jié)果分析

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

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

3.1 IPBFT 算法共識時延實驗

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

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

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

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

3.2 IPBFT 算法吞吐量性能實驗

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

其中，Δt為出塊所用的時間，TΔt為出塊時間內(nèi)完成的交易數(shù)量。

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

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

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

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

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

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

3.3 IPBFT 算法共識通信次數(shù)實驗

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

1）原始PBFT 算法通信次數(shù)

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

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

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

2）IPBFT 算法通信次數(shù)

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

3）通信次數(shù)對比

將兩種算法的通信次數(shù)進(jìn)行對比，在沒有出現(xiàn)視圖切換的情況下，兩個算法通信次數(shù)比值為：

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

在視圖出現(xiàn)切換時，2 個算法通信次數(shù)比值為：

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

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

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

這里解釋兩個特殊情況：

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

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

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

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

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

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

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

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

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

3.5 IPBFT 算法效率實驗

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

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

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

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

4 結(jié)束語

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