基于备选候补机制的PBFT改进研究

惠二鑫 赵鹏 彭俊霞

（太原师范学院 山西省晋中市 030619）

区块链技术随着比特币的出现而问世，其并非一种新的技术，而是将分布式存储、对等网络、非对称加密、共识机制等计算机技术整合起来的新型应用模式[1]。具有去中心化、公开透明、共同维护及不可篡改等特性。

最为区块链核心技术的共识算法，是近年来分布式系统研究的热点。是保证分布式系统中各节点数据一致性的关键，目前，区块链系统中所使用的经典共识算法有PoW 算法，PoS 算法、BFT 算法、PBFT 算法等，不同的算法有各自的优缺点。许多学者在共识策略、一致性协议以及区块结构等方面对PBFT 算法进行了改进，但是该算法应用在一些需要不断扩张的领域中，依旧存在节点网络静态不可变的问题[2]，因此解决PBFT 算法动态性差成为一个急需解决的问题。

1 实用拜占庭容错算法

实用拜占庭容错算法（Practical Byzantine Fault Tolerance, PBFT）[3]是在1999年由Miguel Castro 和Barbara Liskov 提出的。能够在失效节点不超过（n-1）/3（n 为集群节点总数）的情况下确保共识系统的安全性和一致性[4]。PBFT 共识机制中所有节点需要保证数据达成最终一致性，为此PBFT 需进行一致性协议、检查点协议和视图更换协议[5]来确保各个节点的行动一致。

一致性协议是PBFT 共识算法的核心部分，主要通过预准备、准备和确认三个阶段来保证数据的一致性。在集群中每一次共识都是在某一个视图状态下进行的，且每个视图状态下只存在唯一的主节点，共识集群中的其他节点都是副本节点。共识的具体过程如图1 所示，其中C 是客户端，副本0 是主节点，副本3 是失效节点。

在传统PBFT 算法的分布式系统中，所有节点相互独立，且节点发生拜占庭错误也相互独立，共识节点和拜占庭的节点的个数分别为N、f，两者间的约束条件如公式（1）所示：

从上面公式可以看出，在分布式系统中，共识节点的总数和可接受的拜占庭节点数与密切相关。由于PBFT 共识机制本身没有动态机制，不能进行动态共识，因此每一轮的共识节点都是固定的。这个特性在联盟链的实际应用中有很多缺点。例如，新的节点无法加入到网络中；作恶节点也无法从网络中退出。

2 算法改进

2.1 算法思想

针对PBFT 算法节点无法动态感知的问题，本文将PBFT 算法进行改进，首先增设一个额外的候补节点集合，在新增的候补节点中进行备选主节点的选取，让节点可以动态增加或删除。DPBFT算法思路如图2 所示。

图2：DPBFT 算法思路

2.2 增加候补节点

将系统中的节点分为两部分，一部分是共识节点；另一部分是候补节点。共识节点负责系统的共识，候补节点用于备选主节点的选取。在候补节点集合中存放的是新加入系统的节点和共识过程中发生拜占庭错误的节点。

共识节点集合和候补节点集合用R1、R2 表示，其定义如下：

当R1 中主节点拜占庭错误或其他共识节点退出系统中时，R2中选举产生的备用主节点将其替换，被替换掉的节点将淘汰到R2集合中，保证了系统中共识节点数量的稳定，实现了节点的动态替换。

在候补节点集合R2中信任节点的选举方式采用投票选举机制。为了提升节点替换效率，R1 中节点的共识和R2 中信任节点的选取是同步进行的。主节点发生拜占庭错误时，使用R2 中选出备选主节点将其替换，整个过程省去了视图切换。

此外为预防发生拜占庭问题的主节点重复当选主节点的可能，增加一个参数H，候选主节点的计算公式如（4）所示：

其中h 表示区块高度，R2 为候补节点集合v，表示当前视图编号P 为主节点选取结果。

将视图切换过程和主节点的选举相结合，可有效减少视图切换次数，降低了整个共识过程的共识时延。

2.3 候补主节点选取

第一步：在R2 中通过公式（4）计算出候选节点，该向其他节点发送自己将要选举的消息。

第二步：当R2 中其他节点收到候选节点发送的消息后，进行确认。如果R2 集合中有半数以上的节点同意，候选节点将被选举为备用主节点，否则重新选举。

第三步：为防止在选举的过程中参与投票的节点发生超时而导致恶性循环选举问题的出现。改进后的算法为每个节点设置唯一的超时值，当参与投票时节点会有序的进行投票。有效避免所有节点的得票都不足一半情况。节点分先后，最终确定一个唯一的备用主节点，用来替换共识集合R1 中的问题节点。选举过程流程图如图3 所示。

图3：选举过程

2.4 算法的整体流程

根据改进算法的设计思想和具体设计，给出DPBFT 算法的整体流程。如图4 所示。

图4：算法整体流程

DPBFT 算法的总流程如下：

（1）备选主节点成功选举

（2）request 阶段：客户端向主节点发提案消息。

（3）pre-prepare 阶段：在此阶段主节点向所有副本节点发送预准备消息；

（4）副本节点验证收到的提案消息和主节点的状态。如果接收的提案消息正确，进入阶段；否则接受的提案消息被丢弃，转到（2）。如果主节点发生拜占庭错误，视图将进行切换，转到（1）；

（5）prepare 阶段：向所有副本节点发送准备消息；

当某个节点收到超过2f+1 准备消息并且完成验证，告知客户端发送共识达成，否则跳转到（1）；

（6）reply 阶段：若有f+1 个副本节点向客户端进行了反馈，则认为系统共识达成。

3 实验验证及分析

本次实验测试的是在系统运行一段时间后观察PBFT 算法和DPBFT 算法中共识节点和拜占庭节点数。实验将传统PBFT 和改进后的算法中共识节点设置为10 个（包含3 个拜占庭节点）；另外在候补集合中添加3 个节点，在实验开始前候补集合中不设置拜占庭节点。实验结果如图5 所示。

图5：算法效率对比实验

分析实验结果可知，当系统完成3 次视图切换后，PBFT 算法中拜占庭节点的个数始终为3。而DPBFT 算法共识集合中的拜占庭节点在每次视图切换完成后都会添加到拜占庭节点候补集合中，此时候补节点中的拜占庭节点会加1。直到三次视图切换完成，PBFT 算法中的拜占庭节点全部转移到候补节点中。

4 总结展望

本文针对PBFT 算法中节点网络无法动态变化，提出一种动态性的共识算法DPBFT（ Dynamic Practical Byzantine Fault Tolerance）。改进的算法通过增设额外的候补节点集合，在新增的候补节点中进行备选主节点的选取，当主节点出现拜占庭错误时，使用候补节点集合中的备选主节点进行替换，使系统中共识节点的数量可以动态增加或减少。

下一步将在DPBFT 算法的吞吐量上进行研究探索，在不影响系统共识效率的基础上增加吞吐量，使其可以更好的应用商业领域中。