具有监督机制的高效拜占庭容错算法

王日宏，邢聪颖，徐泉清，袁杉杉

1.青岛理工大学 信息与控制工程学院，山东 青岛266520

2.蚂蚁金服，杭州310012

随着比特币[1]的兴起，区块链技术也逐渐引起各界人士的兴趣。区块链综合了密码学、分布式等原理，具有去中心化、可追溯、不可篡改等特性[2]。共识机制作为区块链技术不可或缺的环节，决定着区块链系统的安全性。全节点的交互不需要提前信任其他节点，当某节点提出区块数据后，各节点通过既定的共识机制共同认证和操作数据，通过认证的区块将被加入到区块链中。因此，共识机制在区块链领域占据至关重要的位置。

根据应用场景及用户需求不同，区块链分为公有链、私有链以及联盟链三种。私有链的网络系统归属于特定的组织或机构，数据受限于这些弱中心化机构；公有链对中心化要求最高，允许节点参加链上数据的读写，并能够自由进出网络，其典型共识算法有工作量证明（Proof of Work，PoW）、权益证明（Proof of Stake，PoS）[3]以及授权股份证明（Delegated Proof of Stake，DPoS）[4]等。

联盟链中的节点是事先确定的，并且节点数量较为固定，节点信用度更高。联盟链共识算法分为非拜占庭容错共识算法和拜占庭容错算法。前者主要应用于系统存在故障，但是不存在恶意节点的场景，典型共识算法有Paxos[5]、Raft[6]等；后者应用于伪造信息、恶意响应的场景，在此种情境下，消息可能会被丢失、延迟、重放以及伪造等，典型共识算法有PBFT[7]、HotStuff BFT[8]等。即便是在信任度极高的联盟链中，理论上并不能排除恶意节点或网络环境导致的恶劣行为，况且现有的共识机制大都建立在特定理论假设情况下，例如PBFT共识算法适用于部分同步模式，其在异步模型下仍然面临系统不协调情形[9]。虽然PBFT算法日趋成熟，但是算法仍然对网络带宽要求较高，带宽随节点数量的增加呈多项式级增长，本文就PBFT在算法效率和异步网络环境中的实施问题做出研究，提出了一种高效监督拜占庭容错算法ES-BFT。

本文主要做出了以下贡献：

（1）ES-BFT算法将网络中的节点划分为节点簇，并设置信誉值机制，通过信誉值从节点簇中划分出共识节点与监督节点；共识节点执行PBFT算法。节点的选取机制降低了网络运行的成本，减小了网络带宽的开销，提升了算法的效率。

（2）引入监督机制，算法在PBFT的确认阶段向监督节点发送共识节点状态，及时制止系统不协调情况的发生。当满足系统不协调条件时，监督节点触发共识节点的状态调整。

（3）评估了ES-BFT算法，结果表明，它在效率（延迟和吞吐量）以及安全性上优于PBFT算法。

1 准备知识

1.1 区块链基本架构

区块链是实现了数据公开、透明以及可追溯的架构设计方法，其系统架构[10]分为以下五层：数据层、网络层、共识层、合约层、应用层，如图1所示。

图1 区块链的层级架构Fig.1 Hierarchical structure of blockchain

各层分别支持不同的核心功能，层级之间合作支撑，实现去中心化。数据层主要描述了区块链的底层数据结构；网络层通过P2P网络实现节点间的信息传播及验证等；共识层包含各类共识算法及激励机制，激励机制负责制定相关奖励措施，主要用于公有链，在联盟链中作用并不明显；合约层编程规定区块链的交易方式、流程细节等；应用层涵盖各类区块链应用。本文主要对网络层和共识层进行研究。

1.2 主流共识算法

区块链共识算法不断创新，经典的PBFT算法虽然带来了多项式级的算法突破，但仍然受到网络模型、算法复杂度、传播成本等的限制，因此专业人士在算法复杂度、容错能力以及网络模型方面做出了改进：

针对算法复杂度问题，MinBFT[11]通过可信执行环境，将PBFT的三阶段通信降为两阶段通信；SBFT[12]使用收集器降低通信量，同时使用门限签名降低收集器消息规模和验证签名总的开销，将客户端通信量由O(n)降到O(1)。

