基于防预测分组的PBFT 算法改进方案*

周昌慧 刘万里 梁 峰 李荣臻 徐 雷

（1.南京理工大学计算机与工程学院 南京 210094）

（2.南京市中西医结合医院 南京 210014）

（3.连云港市广播电视台 连云港 222000）

1 引言

区块链这一概念起源于中本聪提出的比特币［1］，其本质是在对等网络中基于密码学构建去中心化的分布式数据库［2］。利用区块链所具有的防篡改、可追溯、链上信息透明公开的特点，网络中的对等节点之间互相信任，一致行动，保证了在分布式场景下的链上数据一致可靠。近些年对于区块链的相关技术的研究愈发火热。2020 年12 月，中国信息通信研究院发布了《区块链白皮书（2020年）》针对区块链的生态和发展做出了系统性的全景观望。随着广大研究者的不懈钻研，逐渐发掘出了区块链更多的潜力，并扩展出医疗、教育、供应链、物联网等非金融领域的应用可能［3］。

区块链的核心技术中，哈希算法保证了链上数据不可篡改，分布式存储实现了去中心化，密码学保证了电子货币和个人资产的安全，共识算法解决分布式一致性问题［4］。其中，共识算法是当下区块链研究的热点。针对不同的分布式应用场景，共识算法需要满足不同的可扩展性、共识效率、数据一致性、分区容错性的需求［5］。研究者基于去中心化程度，将区块链分为公有链、私有链和联盟链。在公有链中，为满足高去中心化需求，共识算法主要以证明机制为主［6］。在私有链和联盟链中，节点身份相对较为可靠［7］，因此共识算法的关注点在于链上数据的一致性和网络的健壮性。目前在区块链领域得到广泛应用的共识算法主要有工作量证明算法（proof of work，PoW）［1］、权益证明算法（proof of stake，PoS）［8］、委任权益证明算法（delegated proof of work，DPoS）［9］和实用拜占庭容错算法（practical Byzantine fault tolerance，PBFT）［10］以及基于上述几种算法的混合算法。

2 相关工作

PBFT算法是当前区块链领域中解决分布式系统下的拜占庭将军问题的主要算法之一，并且可以实际应用在吞吐量较小的分布式系统中，比如在Hyperledger Fabric 项目中被采用［11］。该算法通过三个阶段的节点通信，其中包括两次全网络的广播通信，算法的复杂度为节点规模的指数级，所以随着网络中的节点数量的增长，算法的共识效率快速下降，并且通信开销大幅增长。

针对PBFT 算法的局限性，研究人员试图通过优化共识流程，提高算法在大规模分布式系统下的表现。一种被普遍接受的思路是将网络分组，将一个大规模问题转化成多个并行小规模问题。文献［12］提出了一种基于Raft集群的改进PBFT算法—RBFT。文献［13］提出了一种基于距离的改进PBFT 算法—DS_PBFT。文献［14］提出了一种基于通信时间分组的改进PBFT算法—GBFT。

多数结果表明，针对大规模分布式系统，网络分组确实能够减小通信开销，提高共识效率。但是网络分组的解决方案隐含了一个问题，即共识阶段由于参与共识的节点数量急剧减少所导致的分布式系统的拜占庭容错能力的大幅下降。拜占庭将军问题（Byzantine failures），是由Pease 和Leslie Lamport提出的点对点通信网络中的基本问题［15～16］。特别是在分组结果或分组规则被获知的情况下，该问题的危害性会被放大，攻击者能够以一个更小的代价瘫痪整个分布式系统。

本文测试了基于网络分组的两阶段PBFT 算法，采用固定网络分组的方式模拟网络分组结果被攻击者获知的情况。模拟结果表示，在最坏情况下，攻击者针对性地使其中的两个节点下线便可以瘫痪共识网络，而PBFT 算法该网络规模下应该能够提供四个拜占庭节点的容错能力，可以看出分组结果被获知或是被预测将带来极大的安全隐患。

为解决上述问题，分组算法应具备抗预测能力，主要通过以下特性实现：

1）随机性，分组算法中引入随机数或随机性算法。

2）不相干性，分组结果相互独立，多次分组之间互不影响。

3）局部性，只有少部分节点知道全网分组结果，大部分节点只知道局部分组结果。

基于上述思考，本文提出了一种抗预测分组算法，并证明该算法具备上述特性。本文将该分组算法结合前文的两阶段PBFT 改进算法，实现了一种基于抗预测分组的PBFT 改进算法—RS-PBFT 算法。仿真实验结果表示，该算法在具有比PBFT 算法更高的共识效率和吞吐量的同时极大程度地保留了PBFT算法的拜占庭容错能力。

3 RS-PBFT算法模型

3.1 抗预测分组算法

基于该算法需要具备局部性的考虑，抗预测分组算法的思路是由主节点进行分组，将剩余节点分为小组主节点和共识节点，主节点告知小组主节点所在小组的共识节点成员，并提供签名作为证明，然后由小组主节点向共识节点转发，这样保证了除了主节点以外的其余节点均只知道局部的分组信息。

抗预测分组算法的流程如图1。

PBFT 算法中的主节点选取基于透明的规则，即当前视图编号对节点规模取模得到主节点的序号，这种方式在存在拜占庭节点的网络环境下会产生安全隐患。抗预测分组算法的主节点选取方法参考Raft算法，通过三种身份、随机过期时间、获取选票、心跳维持状态等机制保证主节点选取具备随机性和健壮性。

