基于可验证延迟函数的改进实用拜占庭容错算法

王春东，姜鑫

基于可验证延迟函数的改进实用拜占庭容错算法

王春东*，姜鑫

（天津理工大学 计算机科学与工程学院，天津 300384）（ ∗ 通信作者电子邮箱michael3769@163.com）

针对实用拜占庭容错（PBFT）共识机制的主节点选择不合理和高交易延迟问题，提出一种基于可验证延迟函数（VDF）的改进实用拜占庭容错共识机制VPBFT。首先，针对原有的PBFT算法引入投票机制进行节点选取，并根据随机投票结果将节点划分为普通节点、投票节点、备份节点和共识节点；其次，改进PBFT算法主节点选举机制，即使用VDF进行主节点选举，并利用上一区块哈希值和用户私钥生成随机数，增加主节点的不可预测性，保证共识安全；最后，优化PBFT算法的共识过程，将共识过程简化为三个阶段，从而降低算法复杂度，减少通信开销。实验结果表明，所提出的VPBFT在安全性和共识性能方面优于原有PBFT算法。

区块链；实用拜占庭容错；可验证延迟函数；投票机制；哈希函数；交易延迟

0 引言

区块链技术是结合密码学、点对点网络、分布式存储、共识机制和激励机制的分布式网络数据存储技术，具有分布式对等结构、去中心化信任、数据公开透明和防篡改特点［1］，近年来已经被应用于医疗数据共享［2］、辅助医疗决策和解决重大公共卫生等领域。

区块链没有中央权威节点，所有节点都可平等地参与共识过程。因此，共识机制［3］是确保数据一致性，维护系统安全的核心要素。区块链主要共识算法有工作量证明（Proof of Work， PoW）、权益证明（Proof of Stake， PoS）、委托权益证明（Delegated Proof of Stake， DPoS）和实用拜占庭容错（Practical Byzantine Fault Tolerance， PBFT）等［4］。其中，PoW算法主要应用于公有链中，以比特币为代表的区块链节点通过算力竞争主节点地位，主导共识过程；PoS算法根据节点拥有的币龄决定挖矿难度，拥有最高权益的节点更容易获得新区块的记账权和区块奖励；DPoS算法［5］通过拥有权益的节点使用代币投票选出共识节点，需要代币激励。所以，以上基于证明的共识机制不适用于医疗数据共享领域。

联盟链中的PBFT共识算法不仅考虑系统中的故障节点，而且通过大多数诚实节点一致共识忽略恶意节点作恶行为。与公有链相比，PBFT节点更加稳定，共识效率更高，更符合医疗数据共享联盟链需求。

针对现有研究和PBFT算法的不足，本文提出一种基于可验证延迟函数（Verifiable Delay Function， VDF）的实用拜占庭改进算法VPBFT。首先，在原有PBFT算法中引入投票机制进行节点选举，并成立共识节点委员会，根据随机投票结果将节点分为普通节点、候选节点、投票节点和共识节点；其次，提出一种基于VDF的主节点选择机制，参与节点分布式运行VDF并相互验证结果，实现当前视图下主节点的分布式选举；最后，将PBFT算法的共识过程修改为请求、响应和承诺三阶段，降低通信开销，提高共识效率。

1 相关知识

1.1　PBFT共识算法

1.1.1PBFT共识过程

PBFT共识过程如图1所示。具体共识流程［16］如下：

图1　PBFT共识过程

1.1.2垃圾回收机制

垃圾回收机制［17］是指PBFT算法定期生成系统日志文件，当共识发生错误时进行恢复，以确保系统中大多数节点都可保存状态机中最新数据。主要协议如下：

1.1.3视图更换协议

主节点选举：共识节点网络根据如下计算公式生成新视图下主共识节点。

1.2　可验证延迟函数

VDF［19］是有固定运算顺序并且可以快速验证的大规模并行算法，由初始化算法Setup、计算算法Eval和验证算法Verify组成，算法流程如图2所示。

图2　VDF算法流程

2 VPBFT算法设计与实现

2.1　整体思想

PBFT作为强一致性共识机制，当网络中共识节点数目过多时很难快速达成共识，同时区块生成率较低。为了使PBFT算法更符合医疗数据共享场景，本文提出一种基于VDF的改进算法VPBFT。该算法使用投票机制进行节点选取，并改进主节点选举策略，利用VDF延迟可验证特性分布式选举主节点。最后，优化PBFT算法共识过程，提高通信效率。VPBFT算法设计流程如图3所示。具体改进措施如下：

