结合动态信用机制的PBFT 算法优化方案

刘泽坤，王峰，贾海蓉

（太原理工大学 信息与计算机学院，太原 030024）

0 概述

随着互联网技术的日益发展，以比特币［1］为代表的数字货币随之崛起，支撑比特币系统［2］的底层技术（如区块链技术［3］）也成为研究热点。区块链技术被广泛应用于金融业、能源互联网、农业等领域［4］，本质是“点对点”分布式数据库，具有利用共识机制解决分布式框架问题的优势，能够有效解决去中心化问题。

共识算法作为区块链的核心技术，能够信任不同节点并计算其权益，最终保证区块链系统的一致性。工作证明（Proof of Work，POW）［5］、权益证明（Proof of Stake，POS）、Paxos、实用拜占庭容 错（Practical Byzantine Fault Tolerance，PBFT）等共识算法被广泛应用于金融机构、电子货币行业、农产品溯源等多个领域。POW（俗称“挖矿”）被广泛用于维护系统的一致性和安全性［6］，参与者（俗称“矿工”）被鼓励竞争生成一个有效的块，通过解决一道密码难题赢得奖励［7］，这将促使参与者投入巨大的计算资源来达成共识。奖励通常以虚拟货币的形式存在，包括资源消耗的成本和合理的利润。POW 可容纳上千节点运行，但吞吐量较低且生成新区块所需的时间较长，从而浪费电力资源和算力，不利于更大范围市场的推广。为解决上述问题，SUNNY 提出POS，设计一个可靠机制给予系统各个节点参与决策的权利。在实际应用中，POS［8］不需要花费算力，且记账权来源于权益，“挖矿”是几乎没有成本的［9］。鉴于“挖矿”的零成本，若恶意节点制造分叉链，选择在每条链上“挖矿”，此时无论哪条主链，它们均会获得收益。若大多数“矿工”都选择在所有分叉上“挖矿”，则导致区块链分叉，增大遭受双花攻击的可能性，无法保证区块链的稳定性。Paxos［10］基于消息传递，解决系统内容一致性问题，在执行相同的操作后，所有节点能够得到一致的结果。但Paxos 存在故障风险，若作恶节点发布假消息，网内就存储假消息。为避免上述风险的发生，基于BFT 的PBFT 算法应运而生，PBFT 算法的C/S 架构使得算法复杂度大幅降低，可实现每秒上千次的交易请求和交易量，具有交易时间短、承载交易量大的优点。

随着对共识算法的深入研究，PBFT 算法在不断的改进优化，使证明方法、理论应用呈现多样化、多维化发展。简化的拜占庭容错（SBFT）［11］算法极大程度地加快算法完成共识的速率，各节点都可以自主操作，而无需与其他节点进行交互通信验证，完成快速共识。但是在SBFT 中收集签名的收集器是恶意的，则导致SBFT 的性能大幅下降。DGPBFT［12］算法基于扩展节点的属性，增加节点可信度，并设计节点可信度的评估机制，通过对可信度的节点进行分组，大幅降低通信的复杂度。但当DGPBFT 算法面对硬件错误、网络拥塞、终端遭到恶意攻击等问题时难以实现高效安全的工作［12］。DDBFT［13］将DPOS 应用于PBFT 算法中，使得PBFT［14］算法具有动态性的特点，但是因网络带宽有限，导致网络阻塞且吞吐量降低［15］。授权拜占庭容错（DBFT）算法由BFT 算法演化而来，专用于许可区块链，根据持有股份数量通过投票决定节点是否能进入到共识网内。DBFT 虽然提高算法效率，但是当超过1/3 的节点协同作恶或对主节点进行攻击时，交易请求完成的主导权将被恶意节点掌控，算法的安全稳定性无法得到保障［16］。

本文提出基于信用积分机制和动态增删节点的实用拜占庭容错共识算法DT-PBFT。通过引入动态机制，使联盟链中节点的自主加入和退出更加灵活，增加网络的灵活性。引入信用积分机制，通过增加信用积分筛选出信用度较高的节点作为备选主节点，对恶意节点（信用积分较低的节点）进行网内的自主剔除，以有效地降低恶意节点成为主节点的概率，确保网内各个节点的安全可靠性。在此基础上，利用优化的一致性协议实现对共识流程的改进，并进行一轮全网广播，提高网络的运行效率。

1 传统PBFT 算法

1.1 算法流程

