一种面向联盟链优化的PBFT 共识算法

王微渊，毕远伟，陈霄汉，李传彪

烟台大学计算机与控制工程学院，山东烟台264000

2008 年，笔名为“中本聪”的研究者发表了Bitcoin: A Peer-to-Peer Electronic Cash System[1]，这被认为是比特币奠基性论文。比特币系统于2009 年正式发布之后，作为比特币交易核心的区块链技术也逐步走进大众的视野。区块链是由共识算法、分布式系统、密码学、P2P 网络等多种技术结合的产物。区块链技术拥有去中心化、数据安全、数据不可篡改等特点[2]，在数字货币、数据存储、数据鉴定和金融交易等领域都有很好的应用前景。但目前区块链系统存在着资源消耗过大以及交易时延较低等问题，限制了区块链技术的发展。

根据网络范围，区块链可以分为公有链、私有链、联盟链[2]。公有就是完全对外开放，任何人都可以使用，没有权限的限定，也不需要身份认证之类，不但可以任意参与使用，而且发生的所有数据都可以查看，完全公开透明。私有链是与公有链相对的一个概念，所谓私有就是指不对外开放，仅仅在组织内部使用的系统。联盟链的网络范围介于公有链和私有链之间，通常是使用在多个成员角色的环境下。与私有链一样，联盟链系统一般也是具有身份认证和权限设置的，而且节点的数量往往是确定的。由于联盟链对于用户隐私的保护和系统高安全性，在企业或者机构之间的事务处理、公共业务、政府事务之中被逐渐采用。常见的联盟链有Ripple[3]、Hyperledger Fabric[4]、Stellar[5]。

共识算法是区块链系统中的核心机制，是解决系统中各分布式节点数据一致性问题的关键，直接影响着区块链系统的交易处理能力、系统可扩展性和数据安全性[6]。目前实用拜占庭容错（practical Byzantine fault tolerance,PBFT）算法[7]在联盟链得到了广泛的应用，但是PBFT 算法本身存在通信开销过大、节点可信度不高、无法动态地删除节点等缺陷。近几年针对PBFT 算法的改进也层出不穷。文献[8] 提出了DS-PBFT 运用Grouping 算法对节点进行分组，同时结合Speculation 技术，降低节点间通信的时间复杂度，从而使得共识时延得以降低。文献[9] 提出的IPBFT 算法通过投票选举出主节点，增设候补集合使系统能够动态地增删节点，优化了视图切换协议降低了系统的通信开销。文献[10] 提出了TMBFT 算法，该算法通过提出一种基于信任度的邻居匹配模型进行共识节点的选取并将算法的通信复杂度从O(N2) 降到O(NlbN)，提高了算法的可用性和安全性。

针对联盟链的应用场景，本文提出了一种基于决策树改进的PBFT（decision tree Byzantine fault tolerance,DTBFT）算法。首先，针对联盟链的应用场景，简化了PBFT 算法的一致性协议，降低了通信开销；其次，考虑到系统安全性的问题，引入信誉积分机制，增加C4.5 决策树分类算法[11]，在每轮共识完成后统计节点行为，对节点分类，使系统可以动态地剔除拜占庭节点，提高系统的安全性；最后，为了防止拜占庭节点当选主节点，导致算法频繁执行视图切换协议，造成系统运行效率低的问题，改进了视图切换协议，将主节点的选取范围缩小到节点信誉好的高级节点，以保证主节点的可信度。

1 共识算法分析

1.1 拜占庭将军问题

1982 年，文献[12] 正式提出拜占庭将军问题。目前拜占庭问题采用的假设条件包括：任意节点都可以是拜占庭节点且拜占庭节点之间可以共谋；拜占庭节点发生错误的方式不一定相同，可以是异构的；节点之间通过异步网络连接，网络中的消息可能丢失、乱序到达、延时到达；节点之间传递的信息，第三方可以知晓但是不能窜改、伪造信息的内容和验证信息的完整性。在早期的一些共识算法（如Paxos[13]、VR[14]等）解决的都是非拜占庭问题，也就是可以容忍系统内部节点宕机、消息丢失、延时、乱序等，但是系统内部不允许有恶意节点。而PBFT 算法不但能容忍节点故障，还能容忍在系统内部存在一定的恶意节点。

