基于投票機制的拜占庭容錯共識算法

王海勇 郭凱璇 潘啟青

摘 要：針對現(xiàn)有的區(qū)塊鏈中實用拜占庭容錯（PBFT）共識算法、基于動態(tài)授權(quán)的拜占庭容錯（DDBFT）共識算法、聯(lián)盟拜占庭容錯（CBFT）共識算法普遍存在能耗高、效率低、擴展性差等問題，通過引入投票機制，提出了基于投票機制的拜占庭容錯（VPBFT）共識算法。首先，以PBFT算法為基礎(chǔ)，將網(wǎng)絡(luò)中的節(jié)點劃分為四類具有不同職責(zé)的節(jié)點。其次，算法中的投票節(jié)點具有投票和評分權(quán)，監(jiān)督生產(chǎn)節(jié)點誠實可靠地生產(chǎn)數(shù)據(jù)塊;生產(chǎn)有效的數(shù)據(jù)塊的生產(chǎn)節(jié)點優(yōu)先進入下一輪，候選節(jié)點能夠被選為生產(chǎn)節(jié)點，而普通節(jié)點則能夠成為投票節(jié)點或候選節(jié)點。最后，不同類型的節(jié)點之間具有一定的數(shù)量關(guān)系，能夠在不同類型節(jié)點的數(shù)目或網(wǎng)絡(luò)中的節(jié)點總數(shù)發(fā)生變化時動態(tài)調(diào)整參數(shù)，從而使得算法適應(yīng)動態(tài)網(wǎng)絡(luò)。通過性能仿真分析可知，VPBFT算法相較于PBFT、 DDBFT、CBFT等共識算法，具有低能耗、低時延、高容錯性和高動態(tài)性。

關(guān)鍵詞：區(qū)塊鏈;拜占庭容錯;投票機制;共識算法;數(shù)據(jù)塊

中圖分類號： TP301.6

文獻標(biāo)志碼：A

Abstract： Focusing on the problems of high energy consumption， low efficiency and poor scalability of Practical Byzantine Fault Tolerance （PBFT） consensus algorithm， Dynamic authorized Byzantine Fault Tolerance （DDBFT） consensus algorithm and Consortium Byzantine Fault Tolerance （CBFT） consensus algorithm existed in the blockchain， Practical Byzantine Fault Tolerant consensus algorithm based on Voting （VPBFT） was proposed by introducing voting mechanism. Firstly， based on PBFT algorithm， the nodes in the network were divided into four types of nodes with different responsibility. Secondly， the voting nodes in the algorithm had voting and scoring rights to supervise the production nodes to produce data blocks honestly and reliably， the production nodes producing valid data blocks had priority to be selected into next turn， while the candidate nodes were able to be voted as production nodes， and the ordinary nodes were able to be voted as production nodes or candidate nodes. Finally， different types of nodes had a certain quantity relationship between themselves， which means the parameters were able to be dynamically adjusted when the number of different types of nodes or the total number of nodes in the network changed， so that the algorithm was able to adapt to the dynamic network. Through performance simulation analysis， the proposed VPBFT algorithm has low energy consumption， short delay， high fault tolerance and high dynamicity compared with consensus algorithms such as PBFT， DDBFT and CBFT.

Key words： blockchain; Byzantine Fault Tolerance （BFT）; voting mechanism; consensus algorithm; data block

0 引言

自2008年 “一種完全通過點對點技術(shù)實現(xiàn)的電子現(xiàn)金貨幣”（即比特幣）[1]被提出起，區(qū)塊鏈技術(shù)正一步一步地得到重視。區(qū)塊鏈具有去中心化、分布式、點對點等特點[2]，隨著區(qū)塊鏈技術(shù)的發(fā)展，各種共識算法也層出不窮，比如工作量證明（Proof Of Work， POW）算法[1]、實用拜占庭容錯（Practical Byzantine Fault Tolerance， PBFT）算法[3]等。

