一文读懂Giskard共识协议

时间:2021-07-05 19:06来源:www.xuanxuanjuhui.com作者:未知点击:

导读:
扫描关注公众号

GiskardBFT中的每一个区块只有Prepare投票,没明确的Pre-Commit和Commit阶段,那样区块怎么样达到最后的确认呢?GiskardBFT可看作Pipeline版本的BFT,每一个prepareQC都是对前面区块更高阶段的确认。

现在,应用了Giskard共识协议的PlatON测试网、主网和Alaya互联网都已经长期稳定、高效运行,它的安全性和活跃性得到了充分的验证,同时Giskard共识对解决系统过于中心化,减少互联网通信复杂度、消息复杂度,提高共识效率与整个区块链的买卖处置性能所起到有哪些用途毋庸置疑。

PBFT算法在区块链共识的应用

拜占庭将军问题的解决,有一个十分要紧的首要条件,那就是通信信道需要是靠谱的。假如信道不可以保证靠谱,那样拜占庭问题无解。这也就是FLP不可能原理,即在异步互联网模型假定下,共识算法不可能同时满足安全性和活跃性,也就是说,在一个不靠谱的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。至于啥是安全性和活跃性,大家后面再说。

BFT是一个已经被研究得比较透彻的理论,它告诉大家,基于部分同步互联网模型的假定,在低于三分之一的问题节点和作恶节点状况下,非拜占庭节点之间可达到最后一致性。PBFT是其中最为著名的达成算法,意为实用拜占庭容错算法。现在,区块链的共识算法大多都是基于BFT的达成。GiskardBFT也是由PBFT演进而来。

为何只有两阶段消息不可以达成一致性

容易来讲,就是「省略」了PBFT的Commit阶段,这里读者可能有疑虑:前文不是明确给出结论,需要通过三阶段消息才能达成一致性?其实GiskardBFT不是真的没Commit阶段,而是结合区块链特质,将下一个区块的QC状况作为上一个区块的Commit间接确认。

如图所示prepareQC(2)作为Block(1)的Pre-Commit阶段prepareQC(3)作为Block(1)的Commit阶段,Block(2)的Pre-Commit阶段。

这是早期的一代PoS。依据持有token的数目伪随机地选择验证人进行区块生产。其中还有PoS+PoW策略,通常是PoW出块,通过PoS选择验证人进行验证,的Casper1.0也是一种混合PoS/PoW的策略,作为其从PoW转换到PoS的中间策略。

通过对共识步骤的剖析,相信大伙对view切换步骤都可以非常不错地理解,这里大家不再赘述。下面大家着重剖析PBFT算法存在的问题,与GiskardBFT改进优化。

看到这里,或许你会有以下疑问:

拜占庭容错。选出验证节点后通过运行BFT协议经过多轮投票确认区块完成共识。现在Tendermint、Stellar、Ontology、Zilliqa、等都是使用这种共识算法。

为了进一步降低消息通讯量,大家使用了聚合签名技术。业界主流的聚合签名策略是BLS聚合签名。BLS聚合签名是在BLS签名策略基础上的扩展策略。

PlatON的Giskard共识协议由概率性权益证明PPoS(PlatONproofofstake)和Giskard拜占庭容错协议-GiskardBFT(GiskardByzantineFaultTolerance)组成。PPoS用质押、委托、随机选取的形式选出参与共识的验证节点,GiskardBFT用类BFT算法达成区块的生产和验证。

GiskardBFTviewchange投票步骤

下面,大家再介绍PBFT的视图和视图切换步骤。

本文大家将容易介绍PPoS共识和BFT理论,并剖析PBFT算法特质及PBFT存在的问题,其后重点剖析GiskardBFT借鉴PBFT、Tendermint、Hotstuff等共识协议的演进的道路。

委托权益证明。每一个token持有人可以把权利委托给部分代表,由代表参与区块的生产和验证。

PBFT的共识过程