1.2 PBFT

1999 年提出的PBFT 算法核心由三个协议组成：检查点协议、一致性协议、视图切换协议。系统正常运行时，执行检查点协议和一致性协议。当主节点发生异常或者系统运行缓慢时，才会启动视图切换协议更换主节点。

1.2.1 PBFT 一致性协议

PBFT 算法的大致流程为：假设系统中存在3f+1 个节点（f为系统可容忍的拜占庭节点数目），在预准备阶段，主节点收集交易信息打包区块并向全网广播；在准备阶段，每个节点在收到交易信息后，模拟执行这些交易，计算新区块所需要的Hash 摘要，并向全网广播准备信息；在确认阶段，如果一个节点收到2f个其他节点发来的Hash 摘要与自己相等，就向全网广播一条确认信息；在回复阶段，如果一个节点收到2f条确认信息就可以提交新的区块到本地区块链和状态数据库中，最终达成共识。PBFT 算法一致性协议流程如图1 所示。

图1 PBFT 算法一致性协议流程图Figure 1 PBFT algorithm conformance protocol flowchart

1.2.2 检查点协议

一致性协议中系统每执行一个请求，节点都要记录日志（包括请求阶段、预准备阶段、准备阶段、确认阶段发送的消息）。如果系统不及时清理会导致资源被大量占用，影响系统的可用性。除此之外，由于拜占庭节点的存在，一致性协议无法保证每一个节点都执行了相同的请求，所以导致节点的状态可能不一致。例如，一些节点由于网络延时，导致从某个序号开始之后的请求无法执行。因此，周期性检查点协议是为了将系统内部所有节点状态同步，这实际上是一个追块的过程，节点通过区块链定时广播的世界状态或其他节点发送的消息获知本节点的区块落后，然后启动追块流程。

PBFT 算法的检查点协议很好地解决了日志过多导致的系统资源浪费、可用性降低和拜占庭节点导致的节点状态不一致等问题。

1.2.3 视图切换协议

区块链中每个节点都要在相同的配置信息下工作，该配置信息被称为视图。在PBFT 算法中当主节点发生故障后，需要更换主节点，为了保证系统的正常运行，系统通过运行视图切换协议来实现。

当主节点发生故障后，根据如下公式来选出主节点

式中：P为主节点的编号；V为视图编号；|N| 为系统内部节点数目。假如当前视图即第一轮视图编号为1，参与共识的节点共100 个，1%100=1，也就是1 号节点是主节点；如式(1) 所示，当需要选举新的主节点，第二轮视图编号自增变为2，2%100=2，2 号节点成为主节点，所以视图切换协议是一个轮询的过程。

视图切换协议的触发条件有两个：1）在固定时间T1内没有收到主节点广播的预准备消息；2）在固定时间T2内系统没有生成新的区块，且T2>T1。

当上述条件满足其中一种时系统就会自动触发视图切换协议，具体过程如下：

首先，视图编号+1，向所有节点发送view-change 消息。其次，所有节点当收到的2f+1（f表示系统内部可容忍的拜占庭节点数目）条view-change 消息后，向新视图中的主节点发送view-change-ack 确认消息。新视图中对应的新的主节点将收集来自其他节点的view-change-ack 消息。再次，当收集到2f条确认消息后，组装并广播new-view 消息发送给所有节点，之后根据本地的链接数据执行一致性协议。

虽然PBFT 算法解决了拜占庭问题，但算法本身也存在着不少问题：1）算法通信开销过大，整个共识过程的节点间通信的时间复杂度为O(N2)，其中N是网络中节点的总数目；2）PBFT 算法无法动态增删节点，加入新节点时只能重启系统，资源消耗量大；3）由于节点本身的可信度无法保证导致恶意节点可能担任主节点，会造成安全隐患，不断切换视图，降低运行效率。

