Skip to main content

Polkadot共识第2部分:GRANDPA

December 30, 2019 in 共识-zh-cn
Avatarby Joe Petrowski

翻译:First.vip

来源链接: https://www.first.vip/project/6618.html

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

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

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

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

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

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

GRANDPA协议

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

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

Idle (24 peers), best: #664257 (0x706c…76b7), finalized #664253 (0xe4ab…4d2a)
Imported #664258 (0xee71…6321)
Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)

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

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

GRANDPA轮

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)

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

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

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

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

来源|波卡官方博客

翻译|头等仓Tracey

编译|头等仓Mark

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

From the blog

Consensus

Consensus 2024: Get Ready, Get Set, Polkadot

Polkadot is revving up for Consensus 2024 in Austin, Texas, from May 29th to May 31st. The road to this year’s conference is fueled by the community Indy 500 sponsorship and ecosystem teams and is set to be an unforgettable journey into Polkadot. Before Consensus Polkadot hackathon: North America edition 2024 April 15 to May 6, 2024 The Polkadot hackathon: North America edition 2024 is igniting the imaginations of developers worldwide, offering an unparalleled opportunity to dive deep into

Technology

The Way to a 10x Throughput Lift on Parachains

Parity engineer Dmitry Siniavin explains the calculations involved in determining that Polkadot parachains can increase their throughput rate by a factor of 10.

Ecosystem

Polkadot’s April Ecosystem Insights

Welcome to Polkadot’s new monthly ecosystem insights blog, your go-to source for all the latest tech updates, feedback and discussions happening across the Polkadot Ecosystem. In this blog we’ll explore a variety of topics and gather insights from sources ranging from GitHub to the Forums. Authors: Remy Le Berre and Joshua Cheong Ecosystem Activity OpenGov OpenGov sits at the heart of decision-making within the Polkadot Ecosystem. A place where anyone can freely discuss, propose, vote and v

Subscribe to the newsletter to hear about updates and events.