基于投票机制的拜占庭容错共识算法

王海勇 郭凯璇 潘启青

摘 要：针对现有的区块链中实用拜占庭容错（PBFT）共识算法、基于动态授权的拜占庭容错（DDBFT）共识算法、联盟拜占庭容错（CBFT）共识算法普遍存在能耗高、效率低、扩展性差等问题，通过引入投票机制，提出了基于投票机制的拜占庭容错（VPBFT）共识算法。首先，以PBFT算法为基础，将网络中的节点划分为四类具有不同职责的节点。其次，算法中的投票节点具有投票和评分权，监督生产节点诚实可靠地生产数据块;生产有效的数据块的生产节点优先进入下一轮，候选节点能够被选为生产节点，而普通节点则能够成为投票节点或候选节点。最后，不同类型的节点之间具有一定的数量关系，能够在不同类型节点的数目或网络中的节点总数发生变化时动态调整参数，从而使得算法适应动态网络。通过性能仿真分析可知，VPBFT算法相较于PBFT、 DDBFT、CBFT等共识算法，具有低能耗、低时延、高容错性和高动态性。

关键词：区块链;拜占庭容错;投票机制;共识算法;数据块

中图分类号： TP301.6

文献标志码：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年 “一種完全通过点对点技术实现的电子现金货币”（即比特币）[1]被提出起，区块链技术正一步一步地得到重视。区块链具有去中心化、分布式、点对点等特点[2]，随着区块链技术的发展，各种共识算法也层出不穷，比如工作量证明（Proof Of Work， POW）算法[1]、实用拜占庭容错（Practical Byzantine Fault Tolerance， PBFT）算法[3]等。

拜占庭将军问题（Byzantine generals problem）是区块链中共识算法会考虑到的基本问题[4]。这是一个描述分布式系统一致性的协议问题，拜占庭的将军们必须全体一致决定是否同时对敌军发起攻击，但在将军中存在叛徒，叛徒会发出虚假信息来影响其他将军们的决定，将军们如何在存有叛徒的前提下达成一致的决定，并最终获得胜利正是该问题所要解决的。拜占庭容错问题，在计算机领域可以表述为：如何在存有恶意节点的系统网络中确保系统运行的良好以及信息数据的完整、可靠和一致性，从而作出正确的决策。

在目前现有的共识算法中，较为经典的分布式一致性算法[5]有Paxos算法[6]、Raft算法[7]和PBFT算法。但是，Paxos算法和Raft算法均是面向数据而不是面向交易的，并未考虑到拜占庭问题，即没有考虑系统中存在恶意节点的情况，一旦系统内的恶意节点发送虚假消息，那么整个系统将会存储虚假错误的信息。为解决拜占庭问题，PBFT算法[3， 8]被提出，通过大多数诚实节点来忽略掉恶意节点的消息，该算法能够容忍不超过（n-1）/3个节点失效（其中n为节点总数）。但是PBFT算法采用的是C/S架构[7，9]，不能适应P2P网络，无法动态感知节点数目的变化。

随着区块链技术的进一步发展，一些新的共识算法也层出不穷，其证明方式趋向于多样化和混合化。基于动态授权的拜占庭容错（Dynamic authorized Byzantine Fault Tolerance， DDBFT）算法[10]，将委托权益证明（Delegated Proof Of Stake， DPOS）算法应用于PBFT算法，使得PBFT算法具有动态性的特点，同时也能够提高吞吐量、降低时延，但是由于网络带宽有限，需要确认的区块较大且超出一个节点的处理能力，就会造成阻塞、降低吞吐量。联盟拜占庭容错（Consortium Byzantine Fault Tolerance， CBFT）算法[5]，以PBFT算法为基础，通过区块缓存、区块同步与签名、节点变更实现，具有更高的吞吐量和较低的时延，但是其交易处理的效率和达成共识的效率等需要进一步提升。

在对比分析了已有的一些共识算法后，本文提出了一种改进的PBFT算法，即基于投票机制的拜占庭容错（PBFT based on Voting， VPBFT）共识算法，将投票证明（Proof Of Vote， POV）与PBFT结合，具有低能耗、低时延、高容错性和高动态性。