2 基于决策树改进的PBFT 算法

为了提供一种运行通信开销低、可以动态增删节点、节点身份可靠的共识算法，本文结合联盟链的特点和决策树算法分类的精确性，提出了一种基于C4.5 决策树分类的拜占庭容错算法，其流程如图2 所示。

图2 算法流程图Figure 2 Algorithm flow chart

DTBFT 算法简化了一致性协议，降低算法的通信开销。算法引入了信誉积分机制，在共识结束之后统计节点的连续共识次数、宕机次数、错误通信次数、节点的活跃度（由节点的响应次数除以节点收到消息的总数）。根据上述节点属性，通过决策树分类算法将节点分为高级节点、中级节点、初级节点，动态调整节点身份剔除系统内部的恶意节点，提高节点的可靠性；改进视图切换协议，将系统内部节点信誉度较高的高级节点作为主节点和候选节点的选取。根据节点的功能将节点分为主节点、候选节点、共识节点，具体如下。

主节点：负责生产区块，接受客户端的指令，回复客户端共识完成，该类节点由高级节点中信誉积分最高的节点担任。

候选节点：在主节点没有发生故障时，负责接收回复主节点发送的消息，参与共识过程；在主节点发生故障时，选举成为主节点，开始共识过程，该类节点由选举出主节点后剩余的高级节点担任。

共识节点：负责接受回复主节点消息，参与共识过程，该类节点由中级节点、候选节点担任。

2.1 节点分类规则

机器学习中的决策树分类算法有着计算量较小、算法速度快、分类规则清晰、准确度高等优点，因此本文引入了决策树分类算法来保证节点分类的准确性。

决策树是指用来表示决策和相应的决策结果对应关系的树。树中每一个非叶结点表示一个决策，该决策的值导致不同的决策结果（叶节点）或者影响后面的决策。C4.5 算法用信息增益率来选择决策属性。C4.5 算法具有可处理数据范围包含连续性数值、数据的自适用性较强、可处理不完整数据、属性选择的标准较精确，以及建树完成后具有剪枝作等优点，可避免决策树的不完整性。

在改进的DTBFT 共识算法中加入了决策树分类算法，每轮共识完成后收集节点的信誉积分、宕机次数、连续共识次数、错误通信次数、活跃度，以这些作为特征属性，将高级节点、中级节点、初级节点、剔除作为类别属性。在Hyperledger Fabric 联盟链一个通道中，锚节点是定义在一个已经加入到通道的组织的节点。该节点主要用于节点的发现，可以被这个通道的其他任何节点发现和通信。因此，每一个加入到管通内的组织都至少有一个锚节点，一个组织的节点可以通过查找锚节点来发现这个通道内的其他组织的所有节点，由于算法是针对Hyperledger Fabric 联盟链改进的，所以节点属性的统计由联盟链中的锚节点负责。

3.大鼠全脑缺血再灌注模型的制备：采用改良Pulsinelli四血管闭塞法构建大鼠全脑缺血再灌注模型[5]。用10% 水合氯醛麻醉后固定于操作台，颈后备皮、消毒，于第1 颈椎水平作1～ 2 cm的纵向切口，分离筋膜、肌肉，暴露第1颈椎翼突孔，电凝双侧椎动脉造成椎动脉永久性闭塞，消毒缝合切口。翻转大鼠仰卧位固定，于颈前正中作切口，分离双侧颈总动脉，穿线后打活结埋于皮下备用，缝合。24 h后不采用麻醉固定，仅用无损伤微动脉夹夹闭双侧颈总动脉，持续10 min，造成大鼠全脑缺血。出现大鼠瞳孔散大、翻正反射消失时立即撤去动脉夹，缝合切口。

如图3 所示，节点分类流程如下：首先由Fabric 联盟链中的锚节点进行分类属性的收集并分类；然后通过视图切换协议进行主节点的选举，在共识过程中验证节点；最后由锚节点收集节点行为并剔除恶意节点，剔除的拜占庭节点无法再参与到接下来的共识过程中，并且如果需要重新进入系统，则需要联盟链管理员的确认。C4.5 决策树构造步骤如下。

