Polkadot共识第2部分:GRANDPA

 在序文当中,我讲到了一种共识算法可以帮助计算机网络回答三个问题。 GRANDPA便是解决第二个问题。
头等仓APP下载

 Polkadot共识第2部分:GRANDPA

在序文当中,我讲到了一种共识算法可以帮助计算机网络回答三个问题。 GRANDPA便是解决第二个问题。

1.谁可以提出下一次更改?

2.哪一组更改为最终更改?

3.如果有人打破规则会怎样?

GRANDPA是Polkadot一款决定区块最终性的工具,作用是选出权威链。换句话说,GRANDPA决定哪条链为最终链。它不会自行生产区块,而是,GRANDPA验证人从另一个区块生产模块(我们将在第3部分中讨论)中导入区块。

分离区块生产和安全性的好处之一,除了可以有优良的工程设计外,GRANDPA对导入的区块没有很多限制。 GRANDPA仅要求区块生产系统生产的区块是安全的,遵循GRANDPA的分叉规则,并且区块头必须具有指向其父区块的指针,确保轻客户端可以跟上链条的进度即可。

GRANDPA协议

GRANDPA与其他拜占庭式容错算法不同之处在于,验证人是对区块链投票,而不是对区块进行投票。GRANDPA间接地应用投票,GRANDPA算法寻找有足够选票,且足以认定为最终区块的最高区块号。在寻找区块的过程中,一轮可以确定好几个最终区块。

最后一部分很重要,因为它消除了妨碍其他区块链终结性小工具的瓶颈。与其他PBFT衍生协议一样,GRANDPA的复杂度为O(n²)。也就是说,如果将节点数增加一倍,发送的消息数会增加四倍。共识系统将区块生产与最终性流程分离,使你可以给每个区块发送消息。通过将区块生产隔离在另一个模块中,生产区块的效率变高了(BABE为O(n)),并在一轮中可以最终确认其中的好几个区块。让我们来看一个示例,检查Kusama节点中的以下日志消息:

Polkadot共识第2部分:GRANDPA

发现在一轮中,GRANDPA最终确定了三个区块(664,254至664,256)。

 Polkadot共识第2部分:GRANDPA

上图日志消息显示了GRANDPA如何在一轮中确定多个区块。左侧的深灰色方块是先前最终确定的区块,验证人(右侧的灰色椭圆图形)给新一轮区块生产发送选票。其中三个区块获得了多数选票,被最终确定。

GRANDPA轮

选民执行以下流程来确定新区块:

1.被指定为“主”节点的节点广播它认为继上一轮后,这一轮可以被最终确定的最高区块。

2.等待网络延迟后,每个验证人会为自己认为应该是最高的区块广播一个“预投票”。如果绝大多数验证人是诚实的,则将有最多广播数的区块添加到区块链上。新链会比上一次最终确定的链长出几个区块。

3.每个验证人根据预投票集,计算出将得到最终确定的最高区块。如果预投票集延长了上条最终确认的区块链,则每个验证人都将对这条链投递“预提交”。

4.每个验证人等待接收足够数量的预提交,在新确定的链上提交消息。

与其他拜占庭容错算法(例如PBFT和Hotstuff)相比,细微且重要的一点区别是,在关键路径上没有视图变化。尽管每轮的最高区块发生更改,但视图更改只在异步网络情况下,开启新一轮,因此在部分同步网络中,即使在没有分配最高区块的情况下,协议也会不断更新。

如果协议中有2/3以上的预投票或预提交来自验证人,协议的步骤就完成了。为了确定最终性,必须限制验证人集的投票数。与以概率来确定最终区块的链不同,这种链有无数验证人集。GRANDPA协议并没有定义选择选民集的方法逻辑(参加第4部分)。

GRANDPA支持加权投票。例如,你可以在自己的链上应用GRANDPA协议,这样验证人如果有更多的stake,就能获得更多投票。但在Polkadot中,所有验证人的加权投票都是均等的。这种均等加权经济策略,可以防止少数节点获得较大的网络份额。

安全责任:当发生问题时谁来负责?

GRANDPA具有一项称作“安全责任(accountable safety)”的功能,让验证人对违反安全性的行为负责。当两个区块在不同的链上被最终确认时,会产生安全冲突。安全责任就扮演类似一场事故调查的作用。

首先,两条相互矛盾的链是如何达成最终性的?拜占庭共识系统始终基于以下条件:拥有容错验证人的最大数量是总验证人数量的一部分(在波卡当中占比1/3)。如果让两条相互矛盾的链达成最终性,验证人集不能满足“容错验证人的最大数量是总验证人数量的一部分”这一要求;至少1/3的验证人对这两条链都进行投票。

 Polkadot共识第2部分:GRANDPA

在此示例中,有10位验证人,这意味着3是系统可以承受的最大容错验证人数(f =(10-1)/ 3)。有了4位容错验证人(红色)在一个网络分区,每组诚实的验证人(蓝色)可以认定不同的区块具有最终性。

在两个相互冲突的链上进行投票的行为称为equivocating(相互矛盾)。公认的一个事实是equivocating是对拜占庭容错系统的冒犯。在GRANDPA系统中,我们可以检测出equivocating。

首先,我们先询问节点,为什么投票给第二个区块(认为第2个区块具有最终性),却不投给第一个区块。所有的诚实验证人(大多数认为第2个区块具有最终性)都需要在第二轮用一组预投票或预提交来回答第一个问题。

如果没问题,接着我们会提问第二个问题:你看到过第1轮的哪些投票?我们实质上是在要求他们告发其他验证人,并透露他们从对等节点那里获得的所有投票。结合两个问题,就能找出为两条冲突链投票的验证人。在假定的情况下,他们将受到重罚,但这是区块链工作的逻辑,共识不是这种逻辑。

如果出现安全错误,网络必须执行硬分叉选出最终链。有了安全责任功能,Polkadot可以确保对发起攻击的验证人进行惩罚,并踢出验证人集。

GRANDPA如何验证可用性和有效性?

还记得上面提到的日志消息吗?注意一点,最终区块落后最佳区块后面两个区块。实际上,这种滞后保证区块生产和最终性有所区分。

 Polkadot共识第2部分:GRANDPA

包括Polkadot在内的区块链互操作性系统都存在数据可用性问题。想象一位整理者提交一个区块给验证人,但是其他平行链整理者都没有看到这个区块。如果提交区块的整理者离线了怎么办?验证人有责任在一段时间内存储完整的区块,以便任何平行链整理者都可以请求区块。

验证人应该先执行区块,再给区块投票,但我们想确保他们这样做。Polkadot中有许多名叫“渔民”的节点,它们的作用是执行区块并报告任何验证程序异常的行为,例如提议将无效的平行链区块打包进中继链。

绝不希望出现的情况是:最终确定的是一个无效区块,或者最终确认的区块排序器无法重构。通过保留落后链尖端几个区块的最终性,可以让渔民来验证区块的正确性,并质疑验证人区块的可用性。

我们一直在讨论如何确定规范链,但是这些链选项有哪些来源?这就是需要BABE的地方。请参阅本系列文章第3部分。

来源|波卡官方博客

翻译|头等仓Tracey

编译|头等仓Mark

译文版权属头等仓所有,任何转载请保留文末信息。

本文由 区块链资讯平台头等仓 作者:Mark 发表,其版权均为 区块链资讯平台头等仓 所有,文章内容系作者个人观点,不代表 区块链资讯平台头等仓 对观点赞同或支持。如需转载,请注明文章来源。
头等仓APP下载

发表评论