拜占庭將軍問題（Byzantine generals problem）是區(qū)塊鏈中共識算法會考慮到的基本問題[4]。這是一個描述分布式系統(tǒng)一致性的協(xié)議問題，拜占庭的將軍們必須全體一致決定是否同時對敵軍發(fā)起攻擊，但在將軍中存在叛徒，叛徒會發(fā)出虛假信息來影響其他將軍們的決定，將軍們?nèi)绾卧诖嬗信淹降那疤嵯逻_成一致的決定，并最終獲得勝利正是該問題所要解決的。拜占庭容錯問題，在計算機領(lǐng)域可以表述為：如何在存有惡意節(jié)點的系統(tǒng)網(wǎng)絡(luò)中確保系統(tǒng)運行的良好以及信息數(shù)據(jù)的完整、可靠和一致性，從而作出正確的決策。

在目前現(xiàn)有的共識算法中，較為經(jīng)典的分布式一致性算法[5]有Paxos算法[6]、Raft算法[7]和PBFT算法。但是，Paxos算法和Raft算法均是面向數(shù)據(jù)而不是面向交易的，并未考慮到拜占庭問題，即沒有考慮系統(tǒng)中存在惡意節(jié)點的情況，一旦系統(tǒng)內(nèi)的惡意節(jié)點發(fā)送虛假消息，那么整個系統(tǒng)將會存儲虛假錯誤的信息。為解決拜占庭問題，PBFT算法[3， 8]被提出，通過大多數(shù)誠實節(jié)點來忽略掉惡意節(jié)點的消息，該算法能夠容忍不超過（n-1）/3個節(jié)點失效（其中n為節(jié)點總數(shù)）。但是PBFT算法采用的是C/S架構(gòu)[7，9]，不能適應(yīng)P2P網(wǎng)絡(luò)，無法動態(tài)感知節(jié)點數(shù)目的變化。

隨著區(qū)塊鏈技術(shù)的進一步發(fā)展，一些新的共識算法也層出不窮，其證明方式趨向于多樣化和混合化?；趧討B(tài)授權(quán)的拜占庭容錯（Dynamic authorized Byzantine Fault Tolerance， DDBFT）算法[10]，將委托權(quán)益證明（Delegated Proof Of Stake， DPOS）算法應(yīng)用于PBFT算法，使得PBFT算法具有動態(tài)性的特點，同時也能夠提高吞吐量、降低時延，但是由于網(wǎng)絡(luò)帶寬有限，需要確認(rèn)的區(qū)塊較大且超出一個節(jié)點的處理能力，就會造成阻塞、降低吞吐量。聯(lián)盟拜占庭容錯（Consortium Byzantine Fault Tolerance， CBFT）算法[5]，以PBFT算法為基礎(chǔ)，通過區(qū)塊緩存、區(qū)塊同步與簽名、節(jié)點變更實現(xiàn)，具有更高的吞吐量和較低的時延，但是其交易處理的效率和達成共識的效率等需要進一步提升。

在對比分析了已有的一些共識算法后，本文提出了一種改進的PBFT算法，即基于投票機制的拜占庭容錯（PBFT based on Voting， VPBFT）共識算法，將投票證明（Proof Of Vote， POV）與PBFT結(jié)合，具有低能耗、低時延、高容錯性和高動態(tài)性。

1 相關(guān)工作

從Paxos算法到Raft算法，再到PBFT算法，以及對PBFT算法改進后形成的基于動態(tài)授權(quán)的拜占庭容錯（DDBFT）共識算法和聯(lián)盟拜占庭容錯（CBFT）共識算法，均針對解決分布式系統(tǒng)的一致性問題。

Paxos算法[6]是基于消息傳遞的，旨在解決在分布式系統(tǒng)內(nèi)如何就某一個內(nèi)容達成一致的問題[11]，在分布式系統(tǒng)內(nèi)的所有節(jié)點的初始狀態(tài)一致，在執(zhí)行了相同的操作后，所有節(jié)點就能夠得到一致的結(jié)果。Paxos算法具有高度的容錯性，但較為難懂且難以實現(xiàn)，于是出現(xiàn)了它的簡化版——Raft算法[12]。但是，Paxos和Raft算法是面向數(shù)據(jù)而不是面向交易的，沒有考慮系統(tǒng)中存在惡意節(jié)點的情況，一旦系統(tǒng)內(nèi)的惡意節(jié)點發(fā)送虛假消息，那么整個系統(tǒng)將會存儲虛假錯誤的信息。