图3 节点分类流程图Figure 3 Node classification flow chart

步骤1计算信息熵。信息熵可以度量样本集合是否属于同一类别。其定义如下：假设当前训练集合中熵是类样本所占的比例为Pk（由于本文测试的数据集分类的类别为高级节点、中级节点、低级节点和剔除4 类，因此，此处k的取值为（1、2、3、4）。类别信息熵表示所有样本中各种类别出现的不确定性之和。那么，根据训练集计算类别信息熵为

步骤2计算信息增益。信息增益表示信息的不确定程度。在训练集合中，选择属性特征向量a来对集合进行划分，并且特征向量a总计有5 个取值可能｛节点积分，连续共识次数，宕机次数，错误通信次数，节点的活跃度｝，那么，取第v个值则在样本集合D中选取的是取值为av，并且记作Dv。由式(2) 可计算得出的信息熵，并为分支节点赋予权重用来解决分支节点所含的样本数目不同的问题。于是，使用属性特征向量a来对集合D进行划分的信息增益就可表示为

然而，采用信息增益来选择划分属性，会使其对属性选择产生较多的偏差，从而影响决策树的泛化能力。所以，C4.5 决策树算法选择增益率来选择划分属性。

步骤3计算增益率。C4.5 决策树算法中的增益率的计算是在信息增益的基础上进行延伸的，训练集合D使用属性特征向量a的增益率，公式为

依据上述过程得到的C4.5 决策树，将系统内部的节点分为高级节点、中级节点、初级节点，其中高级节点到系统总节点数目的20%，中级节点占到系统总结点数目的30%，初级节点占到系统总结点数目的50%。三类节点能参与的协议如表1 所示。

表1 节点权限表Table 1 Node permissions table

系统内部节点的等级是动态变化的，当一个新节点加入系统时，其初始积分为70，节点的连续共识次数、宕机次数、错误通信次数、节点活跃度都为0，新加入的节点可以通过完成共识过程，保证节点状态正常，来提升自己的节点等级。系统内所有节点在完成共识过程后其信誉积分加1，并统计本节点共识过程中的连续共识次数、宕机次数、错误通信次数以及计算节点的活跃度，等待下一次节点身份的调整。中级节点在共识过程中发生了拜占庭错误（共识过程中节点传递错误信息的行为）信誉积分将扣5，在下一次C4.5 分类后降为初级节点。当主节点发生了拜占庭错误时，其他节点直接将该节点剔除本轮共识，降为初级节点，节点序号为初级节点中的最后一个。系统通过C4.5 决策树分类算法定期动态的调节节点身份，当系统内部高级节点的数目大于系统内部数目的20%时，这些节点停止成为高级节点，并作为中级节点序号最开始的节点，等待系统内部由于加入或者删除节点导致高级节点数目不足20%时自动升入高级节点，其他节点同理。节点的状态转换图如图4 所示。

图4 节点状态转换图Figure 4 Node state transition graph

2.2 DTBFT 算法一致性协议设计

DTBFT 算法保留了PBFT 算法的各个阶段，去除了共识节点间的通信过程，降低了网络带宽，共识节点选取系统内部的中级节点担任保证系统的节点的可靠性和系统的安全性。算法一致性协议图如图5 所示。

图5 DTBFT 一致性协议图Figure 5 DTBFT conformance protocol graph

1）请求阶段。客户端C向主节点P发送一条，其中O表示执行请求的状态机，T表示时间戳，C表示客户端的编号。

3）准备阶段。共识节点收到主节点P发送的预准备消息，确认消息是否正确，生成准备消息，其中I表示本节点的编号。主节点接收其他共识节点发送的准备消息如果收到了超过(2F+1) 条消息则进入确认阶段（F表示所有节点中允许失效的最大节点数）。否则，认为主节点发生错误，将主节点权限交给新选举的主节点，并由新的主节点发送共识验证失败的消息给所有节点视图号加1。发生错误的主节点降为初级节点。

