基于投票機(jī)制的拜占庭容錯(cuò)共識(shí)算法

王海勇 郭凱璇 潘啟青

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

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

中圖分類號(hào)： TP301.6

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

2 基于投票機(jī)制的拜占庭容錯(cuò)共識(shí)算法

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

2.1 POV機(jī)制

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

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

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

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

2.3 VPBFT算法的算法流程

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

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

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

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

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

整個(gè)過程簡化后如圖3所示。

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

2.5 K的取值

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

2.6 VPBFT算法小結(jié)

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

3 性能分析

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

3.1 低功耗

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

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

3.1.1 與PBFT算法比較

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

3.1.2 與DDBFT算法比較

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

3.1.3 與CBFT算法比較

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

3.2 可靠性

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

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

3.3 動(dòng)態(tài)性

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

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

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

3.4 容錯(cuò)性

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

3.5 低時(shí)延

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

3.6 安全性

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

4 結(jié)語

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

參考文獻(xiàn) （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ù)字貨幣到信用社會(huì)[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] 李劍鋒.基于拜占庭容錯(cuò)機(jī)制的區(qū)塊鏈共識(shí)算法研究與應(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] 劉肖飛.基于動(dòng)態(tài)授權(quán)的拜占庭容錯(cuò)共識(shí)算法的區(qū)塊鏈性能改進(jìn)研究[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.