除此之外， PBFT算法[13]也是專門針對解決拜占庭將軍問題的算法，該算法旨在解決如何在整個網(wǎng)絡(luò)中存在惡意節(jié)點的情況下保證最終決策的一致性、正確性的問題。在PBFT算法中，所有節(jié)點被分為客戶節(jié)點、主節(jié)點和備份節(jié)點3種類型，其中，主節(jié)點和備份節(jié)點被稱為副本節(jié)點。該算法流程分為3個階段：預(yù)準(zhǔn)備階段、準(zhǔn)備階段、確認(rèn)階段。具體過程如圖1所示。

當(dāng)客戶節(jié)點收到至少n+1個副本節(jié)點的結(jié)果是相同的情況下，才認(rèn)可結(jié)果有效。PBFT算法針對分布式系統(tǒng)，而且系統(tǒng)中的指令順序執(zhí)行，是基于C/S架構(gòu)的[8，10]。算法的整個過程分為三階段，具有三次信息的廣播，這對網(wǎng)絡(luò)帶寬造成了一定的浪費。另外，在PBFT算法中，整個網(wǎng)絡(luò)的節(jié)點數(shù)目固定，一旦發(fā)生變動系統(tǒng)無法感知，不具備擴展性。

除了Paxos算法、Raft算法和PBFT算法等經(jīng)典的共識算法外，還有一些新提出的針對PBFT算法進行改進的算法：DDBFT算法、CBFT算法。DDBFT算法，主要針對PBFT算法缺乏動態(tài)性的不足，將DPOS算法應(yīng)用于PBFT算法，使得PBFT算法具有動態(tài)性的特點，同時也能夠提高吞吐量、降低時延，但是由于網(wǎng)絡(luò)帶寬有限，需要確認(rèn)的區(qū)塊較大且超出一個節(jié)點的處理能力，就會造成阻塞，降低吞吐量。CBFT算法，是以PBFT算法為基礎(chǔ)，通過區(qū)塊緩存、區(qū)塊同步與簽名、節(jié)點變更實現(xiàn)，具有更高的吞吐量和較低的時延，但是其交易處理的效率和達成共識的效率等需要進一步提升，且在共識流程、區(qū)塊同步和節(jié)點管理方面仍存在問題。

由此可見，每種算法都具有其各自的優(yōu)勢及不足。其中，PBFT算法擴展性較差，不能夠適應(yīng)動態(tài)變化的網(wǎng)絡(luò)系統(tǒng)。DDBFT和CBFT算法雖然在能耗、吞吐量、擴展性等方面有所改進，但仍然存在效率低、能耗高等不同的問題。由此可見，共識算法仍有一定的改進空間。

2 基于投票機制的拜占庭容錯共識算法

通過對已有算法的分析，尤其是分布式系統(tǒng)的共識算法：PBFT算法、DDBFT算法、CBFT算法等，本文針對這些共識算法的不足之處，提出了VPBFT共識算法。在本文算法中，將POV機制應(yīng)用于傳統(tǒng)的PBFT算法，將網(wǎng)絡(luò)中的節(jié)點劃分為四類，不同類別的節(jié)點具有不同的職責(zé)，不同類別的節(jié)點之間具有一定的數(shù)量關(guān)系。

2.1 POV機制

POV機制將整個聯(lián)盟網(wǎng)絡(luò)中的節(jié)點分為四類：投票者、管理者、候選人、普通用戶[14]。其中，投票者具有推薦、投票管理者的權(quán)利，能夠?qū)Ξa(chǎn)生的交易進行驗證和轉(zhuǎn)發(fā)，也能夠?qū)Ξa(chǎn)生的區(qū)塊進行驗證;管理者只能來自于候選人，被隨機地指定生成區(qū)塊，有一定的任命周期，周期結(jié)束后重新被投票;候選人，由經(jīng)過注冊并獲得多于1名投票者推薦的普通用戶組成，也可以是投票者自薦組成;而普通用戶則可以隨時加入和退出。網(wǎng)絡(luò)中所有節(jié)點都能夠發(fā)生、轉(zhuǎn)發(fā)并驗證交易數(shù)據(jù)，數(shù)據(jù)有效才發(fā)送給投票者和管理者，并由管理者將數(shù)據(jù)放入交易池。而管理者被任命在其任命周期里生產(chǎn)塊，且需要至少1+Nc/2個投票者的同意才能生產(chǎn)相應(yīng)的數(shù)據(jù)塊，其中Nc為投票者節(jié)點的數(shù)目。