其实,拜占庭将军问题最早是由LeslieLamport在1982年发表的论文《TheByzantineGeneralsProblem》提出的,他证明了在将军总数大于3f,背叛者为f或者更少时,忠诚的将军可以达成命令上的一致,即3f+1<=n。而MiguelCastro和BarbaraLiskov在1999年发表的论文《PracticalByzantineFaultTolerance》中初次提出PBFT算法,该算法容错数目也满足3f+1<=n。

只有pre-prepare和prepare两个阶段消息是没办法达成一致的。举例说明,假设没commit阶段,节点1在prepare阶段采集满2*f的签名后,达到Prepared状况,然而这个Prepared只是节点1的一个局部视角,不是全局一致,此时节点1不可以保证其余节点都达到Prepared状况,假如少于f个非拜占庭节点成为Prepared状况,节点1又确认了该消息,那样系统就出现了不同。

PBFT存在的问题

PBFT的视图切换步骤也分为三个阶段:

view-change:各副本节点有问题时,会向其它节点发送view-change消息 view-change-ack:各节点接收到2*f+1个view-change消息后,选举目前存活的节点编号最小的节点成为新的主节点,并向该节点发送view-change-ack消息 new-view:当新的主节点收到2*f+1个其它节点的view-change-ack消息后,向其它节点广播new-view消息。注意:从节点不会发起new-view事件

PPOS——验证节点选取

要让这个问题有解,还需要先引入一个定义——分布式互联网模型,根据分布式系统理论,分布式系统的互联网模型分为三类:

同步互联网模型:节点所发出的消息,在一个确定的时间内,一定会到达目的节点 异步互联网模型:节点所发出的消息,不可以确定必然会到达目的节点 部分同步互联网模型:节点发出的消息,虽然会有延迟,但最后会到达目的节点

容易概要就是:PPoS提供了一种尽量公平、随机地从海量参与节点中选取出若干验证节点的策略。

由上图可知,PBFT是一个典型的三阶段提交算法:

pre-prepare:各节点负责接收区块、实行区块,产生区块投票签名,开始广播签名给所有共识节点 prepare:各节点负责采集签名,某节点采集满2*f的签名后,表明自己达到可以提交区块的状况,开始广播Commit包 Commit:各节点负责采集Commit包,某节点采集满2*f+1的Commit包后,直接将当地缓存的最新区块提交到数据库

相比于传统的分布式系统,公共区块链中没中心化的假设,任何节点都可以加入并自由访问所有些数据,因此公链中不可防止会存在恶意节点。所以,区块链系统中的共识机制不只需要支持CFT(Crashfaulttolerance)还需要支持BFT(ByzantineFaultTolerance)。BFT是一个已经被研究得比较透彻的理论,PBFT是其中最为著名的达成算法,现在广泛应用于各大区块链系统中。

对于prepare和commit阶段来讲,考虑最坏的状况:大家假设收到f个是正常节点发过来的签名,也有f个是恶意节点发过来的,那样,第2*f+1个签名只可能是正常节点发过来的。由此可知,「大部分」正常的节点还是可以让系统工作下去的。所以2*f+1这个参数和n>=3f+1的需要是逻辑自洽的。而在prepare阶段,节点0发出消息即可觉得确认消息,所以prepare阶段仅需采集2*f个签名。

PPoS解决的重要核心点在于验证人的选取不只与节点权益的大小有关,还兼具随机性,也就是说选出的验证节点可能不是权益最高的节点,权益较低的节点也有肯定的选中概率。随机性算法可以保证选取的结果不可预测、不可操控且公平靠谱。PPoS本质上是PoS+VRF策略的结合。

为何不同阶段所需要的签名个数不同

PBFT算法被广泛应用于各类区块链共识,它不只解决了共识过程中可能发生的拜占庭节点问题,同时也使系统一直可以维持两个属性:安全性和活跃性。

安全性:在Crash节点和Byzantine节点两类错误发生时,共识系统不可以产生错误的结果。在区块链中,指的是不会产生双重花费和分叉。 活跃性:系统一直能持续产生提交,在区块链中,指的是共识会持续进行,不会卡住。倘若一个区块链系统的共识不可持续,那样系统没办法响应推广客户端新的买卖请求,也就是不满足liveness。