针对容错能力问题，可信执行环境的实施将部分算法（例如MinBFT、A2M[13]）的容错能力提升为2f+1。

针对网络模型问题，（1）部分共识算法以优化节点的选取为突破口，例如，BBFT[14]、BFT-DPOS[15]及DBFT[16]，此类共识算法通过让部分节点参与共识，提高共识效率；LgTTBFT[17]共识算法提出LgTree节点路由算法，实现了高效的查找效率；（2）部分共识以网络模型为突破口，Paxos、Hot-Stuff以及SBFT算法假设部分同步模式；OBFT[18]算法通过超时时间切换同步和部分同步网络中的拜占庭容错；MinBFT、HoneyBadger[19]等算法属于异步共识算法；Wang从GST（Global Stabilization Time）到来之前的视角分析了PBFT算法的缺陷，PBFT算法可能面临系统不协调的问题，在部分同步网络下并不适用于公链或联盟链。本文主要在PBFT网络节点选取和网络模型问题上做出研究。

1.3 PBFT算法

PBFT算法建立在假设部分同步模式下的拜占庭容错算法，即保证异步模式下的安全性（Safety）和同步模式下的活性（Liveness）。存在一个GST，在GST之后网络变为同步网络。

PBFT是一种状态机副本复制算法，所有副本在视图v的轮转过程中运作，主节点由p=vmod ||R得出，其中v为视图编号，R为副本节点数，p为主节点编号。同时通过超时机制检测主节点状态，当主节点出现问题，从节点触发视图切换机制。算法流程可以分为以下几步：

（1）客户端向主节点发送请求。

（2）主节点接收客户端发来的请求，按顺序对请求进行排序，并广播给从节点。

（3）所有副本节点通过准备和确认阶段两两进行交互。

（4）副本执行请求并将结果返回给客户端。

（5）假设最大拜占庭节点数为f，因此客户端需要等待f+1个不同节点返回的相同结果，才能达成共识。

算法设置View Change协议来解决主节点作恶或宕机的情况，主要通过以下两种方式：（1）副本节点通过检查主节点分配的序号合法性判断主节点状态，当序号不合法时，发起View Change协议；（2）客户端设置超时机制检测主节点掉线或作恶的问题，如果超时，向所有副本节点广播请求消息，副本节点发起View Change协议。

2 ES-BFT算法设计

2.1 算法介绍

由于无法预知PBFT算法的GST到来时间，因此在GST之前，消息传播不可靠，存在丢失（DoS攻击）、被排序等风险。ES-BFT算法旨在解决PBFT算法的系统不协调问题。具体分析了ES-BFT算法的设计内容，一是节点的选取，二是共识与监督的过程。

2.1.1 节点的选取

（1）节点划分

众所周知，DPoS共识机制是一种基于投票选举的共识机制，投票者根据其持有的代币量进行投票，选出101个节点轮流执行区块链的记账和上链等。本文将网络中的节点随机划分为多个节点簇，借鉴DPOS的算法思想，对节点簇中信誉值级别为A的节点进行选举，选举出的N个节点运行PBFT共识，剩余信誉值为A、B类的节点作为监督节点，监督共识过程。共识节点的选取如图2所示。

图2 共识节点的选取Fig.2 Selection of consensus nodes

（2）信誉值等级划分

理想情况下所有节点都能及时完成共识过程中的任务，但是在实际的网络传输中，部分节点可能会出现宕机、不发或错发消息等问题，因此在共识过程引入节点计分制和惩罚制。共识过程根据节点行为产生信誉值计分，成功完成共识或监督的节点加1分，共识过程中存在恶意或不作为行为的节点减5分，同时扣除一定份额的账户资金。惩罚机制的介入使节点作恶时不得不考虑成本问题，这在一定程度上提升了网络的安全性。

系统根据信誉值将节点等级划分A、B、C三种，其中各级别的节点具有的权限如表1所示。

表1 信誉值等级Table 1 Reputation rating