POV機制中的普通接節(jié)點能夠隨時加入網(wǎng)絡(luò)，具有一定的擴展性，而且網(wǎng)絡(luò)中的節(jié)點具有不同的身份和職責(zé)，在一定程度上避免了中心化。VPBFT算法將POV機制引入PBFT算法，能夠利用POV機制動態(tài)性的特點彌補PBFT算法的不足。

2.2 VPBFT算法的網(wǎng)絡(luò)模型

在VPBFT算法中，將整個網(wǎng)絡(luò)中的節(jié)點分為四類：投票節(jié)點、生產(chǎn)節(jié)點、候選節(jié)點、普通節(jié)點。其網(wǎng)絡(luò)模型如圖2所示。

2.3 VPBFT算法的算法流程

VPBFT算法的算法流程可以分為兩個階段：準(zhǔn)備階段和確認(rèn)階段。其過程如下：

1）網(wǎng)絡(luò)中所有節(jié)點都能夠發(fā)生交易，并產(chǎn)生交易數(shù)據(jù)，交易池中存放著產(chǎn)生的大量有效的交易數(shù)據(jù)。

2）編號為i（i=R）的生產(chǎn)節(jié)點從交易池取出一些交易數(shù)據(jù)進行打包，將生產(chǎn)數(shù)據(jù)塊的請求以及所要生產(chǎn)的數(shù)據(jù)塊廣播發(fā)送給投票節(jié)點。這一階段為準(zhǔn)備階段。其中R為隨機數(shù)，包含在上一個生產(chǎn)節(jié)點生成的數(shù)據(jù)塊中，若生產(chǎn)者將要生產(chǎn)的數(shù)據(jù)塊是創(chuàng)世塊，則R為0。

3）投票節(jié)點收到請求后對收到的數(shù)據(jù)塊進行驗證，驗證數(shù)據(jù)塊沒有被惡意篡改后，進行簽名和加蓋時間戳，廣播回復(fù)確認(rèn)消息及該數(shù)據(jù)塊，此階段為確認(rèn)階段。

4）生產(chǎn)節(jié)點在收到至少1+Nv/2個投票節(jié)點的確認(rèn)消息后，生產(chǎn)該數(shù)據(jù)塊。若在一定的時間內(nèi)該生產(chǎn)節(jié)點沒有生成數(shù)據(jù)塊，則由編號為R+1的生產(chǎn)節(jié)點繼續(xù)生成數(shù)據(jù)塊，重復(fù)過程2）。

整個過程簡化后如圖3所示。

在上述過程中，生產(chǎn)節(jié)點需要在其任命周期Tp內(nèi)生成Bp個數(shù)據(jù)塊。其中：前Bp-1個塊為普通數(shù)據(jù)塊，包含交易數(shù)據(jù)、時間戳、投票節(jié)點驗證后的簽名及加蓋的時間戳等信息;最后一個為特殊數(shù)據(jù)塊，不包含交易數(shù)據(jù)，包含投票節(jié)點給出的票數(shù)信息，用以確定下一輪生產(chǎn)數(shù)據(jù)塊的生產(chǎn)節(jié)點。一輪的周期為T，每一輪生產(chǎn)者節(jié)點的數(shù)目為Np，每個生產(chǎn)節(jié)點的任命周期為Tp，則T=Np×Tp。投票節(jié)點是否對生產(chǎn)節(jié)點進行投票使其進入下一輪，依據(jù)的是它們在本輪的表現(xiàn)：若候選節(jié)點成功被投票成為生產(chǎn)者節(jié)點，則加1分;在一輪之內(nèi)，生產(chǎn)節(jié)點表現(xiàn)誠實并在其任期內(nèi)成功生產(chǎn)出有效的數(shù)據(jù)塊，則加1分，否則減1分。一輪結(jié)束后，獲得2分的生產(chǎn)節(jié)點將優(yōu)先被考慮進入下一輪。

2.5 K的取值

在確定隨機數(shù)R的過程中，投票數(shù)K是一個重要參數(shù)，那么，在網(wǎng)絡(luò)中，如何獲得K的值呢？假設(shè)在每一輪中每個投票節(jié)點投出K票，不考慮評分的影響，投票時隨機的，且分別投給Nc個候選節(jié)點中的K個節(jié)點，則每個獲選節(jié)點獲得一票的概率相同，設(shè)為P1，由式（4）所得：