4）确认阶段。主节点P收到共识节点发送的准备消息是否全部正确且相同，并生成确认信息，广播给所有共识节点，CONFIRM 表示新区块确认添加，并将告知客户端。如果存在小于F（F表示所有节点中允许失效的最大节点数）个共识节点发送的消息与主节点的不一致，则继续发送确认消息，生成新的区块，对于消息不一致的节点进行信誉积分的扣除，并记录节点行为；如果超过F个共识节点的发送的消息与主节点不一致，则主节点终止本轮共识，对消息不一致的共识节点进行信誉积分的扣除，重新开始共识过程。

2.3 改进的视图切换协议

原算法的视图切换协议从系统内部所有节点中选出主节点，改进的视图切换协议则从系统内部所有高级节点中选出主节点，且剩余的高级节点将会作为候选节点，当主节点发生错误时接替其主节点的身份。根据信誉积分的大小将系统内部已经分类完成的|RH| 个高级节点根据积分高低依次编号，{0,1,···,|RH|-1}，序号越小被选为主节点的概率越大。

式中：P为最终选出来的主节点的序号；V为当前视图的编号；|RH| 为系统内部所有高级节点的数量。

改进的视图切换协议的触发条件为：1）主节点在固定时间t1内未收到2F+1 条准备信息（F表示所有节点中允许失效的最大节点数）；2）主节点未能在规定时间t2内生成区块，且t2>t1。

满足上述条件的其中一条系统将会执行视图切换协议。

3 算法分析

3.1 通信复杂度分析

在PBFT 算法中，广播消息需要进行预准备、准备和确认三个阶段的通信，对应的通信次数分别为N、N2和N2。在计算其与用户端的通信次数后，PBFT 算法中一个完整的共识过程所需的通信次数如下：T1=1+N+N2+N2+N=2N2+2N+1，在改进的DTBFT算法中由于简化了一致性协议，在忽略决策树分类的前提下算法的三个阶段的通信次数都为N，则T2=4N，T1>T2在忽略决策树分类过程给系统带来的额外通信复杂度，DTBFT 算法将通信复杂度由O(N2) 降低到O(N)。但是当系统需要对拜占庭结点进行剔除时，考虑到C4.5 决策树算法的通信复杂度，导致DTBFT 算法在系统内部存在拜占庭节点的情况下共识时延较高。

3.2 算法正确性分析

根据CAP (consistency-availability-partition tolerance) 原理[15]，一个分布式系统最多只能同时满足可用性、分区容错性和一致性三项中的两项。可用性是指对于一个分布式系统，每一个非故障的节点必须对每一个请求作出响应。分区容错性是指分布式系统在遇到某节点或网络分区故障时，仍然能够对外提供满足一致性和可用性的服务。一致性使得更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一样。

在DTBFT 算法的一致性协议中，虽然简化了一致性协议过程，但是每个阶段非故障的共识节点都会向给自己发送消息的主节点回应，保证算法的可用性。DTBFT 算法通过决策树分类剔除系统内部的故障节点，当主节点发生故障时，通过改进的视图切换协议及时更换主节点，继续完成共识，使算法拥有分区容错性。DTBFT 算法的一致性指强一致性，是在满足可用性和分区容忍性的同时可以采取适当的方式达到最终一致性，即所有节点在经过一定的时间之后，最终能够达成一致的状态；在DTBFT 算法中每个节点都会保存区块链的信息，当新节点加入后，通过一致性协议节点间的消息传递将区块信息同步最终保证算法的强一致性。

3.3 共识节点的安全性分析

本文采用C4.5 算法对参与联盟区块链网络共识的节点的信任级别进行分类。通过本实验数据集采用C4.5 算法、KNN 算法、朴素贝叶斯算法、Logistic、感知器和最大熵分类器进行比较和观察，结果如图6 所示。

