基于完美二叉树通信拓扑的拜占庭容错共识算法.pdf
《基于完美二叉树通信拓扑的拜占庭容错共识算法.pdf》由会员分享,可在线阅读,更多相关《基于完美二叉树通信拓扑的拜占庭容错共识算法.pdf(10页珍藏版)》请在咨信网上搜索。
1、基于完美二叉树通信拓扑的拜占庭容错共识算法李淑芝熊伟志邓小鸿*王智强刘惠文(江西理工大学信息工程学院赣州341000)(赣南科技学院电子信息工程学院赣州341000)(赣州市云计算与大数据重点实验室赣州341000)摘要:针对实用拜占庭容错(PBFT)算法中主节点可预测、通信复杂度高和作恶节点缺少惩罚机制的问题,该文提出一种基于完美二叉树通信拓扑的联盟链拜占庭容错算法(PBT-BFT)。首先设计了信誉评估模型对节点的行为进行评估,同时提出基于信誉的可验证随机函数(R-VRF),使得随机抽取概率与信誉值呈正相关,保证了拥有不同信誉值的节点抽签的公平性和随机性。然后,设计了完美二叉树通信拓扑,将通
2、信复杂度降低至线性复杂度,同时提出轮换主节点和流水线工作机制,提高了共识效率。实验结果表明,与PBFT相比,平均吞吐量提高了121.6%,平均时延降低了73.8%,能够很好地适用于大规模网络节点的联盟链。关键词:完美二叉树;通信拓扑;共识机制;拜占庭容错中图分类号:TN915;TP309文献标识码:A文章编号:1009-5896(2023)07-2484-10DOI:10.11999/JEIT220798Byzantine Fault-Tolerance Consensus Algorithm Based onPerfect Binary Tree CommunicationLIShuzhiX
3、IONGWeizhiDENGXiaohongWANGZhiqiangLIUHunwen(College of Information Science,Jiangxi University of Science and Technology,Ganzhou 341000,China)(School of Electronics and Information Engineering,Gannan University of Science and Technology,Ganzhou 341000,China)(Key Laboratory of Cloud Computing and Big
4、Data,Ganzhou 341000,China)Abstract:Consideringtheproblemsofapredictableprimarynode,highcommunicationcomplexity,andlackofpunishmentmechanismformaliciousnodesinPracticalByzantineFaultTolerance(PBFT)algorithm,aconsortiumchainByzantineFault-TolerantalgorithmbasedonPerfectBinaryTreecommunicationtopology(
5、PBT-BFT)isproposed.InPBT-BFT,areputationevaluationmodelisdesignedtoevaluatethebehaviorofnodes.Atthesametime,aReputation-basedVerifiableRandomFunction(R-VRF)isproposed,whichmakestheprobabilityofrandomextractionpositivelycorrelatedwiththereputationvalue,andensuresthefairnessandrandomnessofthelotteryfo
6、rnodeswithdifferentreputationvalues.Then,aperfectbinarytreecommunicationtopologyisdesignedtoreducethecommunicationcomplexitytolinearcomplexity,andarotatingprimarynodeandPipeliningareproposedtoimprovetheconsensusefficiency.TheexperimentalresultsshowthatcomparedwithPBFT,theaveragethroughputisincreased
7、by121.6%,andtheaveragedelayisreducedby73.8%,whichcanbewellappliedtotheconsortiumchainoflarge-scalenetworknodes.Key words:Perfectbinarytree;Communicationtopology;Consensusmechanism;Byzantinefaulttolerance收稿日期:2022-06-16;改回日期:2022-12-07;网络出版:2022-12-09*通信作者:邓小鸿deng_基金项目:国家自然科学基金(61762046,62166019),江西省
8、自然科学基金(2020BABL202032),江西省教育厅科研项目(GJJ218506,GJJ209412)FoundationItems:TheNationalNaturalScienceFoundationofChina(61762046,62166019),TheNaturalScienceFoundationofJiangxiProvince(2020BABL202032),TheScientificResearchProjectofEducationDepartmentofJiangxiProvince(GJJ218506,GJJ209412)第45卷第7期电子与信息学报Vol.45
9、No.72023年7月JournalofElectronics&InformationTechnologyJul.20231 引言比特币1于2008年一经问世,就引起广泛关注,区块链是比特币的核心支撑技术,已在智慧交通、智慧医疗、智慧教育等领域中广泛应用2,3。共识算法作为区块链中的核心技术,保证了去中心化的节点间的数据一致性,直接影响着区块链系统的性能,已经成为区块链领域的热点研究问题,据研究者统计,当前主流的共识算法已超25种4。实用拜占庭容错(PracticalByzantineFaultTolerance,PBFT)算法5作为一个被广泛应用于联盟链中的共识算法,其共识过程不消耗算力,也
10、不依赖代币,更加适合于联盟链应用场景。尽管如此,PBFT共识算法也存在着不足,主要有以下3个方面:(1)主节点的选择不具备随机性,各节点轮流担任主节点,每一轮的主节点可预测;(2)共识过程中节点间互相转发消息,通信复杂度高;(3)缺少惩罚机制,当主节点作恶时,仅通过视图切换保障共识过程的继续,恶意节点仍然存在于系统中,留下安全隐患。针对PBFT存在的问题,研究者提出了较多优化算法,文献6提出一种基于Raft集群的改进拜占庭共识算法,通过对节点分组,组内采用Raft进行共识,由Raft共识机制选举出领导者,领导者间采用PBFT机制进行共识,保证了共识效率。文献7通过建立信誉模型,选信誉最高的节点
11、为主节点,加入pre-commit阶段来减少节点间通信次数,提高了系统性能。文献8提出了使用时间权重值来选择合适节点参与共识过程,选时间权重值最大的节点为主节点,缩小了共识节点规模,提高了共识效率。文献9提出了一种随机选择算法(RandomSelection,RS),投票选出候选节点,再从候选节点中用RS算法随机选择出固定数量的节点参与共识过程,加速系统达成共识。文献10把共识节点分为主节点、2级节点和3级节点,同时划分主网层和次网层,通过Raft选举领导者的方式选出主节点,通过分层的方式把共识规模缩小提高共识效率。文献11提出一种特征分组模型将共识节点分成多组,缩小共识规模,同时加入信用机制
12、,信誉值最高的作为主节点,优化了共识效率。文献12提出了一种针对高频交易应用场景的改进算法(trust-basedPracticalByzantineFaultTolerance,tPBFT),该算法依据信誉评分机制将节点分为共识节点和普通节点,缩小共识节点规模,使用可验证随机函数(VerifiableRandomFunction,VRF)13选择主节点,并简化了PBFT共识过程中的pre-prepare阶段,减少节点间的交互开销,提高了共识效率。然而上述研究在主节点选取上,要么缺少随机性要么缺少一定的门槛,少有两者并存的策略。在降低通信复杂度上,上述研究通过牺牲部分去中心化程度,缩小共识节点
13、规模,以此缓解通信复杂度过高的问题,缺少改变节点间通信方式的考虑。针对上述问题,本文提出了基于完美二叉树通信拓扑的拜占庭容错共识算法(ByzantineFault-TolerantalgorithmbasedonPerfectBinaryTreecommunicationtopology,PBT-BFT),在主节点的选取和通信结构上做出改进,旨在提高主节点选择的安全性和降低通信复杂度。本文的主要工作如下:(1)针对PBFT类共识算法主节点选取安全性不足的问题,将信誉评估模型与VRF可验证随机函数结合,设计了基于信誉的可验证随机函数(R-VRF),将原本VRF的均匀随机抽取改进为不均匀的随机抽取
14、。实现了既有信誉值的门槛限制又有随机性,同时随机抽取依据信誉值的高低区分被随机到的概率,保证了不同信誉值节点抽签的公平性。(2)针对PBFT类共识算法通信复杂度高的问题,本文依据信誉评估模型构建完美二叉树通信拓扑,将通信复杂度降低至线性复杂度,同时加入轮换主节点和流水线工作机制以提高共识效率。2 PBT-BFT算法2.1 算法模型本文所提PBT-BFT共识算法总体模型如图1所示,分为以下4个步骤:(1,2,.,n)步骤1在每一轮共识开始前,所有共识节点通过信誉评估模型计算出每个共识节点的信誉值,并依据信誉值的高低对共识节点进行排序且编号;步骤2从编号节点的前50%中使用R-VRF(将在2.3节
15、介绍)抽选出主节点,设置了主节点抽取的门槛限制,同时保证了随机性和公平性;步骤3依据主节点和共识节点编号顺序构建节点消息路由表,节点消息路由表是节点间转发消息的规则,该规则依据完美二叉树通信拓扑转发消息,父节点给子节点及兄弟节点转发消息,以降低通信复杂度;步骤4共识过程中的消息转发依据节点路由表进行。共识过程主要分为Prepare和Commit两个阶段,通过轮换主节点和流水线工作的措施,将上一轮共识中的Commit阶段与下一轮共识中的Pre-pare阶段的消息同时通过完美二叉树通信结构一起传递,提高共识效率。2.2 信誉评估模型完美二叉树通信拓扑的消息传递由根节点逐层第7期李淑芝等:基于完美二
16、叉树通信拓扑的拜占庭容错共识算法2485传向叶节点,上层节点宕机或作恶对下层节点影响更大,为了能够更好地体现完美二叉树的特点,本文设计了更加契合完美二叉树通信拓扑特点的信誉评估模型。本文中信誉评估指标共分为3大类:节点贡献度、节点作恶度和节点历史信誉度。各项评估指标如表1所示。(1)节点贡献度:是信誉值增加的唯一途径,每轮共识能够增加的信誉值范围在01。公式为Cir=InfoirMaxInfoir+Bir(1)=0.5BirInfoir/MaxInfoir其中,引入了系数 和,将创建有效区块和转发消息两部分的比重保持一致。同时将整个节点贡献度所能增加的信誉值控制在1分之内。创建有效区块的取值为
17、0或1,式(1)中指转发消息数与最大转发消息数的比值,更加准确地衡量其转发消息占比。(2)节点作恶度:是扣除信誉值的唯一途径,主要包括宕机行为和作恶行为。每轮共识中能够扣除的信誉值范围在02,具体节点作恶度计算方法为Wir=(Downir+Badir)Cost(x)(2)Cost(x)在本文的树形网络通信过程中,同一个节点在一轮共识内宕机或作恶只会出现0次或1次。本文设定出现宕机行为最高扣除信誉值1分,出现作恶行为最高扣除信誉值2分,为连续作恶系数,默认值为1,若同一节点出现连续作恶行为,将执行自增操作,提高连续作恶成本。为代价函数,代价函数主要用于调节通信网络中不同层次节点的作恶代价。本文采
18、用的代价函数如式(3)所示。z(x)xxCost(x)式(3)中函数在0,+)区间内单调递减,值域为(0,1,为防止代价降低至0,设置最小代价值0.1。为通信网络中的层次,随着 逐渐增大,逐渐降低,即节点越远离根部,所需付出的代价越小Cost(x)=z(x),z(x)0.10.1,z(x)sum(j)j 0将,所对应的概率求和,记为,即该分组内的二项分布累积分布,若,且时代表抽中,否则代表未抽中。2.4 通信拓扑PBFT共识过程中通信复杂度过高,其主要原因在于节点间两两互相通信,在网络拓扑中此种方式被认为是网状拓扑结构,文献16指出PBFT共识机制随着共识节点数量的增加,性能瓶颈主要在于通信复
19、杂度。本文对网状通信结构进行改进,将网状通信结构改为完美二叉树通信结构,其构建过程如图2所示。k2k 1O(n)当主节点抽取完成后,对节点重新编号,1号为刚抽中的主节点,2号为余下节点中信誉值最高的节点,以次类推。重新编号完成后,构建最大完美二叉树通信拓扑,使其层次遍历结果与重新排序编号结果一致,即根部为主节点,随后越靠近根部的节点信誉值越高,以此增强通信结构的稳定性。根据完美二叉树的性质,深度为 时,最大能容下个节点,超出的节点不参与此次共识。本文的完美二叉树通信结构将共识过程中的通信复杂度降低至,每个节点只需与其兄弟节点和孩子节点通信。完美二叉树通信拓扑构建完成后,每个节点都在本地维护一张
20、节点消息路由表,指明每个节点消息传递的路径,确保各节点能够按照完美二叉树通信拓扑进行消息传递,如表2所示。n2n2n+1n+1 nn节点消息路由表的构建依托于完美二叉树通信拓扑,当节点编号为 时,其左孩子节点编号为,右孩子节点为,兄弟节点为(为偶数)或n1(为奇数),将节点消息路由表构建完成。2.5 共识流程在前述工作基础上,进入共识阶段,一共分为4个阶段,包括请求、准备、提交和回复,如图3所示。图2完美二叉树通信拓扑的构建第7期李淑芝等:基于完美二叉树通信拓扑的拜占庭容错共识算法2487CRequest,tx,t,cctx(1)请求阶段:客户端给主节点发起请求消息,消息内容为,其中,为交tc
21、cc易信息,为时间戳,为客户端编号,为客户端的签名。Prepare,h,d,t1,2,.,i,Bheadhdt ii(2)准备阶段:主节点收到客户端发来的请求消息后,验证交易和客户端签名是否有效,若有效便将交易打包进区块中。主节点构建准备消息,其中 为区块高度,保证所有节点在同一区块高度下进行共识,为区块头的摘要,为时间戳,为编号为 的节点签名。hdBhead从主节点开始,将Prepare消息按照完美二叉树通信结构逐层传递到叶节点。Prepare消息传递过程中,每个节点首先验证主节点身份是否合法,通过式(7)验证函数验证其合法性,若通过,继续检查 是否正确,摘要 和是否一致,签名是否正确,若都
22、通过检查,则追加自己签名在准备消息后,再将消息转发给自己的邻接节点。Prepare消息传递到叶子节点后,重新计算节点信誉值,抽选出Commit阶段主节点,构建新的节点消息路由表。所有叶子节点将自己验证完成且签名的Prepare消息发送给Commit阶段主节点。1,2,.,iCommit,h,d,t,1,2,.,i,Bheadhdt1 ii(3)提交阶段:提交阶段主节点收到所有叶子节点的准备消息后,收集准备消息中节点的签名进行聚合,签名数量超过2/3时,通过聚合签名技术,合成唯一的签名,提交阶段主节点构建提交消息,消息内容为,其中 为区块高度,为区块头的摘要,为时间戳,为聚合后的签名,为提交阶段
23、主节点的签名,为编号为 的节点签名。从Commit阶段主节点开始,将提交消息按照节点消息路由表逐层传递,收到提交消息的节点验证消息是否有效,若有效则将自己签名追加在Commit消息后,再转发给自己的邻接节点,同时完成本地上链。Commit消息传递到最底层叶子节点后,与Prepare阶段的过程类似,叶子节点将验证完成后且签名的Commit消息发送给下一轮的主节点。Reply,h,t,c,rihtcrii(4)回复阶段:此时的主节点将新区块更新至区块链上,向客户端发送回复消息,消息内容为,其中 为区块高度,为时间戳,为客户端编号,为操作结果,为编号为 的节点签名。在共识过程中,最主要的是准备阶段和
24、提交阶段,在这两个阶段中,构建了两个完美二叉树通信拓扑结构用来完成消息的传递,主要有两个目的:轮换主节点和流水线工作机制。(1)轮换主节点:指在一轮共识中Prepare阶段和Commit阶段分别有各自的主节点。一般基于投票的共识算法中,主节点需要收集副本节点的投票结果,导致主节点在经过1对多的发送消息后,需要多对1的收集消息,增加了通信开销和节点的消息负载压力。轮换主节点后,可以避免这个问题,让Commit阶段的主节点收集Prepare阶段的投票信息,既保证了安全性,又减少了通信开销。(2)流水线工作机制:指在上述轮换主节点的情况下,新一轮共识和上一轮共识交织在一起,在完成上一轮共识Commi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 完美 二叉 通信 拓扑 拜占庭 容错 共识 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。