A类节点均可担任共识、监督以及选举节点三个角色。B类节点信誉值适中，可用于选举共识节点、监督共识过程。C类节点信誉值较低，只可参与投票给A类节点。

2.1.2 共识与监督过程

（1）系统不协调状态

在GST之前，消息传播不可靠，PBFT共识算法可能面临系统不协调的风险。为方便理解，本文阐述了一种攻击方法，假定系统存在1、2、3、4四个节点，其中作恶的主节点编号为1。攻击过程如图3所示。

图3 攻击过程Fig.3 Attack process

预准备阶段：主节点1广播PRE-PREPARE消息给节点1、2、3，但是不向4发送消息。

确认阶段：主节点1向3发送COMMIT消息，但是不向节点2、4发送。

实施以上攻击之后，节点3正常进行任务请求，并将结果返回给客户端，但是节点2、4最多收到两个COMMIT消息，因此节点1、2、4将不会执行此任务。客户端接收不到足够数量的回复，系统将启动View Change过程，但是由于诚实节点2、3、4内部状态不一致，系统将处于不协调状态。

（2）算法流程

ES-BFT算法分两个过程，即共识过程和监督过程，监督过程与共识过程同时进行。共识进行过程中，监督节点负责检测系统不协调状态，当系统出现不协调状态导致共识无法完成时，监督节点发送清除状态信息，系统进入准备阶段重新共识。算法基本流程如图4所示。

图4 共识流程图Fig.4 Consensus flow chart

（3）算法细节

首先，算法选取N≥3f+1个A级信誉值节点为共识节点，其中f为拜占庭节点数，选取除共识节点外的剩余A、B级节点为监督节点，这里将监督节点数量设置为M。其次，完成共识过程和监督过程的搭建。共识开始时，客户端要向共识节点和监督节点发送请求消息。其中，监督节点接收客户端消息是为了在清除状态阶段转发客户端消息，客户端消息的转发避免了节点与客户端再次交互，提高消息传播的效率。最后，在共识的回复阶段，节点除了要向其他节点发送COMMIT消息以外，还要向监督节点发送其在本轮共识收到的PREPARE和COMMIT消息集合。监督节点对比各节点状态，满足系统不协调条件时，向共识节点广播清除状态信息，共识节点计数清除状态信息的数量，如果超过2M/3，那么以当前视图及请求序号开始重新共识。这里的2M/3是根据PBFT共识准备阶段及确认阶段消息数2f+1推论得出。共识过程各消息格式表示如下：

ES-BFT算法根据p=vmod ||R选取当前轮次主节点，其中v表示当前视图编号，R为副本节点个数，p表示主节点编号。客户端向共识主节点和监督节点广播消息，其中o表示请求的操作，t表示时间戳，c表示客户端，REQUEST包含消息内容m和消息摘要d。

预准备阶段：主节点在收到客户端的请求消息后，首先验证客户端请求消息签名是否正确，如果验证成功，主节点需要为请求消息分配序号，然后广播一条<,m>消息给其他从节点，其中v表示视图编号，n表示消息序号，d表示消息摘要，m为消息内容。主节点广播预准备消息内容给从节点。

准备阶段：从节点收到主节点的PRE-PR EPARE消息之后对消息内容进行校验，校验通过，从节点向包括主节点在内的其他节点广播消息，其中i是当前节点编号。副本在相应的日志中记录PR E-PREPARE和PREPARE消息，用于在View Change过程恢复未完成的请求。

小麦从开花到成熟，进入生育后期，一般从5月上旬到6月中旬，约30d。在这个时期主要工作是养根护叶，延长上部叶片的绿色时间，防止早衰或贪青，保花增粒、促进灌浆。

确认阶段：主、从节点分别对接收到的PR EPARE消息进行校验。当节点i收到2f+1条校验通过的PR EPARE消息后，向包括主节点在内的其他节点发送消息。节点将COMMIT消息记录到日志中，用于View Change过程恢复未完成的请求。

回复与监督阶段：首先进行校验，如果节点接收到2f+1条来自不同节点（包括自己）的COMMIT消息，则进入回复阶段。回复阶段主要进行以下两部分内容：