1 相关工作

从Paxos算法到Raft算法，再到PBFT算法，以及对PBFT算法改进后形成的基于动态授权的拜占庭容错（DDBFT）共识算法和联盟拜占庭容错（CBFT）共识算法，均针对解决分布式系统的一致性问题。

Paxos算法[6]是基于消息传递的，旨在解决在分布式系统内如何就某一个内容达成一致的问题[11]，在分布式系统内的所有节点的初始状态一致，在执行了相同的操作后，所有节点就能够得到一致的结果。Paxos算法具有高度的容错性，但较为难懂且难以实现，于是出现了它的简化版——Raft算法[12]。但是，Paxos和Raft算法是面向数据而不是面向交易的，没有考虑系统中存在恶意节点的情况，一旦系统内的恶意节点发送虚假消息，那么整个系统将会存储虚假错误的信息。

除此之外， PBFT算法[13]也是专门针对解决拜占庭将军问题的算法，该算法旨在解决如何在整个网络中存在恶意节点的情况下保证最终决策的一致性、正确性的问题。在PBFT算法中，所有节点被分为客户节点、主节点和备份节点3种类型，其中，主节点和备份节点被称为副本节点。该算法流程分为3个阶段：预准备阶段、准备阶段、确认阶段。具体过程如图1所示。

当客户节点收到至少n+1个副本节点的结果是相同的情况下，才认可结果有效。PBFT算法针对分布式系统，而且系统中的指令顺序执行，是基于C/S架构的[8，10]。算法的整个过程分为三阶段，具有三次信息的广播，这对网络带宽造成了一定的浪费。另外，在PBFT算法中，整个网络的节点数目固定，一旦发生变动系统无法感知，不具备扩展性。

除了Paxos算法、Raft算法和PBFT算法等经典的共识算法外，还有一些新提出的针对PBFT算法进行改进的算法：DDBFT算法、CBFT算法。DDBFT算法，主要针对PBFT算法缺乏动态性的不足，将DPOS算法应用于PBFT算法，使得PBFT算法具有动态性的特点，同时也能够提高吞吐量、降低时延，但是由于网络带宽有限，需要确认的区块较大且超出一个节点的处理能力，就会造成阻塞，降低吞吐量。CBFT算法，是以PBFT算法为基础，通过区块缓存、区块同步与签名、节点变更实现，具有更高的吞吐量和较低的时延，但是其交易处理的效率和达成共识的效率等需要进一步提升，且在共识流程、区块同步和节点管理方面仍存在问题。

由此可见，每种算法都具有其各自的优势及不足。其中，PBFT算法扩展性较差，不能够适应动态变化的网络系统。DDBFT和CBFT算法虽然在能耗、吞吐量、扩展性等方面有所改进，但仍然存在效率低、能耗高等不同的问题。由此可见，共识算法仍有一定的改进空间。

2 基于投票机制的拜占庭容错共识算法

通过对已有算法的分析，尤其是分布式系统的共识算法：PBFT算法、DDBFT算法、CBFT算法等，本文针对这些共识算法的不足之处，提出了VPBFT共識算法。在本文算法中，将POV机制应用于传统的PBFT算法，将网络中的节点划分为四类，不同类别的节点具有不同的职责，不同类别的节点之间具有一定的数量关系。

2.1 POV机制

POV机制将整个联盟网络中的节点分为四类：投票者、管理者、候选人、普通用户[14]。其中，投票者具有推荐、投票管理者的权利，能够对产生的交易进行验证和转发，也能够对产生的区块进行验证;管理者只能来自于候选人，被随机地指定生成区块，有一定的任命周期，周期结束后重新被投票;候选人，由经过注册并获得多于1名投票者推荐的普通用户组成，也可以是投票者自荐组成;而普通用户则可以随时加入和退出。网络中所有节点都能够发生、转发并验证交易数据，数据有效才发送给投票者和管理者，并由管理者将数据放入交易池。而管理者被任命在其任命周期里生产块，且需要至少1+Nc/2个投票者的同意才能生产相应的数据块，其中Nc为投票者节点的数目。