2.6 VPBFT算法小結(jié)

VPBFT算法充分應(yīng)用了POV機制，將網(wǎng)絡(luò)中的節(jié)點劃分為四類具有不同職責(zé)的節(jié)點，并賦予一定的數(shù)量關(guān)系。根據(jù)前文對隨機數(shù)R以及最佳投票數(shù)K計算的描述可知，當(dāng)節(jié)點數(shù)目發(fā)生動態(tài)變化時，系統(tǒng)可自行根據(jù)相應(yīng)的公式計算相應(yīng)的參數(shù)，無需重新啟動系統(tǒng)，確保了算法的動態(tài)性和可擴展性。另外，在本文算法中，節(jié)點的投票權(quán)和生產(chǎn)權(quán)是分開的，能夠確保算法的獨立性。

3 性能分析

本文提出的VPBFT算法，是在PBFT算法的基礎(chǔ)上引入POV機制，具有一定的動態(tài)性，同時在功耗、時延、動態(tài)性等方面也得到了進一步的改善。在配置為I5-8250U處理器、8GB內(nèi)存、256GHz固態(tài)硬盤（Solid State Drive， SSD）的Windows 10系統(tǒng)下，通過Matlab 2017a對VPBFT算法、PBFT算法以及DDBFT算法、CBFT算法等針對PBFT算法進行改進的算法作數(shù)學(xué)計算仿真。

3.1 低功耗

在整個網(wǎng)絡(luò)中，每一種算法都需要進行數(shù)據(jù)傳輸，其所需要使用的網(wǎng)絡(luò)帶寬可用式（8）表示：

其中：Bandwith為所需要使用的網(wǎng)絡(luò)帶寬;N為網(wǎng)絡(luò)中的節(jié)點總數(shù);Blocksize為傳輸數(shù)據(jù)的大小，在區(qū)塊鏈應(yīng)用中，一個區(qū)塊的大小約為990KB。由式（8）可以看出，在Blocksize大小一定時，隨著N的增加，所需要使用的網(wǎng)絡(luò)帶寬隨之增加，如圖5的Bandwith。

3.1.1 與PBFT算法比較

在前文中已知，PBFT算法的整個過程分為預(yù)準(zhǔn)備、準(zhǔn)備和確認(rèn)三個階段，具有三次信息數(shù)據(jù)的廣播傳輸;而VPBFT算法僅有準(zhǔn)備和確認(rèn)兩個階段，具有兩次信息數(shù)據(jù)的廣播傳輸。因此假設(shè)兩種算法中的節(jié)點數(shù)目一致，則兩種算法每次廣播信息數(shù)據(jù)消耗的帶寬一樣，均為Bandwith。則在整體上，VPBFT算法則消耗帶寬為2倍的Bandwith，即圖5中的Bandwith1，PBFT算法消耗的帶寬為3倍的Bandwith，如圖5中的Bandwith2。

3.1.2 與DDBFT算法比較

DDBFT算法是將DPOS機制應(yīng)用于PBFT算法，使得PBFT算法具有動態(tài)性。該算法整個共識過程為共識提案和共識確認(rèn)兩個階段。共識提案階段由主節(jié)點先廣播交易數(shù)據(jù)，經(jīng)過一定的時間后再廣播共識提案;共識確認(rèn)階段由其他節(jié)點在對收到的交易數(shù)據(jù)進行驗證后向主節(jié)點回復(fù)確認(rèn)消息，若驗證失敗則廣播發(fā)送配置變更消息。除此之外，在共識過程之前，網(wǎng)絡(luò)中的代表節(jié)點需要廣播告知其余節(jié)點自己的身份。因此，在DDBFT算法中，具有四次信息數(shù)據(jù)的廣播傳輸。在同一網(wǎng)絡(luò)環(huán)境中，假設(shè)DDBFT算法與VPBFT算法中的節(jié)點數(shù)目一定，則兩種算法每次廣播傳輸?shù)男畔?shù)據(jù)消耗的帶寬一樣，均為Bandwith。那么，在整體上，DDBFT算法消耗的帶寬為4倍的Bandwith，如圖5中的Bandwith3。

3.1.3 與CBFT算法比較