PBFT 是一种状态机副本复制算法［17］，状态机在不同的节点上复制副本，并应用于分布式系统中。在PBFT 模型中，每次产生的主节点都会领导一次共识过程的执行，运行中伴随客户端、主节点和从节点，其中主节点、从节点为备份节点，在运行过程中都会进行数据备份［7］。传统PBFT 算法的共识流程如图1 所示。

图1 传统PBFT 算法共识流程Fig.1 Consensus procedure of traditional PBFT algorithm

传统PBFT算法［18］的共识过程分 为5 个阶段：1）请求阶段，客户端向主节点发送请求消息；2）预准备阶段，客户端向主节点发布请求消息编号，并向其他节点广播预准备消息［19］；3）准备阶段，主节点发布的预准备消息被集群内节点接收后进行自主核验，当从节点核验同意预准备消息后，则转入准备阶段等待其余节点的核验，若从节点核验不同意预准备消息后，则不再继续进入下一阶段［20］，当在集群内收到2f+1 个从节点时，发布的完成预准备消息的核验以及同意进入准备阶段，即表示准备阶段已经完成［21］；4）确认阶段，所有节点都要对外发送进入确认阶段的消息，节点i查验包括自身在内的2f+1 个确认消息，当确认消息与预准备消息一致时，表示此阶段已完成；5）回复阶段，当节点i完成确认阶段后，向客户端反馈回复消息，客户端C只有收到f+1 个反馈信息时，表示发出的请求已经成功完成共识。

1.2 算法分析

PBFT 算法随意选取主节点，可能使得恶意节点连续成为主节点，从而浪费网络资源。虽然恶意主节点能被其他节点识别并推翻［22］，但是更替主节点会增加系统开销、降低共识效率。在共识阶段的一致性协议中，Prepare 和Commit 两阶段均采用节点在全网内广播交互验证的方法。随着节点数的增加，系统所需的网络开销和带宽容量呈多项式级增加，导致PBFT 算法无法工作。集群内节点在原有的预准备阶段前可能处于宕机或自主退出网络的状态，节点一旦超过算法允许的延迟时间，就无法参与后续共识流程。由于缺少退出环节，该节点仍存在于网内，但是在PBFT 算法后续的共识过程中，其他节点仍要向该节点发送无效的交互验证消息，增加了网络开销。节点无法动态地加入和退出集群，使得算法在具体应用时灵活性较差。

2 DT-PBFT 算法

DT-PBFT 算法以PBFT 为基础，加入了动态机制、信用积分机制和协议一致性的优化，有效解决了PBFT 的动态性较差、灵活性较差、通信开销的时延较大等问题。

2.1 动态机制

动态机制的主要功能是节点动态加入共识网络和动态退出共识网络，在节点动态加入和退出的过程中并不需要重新动态启动区块链网络，有效提高共识算法的灵活性。

2.1.1 节点动态加入

节点动态加入的流程主要有以下5 个步骤：

1）申请阶段：当启动网络中存在的新增节点后，若该节点要加入到集群中参与后续的共识阶段，应先向集群内所有节点发送请求加入集群的消息s，并加上时间戳，发起AddNode 请求连接。

2）认证新节点阶段：当现有节点收到来自新增节点发起的AddNode 请求时，通过广播并收集其他节点发送的AgreeAdd 消息。当节点收集到2f+1 条AgreeAdd 消息时，则向新增节点发送同意加入集群的认证消息。当新节点收到2f+1 条认证消息时，则请求达成一致，允许新增节点加入到集群中。

3）数据同步阶段：新增节点进入主动恢复Recovery 的流程。新增节点发送数据同步的请求，并广播给其他节点，同时其他节点给新增节点发送当前所存的全部信息，以实现新增节点的数据同步。

4）入网阶段：在完成数据同步之后，向全区块链网络的所有节点广播JoinNet的请求，请求参与区块链网络的共识。所有的现有节点收到来自新增节点发送的JoinNet 请求，同时通知所有的现有节点，新增节点正式入网，并重新计算网内节点总数以及新视图v。

5）回执阶段：由主节点向所有集群内节点发布UpdataNet 信息，当所有共识节点收到消息后，更新区块链集群内节点总数N和视图v，完成新增节点的流程。当视图和节点总数更新完成后，共识节点向主节点进行反馈，当主节点收到2f+1 条信息，即网内已完成并入新节点，则完成一次动态增加节点的共识行为。

节点动态加入流程如图2 所示，图中New_Replica5 为新增节点。