节点发送给客户端，r为请求操作结果。当客户端收到f+1个由不同节点发来的相同的REPLY消息，共识达成并记录。当检测到节点不能正常完成共识时，客户端考虑是否重新发送消息。

节点在向客户端回复的同时向监督节点发送消息，其中，Pi表示节点i收到的PREPARE消息集合，Ci为节点i收到的COMMIT消息集合。Pi、Ci集合决定了监督过程的进行与否。当集合中节点状态呈现两种相同状态时，系统处于不协调状态，监督节点转发清除状态信息。

当S TATE消息集合中节点呈现两种相同状态时，监督节点对节点进行计数，如果计数值为2f+1，则向共识节点转发清除状态信息，清除状态信息格式为，其中m为消息内容，v为当前视图，n为当前消息序列号。CLEARSTATE消息中包含的消息内容能有效降低节点与客户端的交互次数。当共识节点接收到超过2M/3条CLEAR STATE消息，各节点进入准备阶段重新共识。

总的来说，一般情况下，View Change协议完全有能力解决共识失败的问题，但是无法在系统不协调情况下做出解决。监督机制的设立有效解决了GST到达之前的系统不协调问题。因此，对于一般状态，共识节点触发View Change协议正常处理，监督节点不做任何处理；而对于不协调状态，需要监督节点辅助进行共识。

2.2 算法分析

在PBFT算法中，随着网络中共识节点数量的增加，网络对于带宽的需求将以多项式级别增长，同时，网络节点的动态增删将导致网络的多次初始化。如果要求所有加入网络的节点参与共识，不论是网络带宽的需求还是动态性都将受到限制。ES-BFT算法使用DPoS算法选举部分A类节点为共识节点，减少了网络中参与共识的节点数量，提升了共识网络的稳定性，有效降低了网络对于带宽的需求。共识节点需要有一定的网络投票以及信誉值，因此共识节点出现拜占庭错误的几率会降低，从而在一定程度上保证了共识的安全性。

监督机制的设立能有效保证共识的安全性和活性，安全性要求所有诚实节点会提交一致的共识结果，活性要求节点在一定的时间范围内达成共识。PBFT算法在安全性问题上已做出解决方案，这里不做分析。系统不协调状态将导致共识和视图更换阶段难以进行，监督机制的设立恰巧避免了系统出现不协调的状态，因此能够保证算法的活性。

2.3 算法评估结果

本节中，选择通过go语言实现PBFT算法，并在PBFT算法基础上作了改进，得到ES-BFT算法；为控制变量，实验建立在相同网络环境中，不考虑节点会执行其他服务的情况下，在本地开启多节点模拟了ES-BFT算法、PBFT算法的共识过程；实验过程中记录数据吞吐量、共识时延等数据，最后通过对实验数据取平均值得出最终实验结果。实验表明，无论在吞吐量还是时延上，ESBFT都表现出优异的性能，同时在系统不协调情况下，ES-BFT表现出不错的交易时延。测试环境配置如表2。

表2 环境配置Table 2 Environment configuration

2.3.1 数据吞吐量测试

数据吞吐量表现为单位时间内打包的交易数，是反映共识算法性能的关键指标。本次实验首先认证在固定的网络环境中，监督节点的数量对数据吞吐量的影响。测试过程中，在本地开启17个端口，其中分别选取4、7、10、13个端口作为监督节点，其余节点为共识节点。另开启一个新端口作为客户端节点，客户端节点向共识和监督节点发送请求消息。每组测试分别记录20组数据，数据吞吐量测试结果取各组记录平均值，测试结果如图5。

图5 监督节点数量对数据吞吐量的影响Fig.5 Impact of the number of monitoring nodes on data throughput

图5表明，随网络中监督节点数量的增加，网络中数据吞吐量有了迅速提升。因此可以得出，在同一网络规模下，监督节点的设置大大提升了数据吞吐量，监督节点占比越高，数据吞吐量越高，监督节点在一定程度上提升了数据的传输效率。