CBFT算法是以PBFT算法為基礎(chǔ)，通過區(qū)塊緩存、區(qū)塊同步與簽名、節(jié)點變更實現(xiàn)等三個階段來實現(xiàn)的。該算法仍具有PBFT算法流程的三階段，只是當(dāng)備份節(jié)點向所有副本節(jié)點廣播發(fā)送準(zhǔn)備消息時，其他副本節(jié)點會率先形成確認(rèn)消息，在收到準(zhǔn)備消息后進行驗證。若驗證可靠則直接發(fā)送已形成的確認(rèn)消息，否則更改確認(rèn)消息后再發(fā)送。因此，CBFT算法對網(wǎng)絡(luò)帶寬的消耗同PBFT算法，為3倍的Bandwith，如圖5中的Bandwith4。

3.2 可靠性

為了能夠獲得投票節(jié)點的投票和認(rèn)可，生產(chǎn)節(jié)點在贏得投票后，在其任命周期內(nèi)必須誠實地工作，生產(chǎn)出有效的數(shù)據(jù)塊，完成自己的任務(wù)。在VPBFT算法中，生產(chǎn)節(jié)點會越來越可靠。如果生產(chǎn)節(jié)點在任命期內(nèi)沒有生成有效的數(shù)據(jù)塊，且有如惡意篡改數(shù)據(jù)等不誠實行為，或者其生產(chǎn)的數(shù)據(jù)塊不被投票節(jié)點認(rèn)可，那么它的分?jǐn)?shù)將會下降，在下一輪中它被投票的可能性將會降低甚至可能得不到投票。沒有獲得投票的生產(chǎn)節(jié)點將失去生產(chǎn)數(shù)據(jù)塊的機會，同時也就失去了獲得工資的機會。由VPBFT算法的過程可知，候選節(jié)點成功被投票成為生產(chǎn)者節(jié)點時可獲得1分，若在一輪之內(nèi)，表現(xiàn)誠實并在任期內(nèi)成功生產(chǎn)出有效的數(shù)據(jù)塊，再加1分;否則減1分。一輪之后，可靠的節(jié)點獲得2分，惡意節(jié)點獲得0分。因此，惡意節(jié)點將難以獲得投票，而可靠的生產(chǎn)節(jié)點更有可能被投票，從而使得整個系統(tǒng)更加地可靠?？梢酝ㄟ^投票數(shù)K、生產(chǎn)節(jié)點獲得工資W來調(diào)整控制生產(chǎn)節(jié)點的可靠性。

首先是投票數(shù)K。假設(shè)參數(shù)A的大小為候選節(jié)點因獲得評分高低而被投票的可能性的大小，則候選節(jié)點被成功投票為生產(chǎn)節(jié)點的概率可用式（9）表示：

3.3 動態(tài)性

PBFT算法是基于狀態(tài)機復(fù)制原理的，采用C/S的請求響應(yīng)模式，是靜態(tài)網(wǎng)絡(luò)拓撲結(jié)構(gòu)的算法，無法動態(tài)地感知節(jié)點加入或離開網(wǎng)絡(luò)，尤其是節(jié)點數(shù)目増加時，更是無法感知，甚至需要重新啟動系統(tǒng)，重新開始計算、傳輸信息數(shù)據(jù)。一旦節(jié)點數(shù)目發(fā)生變化，且未重新啟動系統(tǒng)，仍按照之前的節(jié)點數(shù)目進行運算，將使得新加入的節(jié)點資源的浪費或為不存在節(jié)點占用一定的系統(tǒng)資源。VPBFT算法在一定程度上解決了動態(tài)性的問題。

VPBFT算法，將整個網(wǎng)絡(luò)系統(tǒng)中的節(jié)點劃分為四類并加以量化，其中投票節(jié)點能夠?qū)ιa(chǎn)節(jié)點進行評分以及對候選節(jié)點進行投票。被投票選中的候選節(jié)點成為生產(chǎn)節(jié)點并在投票節(jié)點的監(jiān)督下進行數(shù)據(jù)塊的生產(chǎn)。根據(jù)式（1）可知，一旦節(jié)點發(fā)生變化，相應(yīng)的節(jié)點參數(shù)Nv、Nc、Np、No也將發(fā)生變化，根據(jù)式（6）和式（7）即可求得相應(yīng)的K值和R值，從而確定投票數(shù)和第一個生產(chǎn)數(shù)據(jù)塊的生產(chǎn)節(jié)點，相應(yīng)地，也能夠調(diào)整最大容忍惡意節(jié)點的數(shù)目。