图2 节点动态加入流程Fig.2 Dynamic joining procedure of nodes

2.1.2 节点动态退出

节点动态退出的流程如图3所示，其中Del_Replica5为主动请求退出的节点。

图3 节点动态退出流程Fig.3 Dynamic exit procedure of node

节点动态退出流程分为以下4 个步骤：1）申请阶段，当Del_Replica5 节点主动要求退出时，由该节点开始向其他节点广播Del-request 消息；2）认证消息阶段，其他节点收到Del-request 消息后，假设该节点退出现有区块链网络，计算删除该节点后的视图v和节点总数N，通过向区块链网络中的其他节点广播自己同意删除Del_Replica5 节点，若收集到f条AgreeDel 的消息，则所有节点同意并删除该节点发起数据同步的请求，并将删除该节点后的视图v、节点总数N等消息封装；3）退网阶段，当Del_Replica5节点退出后，主节点发送UpdataNet 信息；4）更新网络，全网所有节点收到UpdataNet 信息后，更新区块链网络中节点总数N和视图v，完成删除该节点的流程。

2.2 信用积分机制

PBFT［23］引入整体信用积分机制，通过对集群内节点随机选择主节点的机制进行改进。信用积分机制的流程如图4 所示。

图4 信用积分机制流程Fig.4 Procedure of credit scoring mechanism

定义1（信用机制分层设置）在拜占庭容错算法中区块生成验证由主节点主导完成。为改进原始算法，DT-PBFT 使得各个节点能更好地被监控，引入信用积分机制主要是对所有节点进行分层，将节点分为备选主节点层、中间层、警告层、清理层，并将分数值设为n且上限设为100，根据不同分数段对区间进行区分。

1）备选主节点层（80≤n≤100）：在交易时将集群内较可靠的节点作为主节点，以解决拜占庭节点可能被连续选作主节点而造成算法运行效率较低的问题。当主节点需切换时，仍会在备选主节点中选取节点进行替换。

2）中间层（40

3）警告层（20

4）清理层（n<20）：节点初始信用分值处于中间层，经多次作恶行为后进行分值减半处理，将被网络内定为不信任节点，并将信息返回到集群内的每个节点，再由主节点删除该节点的请求，最终经交互后确认将该节点移除出网络，借助这个机制来减少网内的拜占庭节点，从而提高算法的效率，降低无效的网络开销。

定义2恶意节点被清出网络的流程如图5 所示。当存在恶意节点被踢出现有区块链网络时，首先计算删除恶意节点后的视图v、节点总数N；其次由主节点向其他节点广播Del-message 消息，其他节点收到Del-message 消息后，并向区块链网络中的其他节点广播自己同意删除Del_Replica5；若收集到f条AgreeDel 的消息，则所有节点同意并删除该节点发起数据同步的请求，并将删除该节点后的视图v、节点总数N等消息封装；最后Del-Node5 节点退出后，主节点发送UpdataNet 信息，全网所有节点收到UpdataNet 信息后，更新区块链网络中节点总数N和视图v，完成删除该节点的流程。

图5 恶意节点被清除出网络的流程Fig.5 Procedure of removing malicious nodes from the network

定义3（信用机制节点层次变更）在本文的信用机制中，根据每次请求处理的结果，针对性地对节点的信用分值进行增减。若视图完成一次更替后，则将对所有参与交易的节点分值均加1，若交易失败后，则将拜占庭节点的积分减为原积分的50%。采用信用机制的优点主要有：1）若拜占庭节点处于上两层之中，通过减半机制将备选主节点层的拜占庭节点先降到中间层或将中间层的拜占庭节点降到警告层，通过降级剔除拜占庭节点，提高信用机制的可靠性，同时也给好节点（即非作恶节点）一到两次的缓冲机会，避免出现误操作或网络因素而造成交易请求失败，被集群直接判定为拜占庭节点，最终被移除出网络，提高了在实际应用中的灵活性；2）采用信用积分的减半操作增大对拜占庭节点的作恶惩罚，并通过奖励机制对好节点进行激励，提高好节点的分值，使其进入到备选主节点层中。本文结合这两个优点能大幅减少整个网络中的拜占庭节点数，避免PBFT 算法中类似于拜占庭节点连续当选主节点的情况，解决算法效率降低的问题。

2.3 一致性协议优化