在PBFT算法中引入投票机制进行节点选举，根据投票结果将节点划分为普通节点、投票节点、备份节点和共识节点，由可信度较高的投票节点随机选举产生备份节点和共识节点主导共识过程，减少通信开销。

提出基于VDF的主节点分布式选举，在节点选取阶段生成主节点后，各主节点独立运行VDF的初始化函数，通过将上一区块哈希值和自身私钥作为函数输入保证VDF输出唯一性。同时，设置延迟参数检测恶意挖矿竞争，抵抗旷工硬件优势带来的并行加速优势，保证共识安全。

为减少通信开销，本文方案将共识过程简化为请求、响应、承诺三个阶段。投票式节点选取和分布式主节点选举策略保证了系统节点的可靠性，因此删除PBFT算法中客户端和系统节点之间的交互操作，由主节点完成与客户端的交互。

图3　VPBFT算法流程

2.2　算法设计

2.2.1系统节点选取

为了增加参与节点的可信度，保证共识安全，本方案使用投票机制进行节点选取，通过随机节点广播投票，其余节点相互验证方式选举系统节点。设置节点委员会实现不同节点间相互制约，同时根据网络规模设定节点数量，保证系统稳定运行。

委员会节点由普通节点、投票节点、备份节点和共识节点组成，其中，投票节点负责对备份节点和共识节点进行推荐和投票，并验证和转发主节点广播交易。作为系统选举初始化节点，投票节点由普通节点实名认证生成；共识节点发起新区提案并对交易进行验证，主导当前视图的共识过程；备份节点不可发起新区块共识，但可以验证和接收新区块，并拥有全网数据副本，当共识节点有违规和退出行为时，由备份节点递补；普通节点可以发布交易，不可参与共识，可以随机加入和退出。VPBFT节点模型如图4所示。

VPBFT网络中系统节点数量可动态调整。从共识节点中选择主节点，同时隔离恶意节点，在视图更换时伴随系统节点重新选举，根据节点可靠性对普通节点、投票节点、备份节点和共识节点角色动态调整，以适应动态网络，优化共识性能。

图4　VPBFT节点模型

VPBFT节点选择投票过程如下：

2）投票节点汇总本地投票信息表，得到当前网络规模下各共识节点、备份节点和普通节点数目，生成委员会节点列表并相互广播确认。

3）各投票节点收集委员会各投票节点广播信息，当有效广播信息超过/2时，完成本视图下节点选取过程。

2.2.2主节点选举策略

VPBFT分布式主节点选举过程如下：

1）初始化阶段：各共识节点独立计算私钥哈希值初始化随机安全参数，通过私钥保密性保证分布式随机生成，确保VDF去中心化运行。根据节点规模设置延迟时间，保证共识速度和出块效率，参数的设置使得恶意节点使用硬件优势并行加速不可行。最后各共识节点运行Setup函数生成计算参数和用于验证参数，Setup函数计算公式如下：

2）竞争阶段：各共识节点完成参数初始化后，以最新区块高度的哈希值作为输入，运行VDF计算函数Eval，竞争主节点地位，广播计算结果、证明和证明参数，便于其余节点验证。Eval函数计算公式如下：

共识节点和备份节点收到验证广播后，运行VDF验证函数Verify，校验通过后保存结果值哈希值到本地索引表并转播广播内容，验证失败将消息丢弃。Verify函数计算公式如下：

在时间段中，参与竞争共识节点不断接收计算哈希值广播，并与当前存储哈希值进行比较，小于当前哈希值则进行替换操作，否则丢弃此哈希值。最终每个共识节点保留一份时间段内生成最小哈希值记录，广播此记录。

图5　VPBFT主节点选举流程

2.2.3VPBFT共识过程

本方案提出的VPBFT算法使用分布式网络拓扑结构，事务的发起方从原始客户端变为主节点。假设共识网络中参与节点原始状态一致，那么每个节点的配置信息、存储备份和区块高度等也相同，保证了节点参与竞争主节点的公平性。

PBFT是一个经典的分布式共识算法，它的三阶段请求方法也基于分布式进行设计，主要目的是在以状态机副本为主的分布式系统中正确执行指令顺序，由于在区块链上达成共识需要在整个网络中进行多次信息广播和验证，因此可以合并原始客户端发送阶段，由当前主节点完成与客户端的交互行为，减少共识过程中信息的传递，提高共识效率。