由此可見，相對于PBFT算法，VPBFT算法能夠動態(tài)地感知節(jié)點加入或離開網(wǎng)絡(luò)，當(dāng)節(jié)點數(shù)目増加時，不需要重新啟動系統(tǒng)，不會出現(xiàn)新加入的節(jié)點資源的浪費或為不存在節(jié)點占用一定的系統(tǒng)資源的情況。

3.4 容錯性

在VPBFT算法中能夠容忍的失效節(jié)點數(shù)f1不超過1+Nv/2，最多為Nv/2，其中Nv為網(wǎng)絡(luò)中投票節(jié)點的數(shù)目。在PBFT算法中，所有節(jié)點被分為三種類型：客戶節(jié)點、主節(jié)點和備份節(jié)點。其中，主節(jié)點和備份節(jié)點被稱為副本節(jié)點，且副本節(jié)點總數(shù)為Nt，編號為{0，1，… ，Nt-1}。PBFT算法中最多能夠容忍的惡意節(jié)點數(shù)為f2=（Nt-1）/3。假設(shè)Nv=Nt，也就是在兩種算法中對數(shù)據(jù)具有驗證權(quán)的節(jié)點數(shù)目相同的前提下，通過式（10）可以得到f2

3.5 低時延

在計算機網(wǎng)絡(luò)中，時延包括發(fā)送時延、處理時延、傳輸時延。同一個網(wǎng)絡(luò)環(huán)境中，PBFT算法與VPBFT算法對于信息數(shù)據(jù)的發(fā)送時延是一樣的，且每次對數(shù)據(jù)的處理時延也是一樣的。但是，PBFT算法是三階段三廣播，對數(shù)據(jù)進行三次處理時延，而VPBFT算法是二階段二廣播，只有兩次處理時延。因此，VPBFT算法的總處理時延低于PBFT算法。同時，VPBFT算法有效地提高了信息數(shù)據(jù)的傳輸速率，縮短了傳輸時間。因此，VPBFT算法與PBFT算法相比有效地降低了傳輸信息數(shù)據(jù)的時延，提高了效率。

3.6 安全性

假設(shè)在VPBFT算法中非法數(shù)據(jù)塊能夠被驗證通過。那么，由于生產(chǎn)節(jié)點必須獲取至少1+Nv/2的投票節(jié)點的確認(rèn)消息才能確定生產(chǎn)該數(shù)據(jù)塊，所以在有效的投票節(jié)點數(shù)量多于1+Nv/2的情況下，有效投票節(jié)點不會認(rèn)可非法數(shù)據(jù)塊。因此，非法數(shù)據(jù)塊得到的確認(rèn)消息最多為Nv-（1+Nv/2）=Nv/2-1，不能夠被驗證通過。這與假設(shè)相矛盾，因此假設(shè)不成立，非法數(shù)據(jù)塊不能夠被驗證通過，VPBFT算法具有一定的安全性。

4 結(jié)語

本文介紹了拜占庭問題以及一些共識算法，如POW、Paxos、Raft和PBFT算法以及對PBFT進行改進的算法：DDBFT、CBFT等。通過分析對比已有算法，發(fā)現(xiàn)各有不足，其中PBFT算法的三階段三廣播，浪費了一定的網(wǎng)絡(luò)帶寬，且無法感知網(wǎng)絡(luò)中節(jié)點數(shù)目的變動，不具備動態(tài)性;DDBFT算法和CBFT算法，雖然在一定程度上具備了動態(tài)性，但其容錯性、能耗方面還存在缺陷。針對這些不足，尤其是PBFT算法的不足之處，本文提出了VPBFT算法。該算法以PBFT算法為基礎(chǔ)，引入投票機制，將網(wǎng)絡(luò)中的節(jié)點劃分為四類，不同身份的節(jié)點具有不同的職責(zé)，在一定程度上弱化了中心制。該算法中，各類節(jié)點之間具有一定的數(shù)量關(guān)系，當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)目發(fā)生變動時，能夠根據(jù)數(shù)量關(guān)系進行相關(guān)參數(shù)的調(diào)整，無需重新啟動系統(tǒng)，具有一定的動態(tài)性。通過對比可知，與PBFT算法相比，VPBFT算法具有更低的能耗和時延、更高的容錯性，以及一定的動態(tài)性和可靠性;與DDBFT算法相比，VPBFT算法具有更低的能耗和時延、更高的容錯性;與CBFT算法相比，VPBFT算法具有更低的能耗和時延。但VPBFT算法還存在一些問題，如在容錯性上不能夠保證高于CBFT算法、節(jié)點處理數(shù)據(jù)能力有限等，需要更深入的研究。