图6 分类算法精度对比图Figure 6 Comparison chart of classification algorithm accuracy

本文300 个实验数据，包括240 个训练样本和60 个测试样本。从实验结果可以看出，C4.5决策树具有最好的分类精度，使用C4.5 决策树可以有效地提高共识节点分类的精确度和提高算法的安全性。

4 实验及结果分析

在联盟链场景下对本方案中DTBFT 共识算法进行测试，实验基于Hyperledger fabric，以及其测试工具Hyperledger caplier，搭建了一个50 个节点的联盟链网络，通过Fabric 共识模块可插拔的特性，分别运行PBFT 和DTBFT 算法。通过节点发送不同消息，模拟拜占庭攻击，具体软硬件环境如表2 所示。

表2 软硬件配置表Table 2 Hardware and software configuration table

4.1 吞吐量

吞吐量是指单位时间内处理事务的数量，在共识算法中是指在单位时间所能共识成功的交易数量。较高的吞吐量证明共识算法本身的性能较高，吞吐量公式为

式中：S为吞吐量；N为共识成功的交易数量；T为总时间。实验中设置客户端发送1 500 条消息，记录每秒能够完成共识的交易数量，并且分别在系统内部存在拜占庭节点和不存在拜占庭节点的情况下，针对不同节点数进行测试，实验结果如图7 所示。

图7 吞吐量对比图Figure 7 Throughput comparison chart

由吞吐量折线图可以看出，吞吐量的大小与参与共识的节点数量成反比。在系统内部有拜占庭节点的情况下，DTBFT 的吞吐量大小在相同节点数目的情况下要高于PBFT 算法。

4.2 共识时延

共识时延作为衡量共识算法的重要指标，在区块链中表示交易从发起到完成的时间差。较低的时延使得区块链的可用性和安全性更高。测试时延性公式为

式中：T（submit）为共识完成确认的时间；T（authentication）为共识认证阶段开始的时间。实验中每150 次交易取一次平均值，并在不同数目节点下进行，实验结果如图8 所示。

图8 共识时延对比图Figure 8 Consensus delay comparison chart

由共识时延对比图中可以看出，在系统内部没有存在拜占庭节点的情况下，DTBFT 算法要快于PBFT 算法，但是当系统内部存在拜占庭节点时，在DTBFT 算法最坏的情况下共识时延略高于PBFT 算法。

4.3 算法安全性测试

针对PBFT 算法无法动态剔除拜占庭节点的问题，DTBFT 算法引入了积分机制，以此来剔除系统中的拜占庭节点，保障系统安全性。实验中系统内部的预设节点数目为1 000，其中存在300 个拜占庭节点，在系统运行的过程中会有拜占庭节点加入进来，分别运行PBFT算法和DTBFT 算法，进而根据共识轮次的增多查看系统内部的拜占庭数目。实验结果如图9所示。

图9 拜占庭节点数目图Figure 9 Byzantine node number graph

由实验结果可知，运行11 轮后系统内部的拜占庭节点数目为6，由此可见当系统趋于稳定时，DTBFT 算法可以去除系统内部的拜占庭节点，拜占庭节点当选为主节点的概率降低，保证了系统的安全性。在新的拜占庭节点加入后，无法完成共识过程而被系统剔除，而PBFT算法的拜占庭节点数目基本不变。因此，实验证明DTBFT 算法具有较高的安全性能。

5 结语

本文在联盟链的应用场景下，针对PBFT 算法的通信开销过大、节点可信度无法保证、算法无法动态地增加和删除节点等问题，提出了DTBFT 算法。算法引入了信誉积分机制，保证节点的信誉度，简化了原本算法的一致性协议，降低了算法的通信开销。在检查点协议中增加了C4.5 决策树分类算法，对系统内部的节点进行定期分类，使得系统能够将恶意节点剔除。此外，改进了视图切换协议，将主节点选取范围缩小到积分较高的节点。但是，在系统内部存在拜占庭节点时，DTBFT 算法的共识时延较长，未来的工作会针对该问题对算法的性能继续优化。