传统PBFT 算法［24］中，若要求算法在f<（N-1）/3的基础上达到一致性共识，则表明合法数量的节点已验证通过消息，即要求消息进入确认阶段后保证已有2f-1 的节点已完成准备阶段。PBFT 算法共需两轮全网节点交互确保消息准确一致，最终使得算法的复杂度为O（N2）才可满足算法可靠性的需求。其中N为总节点数，f为存在的拜占庭节点数目。PBFT 算法存在选择主节点时的随机性，以及整个节点网络灵活性较差的问题，导致在共识过程中无法及时将恶意节点排出。当主节点发生故障或拜占庭节点成功作恶，甚至连续多次触发视图更换协议时，PBFT 算法将不断重新选取主节点进行共识阶段的信息交互验证直至共识成功，导致浪费大量网络开销。为解决上述问题，本文提出的DT-PBFT 算法以增加信用积分筛选作为基础，采用优化一致性协议和动态机制保证集群内节点的可靠性。其中增加信用积分筛选信用度较高的节点作为备选主节点，增强主节点的可信任度。动态机制降低了有问题节点被选作主节点的概率以及在共识阶段中减少一轮全网共识验证的交互信息，使算法的复杂度降低。假设全网节点数为N，那么完成一次共识过程传递需要消息的次数如式（1）所示：

M=N2+3N-1 （1）

优化后的一致性协议流程如图6 所示，主节点以及整个网络的可信任程度得到了提高，有效减少了因主节点出现故障而导致不断进行视图更换的现象，同时避免了作恶节点可连续被选为主节点的情况。基于上述优势，优化后的一致性协议保证了算法的有效性和可靠性，提高了算法的吞吐量和算法共识达成一致的成功率，尤其在节点数较多情况下，大幅降低了网络开销，节约网络资源。

图6 一致性协议流程Fig.6 Procedure of consistency protocol

3 仿真实验与结果分析

本文从吞吐量、时延、交易请求完成率以及CPU 的利用率等方面对DT-PBFT、DDBFT 和PBFT 进行对比，以验证算法的有效性、适用性及节能性。该仿真实验所用的PC 机配置为 Intel Core i7-9750H 2.6 GHz CPU及Intel Core i5-6500 3.2 GHz CPU 双机连接实现主从端分立仿真测试，通过Java 多线程机制模拟网络中的共识节点通信交互过程。

3.1 时延测试

交易时延是指客户端向主节点发送一个交易请求，以确认完成共识的时间间隔［25］。该实验的交易时延取200 次交易的平均值。图7 所示为不同算法的交易时延对比。

图7 不同算法的交易时延对比Fig.7 Transaction delay comparison among different algorithms

从图7 可以看出，当存在作恶节点时，随着节点个数的增加，相比PBFT 算法，DT-PBFT 交易时延增长的速度得到有效减慢。但因DT-PBFT 增加了动态处理机制，使得时延略高于DDBFT。DT-PBFT 虽然增大了部分时延，但在处理数据上具有较优的灵活性及稳定性。

3.2 交易请求有效完成率

交易请求有效完成率是当交易请求发出时经过一次主节点选举即可顺利完成请求，通过有效的完成率表征该网络内节点整体的可信程度及安全可靠性。随着节点数的增加，不同算法的交易完成次数对比如图8 所示。从图8 可以看出，无论节点数是多少，DT-PBFT 算法的交易完成次数均最多。

图8 不同算法的交易完成次数对比Fig.8 Number of transactions completion comparison among different algorithms

表1所示为不同算法的交易请求有效完成率对比。随着节点数的不断增加，DDBFT 和PBFT 的有效完成率呈现明显的下降趋势，而DT-PBFT 虽然有一定程度的下降，但整体变化较平稳。因此，DT-PBFT 算法在共识过程中具有较优的稳定性，由极大程度降低作恶节点当选主节点的概率。同时主动删除作恶节点的机制可以将作恶节点从网内剔除，提升了网内节点整体的安全稳定性，使得每次请求顺利达成共识，减少因多次重发引起网络资源的浪费，从而降低网络开销。

表1 不同算法的交易请求有效完成率 Table 1 Effective completion rates of transaction requests comparison among different algorithms

3.3 吞吐量测试

吞吐量是指单位时间内完成的交易数量，一般用每秒事务处理量（Transaction Per Second，TPS）来表示［17］。该实验设置客户端发送1 000 条交易请求，记录每秒能够完成共识的交易数量。为保证仿真实验结果的代表性，实验数据取多次结果的平均值（取整）。吞吐量测试主要从两方面进行分析：1）单独在信用积分机制下对4 种算法进行对比；2）在信用积分机制条件下再增加随机的增或退节点，以测试4 种算法在仿真模拟实际应用中对动态灵活性的表现情况。