參考文獻 （References）

[1] NAKAMOTO S. Bitcoin： a peer-to-peer electronic cash system [EB/OL]. [2018-08-18]. https：//www.audible.com/pd/Bitcoin-A-Peer-to-Peer-Electronic-Cash-System-Audiobook/B077T5SCP2.

[2] 長鋏，韓鋒.區(qū)塊鏈：從數(shù)字貨幣到信用社會[M].北京：中信出版社，2016：54-63.（CHANG J， HAN F. Blockchain： from Digital Currency to Credit Society [M]. Beijing： CITIC Press， 2016： 54-63.）

[3] BRACHA G， TOUEG S. Asynchronous consensus and broadcast protocols [J]. Journal of the ACM， 1985，3 2（4）： 824-840.

[4] LAMPORT L， SHOSTAK R， PEASE M. The Byzantine generals problem [J]. ACM Transactions on Programming Languages & Systems， 1982， 4（3）： 382-401.

[5] 李劍鋒.基于拜占庭容錯機制的區(qū)塊鏈共識算法研究與應(yīng)用[D].鄭州：鄭州大學(xué)，2018：14-15，31-56.（LI J F. Research and application of? blockchain consensus algorithm based on Byzantine fault tolerance mechanism [D]. Zhengzhou： Zhengzhou University， 2018： 14-15， 31-56.）

[6] LAMPORT L. The part-time parliament [J]. ACM Transactions on Computing Surveys， 1998， 16（2）： 133-169.

[7] ONGARO D， OUSTERHOUT J. In search of an understandable consensus algorithm [C]// ATC14： Proceedings of the 2014 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2014： 305-319.

[8] REITER M K. A secure group membership protocol [J]. IEEE Transactions on? Software Engineering， 1996， 22（1）： 31-42.

[9] ANDROUTSELLIS-THEOTOKIS? S， SPINELLIS D， et al. A survey of peer-to-peer content distribution technologies [J]. ACM Transactions on? Computing Surveys， 2004， 36（4）： 335-371.

[10] 劉肖飛.基于動態(tài)授權(quán)的拜占庭容錯共識算法的區(qū)塊鏈性能改進研究[D].杭州：浙江大學(xué)，2017：41-67.（LIU X F. Research on performance improvement of blockchain based on dynamic authorized Byzantine fault tolerance consensus algorithm [D]. Hangzhou： Zhejiang University， 2017： 41-67.）

[11] JDON.分布式系統(tǒng)Paxos算法[EB/OL]. [2018-08-18]. https：//www.jdon.com/artichect/paxos.html.（JDON.Distributed system Paxos algorithm [EB/OL].[2018-08-18]. https：//www.jdon.com/artichect/paxos.html.）

[12] ONGARO D， OUSTERHOUT J. In search of an understandable consensus algorithm （extended version） [EB/OL]. [2018-08-18]. https：//raft.github.io/raft.pdf.

[13] CASTRO M， LISKOV B. Practical Byzantine fault tolerance [C]// Proceeding of the 1999 Third Symposium on Operating Systems Design and Implementation. Berkeley， CA： USENIX association， 1999： 173-186.

[14] LI K， LI H， HOU H， et al. Proof of vote： a high-performance consensus protocol based on vote mechanism & consortium? blockchain [C]// Proceedings of the 2017 IEEE International Conference on High Performance Computing and Communications， IEEE International Conference on Smart City， IEEE International Conference on Data Science and Systems. Piscataway， NJ： IEEE， 2017： 466-473.

[15] DWORK C， NAOR M. Pricing via processing， or， combating junk mail [C]// Proceedings of the 1993 12th Annual International Cryptology Conference， LNCS 1328. Berlin： Springer， 1993： 139-147.