为体现实验的一般性，选取典型的4个监督节点进行后续测试。在同样的网络环境下，设置8、12、16、20个端口，开启一个客户端节点，分别对PBFT算法、ESBFT算法进行吞吐量测试。每一轮进行20次测试，最后统计平均数据吞吐量。测试结果如图6。

由图6可以得出，网络节点数为8、12、16、20时，ESBFT算法比PBFT算法在数据吞吐量上分别有125%、109.1%、69.7%、67.4%的提升。进而表明，由于网络中参与共识的节点规模变小，在同等规模的网络环境中ES-BFT算法的数据吞吐量更高，算法更优。

图6 ES-BFT算法与PBFT算法数据吞吐量对比图Fig.6 Comparison of data throughput between ES-BFT algorithm and PBFT algorithm

2.3.2 共识时延测试

共识时延表现为请求发起到请求被写入的时间间隔，是反映共识算法性能的又一关键指标。在进行两种算法时延对比之前，实验测试了监督节点数量对网络时延的影响，选取17个网络节点，其中监督节点数量分别为4、7、10、13。实验记录从请求交易到交易提交的时间，每组节点进行20次测试，测试结果选取测试平均值，测试结果如图7。

图7 监督节点数量对共识时延的影响Fig.7 Impact of the number of supervisory nodes on consensus delay

图7表明随着监督节点数量的增加，共识时延明显缩短。因此在实际应用中，可通过适当降低共识节点的比例来提高共识效率。

同数据吞吐量测试，本次测试首先开启1个客户端端口；其次，分别开启了8、12、16和20个网络节点端口，并从中选取具有代表性的4个监督节点；最后，测试了在相同网络环境、各节点不进行任何服务情况下PBFT算法和ES-BFT算法的共识时延，同样，每组测试各进行20次，测试结果选取20组数的平均值。测试结果如图8。

由图8的测试结果计算得出，实验节点数量一定的情况下，ES-BFT算法的共识时延比PBFT算法时延下降69.8%、45.3%、32.9%、39.4%。由此表明，ES-BFT算法在共识时延上较PBFT算法有更大的优势，随着节点数的增多，PBFT算法时延上升明显，而ES-BFT算法时延相对稳步上升。共识时延是算法性能的直接体现，因此在不考虑网络环境影响、节点任务的情况下，单纯就共识算法性能一项来讲，ES-BFT算法性能优于PBFT算法。

图8 ES-BFT算法与PBFT算法共识时延对比Fig.8 Consensus delay comparison between ES-BFT algorithm and PBFT algorithm

ES-BFT算法的监督机制避免了在GST到达之前的系统不协调情况的发生，在一定程度上提升了共识算法的安全性。本次实验模拟主节点作恶，为方便理解，以4个节点为例，将节点分组并编号为1、2、3、4，主节点1在预准备阶段向除4以外的其他节点发送消息，其他节点消息正常发送；在确认阶段，主节点向2发送消息，但是不向3、4发送；本次的模拟方法将使四组节点两两进入相同状态，系统产生不协调情况。实验模拟了监督节点数为4，共识节点数分别为4、8、12、16的情形，每组节点记录20组共识时延数据，测试结果取各组平均数，结果如图9。

图9 系统不协调下的ES-BFT算法共识时延Fig.9 ES-BFT algorithm consensus delay under system inco-ordination

图9为系统不协调情境下ES-BFT算法在监督机制下从系统不协调到再次共识的总时延，图9表明，监督机制的设计在有限时延内有效避免了系统不协调导致的长时间无法共识的情况。

3 结束语

ES-BFT算法提出了一种新的节点选取办法和监督机制。节点的划片选取和信誉值机制不仅有效地提高了共识节点的随机性与可信性，还提升了网络的灵活性；监督机制的设立成功避免了共识系统不协调的情况。实验进一步认证，监督节点的使用提升了网络的灵活性，在实际应用中，用户可根据需求选取监督节点数量；节点选取和监督机制的实施有效地提升了PBFT算法的共识效率和安全性。本文算法是在不考虑复杂的网络环境以及网络节点不进行其他任务的条件下获得的，以上限制条件值得在接下来的工作中进行探索研究。