POV机制中的普通接节点能够随时加入网络，具有一定的扩展性，而且网络中的节点具有不同的身份和职责，在一定程度上避免了中心化。VPBFT算法将POV机制引入PBFT算法，能够利用POV机制动态性的特点弥补PBFT算法的不足。

2.2 VPBFT算法的网络模型

在VPBFT算法中，将整个网络中的节点分为四类：投票节点、生产节点、候选节点、普通节点。其网络模型如图2所示。

2.3 VPBFT算法的算法流程

VPBFT算法的算法流程可以分为两个阶段：准备阶段和确认阶段。其过程如下：

1）网络中所有节点都能够发生交易，并产生交易数据，交易池中存放着产生的大量有效的交易数据。

2）编号为i（i=R）的生产节点从交易池取出一些交易数据进行打包，将生产数据块的请求以及所要生产的数据块广播发送给投票节点。这一阶段为准备阶段。其中R为随机数，包含在上一个生产节点生成的数据块中，若生产者将要生产的数据块是创世块，则R为0。

3）投票节点收到请求后对收到的数据块进行验证，验证数据块没有被恶意篡改后，进行签名和加盖时间戳，广播回复确认消息及该数据块，此阶段为确认阶段。

4）生产节点在收到至少1+Nv/2个投票节点的确认消息后，生产该数据块。若在一定的时间内该生产节点没有生成数据块，则由编号为R+1的生产节点继续生成数据块，重复过程2）。

整个过程简化后如图3所示。

在上述过程中，生产节点需要在其任命周期Tp内生成Bp个数据块。其中：前Bp-1个块为普通数据块，包含交易数据、时间戳、投票节点验证后的签名及加盖的时间戳等信息;最后一个为特殊数据块，不包含交易数据，包含投票节点给出的票数信息，用以确定下一轮生产数据块的生产节点。一轮的周期为T，每一轮生产者节点的数目为Np，每个生产节点的任命周期为Tp，则T=Np×Tp。投票节点是否对生产节点进行投票使其进入下一轮，依据的是它们在本轮的表现：若候选节点成功被投票成为生产者节点，则加1分;在一轮之内，生产节点表现诚实并在其任期内成功生产出有效的数据块，则加1分，否则减1分。一轮结束后，获得2分的生产节点将优先被考虑进入下一轮。

2.5 K的取值

在确定随机数R的过程中，投票数K是一个重要参数，那么，在网络中，如何获得K的值呢？假设在每一轮中每个投票节点投出K票，不考虑评分的影响，投票时随机的，且分别投给Nc个候选节点中的K个节点，则每个获选节点获得一票的概率相同，设为P1，由式（4）所得：

2.6 VPBFT算法小结

VPBFT算法充分应用了POV机制，将网络中的节点划分为四类具有不同职责的节点，并赋予一定的数量关系。根据前文对随机数R以及最佳投票數K计算的描述可知，当节点数目发生动态变化时，系统可自行根据相应的公式计算相应的参数，无需重新启动系统，确保了算法的动态性和可扩展性。另外，在本文算法中，节点的投票权和生产权是分开的，能够确保算法的独立性。

3 性能分析

本文提出的VPBFT算法，是在PBFT算法的基础上引入POV机制，具有一定的动态性，同时在功耗、时延、动态性等方面也得到了进一步的改善。在配置为I5-8250U处理器、8GB内存、256GHz固态硬盘（Solid State Drive， SSD）的Windows 10系统下，通过Matlab 2017a对VPBFT算法、PBFT算法以及DDBFT算法、CBFT算法等针对PBFT算法进行改进的算法作数学计算仿真。

3.1 低功耗

在整个网络中，每一种算法都需要进行数据传输，其所需要使用的网络带宽可用式（8）表示：