3.3.1 信用积分机制作用

本节实验在PBFT 算法的基础上加入信用积分机制，仅允许对作恶节点按信用积分机制进行合理的剔除，实验结果如图9 所示。图9 显示随着节点数的增加，交互信息呈指数级增加，4 种算法共识过程的吞吐量会随之递减。因DT-PBFT 引入的信用积分机制以及将共识阶段由三阶段缩减为两阶段的优势性，能自动剔除网内积分较低的作恶节点，最大程度减少无用的开销。DT-PBFT 稳定的下降趋势明显优于DDBFT、DGPBFT 以及PBFT，证明其具有良好的安全稳定性，在存在作恶节点的环境下可以凸显出更大的优势，也更贴合实际的应用场合。

图9 不同算法在信用积分机制下吞吐量对比Fig.9 Throughput comparison among different algorithms under credit scoring mechanism

3.3.2 信用积分机制与动态机制的作用

在不同初始节点数（n>4）下，交易请求执行的过程中，本文随机对节点进行增/删，每次均增/删一个节点作为测试，各增/删十次。为了使仿真实验结果适用于实际应用的场合，本节随机设置增/删节点来代替实际应用场合中节点的入/出，并进行多次实验取均值，使结果具有代表性。因为PBFT 对于增删节点在实际测试中表现较差，所以本节主要对DT-PBFT、DDBFT 和DGPBFT 算法进行对比分析。当引入动态机制时不同算法的吞吐量对比如图10 所示。

图10 当引入动态机制时不同算法的吞吐量对比Fig.10 Throughput comparison among different algorithms when introducing dynamic mechanism

从图10 可以看出，加入动态机制对于DDBFT、DGPBFT 的吞吐量也具有一定影响，对DT-PBFT 吞吐量的影响程度并不明显。因此，DT-PBFT 具有更强的稳定性和灵活性。结合交易请求有效完成率可以看出，动态机制的引入对于DT-PBFT 只产生了低程度的吞吐量降低，但在整体完成交易请求成功率、效率以及动态特性上更能体现DT-PBFT 算法优异的综合性能。

3.4 CPU 的使用率

本文对CPU 的使用率进行仿真数据分析，为保证实验结果具有普遍性，该实验取多个时刻下不同算法的利用率进行平均后取整。不同算法的CPU 使用率对比如图11 所示。

图11 不同算法的CPU 使用率对比Fig.11 CPU utilization comparison among different algorithms

从图11 可以看出，CPU 的使用率随着节点数的增加各算法会伴随不同程度的信息交互量的提升。其中DT-PBFT 算法的上升趋势较DDBFT、DGPBFT 算法平稳。随着节点数不断增加，DT-PBFT 算法的CPU 使用率的增长率越低，具有较优的节能性。当节点数设置为22时，PBFT 和DDBFT 的CPU 使用率已经达到了65%，且DGPBFT也高于60%，而DT-PBFT仍维持在50%左右。因此，DT-PBFT 具有较优的节能性，在实际应用过程中有效地节省了CPU 资源。

4 结束语

由于PBFT 算法中的节点存在无法随时动态地加入或退出网络、主节点选取过于随意且通信开销大等问题，因此本文提出一种实用拜占庭容错算法DT-PBFT，通过引入动态加入或退出机制，使节点可以根据不同需求随时加入或退出集群，从而提高网络工作时的动态性。设计信用积分机制，通过奖惩机制对节点分数进行分段，以选择集群内信任度高的节点作为主节点，有效降低拜占庭节点当选主节点的概率，减少网络开销。同时通过动态退出机制剔除信用值较低的作恶节点，提高共识的成功率，将共识阶段中的两次全网广播改为一次。在进入正式共识前，通过对节点确认后再更新视图，减少无效的信息交互以及对带宽的消耗。实验结果表明，本文所提DT-PBFT 算法在实际应用过程更具灵活性且更加高效，在减少对网络资源消耗的同时节能性也得以提升。下一步将优化动态机制，在弱网络环境下改进本文提出的DT-PBFT 算法，保证DT-PBFT 算法的交易请求有效完成率和共识安全性的前提下，提高共识效率且减少通信开销。