非主节点在收到主节点宣告身份之后，会生成一个分组投票地图，为每个节点随机生成一个数字，然后发送给主节点。主节点会维护一个分组投票统计的数据结构用于缓存其他节点发来的分组投票地图，然后接受其他节点的投票信息，主节点自身不参与投票。主节点在收到超过全网三分之二节点的投票信息之后会根据投票结果得出分组，并告知小组主节点自身小组内的成员组成，小组主节点再转发给小组内的其他成员。

抗预测分组算法具备随机性、不相干性和局部性。主节点的选举基于随机过期时间，每个节点成为主节点的可能性相同，选举结果具备随机性。主节点不参与分组投票，分组投票由全网节点参与，基于多个随机数地图加和产生，分组结果具备随机性。每次分组结果仅依赖于本轮收集到的随机数地图，不受其他参数和环境影响，具备不相干性。除了主节点之外的节点仅知道自身分组的情况，没有其他分组的节点规模和节点身份的信息，具备局部性。进行多次模拟实验记录分组情况，得到的结果也满足随机性和不相干性。

3.2 RS-PBFT算法

RS-PBFT 算法是将抗预测分组算法与两阶段PBFT 改进算法结合，需要考虑拜占庭网络中节点可能做出的异常行为，对抗预测分组算法的流程进行修改。

在主节点选举过程中，拜占庭节点可能私自设置一个极小的唤醒时间，保证自己成为主节点，这样不仅能够知道全网的分组结果，更给系统带来极大的安全隐患。RS-PBFT 算法在主节点选举阶段加入水线，将选举阶段开始之后固定间隔的一个时间作为水线，对于水线时间之前的请求选票行为不作回应。

在主节点选举过程中，拜占庭节点可能伪造当选信息欺骗其他节点，扰乱正常的选举过程，形成系统内部“分裂”的结果。RS-PBFT 算法在投票阶段加入节点签名信息，主节点在广播当选信息时需要带上获得的全部选票信息及节点的签名信息，其他节点只有验证过该节点的正当选票数量达标才承认其主节点的身份，否则不作回应。

在分组投票过程中，拜占庭节点可能为自己和同谋分配一个极大值，保证自己和同谋成为小组主节点，多个拜占庭节点成为小组主节点会增加共识结果被操纵的可能性。RS-PBFT 算法在接受投票地图的时候设置一个阈值，对于超过阈值的数做0处理。

在节点通信过程中，拜占庭节点可能利用历史信息或伪造信息来混乱网络的正常运作。RS-PBFT 算法在进行关键性阶段的通信时，会进行报文的摘要和签名的验证，并且将通信结果写入日志。

4 仿真与实验分析

下面从通信开销、共识时延、容错能力三个方面对RS-PBFT 算法进行测试分析，实验环境为64位Windows10 操作系统，8 核CPU，8GB 运行内存，通过多进程加端口映射的方式模拟P2P节点网络，测试代码开发环境为GoLang1.15+Goland2021.2.3。

4.1 通信开销

假设系统内节点个数为n，PBFT 算法进行单次共识所需要的通信次数为

假设系统内分组数目为G，每个分组内的节点个数为g，RS-PBFT 算法进行单次共识所需要的通信次数为

RS-PBFT 算法进行一次节点分组需要的通信次数为

当n=13，G=3 时，RS-PBFT算法进行单次共识所需的通信次数约为PBFT 算法的35%，进行一次分组所需的通信次数是进行单次共识的56%，综合来看在通信开销方面具备很大优势。并且随着n增长，RS-PBFT 算法的通信次数的涨幅会比PBFT小。

4.2 共识时延

以PBFT算法为对照，以系统内节点个数n=13为起点，每次增加4 个节点，通过多组实验进行RS-PBFT 算法的共识时延测试，在此定义共识时延为发送请求到收到回复之间的间隔。测试结果如图2所示，可以看出RS-PBFT算法的共识效率较PBFT算法有明显提升。

图2 RS-PBFT与PBFT共识时延对比折线图

4.3 容错能力

此处测试RS-PBFT 算法在面对攻击者随机攻击使节点下线时的抵抗能力，以系统内节点个数n=13，G=3 为网络参数，使用RS-PBFT 算法进行多轮共识，每轮共识之前随机使一个节点下线，测试指标为不能够完成共识的轮次。测试结果如图3 所示。最后得到平均结果为3.952 轮，而PBFT 算法的结果为5轮，说明RS-PBFT算法较好地保留了PBFT算法的容错能力。

图3 RS-PBFT容错能力测试折线图

5 结语

区块链共识算法中的PBFT算法由于共识流程中大量的消息广播表现出通信开销大、共识效率低下的问题。针对这一问题，研究者普遍认可通过网络分片的方式提升算法的性能。但分组会带来拜占庭容错能力下降的问题，特别是在节点分组结果被预测的情况下，攻击者能够以更小的代价使网络失去共识能力。本文提出具备随机性、不相关性和局部性的抗预测分组算法，并考虑拜占庭节点行为做出抗拜占庭算法改进，将其与两阶段PBFT 改进算法结合提出RS-PBFT 算法。经过分析和实验表明，RS-PBFT 算法在解决了通信开销大和共识效率低下的问题，并且在容错能力上较好地保留了PBFT算法的性能。