所有些BFT协议都通过view-change来更换主节点。PBFT,SBFT等协议具备独立的view-change步骤,当主节点出问题后才触发。而在Tendermint、HotStuff等协议中没显式的view-change步骤、view-change步骤合入正常步骤中,因此提升了view-change的效率,将view-change的通信复杂度减少。

拜占庭将军问题所描述的是好的将军不知晓其他将军是好的,还是坏的,但所有好的将军的目的是:行动一致,一同进退。所以,他们需要在方案上达成一致。

PBFT的视图切换步骤

在介绍PPoS之前,大家先科普一下PoS,现在PoS共识策略可以分为四类:

此处优化是GiskardBFT的独到革新之处。这里的并行指的是:区块生产和区块验证的并行化。

可验证随机函数用于验证节点的随机选取。现在,Dfinity、Cardano和ALGO币等使用了这种策略。

拜占庭将军问题

看到这里,相信大伙对拜占庭节点也有了初步的理解。容易地说,在区块链系统中存在以下两类错误:

第一类错误是节点崩溃、互联网问题、丢包等,这种错误种类的节点是没恶意的,是非拜占庭错误。 第二类错误是节点可能是恶意的,不遵守协议规则。比如验证者节点可以延迟或拒绝互联网中的消息、领导者可以提出无效块或者节点可以向不一样的对等体发送不一样的消息。在最坏的状况下,恶意节点可能会相互协作。这部分被统称为拜占庭错误。

这种做法很大提升出块速度,也提升了系统的共识性能。

概要一下,view-change步骤优化的两个重点:

无需显式的viewchange步骤,降低投票动作。 没view-change-ack和new-view阶段,而是结合区块链特质,由后续的prepareQC(n)对新的view进行「间接」确认。

验证节点被选举出来之后,运行共识协议进行区块生产和验证,整个过程需要节点之间相互协作,对区块进行相互确认,得出一致结论,达成区块共识。

在GiskardBFT中,大家把针对block和view-change消息的多个节点签名聚合成一个签名,可以容易地理解为:把多个节点的一段非常长的签名「压缩」为一个签名。这种做法很大地减少了通讯量,对提升协议的通信效率也起到了非常大有哪些用途。

技术本质脱不能离开传统分布式系统。分布式一致性算法是传统分布式系统的一大难点,经过多年的研究和应用,诞生了如paxos、raft、zab等成熟安全的算法。

上文中提到,区块链中的共识算法不只需要考虑Crash节点,还需要考虑Byzantine节点。啥是拜占庭节点?大家从一个故事说起。

下图是显式的ViewChange步骤,可以看到它并没类似PBFT中的view-change-ack和new-view阶段,这两个步骤被后续的prepareQC(n)进行代替。

PoS共识概述

结语

在战争的时候,拜占庭军队内所有将军需要达成一致的共识,决定是不是有赢的机会才去攻打敌人的阵营。但,在军队内大概存有叛徒和敌军的特务,左右将军们的决定影响将军们达成一致共识。在已知有将军是叛徒的状况下,其余忠诚的将军怎么样达成一致协议的问题,这就是拜占庭将军问题。

大家直接以PBFT算法在区块链共识的应用为例,概要算法的核心步骤:

引进pipeline方法对区块进行确认

在传统BFT主导的区块链系统中,每一个区块的共识一般都需要经历明确的Pre-Commit和Commit阶段才最后确认:

Pre-Commit:当节点收到2*f+1个Prepare投票时会广播Pre-Commit,Pre-Commit可以看作对Prepare阶段的确认。 Commit:当收到2*f+1个Pre-Commit投票时,表明所有节点对指定消息达成一致,提交到当地磁盘。

GiskardBFT结合区块链的链式结构,引进pipeline方法对区块进行确认,使得协议变得简单而优美,可以非常不错地进行步骤化作业,提升了协议的性能,另外也对协议的可扩展性留足了设计空间。