VPBFT共识过程具体步骤如下：

1）发起共识。主节点根据共识策略从内存池中选举事务并将它们打包到一个请求消息中进行广播，以启动新一轮共识。如果共识节点和普通节点在超时之前接收到广播消息，将对消息进行验证；否则主节点违规超时，其余共识节点广播视图更换消息，请求更换视图。

2）广播响应消息。共识节点和备份节点如果在超时之前接收所有的请求消息，对消息进行验证，验证通过进行广播回复，否则尝试更换视图。

3）收集响应消息并广播承诺消息。主节点和其余节点在超时前收集足够的回复消息并进行验证，如果验证通过将进行广播验证，否则将更改视图。

4）收集承诺消息并生成新区块。参与共识的每个节点如果在超时前收集到足够多有效承诺消息，则在验证通过后将生成新区块并相互广播，实现区块同步，完成共识。

3 VPBFT算法实验分析

3.1　安全性分析

VPBFT的安全性主要体现在高可靠性和高容错性两方面，具体分析如下。

3.1.1可靠性分析

VPBFT安全性主要受两个方面影响：投票式节点选取保证只有随机投票数较高的节点才能参与系统，维持系统节点安全性；主节点选举策略实现当前视图下主节点的分布式随机选举，避免恶意节点控制共识过程，危害系统安全。

在节点选取阶段，普通节点经过实名认证获得投票权利，保证了投票节点的可信度与安全性。备份节点和共识节点都由投票节点随机投票选取获得，同时备份节点监督共识节点行为，当共识节点产生违规行为时，投票节点和备份节点都可启动视图更换协议，完成主节点更换，保证共识过程安全。

主节点选举过程中根据系统规模设置延迟参数抵抗恶意用户通过硬件优势竞争主节点地位，避免算力浪费。同时，用户分布式独立生成安全参数保证系统去中心化特性，并使用区块哈希值和用户私钥组合方式增加主节点选举的不可预测性，通过一系列节点广播和累计有效广播保证当选节点有效主导共识，增加系统可靠性。

随着系统运行，节点选取策略和主节点安全选举保证了VPBFT共识的可靠性，降低恶意节点当选主节点概率，使主节点错误率降低，提高了VPBFT的效率，即单位时间内的工作量（Transaction Per Second， TPS），共识结果更加可靠，实验结果如图6所示，VPBFT算法比PBFT算法可靠性更高。

图6　VPBFT和PBFT的可靠性比较

3.1.2容错性分析

3.2　性能验证

本文实现了一个基于Python语言的区块链原型系统，并分别运行PBFT和VPBFT算法，通过测试和比较验证了VPBFT算法的整体效果。测试环境为Windows操作系统，CPU为Intel Core i5-6200U 2.30 GHz，内存为8 GB，固态硬盘为512 GB。

3.2.1交易延迟测试

交易延迟指由节点发起的一笔交易从广播到添加到区块所消耗的时间。在P2P网络上进行测试，设定事务数为200，分别对5、10、15、20、25和30个节点进行测试，结果如图7所示。可以看出，VPBFT算法交易延迟明显比PBFT算法短，而且随节点数的增加，PBFT算法的交易延迟增加得更快，而VPBFT算法交易延迟相对稳定，增长较慢。因此，在节点数较多的情况下，VPBFT算法优势更明显。

图7　VPBFT和PBFT的交易延迟比较

3.2.2出块效率比较

出块效率为单位时间内生成区块数，是区块链系统稳定性的重要标志。如图8所示，通过区块链原型测试，在15个共识节点参与共识场景下，分别对100、200、300、400和500个事务量进行比较，PBFT算法平均出块效率为2.17，VPBFT算法的平均出块效率为3.94，是PBFT的1.8倍。因此，与PBFT算法相比，VPBFT算法的出块效率有较大的提高，在稳定性方面具有优势。

图8　不同事务量下VPBFT和PBFT的出块效率比较

为了进一步比较大规模节点下VPBFT与PBFT的出块效率，分别设置了100到500节点模拟验证区块出块效率，实验结果如图9所示。

图9　不同节点规模下VPBFT和PBFT的区块生成率比较

由图9可以看出，在VPBFT与PBFT运行期间出块效率是稳定的，由于VPBFT进行了恶意节点识别与主节点随机选举，改进后的VPBFT共识机制更高效，在大规模网络节点下出块效率更高。

