基于联盟链PBFT的BRaft共识算法.pdf
《基于联盟链PBFT的BRaft共识算法.pdf》由会员分享,可在线阅读,更多相关《基于联盟链PBFT的BRaft共识算法.pdf(6页珍藏版)》请在咨信网上搜索。
1、第 22卷 第 9期2023年 9月Vol.22 No.9Sept.2023软 件 导 刊Software Guide基于联盟链PBFT的BRaft共识算法白尚旺,达泓宇,高改梅,刘春霞,党伟超(太原科技大学 计算机科学与技术学院,山西 太原 030024)摘要:针对联盟链共识算法不能同时实现低时延、高吞吐量、高安全性的问题,提出适用于联盟链的可容错Raft共识算法BRaft(PBFT-Raft)。BRaft利用RSA签名解决拜占庭Leader节点篡改日志的问题,并在PBFT算法三段协议的基础上,引入标识位W,解决拜占庭Follower节点恶意响应Leader节点的问题,确保在拜占庭节点发送错
2、误消息的情况下日志项依然能够被正确提交。实验结果表明,BRaft在保证算法可理解性和共识效率的同时,提高了算法安全性。关键词:Raft算法;PBFT算法;拜占庭节点;数字签名;标识位DOI:10.11907/rjdk.222261开 放 科 学(资 源 服 务)标 识 码(OSID):中图分类号:TP311 文献标识码:A文章编号:1672-7800(2023)009-0132-06BRaft Consensus Algorithm Based on Consortium Chain PBFTBAI Shangwang,DA Hongyu,GAO Gaimei,LIU Chunxia,DANG
3、 Weichao(School of Computer Science and Technology,Taiyuan University of Science and Technology,Taiyuan 030024,China)Abstract:Aiming at the problem that the current alliance chain consensus algorithm cannot achieve low latency,high throughput,and high security at the same time,a fault-tolerant Raft
4、consensus algorithm suitable for alliance chain-BRaft(PBFT-Raft)is proposed.BRaft used digital signature to solve the problem of Byzantine leader node tampering with logs,and based on the three-stage agreement of PBFT algorithm,it introduced the flag W,which solve the problem of Byzantine follower n
5、ode maliciously responding to leader node,and ensure that the error message sent by Byzantine node can be prevented.In this case,the log entry can still be submitted correctly.The experimental results show that BRaft improves the security of the algorithm while ensuring the comprehensibility and con
6、sensus efficiency of the algorithm.Key Words:Raft algorithm;PBFT algorithm;Byzantine node;digital signature;identification bit0 引言2008年,中本聪首次提出比特币,数字货币进入了新篇章1。在比特币创始论文中,区块链被定义为一种数据结构,其实质是一个由区块构成的去中心化的链式账本,每个区块按时间顺序表示用户之间的事务传输。区块链具有去中心化、不可篡改、匿名性等基本特性2,因此它还可以作为一个分布式网络协议,使彼此不认识的不同参与者之间建立信任关系3,而不涉及任何中心角
7、色或第三方。共识算法作为区块链中的最重要一环,着重解决存在故障时如何协调分布式节点之间的交互,保证各节点所维护的数据副本的一致性,避免出现数据不一致、信息不对称等问题。根据区块链的去中心化程度,可将其划分为公有链、联盟链和私有链。对于不同的区块链,采用的共识算法也不同。以比特币、以太坊为代表的公有链去中心化程度最高,通常采用的共识机制有工作量证明机制PoW(Proof of Work)4、权益证明机制(Proof of Stake,PoS)5、委托权益证明(Delegated proof of stake,DPoS)6。私有链的去中心化程度最低,它的写入权限由个人或某个组织机构所掌握,一般应用
8、于企业内部。以Hyperledger Fabric为代表的收稿日期:2022-10-24基金项目:太原科技大学科研启动基金项目(20192062);太原科技大学研究生教学改革研究课题(JG2022010)作者简介:白尚旺(1964-),男,硕士,太原科技大学计算机科学与技术学院教授、硕士生导师,研究方向为数据库与软件工程技术、区块链技术;达泓宇(1996-),女,太原科技大学计算机科学与技术学院硕士研究生,研究方向为区块链技术、共识算法;高改梅(1978-),女,博士,太原科技大学计算机科学与技术学院副教授,研究方向为网络安全、区块链技术;刘春霞(1977-),女,硕士,太原科技大学计算机科学
9、与技术学院副教授,研究方向为软件工程、数据库技术、区块链技术;党伟超(1974-),男,博士,太原科技大学计算机科学与技术学院副教授,研究方向为智能计算、区块链技术。本文通讯作者:高改梅。第 9 期白尚旺,达泓宇,高改梅,等:基于联盟链PBFT的BRaft共识算法联盟链去中心化程度介于二者之间,一般由多个机构共同参与管理,并允许授权的节点加入网络。与公有链相比,具有更好的交易速度和安全性,是区块链落地的主要方向。目前,联盟链共识算法主要分为拜占庭容错(Byzantine Fault Tolerance,BFT)共识算法7和非拜占庭容错共识算法两类。BFT算法的核心就是在存在恶意节点的情况下,保
10、证其余正常节点间能够达成共识。常用的BFT共识机制主要有实用拜占庭容错(Practical Byzantine Fault Tolerance,PBFT)8、联邦拜占庭容错(Federal Byzantine Fault Tolerance,FBFT)9和投机拜占庭容错(Speculative Byzantine Fault Tolerance,SBFT)10共识机制,但这类共识算法普遍存在通信复杂度较高的问题。非拜占庭容错共识算法是建立在对所有节点的信任机制上,具有低时延、高吞吐量的优势,常见的有Paxos11、Raft12共识算法,但不能容忍拜占庭节点的存在,由此提出一系列共识算法的改进方
11、案。Copeland 等13结合 Raft共识算法和 PBFT 共识算法的优点提出 Tangaroa 共识算法,该算法在日志复制的过程中添加了哈希函数,确保在有恶意节点攻击的情况下仍能保持安全性,但是该算法无法容忍多个拜占庭节点的联合攻击。Martino等14在Tangaroa共识算法的基础上提出一种新型高性能或可扩展性的BFT共识算法Scal-ableBFT,可用于实现大规模的高性能许可私有链。黄冬艳等15提出一种基于Raft集群的拜占庭容错共识算法RBFT,将节点进行分组,组内采用Raft共识机制,而每组的Leader节点重新构成一个管理组实行PBFT算法。该算法较好地融合了Raft共识效
12、率高和PBFT拜占庭容错性能好的特点,但需要引入大量的监督节点。本文在分析Raft算法的不足后,通过对已有拜占庭算法进行研究,使用RSA签名以防止节点身份伪造和消息篡改,解决在共识过程中Leader节点作恶的问题。同时,在PBFT算法三段协议的基础上引入标识位W保证算法的一致性,实现Raft算法在日志复制过程中的拜占庭容错,目的在于提高Raft算法安全性的同时又保证比PBFT更低的算法复杂度。1 相关工作1.1PBFT共识算法PBFT共识机制将原始拜占庭容错共识算法的通信复杂度从指数级降到了多项式级,共识效率得到明显提高。PBFT算法中的核心概念有3个部分:视图(view)、副本(replic
13、a)、角色(primary,backups)。视图表示当前系统的全局状态,副本表示系统中所有参与共识的节点,而在每个视图中,副本的角色又分为两类:主节点(primary)和备份节点(backups)。假设系统中的恶意节点数为f,PBFT需要满足总节点数至少为3f+1。算法的共识过程如图1所示。PBFT的具体执行步骤如下:请求阶段,客户端向主节点发送请求;预准备阶段,主节点在收到客户端发出的请求后,先检查请求的合法性,若合法,主节点将此消息写入本地日志然后进入预准备阶段,并向其他副本节点广播预准备消息;准备阶段,副本节点在收到消息后先确认消息的正确性,若正确就进入准备阶段,并向其他副本节点广播准
14、备消息,同时将预准备消息和准备消息写入本地日志;确认阶段,当一个节点在一段时间内接收到 2f个以上的准备消息,就发送确认消息给所有副本节点;应答阶段,副本节点接收到2f个来自其他节点的确认消息后,验证消息的一致性,并向客户端返回应答消息。客户端收到2f+1个应答消息,表明共识完成。1.2Raft共识机制Raft算法是 Paxos 算法的改进,是从多副本状态机的角度提出,用来对多副本状态机的日志复制进行管理16。一个Raft群集中有若干个成员节点,这些节点有3种角色:领导者(Leader)、参与者(Candidate)和跟随者(Follower),并由Leader统一管理。(1)Leader。L
15、eader由Candidate通过领导者选举协议选举产生,用于接收客户端的请求,并将客户端请求对应的日志项追加到自己的日志中,然后转发给Follower进行复制,当日志复制到大多数节点时,Leader将发送请求给Follower进行日志提交。(2)Follower。Follower接收并复制由Leader同步的日志。在Leader广播可以提交日志后,提交日志。(3)Candidate。在 Leader 选举过程中由 Follower 过渡为Leader的临时状态。参与共识的节点之间通过异步远程过程调用(RPC)进行交互,调用请求主要分为以下两种:RequestVoteRPC:用来进行投票请求,
16、包含 Candidate节点的当前任期、日志中最后一条日志项的索引和任期等17,接收到请求的Follower通过验证当前Candidate节点提供的任期号,选取最优 Leader,避免拜占庭 Leader节点丢弃日志或对日志任意排序。AppendEntriesRPC:用来进行日志复制,包含领导者id、领导者当前任期term、新附加的日志项、前一个条目在Leader 日志中的索引 prevLogIndex、任期 prevLogterm 以及提交索引commitIndex。应答确认准备预准备请求 主节点副本节点?副本节点2 副本节点3客户端Fig.1PBFT consensus process图1
17、PBFT共识过程 1332023 年软 件 导 刊1.2.1领导者选举图2描述了3种不同状态节点之间的关系。当服务器启动时,所有节点初始状态为Follower。经过一段随机时间后,Follower节点当前任期加一,然后转变为Candidate节点,Candidate节点首先给自己投票,随后将RequestVote请求发送给 Follower 节点以获取唯一投票。当 Candidate 节点接收到大多数选票时,转变为Leader节点18。收到投票请求的 Follower 节点首先会检查 Candidate最后一条日志项的任期号,只有在发出 RPC 的 Candidate的日志项具有的任期号比它本
18、地保存的日志项的任期号更大,或者在任期号相同但具有比它更大的索引值时,Follower才会将他们的选票授予该节点。1.2.2日志复制日志是由日志项组成,日志项是一种包含用户指定的数据、索引值、Leader节点任期的数据格式。如图3所示,首先,客户端向 Leader 节点发送需要执行的请求;其次,Leader节点在收到客户端请求后会将带有客户端命令的日志项追加到自己的日志中,并向 Follower 节点发送 AppendEntriesRPC,进行日志复制。收到AppendEntriesRPC请求的Follower节点首先将自身最新条目与RPC中的条目进行比较。如果两个日志项具有相同的索引和任期,
19、Follower会将接收到的新的日志项附加到其日志并将AppendEntriesRPC发送给Leader,表示复制成功。当Leader在收到集群中大多数Follower复制成功的响应后,将此日志项标记为已提交。日志项中的指令交由状态机执行,并将结果反馈给客户端。2 BRaft共识算法在 Raft 算法中,日志是否提交由 Leader 节点判断,Leader节点在向所有 Follower节点复制日志项时,如果收到一定数量 Follower节点的响应,Leader将日志项中的指令交由状态机执行,并在未来的心跳消息或者日志复制消息中广播给 Follower节点。但在拜占庭环境下,Leader节点可以
20、发送错误消息给Follower节点,Follower节点可以在没有将日志项添加至日志列表时恶意响应Leader,以误导Leader收到了一定数量的响应。由此可知,仅依赖Leader无法确保日志项被正确复制,进而无法确保算法安全性。BRaft通过对客户端的消息进行数字签名以防止拜占庭节点作恶。在Follower节点对Leader的消息进行验证之后,算法在结合PBFT的三段协议的基础上引入标识位W,确保在拜占庭节点作恶的情况下日志项依然能够被正确提交。这样,不仅减少了Follower节点作恶的可能性,并且相比于PBFT算法的准备和确认阶段,节点之间不再需要额外通信,理论上提高了日志追加的时效。2.
21、1前提与假设假设BRaft集群中一共包含n个节点,f个拜占庭节点BRaft算法需要满足式(1)以确保算法的容错能力。n 3f-2 (Leader为拜占庭节点)n 3f+1 (Leader为正常节点)(1)在共识过程中,节点存在宕机或者作恶的可能性,BRaft的容错能力分两种情况:当 Leader节点为拜占庭节点,Follower集群节点数为n-1,Follower节点中存在的拜占庭节点数为f-1,如果n-1-(f-1)个节点已经达成共识,来自 f-1 个拜占庭节点的决策不会影响正常节点的决策(n-1-(f-1)-(f-1)f-1),由此可知BRaft集群节点总数需要满足n3f-2;当Leade
22、r节点为正常节点时,Follower集群节点数为n-1,Follower节点中存在的拜占庭节点数为f,如果n-1-f个节点已经达成共识,来自f个拜占庭节点的决策不会影响正常节点的决策(n-1-f-ff),此时BRaft集群节点总数需要满足n3f+1。2.2签名验证BRaft 通过 RSA 数字签名作为消息被篡改的检测机制,且在算法运行过程中,所有的共识节点均拥有客户端的公钥PK。在签名过程中,首先,客户端对原文进行Hash运算,得到摘要M,并使用客户端私钥SK对摘要M进行加密,形成数字签名D;然后,将原文和数字签名一同发送给Leader,Leader节点在收到客户端发来的数字签名及原文后,会将
23、自身信息与客户端消息打包一起发给Follower节点,Follower节点在收到数字签名后,先用客户端公钥 PK对摘要进行解密,确定是客户端消息之后,再用同样的Hash算法对原文计算摘要值,判断Leader是否对消息进行篡改。clientLeaderFollowerFollowerFollower1.请求5.返回3.日志复制 Fig.3Log copy process图3日志复制过程Follower CandidateLeader超时,开始选举超时,触发选举收到大多数选票发现新的Leader节点发现更高任期的Leader节点Fig.2Raft state transitions图2Raft状态
24、转换 134第 9 期白尚旺,达泓宇,高改梅,等:基于联盟链PBFT的BRaft共识算法在 Follower 节点对客户端消息验证之后,BRaft 结合PBFT三段协议的思想,并通过标识位W保持在拜占庭环境节点的一致性,即每一个Follower节点存在一个标识位W(0表示验证不通过,1表示验证通过),每个标识位的初始状态为 0。当 Follower节点经过验证之后的标识位 c为1,且有 2f+1个 c发生变化且值的总和至少为 f+1时,可以证明Leader为正常节点。当Follower节点经过验证之后的标识位 c 为 0,Follower 集群中当有 2f-1 个标识位发生变化,且这2f-1个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 联盟 PBFT BRaft 共识 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。