一种改进的实用拜占庭容错算法*

谷志峰 张 虎

（河南科技大学软件学院 洛阳 471003）

1 引言

近年来，数字货币愈发流行，对人们的生活产生了很大的影响，而区块链技术是数字货币产生的基础，区块链的本质是去中心化的分布式账本数据库，是确保数字货币安全可靠的关键技术，它需要综合共识算法、网络通信、密码学原理、智能合约等多种技术来进行实现，具有去中心化、防篡改、透明和可追溯性等特点［1~2］。区块链技术被认为是一种具有颠覆传统行业潜力的新兴技术，在金融、物联网、医疗等领域具有广阔的应用前景［3~5］。

区块链技术的关键是共识算法，共识算法用于解决去中心化分布式互联网络中如何判断区块数据的正确性和所有权的问题，从而使所有节点达成共识。根据不同的应用场景，共识算法的侧重点会有所差异。公共链主要使用PoW［6］算法、PoS［7］算法、DPoS［8］算法及其变形算法，而联盟链使用的共识算法主要有Paxos［9］算法、Raft［10］算法和PBFT［11］算法，这些共识算法主要是基于消息传递的，其中最典型的是实用拜占庭容错（PBFT）算法，PBFT 解决了先前拜占庭容错算法效率低下的问题。当系统中存在（n-1）/3 个错误节点时，它仍能保证系统的安全性和可行性，分布式共识也能得到正确的达成。

但现有的PBFT 算法仍有不足之处。在PBFT算法中，选择主节点的方式是按照节点编号大小依次进行的，这种主节点的选择方式随意性较大，并且在选择主节点后，并未验证其真伪性，这就使得被选中的主节点极有可能是恶意节点，因此，存在一定的安全隐患。虽然主节点的恶意性会在后续共识过程中被从属节点识破，并被视图切换协议推翻，但还是会造成一定程度的损失。另外频繁的视图切换也会增加系统开销并降低系统效率［12］。

针对现有的PBFT 算法主节点选举方式随意、不能保证主节点可信性等问题，本文提出一种改进的PBFT 共识算法模型——RPBFT 算法，改进后的算法分两个阶段，第一阶段利用Raft算法机制并结合积分策略选取胜利节点集合，第二阶段使用PBFT 算法进行主节点的选取，本文RPBFT 算法有效缓解了传统PBFT算法中因拜占庭节点存在而造成的视图连续切换问题，降低了通信开销，提高了共识效率。

2 算法设计

2.1 胜利节点集合选取

针对传统PBFT算法中主节点选取方法的不足之处，本文在RPBFT 算法中进行了改进，改变了PBFT 算法中主节点轮流坐庄的随意选取方式，让主节点从可信程度更高的胜利节点集合中进行选取，从而提高了主节点选取的中靶率，因此本文RPBFT算法的关键是胜利节点集合的选取，其选取方法将利用Raft算法并结合积分策略进行［13］，具体如下。

在Raft算法中的每个节点都拥有三个属性：节点状态（status）、超时时间（timeout）、当前任期（term）。

1）节点状态（status）：status 有三个状态值，即领导者（leader）、跟随者（follower）、候选者（candidate），其中领导者负责接受客户的请求，并与跟随者同步日志。当日志与大多数节点同步时，领导者通知跟随者提交日志。跟随者负责将领导者同步的日志进行接收和保存，并提交领导者通知的可以提交的日志，候选者在整个选举过程中充当的是临时角色。

节点的这三种状态的转化过程如上图1 所示，即跟随者仅负责响应来自其他节点的请求，若直到超时，跟随者仍没有收到领导者的消息，它将成为候选者并开始领导者的选举。获得多数节点选票的候选者将成为新的领导者。在宕机之前，领导者将始终保持领导者的状态。

图1 Raft算法节点状态转换

2）超时时间（timeout）：超时时间通常指的是心跳超时，心跳是领导者向跟随者发送一次心跳所需要的时间。一旦这段时间结束，跟随者会觉得这位领导者已经宕机了，这将开启一个新的选举周期。

3）当前任期（term）：Raft 算法将时间分为几个任期（term），每个任期（term）都是从领导者选举开始的。领导者被成功选举后，在整个任期内，领导者将管理整个集群。如果领导者选举失败，任期也会随之结束。

本文RPBFT 算法将在Raft 算法中的每个节点原有属性的基础上再添加一个积分（score）属性，当节点成功执行一次共识，将获取一定数量积分值，反之将会减去一定数量积分值，积分策略如下：首先每个节点的原始积分为0，当节点成功执行一次共识过程，积分在10 及其以上的节点，其积分累加0.2，积分在5~10之间的节点，其积分累加0.5，积分在0~5 之间的节点，其积分累加1，具体如式（1）所示：

若节点在共识过程中出现错误，则积分在10及其以上的节点，其积分减1，积分在5~10 之间的节点，其积分减3，积分在5 以下的节点，积分直接降为0，具体如式（2）所示：