4 结语

为了提高PBFT算法主节点选择安全性和共识效率，本文提出了VPBFT，并通过投票处理将节点分为普通节点、投票节点、备份节点和共识节点。同时使用可验证延迟函数改进PBFT主节点选举方式，增加主节点选举的不可预测性，保证共识安全。最后，共识节点参与共识过程，并将共识过程简化为三个阶段，减少带宽资源消耗。实验结果表明，VPBFT算法在可靠性、容错性、交易延迟和区块生成率方面比PBFT算法具有优势，更适合于实际应用。

[1] 张亮，刘百祥，张如意，等. 区块链技术综述［J］. 计算机工程， 2019， 45（5）：1-12.（ZHANG L， LIU B X， ZHANG R Y， et al. Overview of blockchain technology［J］. Computer Engineering， 2019， 45（5）： 1-12.）

[2] 罗文俊，闻胜莲，程雨. 基于区块链的电子医疗病历共享方案［J］. 计算机应用， 2020， 40（1）：157-161. （LUO W J， WEN S L， CHENG Y. Blockchain-based electronic medical record sharing scheme［J］. Journal of Computer Applications， 2020， 40（1）： 157-161.）

[3] 郭上铜，王瑞锦，张凤荔. 区块链技术原理与应用综述［J］. 计算机科学， 2021， 48（2）：271-281.（GUO S T， WANG R J， ZHANG F L. Summary of principle and application of blockchain［J］. Computer Science， 2021， 48（2）： 271-281.）

[4] WANG W， HONG D T， HU P， et al. A survey on consensus mechanisms and mining strategy management in blockchain networks［J］. IEEE Access， 2019， 7： 22328-22370.

[5] 方维维，王子岳，宋慧丽，等. 一种面向区块链的优化PBFT共识算法［J］.北京交通大学学报， 2019， 43（5）：58-64. （FANG W W， WANG Z Y， SONG H L， et al. An optimized PBFT consensus algorithm for blockchain［J］. Journal of Beijing Jiaotong University， 2019， 43（5）： 58-64.）

[6] LI Y， WANG Z， FAN J， et al. An extensible consensus algorithm based on PBFT［C］// Proceedings of the 2019 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. Piscataway： IEEE， 2019： 17-23.

[7] GAB B， WU Q， LI X， et al. Classification of blockchain consensus mechanisms based on PBFT algorithm［C］// Proceedings of the 2021 International Conference on Computer Engineering and Application. Piscataway： IEEE， 2021： 26-29.

[8] 任秀丽，张雷. 基于实用拜占庭容错的改进的多主节点共识机制［J］. 计算机应用， 2022， 42（5）：1500-1507. （RENG X L， ZHANG L. Improved multi-primary node consensus mechanism based on practical Byzantine fault tolerance［J］. Journal of Computer Applications， 2022， 42（5）： 1500-1507.）

[9] 甘俊，李强，陈子豪，等. 区块链实用拜占庭容错共识算法的改进［J］. 计算机应用， 2019， 39（7）：2148-2155.（GAN J， LI Q， CHEN Z H， et al. Improvement of blockchain practical Byzantine fault tolerance consensus algorithm［J］. Journal of Computer Applications， 2019， 39（7）： 2148-2155.

[10] GUAN G， FENG L， NING J， et al. Improvement of practical Byzantine fault tolerant consensus algorithm for blockchain［C］// Proceedings of the IEEE 3rd International Conference on Frontiers Technology of Information and Computer. Piscataway： IEEE， 2021： 182-187.

[11] JIANG W， CHEN L， WANG Y， et al. An efficient Byzantine fault-tolerant consensus mechanism based on threshold signature［C］// Proceedings of the 2020 International Conference on Internet of Things and Intelligent Applications. Piscataway： IEEE， 2020： 1-5.

[12] CHEN R， WANG L， ZHU R， et al. An improved practical Byzantine fault tolerance algorithm based on vague sets and random numbers［C］// Proceedings of the 7th International Conference on Intelligent Computing and Signal Processing. Piscataway： IEEE， 2022： 151-155.

[13] ZHANG Z， ZHU D， FAN W. QPBFT： practical Byzantine fault tolerance consensus algorithm based on quantified-role［C］// Proceedings of the IEEE 19th International Conference on Trust， Security and Privacy in Computing and Communications. Piscataway： IEEE， 2020： 991-997.