其中：Bandwith为所需要使用的网络带宽;N为网络中的节点总数;Blocksize为传输数据的大小，在区块链应用中，一个区块的大小约为990KB。由式（8）可以看出，在Blocksize大小一定时，随着N的增加，所需要使用的网络带宽随之增加，如图5的Bandwith。

3.1.1 与PBFT算法比较

在前文中已知，PBFT算法的整个过程分为预准备、准备和确认三个阶段，具有三次信息数据的广播传输;而VPBFT算法仅有准备和确认两个阶段，具有两次信息数据的广播传输。因此假设两种算法中的节点数目一致，则两种算法每次广播信息数据消耗的带宽一样，均为Bandwith。则在整体上，VPBFT算法则消耗带宽为2倍的Bandwith，即图5中的Bandwith1，PBFT算法消耗的带宽为3倍的Bandwith，如图5中的Bandwith2。

3.1.2 与DDBFT算法比较

DDBFT算法是将DPOS机制应用于PBFT算法，使得PBFT算法具有动态性。该算法整个共识过程为共识提案和共识确认两个阶段。共识提案阶段由主节点先广播交易数据，经过一定的时间后再广播共识提案;共识确认阶段由其他节点在对收到的交易数据进行验证后向主节点回复确认消息，若验证失败则广播发送配置变更消息。除此之外，在共识过程之前，网络中的代表节点需要广播告知其余节点自己的身份。因此，在DDBFT算法中，具有四次信息数据的广播传输。在同一网络环境中，假设DDBFT算法与VPBFT算法中的节点数目一定，则两种算法每次广播传输的信息数据消耗的带宽一样，均为Bandwith。那么，在整体上，DDBFT算法消耗的带宽为4倍的Bandwith，如图5中的Bandwith3。

3.1.3 与CBFT算法比较

CBFT算法是以PBFT算法为基础，通过区块缓存、区块同步与签名、节点变更实现等三个阶段来实现的。该算法仍具有PBFT算法流程的三阶段，只是当备份节点向所有副本节点广播发送准备消息时，其他副本节点会率先形成确认消息，在收到准备消息后进行验证。若验证可靠则直接发送已形成的确认消息，否则更改确认消息后再发送。因此，CBFT算法对网络带宽的消耗同PBFT算法，为3倍的Bandwith，如图5中的Bandwith4。

3.2 可靠性

为了能够获得投票节点的投票和认可，生产节点在赢得投票后，在其任命周期内必须诚实地工作，生产出有效的数据块，完成自己的任务。在VPBFT算法中，生产节点会越来越可靠。如果生产节点在任命期内没有生成有效的数据块，且有如恶意篡改数据等不诚实行为，或者其生产的数据块不被投票节点认可，那么它的分数将会下降，在下一轮中它被投票的可能性将会降低甚至可能得不到投票。沒有获得投票的生产节点将失去生产数据块的机会，同时也就失去了获得工资的机会。由VPBFT算法的过程可知，候选节点成功被投票成为生产者节点时可获得1分，若在一轮之内，表现诚实并在任期内成功生产出有效的数据块，再加1分;否则减1分。一轮之后，可靠的节点获得2分，恶意节点获得0分。因此，恶意节点将难以获得投票，而可靠的生产节点更有可能被投票，从而使得整个系统更加地可靠。可以通过投票数K、生产节点获得工资W来调整控制生产节点的可靠性。

首先是投票数K。假设参数A的大小为候选节点因获得评分高低而被投票的可能性的大小，则候选节点被成功投票为生产节点的概率可用式（9）表示：

3.3 动态性

PBFT算法是基于状态机复制原理的，采用C/S的请求响应模式，是静态网络拓扑结构的算法，无法动态地感知节点加入或离开网络，尤其是节点数目増加时，更是无法感知，甚至需要重新启动系统，重新开始计算、传输信息数据。一旦节点数目发生变化，且未重新启动系统，仍按照之前的节点数目进行运算，将使得新加入的节点资源的浪费或为不存在节点占用一定的系统资源。VPBFT算法在一定程度上解决了动态性的问题。