利用Raft 算法，每个节点都会拥有一个积分值，根据节点的积分值从大到小的顺序对节点进行排序，形成初始节点集合｛n1，n2，…，ni｝，其中i表示节点的编号，编号的最大值为系统节点的总数N，根据实用拜占庭算法共识原理，节点中的拜占庭节点的最大容忍数为（N-1）/3，所以系统节点中合法节点的最小数目应为（2N+1）/3，因此，可以从初始节点集合中按顺序选出（2N+1）/3 个节点作为胜利节点集合｛c1，c2，…，cj｝，其中j表示胜利节点的编号，j的最大值为（2N+1）/3，这样本文算法的第二阶段中主节点的选取可以从可信度更高的胜利节点集合中进行选择，从而优化了传统PBFT 算法中主节点选取的盲目和随意性问题。

2.2 共识过程

胜利节点集合确定之后，本文RPBFT 算法将借助PBFT算法的一致性协议算法思想使系统中节点达成共识，具体过程如图2所示。

图2 PBFT算法共识过程

图中节点0 表示主节点，节点1 和节点2 表示普通节点，节点3表示拜占庭节点，节点0的传统选举方式是p=v mod n，其中v 表示视图编号，n 表示节点数量，本文RPBFT算法中节点0首先将从算法第一阶段中选取的胜利节点集合中选取，然后再参与一致性协议算法，具体流程如下：

1）请求阶段：客户端c 向节点0 发送内容为的请求消息。其中ts 是时间戳，ms 是需要共识的内容。该阶段主要用于将需要共识的消息传递给主节点。

2）预准备阶段：主节点收到请求后，将分配一个序号给需要共识的内容ms，然后向所有普通节点广播预准备消息<，ms>，其中vi是视图号，sn 是消息ms 的序号，bf是请求消息ms的简要，普通节点收到预准备消息后，要对消息序号sn 和简要bf 进行检查。在该阶段主要完成两个工作：一是为共识内容分配序号，二是主节点将消息传输给其他节点。

3）准备阶段：编号为i的节点首先会对收到的预准备消息的消息签名、消息序号sn 和摘要bf 进行验证，如果验证通过，则将向所有普通节点广播内容为的准备消息，当2f+1 个不同节点接收到与预准备消息一致的准备消息时，准备阶段完成。该阶段的任务是：验证在预准备阶段和准备阶段接收的视图编号、分配给共识内容ms的序号和消息内容。

4）确认阶段：节点在准备阶段完成后，进入确认阶段。节点i将向所有节点发送一条确认消息，其中D（ms）是消息ms 的验证签名。接收到确认消息后，节点将对消息签名和视图号的一致性进行检查。当检查通过并接收到2f+1个与预准备消息一致的确认消息时，确认阶段完成。

5）响应阶段：该阶段用于向客户端发送共识成功消息。其中rs 是请求的最终执行结果［14］。

3 虚拟仿真测试

3.1 实验设置

本文在Win7 系统下，利用实验室局域网内6台计算机和VMware虚拟机平台（Linux CenterOS系统），简易模拟30 个区块链节点，虚拟节点IP 地址如表1所示。

表1 实验节点

实验环境配置如表2所示。

表2 实验设备配置和开发环境

本文利用Java 语言编写了PBFT 算法程序，然后利用Raft算法思想并结合积分策略对PBFT算法进行优化，得到本文算法RPBFT 算法，本文利用开源测试工具OpenSTA 软件对这两种算法的数据吞吐量和共识时延进行测试，并对测试结果进行分析，分析表明RPBFT 算法在数据吞吐量以及共识时延上都有所改进。

3.2 数据吞吐量测试

吞吐量是指单位时间内交易完成的数量。它是衡量共识算法性能的重要指标。吞吐量的大小显示了系统负载承受、事务处理或交易请求的能力。通常用TPS表示，TPS公式为

其中，∆t为出块所用的时间，T∆t为出块时间内完成的交易数量［12］。

由于吞吐量的大小与节点的数量有关［15］，因此本文测试将在共识节点数量分别为5、10、15、20、25、30 个的情况下，对各算法的吞吐量进行测试，并将测试数据导入Origin 分析软件进行分析，绘制出两种算法的吞吐量对比图，如图3所示。

图3 数据吞吐量对比图

从图3 中可以看出，随着节点数量的增加，两种算法的吞吐量都有所下降，但RPBFT 算法的吞吐量仍高于原始PBFT算法。

3.3 共识时延测试

共识时延表示交易提交和写入之间的时间差，即完成一次共识所需的时间。它是衡量共识算法运行效率的重要指标。较低的共识延迟使交易能够快速确认，使得区块链更加安全和实用［12］。用公式可以表示为

其中Tdelay为一次交易所需要的时间，Tc为确认交易执行成功的时间，Tp为交易产生的时间。两种算法的共识时延对比如图4所示。

图4 共识时延对比图

从图4 中可以看出，随着节点数量的增加，两种算法的共识时延都有所增加，但本文算法RPBFT具有更低的共识时延。

4 结语

传统的PBFT 共识算法中主节点选取比较随意，节点的可靠性无法得到保证，本文针对PBFT算法中主节点选举随意的问题提出了一种改进策略，该策略以PBFT算法为基础，优化了PBFT算法中主节点的选举方法，将PBFT 算法中主节点轮流坐庄的选举方法改为从本文算法选出的胜利节点中进行选取，从而缩小了主节点的选取范围，经实验证明，改进后的算法数据吞吐量较传统PBFT 算法有很大的提高，而共识时延较传统PBFT 算法有所降低。