高效的实用拜占庭共识算法.pdf

2023 年第 5 期计算机与数字工程收稿日期：2022年11月20日，修回日期：2022年12月14日作者简介：王薛平，男，硕士研究生，研究方向：区块链。1引言区块链技术1因具有去中心化、防篡改等特点被广泛应用到金融、物联网和贸易管理中，是将数字加密、智能合约2、共识机制等技术结合起来构建而成的一种分布式的系统架构，由于去中心化的特性，应用领域3也越来越广泛。区块链的网络架构一般采用点对点网络4架构，所有节点的地位都是对等的，并且以拓扑结构相互连接，节点间采用中继转发的模式进行通信。由于没有中心化的参与，所以节点间的一致性由共识算法来保持。区块链的共识算法5是为了解决状态一致性和拜占庭将军问题。早先为了解决拜占庭将军问题，提出了拜占庭容错（BFT）算法6，依靠节点间传递消息对提案达成共识，由于消息复杂度的问题使得BFT的实用性较低。1999年，Castro等提出实用拜占庭容错共识算法（PBFT）7，在BFT共识算法的基础上进行改进，降低了复杂度，在实际应用中有了较高的可行性。PBFT算法8被应用至联盟链中，但是相对应的也会产生一些缺陷，首先PBFT算法的验证阶段较为繁琐，出于安全性的考虑会对准备阶段的信息进行重新验证，以防止视图更改后出现信息不一致的情况。在联盟链的环境中，会对每个节点进行认证以及监督，网络较为稳定，视图也不会频繁发生变化，即使在视图发生变化后增加同步和验证过程高效的实用拜占庭共识算法王薛平（西安邮电大学计算机学院西安710121）摘要针对实用拜占庭容错（PBFT）共识算法中存在通信开销过大、效率低下的问题，论文提出一种高效的实用拜占庭（Efficient Practical Byzantine Fault Tolerance，EPBFT）算法。为了解决共识效率低下的问题，EPBFT算法改变主节点的选取过程，淡化主节点在广播交易过程中的功能，在系统初始化后通过数据的验证和备份，使得链中的每一个节点相对平等且高效；为了减少节点间的通信次数，将共识过程修改为request和prepare-response两个阶段。实验结果表明，与PBFT算法相比，系统响应时延从原来的39ms减少到30ms，吞吐量从原来的351TPS提高至696TPS，系统性能有了明显提高。关键词PBFT；EPBFT；通信开销；时延；吞吐量中图分类号TP311.5DOI：10.3969/j.issn.1672-9722.2023.05.004Efficient Practical Byzantine Consensus Tolerance AlgorithmWANG Xueping（School of Computer，Xian University of Posts and Telecommunications，Xian710121）AbstractAiming at the problems of high communication overhead and low efficiency in practical Byzantine fault tolerance（PBFT）consensus algorithm，this paper proposes an efficient practical Byzantine fault tolerance（EPBFT）algorithm.In order tosolve the problem of low consensus efficiency，EPBFT algorithm changes the selection process of the master node，desalinates thefunction of the master node in the broadcast transaction process.After the system initialization，the data is verified and backed up tomake each node in the chain relatively equal and efficient.In order to reduce the number of communication between nodes，the consensus process is modified to request and prepare response.Experimental results show that compared with PBFT algorithm，the system response delay is reduced from 39ms to 30ms，the throughput is increased from 351TPS to 696TPS，and the system performance is significantly improved.Key WordsPBFT，EPBFT，communication overhead，time delay，throughputClass NumberTP311.5总第 403期2023 年第 5期计算机与数字工程Computer&Digital EngineeringVol.51No.5997第 51 卷也同样能够确保数据的一致性9，从而可以优化共识过程。本文针对上述问题，结合区块链应用的特点，提出一种改进的PBFT算法。本算法淡化了原算法中主节点的功能转化为客户端直接向网络中的节点通信，由网络中的节点来进行广播。在其他节点收到请求消息后，进行消息的验证，其次通过 request和prepare-response两个阶段来完成共识并且减少了节点间的通信开销。2背景及相关工作在目前区块链的共识算法中工作量证明（PoW）10以及权益证明（PoS）11主要应用于公有链，前者依靠算力后者则依靠数字货币来进行共识操作，由于资源消耗较大以及实际场景没有数字货币等问题，导致了实用性较差的结果。方轶等提出一种基于环签名的PBFT共识算法改进方案12，通过特殊的签名方式有效提高了效率以及吞吐量，但是通信开销的问题并没有得到解决。张仕将等提出了一种基于Gossip协议的拜占庭共识算法13，通过Gossip协议进行通信提升了算法的安全性，但是根本的效率问题并没有改善。徐浩等提出动态实用拜占庭容错14，该协议允许节点的动态加入和退出，具有很好的安全性和鲁棒性，在效率方面的表现较差。3优化后的EPBFT算法针对PBFT算法中通信开销过大、效率低下的缺点，本文提出了优化后的 EPBFT算法。主要应用场景为节点相对较为固定的联盟链，根据联盟链的特点对传统的PBFT算法进行了改进，优化其共识过程，在不影响其安全的前提下，提升了效率并且减少了网络开销。3.1算法设计在联盟链中，每个节点都有较高的信誉度，网络运行环境相对稳定，在此情景下通过选取主节点再进行广播消息的方式极大的影响了效率。因此本文算法通过数据备份和验证阶段代替选取主节点，可以保证安全性15的同时提高了效率。并且改变客户端向主节点提交请求的过程，在联盟链中所有节点都可以将消息广播至整个网络16。3.2算法过程系统初始化后，网络中的节点开始进行数据备份和验证。为了满足共识的要求，每个节点需有相同的区块数据、视图编号、区块高度等。完成验证和备份后，系统进入请求阶段和准备响应阶段，以下为算法具体步骤：Step 1：系统初始化，进行数据验证和备份阶段，每个节点从链最长的节点开始备份，获取后进行验证再将其保存。Step 2：超过 2f+1 个节点备份成功时验证成功。Step 3：事务发起者C节点向其他节点广播已签名的事务。Step 4：各节点接受到消息后，验证其合法性，进入请求阶段，当累计数量每个节点超过2f+1时对其他节点进行广播。Step 5：进入准备响应阶段并验证消息合法性，如果合法返回C节点进行缓存，等收到足够数量的交易后，生成一个区块。其算法的流程图如图1所示。C123requestprepare-response图1EPBFT算法流程图系统初始化后的备份和验证阶段，目的是通过备份使每个节点数据信息一致，验证获取数据的节点是否为恶意节点。备份阶段：需进行备份的节点C1向最长链节点C2发送请求，待收到请求到检查视图编号是否一致。如果编号一致，则同步消息到C1，如果不一致，根据其他节点拥有的不同数据块，将备份请求和对应数据区块发送至其他节点。验证阶段：其他节点在收到最长链节点C2发送的备份数据后，会验证其合法性。如果合法，将数据保存并把消息广播至整个网络。如果验证失败，将其丢弃并保存其他节点发送的验证结果。当节点 C1 同步其他节点返回的消息数量超过 2f+1时，可确保每个节点的信息状态一致。在验证完成后，每个节点将信息广播至整个网络进入共识阶段。以下为具体的共识过程。请求阶段：C向其他节点进行广播，其他节点收到消息后，如果消息通过则进入准备响应阶段，如果未通过验证，表明C节点可能为恶意节点需要进行验证并广播更改视图。准备响应阶段：节点向其他节点广播准备响应消息，并保存请求和准备响应消息。当消息数量超王薛平：高效的实用拜占庭共识算法9982023 年第 5 期计算机与数字工程过2f+1与其他节点一致，则该阶段完成。4实验分析本节将通过通信开销、时延、吞吐量等指标对EPBFT算法进行测试，并与原PBFT算法进行对比以验证算法的实用性。4.1通信开销对比1）PBFT通信开销通过对前文的PBFT算法进行分析，共识过程总通信次数为2n（n-1）。更改视图时，通信的次数为（n-1）2。从其他节点收到视图变更后，发送变更确认信息至其他节点，此阶段通信次数为（n-1）。假设视图变更的概率为P时，通信的总次数为C=2n（n-1）+Pn（n-1）（1）2）EPBFT通信开销上文对EPBFT算法的共识过程分析可知通信次数为n（n-1）。同步信息在数据同步验证阶段发送至其他节点通信次数为（n-1）。在同步验证的过程中，所有节点将信息发送到除自身之外的所有节点，该过程的通信次数为（n-1）2，同步完成后，所有节点将信息返回，通信次数为（n-1）。因此算法的总通信次数为C=n（n-1）+P（n2-1）（2）以4个节点、6个节点、8个节点为例，当不更改视图的情况下，测试其通信次数，实验结果如图2所示。121086420通信次数468节点数EPBFTPBFT图2通信开销对比图基于以上分析，EPBFT算法的设计有效减少了共识过程的数据传输次数以及通信开销，且不减少系统的容错能力，提高了共识效率。4.2吞吐量对比吞吐量指在单位时间内系统处理的事务数，用TPS（Transaction Per Second）表示。本次实验设置从客户端发出1000条请求，在不同的节点数下记录每秒完成的交易数并进行对比，如图3所示。图3吞吐量对比图通过对图3的分析，在节点越来越多的情况下吞吐量缓缓下降，在对比后可知优化后的 EPBFT算法远高于原 PBFT算法。平均吞吐量从原来的351TPS提高到696TPS。4.3通信时延对比本次通信时延实验的对比在搭建的基于java的考试系统上进行，环境搭建在vmware中，操作系统是ubuntu16.4。图4通过查询考试结果信息为例，以40次查询结果为例，横坐标x表示了第x次查询，纵坐标t表示查询时Fabric的响应时间。实验结果表明，使用原PBFT算法是时延均值为39ms，而使用优化后的EPBFT时延的均值为30ms。相比较之下系统时延方面有较好的提升，使得用户拥有更好的体验。图4系统响应时间5结语提出了一种基于 PBFT 算法改进的 EPBFT 算法。PBFT算法中选取主节点的过程，在不影响整体操作的情况下进行了省略，极大地提高了数据同步以及验证的效率，同时优化了共识过程。通过优化使得EPBFT算法更适用于联盟区块链的环境。通过实验可知，共识过程中通信开销从原来的2n（n-1）缩短至n（n-1），有效减少了通信开销。吞999第 51 卷吐量从原来的 351TPS 提高至 696TPS。通过搭建的区块链平台进行测试，系统响应时延从原来的39ms减少到30ms。在未来的工作中，可对算法的安全性进行提高，增加节点的动态添加功能，对算法进一步优化，提高算法的适用性。参 考 文 献1邵奇峰，张召，朱燕超，等.企业级区块链技术综述J.软件学报，2019，30（9）：2571-2592.SHAO Qifeng，ZHANG Zhao，ZHU Yanchao，et al.Survey of enterprise blockchainsJ.Journal of Software，2019，30（9）：2571-2592.2LIU Jing，LIU Zhentian.A Survey on Security Verificationof Blockchain Smart Contracts J.IEEE Access，2019，7：77894-77904.3张利华，蓝凡，姜攀攀，等.基于双区块链的医疗记录安全存储与共享方案 J.计算机工程与科学，2019，41（09）：1581-1587.ZHANG Lihua，LAN Fan，JIANG Panpan，et al.A securemedical record storage and sharing scheme based on dual-blockchainJ.Computer Engineering&Science，2019，41（09）：1581-1587.4M.Wichtlhuber，P.Heise，B.Scheurich，et al.Reciprocitywithvirtualnodes：SupportingmobilepeersinPeer-to-Peer content distribution C/Proceedings of the9th International Conference on Network and Service Management（CNSM 2013），Zurich，2013：406-409.5袁勇，倪晓春，曾帅，等.区块链共识算法的发展现状与展望 J.自动化学报，2018，44（11）：2011-2022.YUAN Yong，NI Xiaochun，ZENG Shuai，et al.Blockchain Consensus Algorithms：The State of the Art and Future Trends J.Acta Automatica Sinica，2018，44（11）：2011-2022.6范捷，易乐天，舒继武.拜占庭系统技术研究综述 J.软件学报，2013，24（6）：1346-1360.FAN Jie，YI Letian，SHU Jiwu.Overview of smart contracttechnology in blockchain system J.Journal of Software，2013，24（6）：1346-1360.7Sukhwani H，Martinez J M，Chang X，et al.PerformanceModeling of PBFT Consensus Process for PermissionedBlockchainNetwork（HyperledgerFabric）C/2017IEEE 36th Symposium on Reliable Distributed Systems（SRDS）.IEEE，2017.8邵奇峰，金澈清，张召，等.区块链技术：架构及进展J.计算机学报，2018，41（05）：969-988.SHAO Qifeng，JING Cheqing，ZHANG Zhao，et al.Blockchain Technology：Architecture and progress J.Journalof Computer Science，2018，41（05）：969-988.9张协衍，章兢.基于连续时间模型的多智能体系统采样 数 据 一 致 性J.自 动 化 学 报，2014，40（11）：2549-2555.ZHANG Xieyan，ZHANG Jing.Sampled-data Consensusof Multi-agent Systems with General Linear DynamicsBased on a Continuous-time Model J.Acta AutomaticaSinica，2014，40（11）：2549-2555.10袁勇，王飞跃.区块链技术发展现状与展望 J.自动化报，2016，42（4）：481-494.YUAN Yong，WANG Feiyue.Blockchain：The State ofthe Art and Future Trends J.Acta Automatica Sinica，2016，42（4）：481-494.11Y.Cheng，X.Hu，J.Zhang.An Improved Scheme ofProof-of-Stake Consensus Mechanism C/2019 4th International Conference on Mechanical，Control and Computer Engineering（ICMCCE），Hohhot，China，2019：826-8263.12方轶，邓建球，丛林虎，等.一种基于环签名的PBFT区块链共识算法改进方案 J.计算机工程，2019，45（11）：32-36.FANG Yi，DENG Jianqiu，CONG Linhu，et al.An Improved Scheme for PBFT Blockchain Consensus Algorithm Based on Ring Signature J.Computer Engineering，2019，45（11）：32-36.13张仕将，柴晶，陈泽华，等.基于Gossip协议的拜占庭共识算法 J.计算机科学，2018，45（2）：20-24.ZHANG Shijiang，CHAI Jing，CHEN Zehua，et al.Byzantine Consensus Algorithm Based on Gossip ProtocolJ.Computer Science，2018，45（2）：20-24.14X.Hao，L.Yu，L.Zhiqiang，et al.Dynamic PracticalByzantine Fault ToleranceC/2018 IEEE Conferenceon Communications and Network Security（CNS），Beijing，2018：1-8.15韩璇，袁勇，王飞跃.区块链安全问题：研究现状与展望 J.自动化学报，2019，45（1）：206-225.HAN Xuan，YUAN Yong，WANG Feiyue.Security Problems on Blockchain：The State of the Art and FutureTrendsJ.Acta Automatica Sinica，2019，45（1）：206-225.16Chen J，Zhang X，Shangguan P.Improved PBFT Algorithm Based on Reputation and Voting MechanismJ.Journal of Physics Conference Series，2020，1486：32023.王薛平：高效的实用拜占庭共识算法1000