话不多说,直接上视图切换步骤图:

GiskardBFT的区块确认步骤

PlatON的共识策略PPoS,也就是大家常说的概率性权益证明,它本质是一种PoS共识策略,依据节点的权益绘制成二项分布累积分布曲线,并用VRF随机选取验证节点。

BFT——区块共识

应用BLS聚合签名

在后期的协议版本中,大家将继续深入优化:验证人的选取不只使用VRF,还计划结合可验证秘密推荐PVSS、BLS等密码算法进一步增加随机性;引入分组共识第三提高算法的可扩展性,以高效支持更多的验证节点加入,增加互联网的安全性和容错性。

DPoS(DelegatedProofofStake)

为何三阶段消息可以达成一致性

说到这里,其实就非常不错理解为何三阶段消息可以达成一致性,某节点采集满2*f+1的Commit包意味着有f+1个非拜占庭节点达成了Prepared状况,也就意味着「多数」节点已经认可了消息。

Chain-Based

拜占庭罗马帝国国土辽阔,为了达到防御目的,每块封地都驻扎一支由将军统领的军队,每一个军队都分隔非常远,将军与将军之间只能靠信差传递消息。

GiskardBFT也是基于view的的共识协议,为减少通讯复杂度,GiskardBFT也没显式的viewchange步骤,而是把这个步骤和正常出块步骤结合。GiskardBFT约定每一个建议节点在本视图内连续产生10个区块,并且每一个区块都达成QC状况后,则自动切换到下一个view,无需单独的view-change投票步骤。

通过对PBFT共识步骤三阶段的详细剖析,可以看到消息传输的开销非常大。系统在尝试达成状况共识时,涉及到n个节点都需要广播消息到n-1个其它节点,因此算法通信复杂度达到O(n²),在节点数目为1000的状况下所需要交换的通信量为1,000,000。有实验得出当节点数目超越20时,算法的性能会急剧降低。

区块生产和验证并行化

BFT(ByzantineFaultTolerance)

GiskardBFT共识优化

PlatON的由概率性权益证明PPoS(PlatONproofofstake)和Giskard拜占庭容错协议-GiskardBFT(GiskardByzantineFaultTolerance)组成。PPoS用质押、委托、随机选取的形式选出参与共识的验证节点,GiskardBFT用类BFT算法达成区块的生产和验证。

另外,在PBFT选举Leader的过程中,大概经过多轮交互,选举出的Leader一直长期运行,直到Leader节点出现问题才发起视图切换步骤。但在区块链系统中,视图view表示一个共识单元,共识过程由一个接一个的view组成,每一个view中由一个确定的建议人来主导共识协议,产生区块,其余验证人对区块进行投票签名达成协议。由于节点产生区块与利益有关,因此需要频繁地更换出块节点,也就是需要频繁地切换视图view,这必然会带来巨大的互联网资源消耗。

VRF(VerifiableRandomFunction)

所以大家基于BFT协议,结合区块链的特质,主要围绕着以下几个方面进行协议优化,设计了GiskardBFT。

view-change步骤优化

上文提到,GiskardBFT是基于视图view的共识协议,每一个建议节点在本视图内连续产生10个区块,并行步骤如下:

建议节点在一个view内可以连续建议多个区块,下一个区块的产生不需要等上一个区块达到QC状况。 验证人在接收上一个区块投票的同时,可以并行实行下个区块的买卖。

PBFT共识算法用视图view记录每一个节点的共识状况,相同视图节点维护相同的Leader和Replicas节点列表。当Leader出现问题,为了保证协议活跃性,会发生视图切换,若视图切换成功(至少2*f+1个节点达到相同视图),则依据新的视图选出新leader。

相关文章
推荐文章

热门标签

区块链平台靠谱吗_听听一个过来人是怎么说的_星球网

Copyright © 2002-2021 星球网 (http://yuchub.com) 网站地图 TAG标签 备案号:

声明: 本站文章均来自互联网,不代表本站观点 如有异议 请与本站联系 本站为非赢利性网站