[14] YU G， WU B， NIU X. Improved blockchain consensus mechanism based on PBFT algorithm［C］// Proceedings of the 2nd International Conference on Advances in Computer Technology， Information Science and Communications. Piscataway： IEEE， 2020： 14-21.

[15] 刘懿中，刘建伟，张宗洋，等. 区块链共识机制研究综述［J］. 密码学报， 2019， 6（4）：395-432.（LIU Y Z， LIU J W， ZHANG Z Y， et al. Overview on blockchain consensus mechanisms［J］. Journal of Cryptologic Research， 2019， 6（4）： 395-432.）

[16] 李腾. PBFT共识算法的改进及其应用研究［D］. 邯郸：河北工程大学， 2021： 2.（LI T. Improvement and application of practical Byzantine fault tolerance consensus algorithm［D］. Handan： Hebei University of Engineering， 2021： 2.）

[17] 颜丙辉. 基于拜占庭容错的区块链共识方法研究［D］. 哈尔滨：哈尔滨工程大学， 2020： 2.（YAN B H. Research on block chain consensus methods based on Byzantine fault tolerance［D］. Harbin： Harbin Engineering University， 2020： 2.）

[18] 孙耀景. 基于实用拜占庭容错算法的区块链共识算法研究［D］. 湘潭：湘潭大学， 2020： 2.（SUN Y J. Research on the blockchain consensus algorithm based on practical Byzantine fault tolerant algorithm［D］. Xiangtan： Xiangtan University， 2020： 2.）

[19] BONEH D， BONNEAU J， BÜNZ B， et al. Verifiable delay functions［C］// Proceedings of the 2018 Annual International Cryptology Conference， LNCS 10991. Cham： Springer， 2018： 757-788.

[20] ZHOU M， LIN X， LIU A， et al. An improved blockchain consensus protocol with distributed verifiable delay function［C］// Proceedings of the 2021 IEEE International Conference on Electronic Technology， Communication and Information. Piscataway： IEEE， 2021： 330-337.

Improved practical Byzantine fault tolerance algorithm based on verifiable delay function

WANG Chundong*， JIANG Xin

（，，300384，）

To solve the problems of unreasonable primary node selection and high transaction delay in Practical Byzantine Fault Tolerance （PBFT） consensus mechanism， an improved PBFT consensus mechanism based on Verifiable Delay Function （VDF） was proposed， called VPBFT. Firstly， a voting mechanism was introduced into original PBFT algorithm to select nodes， which were divided into ordinary nodes， voting nodes， backup nodes and consensus nodes according to random voting results. Secondly， the primary node selection mechanism of PBFT algorithm was improved by using VDF for primary node selection， and random numbers were generated by the hash value of the previous block and the user’s private key to increase the unpredictability of the primary node and ensure the consensus security. Finally， the consensus process of PBFT algorithm was optimized by simplifying consensus process into three stages， thereby reducing the algorithm complexity and communication overhead. Experimental results show that the proposed VPBFT outperforms the original PBFT algorithm in terms of security and consensus performance.

blockchain; Practical Byzantine Fault Tolerance (PBFT); Verifiable Delay Function (VDF); voting mechanism; hash function; transaction delay

1001-9081（2023）11-3484-06

10.11772/j.issn.1001-9081.2022111708

2022⁃11⁃18；

2023⁃02⁃24；

“科技助力经济2020”重点专项（SQ2020YFF0413781）；天津市科委重大专项（15ZXDSGX00030）； 国家自然科学基金面上—联合基金资助项目（U1536122）。

王春东（1969－），男，天津人，教授，博士，CCF会员，主要研究方向：网络信息安全、普适计算、移动计算、智能信息处理； 姜鑫（1997－），男，山东菏泽人，硕士研究生，主要研究方向：区块链、数据共享。

TP301

A

2023⁃02⁃25。

This work is partially supported by “National High Science and Technology for Economy 2020” Key Project （SQ2020YFF0413781）， Major Project of Tianjin Science and Technology Commission （15ZXDSGX00030）， National Natural Science Foundation of China （General Joint Fund） （U1536122）.

WANG Chundong， born in 1969， Ph. D.， professor. His research interests include network information security， ubiquitous computing， mobile computing， intelligent information processing.

JIANG Xin， born in 1997， M. S. candidate. His research interests include blockchain， data sharing.