VPBFT算法，将整个网络系统中的节点划分为四类并加以量化，其中投票节点能够对生产节点进行评分以及对候选节点进行投票。被投票选中的候选节点成为生产节点并在投票节点的监督下进行数据块的生产。根据式（1）可知，一旦节点发生变化，相应的节点参数Nv、Nc、Np、No也将发生变化，根据式（6）和式（7）即可求得相应的K值和R值，从而确定投票数和第一个生产数据块的生产节点，相应地，也能够调整最大容忍恶意节点的数目。

由此可见，相对于PBFT算法，VPBFT算法能够动态地感知节点加入或离开网络，当节点数目増加时，不需要重新启动系统，不会出现新加入的节点资源的浪费或为不存在节点占用一定的系统资源的情况。

3.4 容错性

在VPBFT算法中能够容忍的失效节点数f1不超过1+Nv/2，最多为Nv/2，其中Nv为网络中投票节点的数目。在PBFT算法中，所有节点被分为三种类型：客户节点、主节点和备份节点。其中，主节点和备份节点被称为副本节点，且副本节点总数为Nt，编号为{0，1，… ，Nt-1}。PBFT算法中最多能够容忍的恶意节点数为f2=（Nt-1）/3。假设Nv=Nt，也就是在两种算法中对数据具有验证权的节点数目相同的前提下，通过式（10）可以得到f2

3.5 低时延

在计算机网络中，时延包括发送时延、处理时延、传输时延。同一个网络环境中，PBFT算法与VPBFT算法对于信息数据的发送时延是一样的，且每次对数据的处理时延也是一样的。但是，PBFT算法是三阶段三广播，对数据进行三次处理时延，而VPBFT算法是二阶段二广播，只有两次处理时延。因此，VPBFT算法的总处理时延低于PBFT算法。同时，VPBFT算法有效地提高了信息数据的传输速率，缩短了传输时间。因此，VPBFT算法与PBFT算法相比有效地降低了传输信息数据的时延，提高了效率。

3.6 安全性

假设在VPBFT算法中非法数据块能够被验证通过。那么，由于生产节点必须获取至少1+Nv/2的投票节点的确认消息才能确定生产该数据块，所以在有效的投票节点数量多于1+Nv/2的情况下，有效投票节点不会认可非法数据块。因此，非法数据块得到的确认消息最多为Nv-（1+Nv/2）=Nv/2-1，不能够被验证通过。这与假设相矛盾，因此假设不成立，非法数据块不能够被验证通过，VPBFT算法具有一定的安全性。

4 结语

本文介绍了拜占庭问题以及一些共识算法，如POW、Paxos、Raft和PBFT算法以及对PBFT进行改进的算法：DDBFT、CBFT等。通过分析对比已有算法，发现各有不足，其中PBFT算法的三阶段三广播，浪费了一定的网络带宽，且无法感知网络中节点数目的变动，不具备动态性;DDBFT算法和CBFT算法，虽然在一定程度上具备了动态性，但其容错性、能耗方面还存在缺陷。针对这些不足，尤其是PBFT算法的不足之处，本文提出了VPBFT算法。该算法以PBFT算法为基础，引入投票机制，将网络中的节点划分为四类，不同身份的节点具有不同的职责，在一定程度上弱化了中心制。该算法中，各类节点之间具有一定的数量关系，当网络中节点数目发生变动时，能够根据数量关系进行相关参数的调整，无需重新启动系统，具有一定的动态性。通过对比可知，与PBFT算法相比，VPBFT算法具有更低的能耗和时延、更高的容错性，以及一定的动态性和可靠性;与DDBFT算法相比，VPBFT算法具有更低的能耗和时延、更高的容错性;与CBFT算法相比，VPBFT算法具有更低的能耗和时延。但VPBFT算法还存在一些问题，如在容错性上不能够保证高于CBFT算法、节点处理数据能力有限等，需要更深入的研究。

参考文献 （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] 长铗，韩锋.区块链：从数字货币到信用社会[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] 李劍锋.基于拜占庭容错机制的区块链共识算法研究与应用[D].郑州：郑州大学，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].杭州：浙江大学，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.分布式系统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.