基于位置的改进HotStuff共识机制与仿真.pdf
《基于位置的改进HotStuff共识机制与仿真.pdf》由会员分享,可在线阅读,更多相关《基于位置的改进HotStuff共识机制与仿真.pdf(6页珍藏版)》请在咨信网上搜索。
1、468第40 卷第6 期2023年6 月真机仿算文章编号:10 0 6-9 348(2 0 2 3)0 6-0 46 8-0 6基于位置的改进HotStuff共识机制与仿真张宇翔,向海,李博,廖浩德(西南石油大学计算机科学学院,四川成都6 10 50 0)摘要:共识算法作为区块链的核心技术,是影响区块链性能的关键因素。现有主流共识算法从各种方面对共识效率进行改进,但鲜有基于位置因素的。现提出一种基于位置因素的改进HotStuff 算法。引人一种分组的机制,将节点根据位置不同分为若干组,分组内节点单独对请求进行共识,提出一种远程共识协议,由主节点将共识结果发送给其它组进行远程共识,提高每次共识能
2、够处理的请求数量。通过仿真表明,改进后的HotStuff算法较于原本HotStuff算法在吞吐量上有所提升,在通信开销、平均延迟方面有所降低。关键词:共识算法;位置;分组;联盟链中图分类号:TP302.8文献标识码:BImproved HotStuff Consensus Mechanism and SimulationBased on Location FactorsandZHANG Yu-xiang,XIANG Hai-yun,LI Bo,LIAOHaode(School of Computer Science,Southwest Petroleum University,Chengdu
3、610500,Sichuan Province)ABSTRACT:As the core technology of the blockchain,the consensus algorithm is a key factor affecting the perform-ance of the blockchain.The existing mainstream consensus algorithms improve consensus efficiency from various as-pects,but few are based on location factors.This pa
4、per proposes an improved HotStuff algorithm based on locationfactors.A grouping mechanism is introduced to divide nodes into several groups according to different locations.Thenodes within the group independently agree on requests.Then the master node sends the consensus results to othergroups for c
5、onsensus,increasing the number of requests that can be processed by each consensus.Experiments showthat the improved HotStuff algorithm has improved throughput compared with the original HotStuff algorithm,and hasreduced communication overhead and average delay.KEYWORDS:Consensus algorithm;Location;
6、Grouping;Alliance chain1引言2008年中本聪比特币:一种点对点的电子现金系统I问世,标志着区块链技术的诞生。区块链作为一个典型的去中心化的分布式数据存储系统,以其安全性,不可篡改性而被人们熟知,而在区块链系统中的所有参与者之间就一项事务达成共识需要通过共识机制来实现。可以说共识机制是区块链的核心,共识机制不仅保证了区块链的安全性,更影响着区块链的性能,如何在区块链系统中高效达成共识是制约区块链技术发展应用的重要问题2 基金项目:新工科建设数据智能与区块链应用技术(2 0 1801209004)收稿日期:2 0 2 1-10-2 0修回日期:2 0 2 1-11-0 2共
7、识算法根据容错机制的不同,可以分为故障容错(Cr a s h Fa u l t T o l e r a n c e,CFT)共识算法和拜占庭容错(ByzantineFaultTolerance,BFT)共识算法3。故障容错指参与共识过程中的节点不会作恶,只可能发生宕机等错误的情况下达成共识;而拜占庭容错指存在拜占庭将军问题4,即在参与共识过程的节点中存在故意作恶的节点的情况下保证共识过程的成功。根据应用场景的不同,可以分为公有链的共识算法和联盟链的共识算法。公有链的共识算法主要有POW共识算法5,POS共识算法6 ,DPOS共识算法7 等,这些共识算法可能会导致区块链的分叉,因此在公有链中应用
8、较多,公有链因打包上链延迟大、区块大小有限而在应用时有诸多限制,有人针对这些缺点做出了一些改进8.9 。联盟链的共识是以拜占庭共识算法为主的共识算法,有PBFT10,SBFT1,HotStuff【12 等,这些算法是强一致性算469法,不允许区块链的分叉,因此其更加适用于联盟链,而联盟链为了获得更好的性能,对于共识或验证节点的配置和网络环境有一定要求13PBFT是LISCOV等人在19 9 9 年提出的一种实用拜占庭算法,该算法解决了分布式系统中的拜占庭问题,其容错率为n3f+1,其中n是总节点数量,f是拜占庭节点数量。PBFT算法的出现,最早使用三阶段提交协议实际的解决了拜占庭将军问题。PB
9、FT的出现使得后续联盟链很多都在使用该算法,最为人们熟知的就是超级账本(HyperledgerFab-ric)【14 随着近年来区块链的兴起,PBFT的O(n)的通信复杂度使得性能随着增长的网络规模而下降。因此针对PBFT性能的提升逐渐变得重要。YIN等人在2 0 18 年提出的HotStuff算法采用了门限签名的方法实现了O(n)的通信复杂度。该算法总结对比了目前主流的拜占庭类共识协议,构建了基于经典拜占庭共识协议实现PipelineBFT的共识模式。HotStuff 创新采用了Pace-maker将活性(Liveness)和安全性(Safety)解耦,同时也提高了该共识算法的可扩展性。由于
10、HotStuff的高可用性和低复杂度,Facebook推出的Libral15正是采用了HotStuff 共识算法。然而,HotStuff算法的通信模式为全节点直接通信,若节点分布地域较广,节点间通信将会带来高延迟,从而极大降低吞吐量,造成较大的通信代价16 这是影响联盟链共识效率的重要因素。鉴于此,本文提出一种基于位置分组的根据HotStuff算法思想改进的共识协议,将节点根据位置的不同分为若干组,组内单独进行共识,再由各组主节点将共识结果传输给其它组进行共识,每次可以同时处理若干个请求,提高了共识的效率。2HotStuff算法2.1算法概述设节点总数为n,拜占庭节点的个数为f,且满足n3f+
11、1。共识过程采用视图(View)的方式进行,即每个视图达成一轮共识,视图有其唯一编号(ViewNumber)且单调递增,用来标识视图,每个视图都有一个主节点(Leader)领导所有副节点(Replica)共识,在当前共识完成后,执行View编号递增并开启下一轮共识。如果遇到了主节点机或者主节点作恶的情况,则更换主节点并开始下一轮视图。HotStuff采用了门限签名的机制,引人了一个新的概念“仲裁证书”(QuorumCertificate,Q C)。Q C指在一个三元组之上且组合了n-f个副节点部分签名进而达成共识的证明。当前阶段Leader收集到超过n-f个Replica签名确认过的数据包及V
12、iewNumber形成的一个集合,用于表示当前阶段已经被副节点达成共识。HotStuff三阶段共识流程如图1所示2.2共识过程2.2.1Prapare阶段Pre-州护点PrepareCommitCommitDecide节点1节点2节点3图1HotStuff共识各阶段流程在每一轮View开始的时候,所有Replica向Leader发送NewView消息,表示新视图的开始。NewView消息包含每个副节点对最新区块的投票签名prepareQC(允许为空),Leader收到超过n-f个NewView消息后,将收到的NewView中区块最高的prepareQC形成HighQC,保证没有更高的视图可以使
13、用,即保证了当前区块是最安全的,后续共识在此基础上展开。Leader形成HighQC后,在对应区块的后面打包新的区块并以prepare消息广播。副节点收到prepare消息后,对该消息进行签名摘要(投票)。2.2.2Pre-Commit 阶段此时Leader收集副节点的签名消息,当Leader收集到n-f个投票后,形成prepareQC,并以pre-commit消息向所有副本广播prepareQC。副节点通过pre-commit投票对Leader做出响应,并对提案进行投票。2.2.3Commit 阶段Commit阶段类似于Pre-Commit阶段,副节点收到pre-pareQC后,对prepa
14、reQC投票,此时Leader收集副节点的投票,当收集到n-f个pre-commit投票时,将其组合为precom-mitQC,以commit类型消息广播,此时副节点接收使用commit消息响应,对precommitQC进行投票。2.2.4Decide阶段进人Decide阶段后Leader节点开始收集副节点的投票,当其收到n-f个commit投票后,将它们合并为commitQC,并以decide消息的形式将commitQC发送给其余副节点。当副节点收到decide消息后,获取commitQC,将该commitQC中包含的提案视为已经提交的请求,并在自己的副本中执行该请求。完成后,副节点增加vi
15、ewNumber并启动下一个视图。2.2HotStuff复杂度分析在HotStuff的每个阶段,只有Leader向所有副节点广播,而副节点使用部分签名向发送者回复一次以完成签名和部分投票。在Leader的角度下,每阶段形成的QC都是由n-f个来自副节点的投票组成。因此,在每个阶段下,通信的复杂度是O(n)。由于有固定的阶段数,每个视图的总体复杂度为0(n)。HotStuff算法将拜占庭容错类共识算法复杂度降低到了O(n),缩小了节点间的通信开销,但是忽略了实际因素的影470响。当节点与节点间的距离过大,会导致难以避免的通信延迟和负担,从而导致吞吐量的急剧下降,随着节点间距离的增大,延迟也会随之
16、增长。随着联盟链的扩大,节点也将分布的越来越广,考虑位置因素是将会变得尤为重要。31PBHS算法随着联盟链的广泛应用,各行各业都置身于联盟链中,在实际应用场景下,节点间的各节点间距离跨域很大,节点间通信有一定延迟,这就导致链中节点间共识效率降低,而共识效率是影响联盟链实际使用的重要影响因素。将位置因素纳人考虑,根据HotStuff 的算法思想,本文提出一种改进的共识算法PBHS(PositionBasedHotStuff)算法。3.1算法概述假设系统中的总节点有n个,分为G组,每组m个节点,g(id)表示第i组第id个节点,其中m满足m3f+1,其中f是每个组内所能容纳的最大拜占庭节点。网络模
17、型使用部分同步模型,即存在一个不确定的全局稳定时间GST(G l o b a l St a b l e T i me),在指令发出后的一定时间后,所有的非拜占庭节点都能对指令的顺序及结果产生共识,从而使得网络状态确定。PBHS算法分为两个阶段,分别是Local共识阶段和Re-mote共识阶段。在每轮共识开始时,每组仅仅处理当地的请求,通过Local共识阶段可以是的组内达成共识并产生一个最终证书,该证书包含了组内节点对请的签名。接下来,每组与每组之间共享本地的请求和最终证书,为了减小组与组之间的通信,使用新的乐观响应协议。每组将收到的请求和最终证书在组内共识,此时如果发现错误,可以启用远程视图更
18、改协议。最后,在收到所有的请求和证书后,执行该系列请求,但是每个组仅返回当地请求的结果。整体共识示意图如图2 所示。各分组节点内部进行共识,后由主节点将共识结果在组间进行共识,进而达成整体共识,执行请求后由分组返回当地请求结果。图2PBHS算法整体示意图3.2Local共识阶段本地共识采用HotStuff的共识方式,使用门限签名,在prepare、p r e-c o mmi t、c o mmi t、d e c i d e 阶段均由Leader节点收集副节点的部分签名形成相应阶段的QC。在PBHS算法中,decide阶段完成后各副本并不是直接执行请求,而是形成一个最终证书(finalCertif
19、icate,fc)。Zg:(id).validsSignaturemfc=(1)Local共识阶段的任意一轮共识满足以下两点:(1)任意一个非拜占庭节点最终能够正确执行客户端请求。(2)所有的非拜占庭节点在一轮视图中处理的是同一个请求。定理1保证了Local共识阶段在同一视图中只有一个请求被执行。定理1:对于任意两个合法QC和QC2,如果两种QC的类型相同,则必然有QC,和QC,所带表的视图不同,组内视图中保证同时最多只有一个请求能够被执行。即:viewNumber;=viewNumber2QCi.typeQC2.type(viewNumber,+viewNumber2QCr.type=QC2
20、.type(2)证明:对于任意的QC,和QC2,假设,QC,的类型和QC2的类型相同,且属于同一个视图,因为QC是组内超过m-f=2f+1个节点投票得出,若形成了两个相同类型的QC且属于同一个视图则代表至少有一个正常工作的节点对不同的请求投票两次,而每轮共识中每个正常节点仅对消息投票一次,二者相悖,故不可能有多个请求在同一组内被同时执行,证明完毕。3.2.1Local共识阶段安全性分析定理2:对于组内共识,由于该阶段内分组仍满足m3f+1,所以组内系统,即本地共识阶段仍满足拜占庭容错,该阶段安全性在拜占庭节点数量满足条件的情况下能够得到保证。证明:分组节点数量是m,设拜占庭节点数量为f,非拜占
21、庭节点数量为a,最终能够保证安全性所需非拜占庭节点数量为x,则有m=f+a,且ax(3)为保证在非拜占庭节点正常接收消息并做出回应,必须满足ax2+2(4)由式(3)(4)合并得出3-am(5)2代换得m3f(6)式(6)满足题设m3f+1,证毕。在节点数量方面,多数拜占庭容错类共识算法的实际部署节点数量较小,但其安全性却是严格的,因此在分组后组内节点数量变少不会对本地共识阶段造成安全性影响3.3Remote共识阶段当组内完成请求的Local共识之后,将进人Remote共识阶段,即将请求与形成的最终证书与其它组共享。设gEG471为一个组,在g的第i轮本地达成共识后,将请求和最终证书fc发送给
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 位置 改进 HotStuff 共识 机制 仿真
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。