Polkadot 共识第 2 部分 : GRANDPA

这是我们的Polkadot共识系列文章的第 2 部分。有关简介,请参见第 1 部分。

在该系列的简介中,概述了一种共识算法可以帮助计算机网络回答三个问题。GRANDPA将解决第二个问题。

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

2. 哪一组是最终的更改?

3. 如果有人违反规则怎么办?

GRANDPAPolkadot的结尾工具,其作用是正确地选择模范链,表明GRANDPA的一系列改动是最后的步骤。GRANDPA不会自行生成块;相反的是,GRANDPA验证者将从另一个区块生产组件中导入区块(我们将在第 3 部分中讨论)。

分离区块生产和安全性的好处,除了是一个不错的工程设计外,还有GRANDPA对其导入的区块没有施加很多限制。GRANDPA仅要求块生产系统具有最终的安全性,遵循GRANDPA的分叉选择规则,并且在新区块的标头具有指向旧区块的指针。该特性确保轻型客户端可以跟随在链上。

GRANDPA 协议

GRANDPA与其他拜占庭式容错(BFT)区块链算法不同之处在于,验证者对链而不是区块进行投票。该协议采用过渡性地投票机制,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,246)。

Polkadot 共识第 2 部分 : GRANDPA

如上面的日志消息所示,这是GRANDPA如何在一个回合中完成多个块的示例。左侧的深灰色块是最终确定的,验证者(右侧的灰点)已为新回合发送了选票。另外三个街区占大多数并最终确定下来了。

一个 GRANDPA 回合

选民将执行以下操作以生成新的区块:

  1. 被指定为“主要”节点将广播其认为之前可能获得的最高选票区块作为最终区块。

  2. 在等待一段网络延迟之后,每个验证者都会广播一个其认为应该确定的最高选票区块的“预投票”,并认为其应当是最终区块。如果验证者的绝大多数是诚实的,则此区块应扩展最初广播的链上。所以新链可能比最后确定的链还多几个区块。

  3. 每个验证者根据预投票计算可以确定最终那个最高选票的区块。如果预投票集扩展到最后一条最终确定的链,则每个验证者将对该链进行“预执行”。

  4. 每个验证者都等待接收足够的预执行,以在新确定的链上传递信息。

与其他拜占庭容错算法(例如 PBFT 和 Hotstuff)的细微但重要的区别是,该投票环节的关键路径上没有意见变化。尽管每一轮的主要内容都有所改动,但这种更改仅在异步网络中开启新一轮回合,所以在部分同步的网络中即使不分配主要地带,协议也将始终前进。

当协议进程中获得了验证者的三分之二以上的预投票预执行,则表明该进程是可完成的。为了获得最后的结果,必须限制验证者的手中票数,这与可以具有无限的验证者集确定性的链不同。选择投票者集合的方法是在GRANDPA协议之外定义的逻辑(请参阅第 4 部分)。

GRANDPA支持加权投票。例如,您可以在您的链中运行GRANDPA,在此情况下拥有更多赌注的验证者可以获得更多选票。但是在Polkadot中所有验证人都有一个均等的加权投票。这种加权是一项经济决策,目的是防止少数节点获得较大的网络份额。

安全责任:当意外发生时

GRANDPA具有一项称为“安全责任”的功能,可使验证者对违反安全性的行为负责。当确定不同链中的两个区块时会发生安全冲突,安全责任功能就类似于发生意外后的调查。

但是首先要明确两个相互冲突的链是如何形成的?BFT 系统始终建立在以下条件之上:有问题的验证者的最大数量为总验证者的一小部分(在我们的情况下为三分之一)。如果验证者集未能满足上述要求,为了最终明确两个冲突的链,至少有三分之一的验证人对这两个链进行了投票。

Polkadot 共识第 2 部分 : GRANDPA

在此示例中,有 10 个验证者,这意味着 3 是系统可以承受的最大错误验证者数目(f =(10-1)/ 3)。有了 4 个错误的验证器(红色)和一个网络分区,每组诚实的验证者蓝色)可以各自区块是最终区块。

在两个相互冲突的链上进行投票是一种模棱两可的行为。实际上大家都认为模棱两可是对 BFT 系统的攻击,但在GRANDPA中我们可以检测到这种行为。

首先,我们将询问节点投票决定一个新区块时为什么没有考虑上一个区块的情况。任何诚实的验证者都应启用第二轮的一组预投票或预执行来答复这个问题,因为第二个区块总会拥有大部分的选票。

如果第一个问题成立,那么我们会问第二个问题:您看到过第一轮的哪些选票?我们实质上是在要求它们批准其他验证人,并透露他们从同行那里获得的所有投票。在这两个集合的联合中的某个位置,您会发现为两个冲突链投票的验证者。一旦上述结果被证实,它们将受到重罚,但这是仅是链上的逻辑工作而不是共识的结果。

如果发生安全故障,则网络将必须通过硬分叉来选择哪个两个冲突链中哪个是终链。从安全的角度出发,Polkadot可以确保对实施攻击的验证者进行惩罚,并将其从验证者集中剔除。

GRANDPA 如何实现可用性和有效性

还记得上面的日志消息吗?注意到最终区块是在最佳区块后面的第二个区块。这种滞后实际上是保持区块生产和完成不同的优势。

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

包括Polkadot在内的区块链互操作性系统都存在数据可用性的问题。设想有一个整理者将一个区块提交给验证者,但是其他平行链收集者都没有看到它。如果提交区块信息的收集者下线了怎么办?验证者有责任在一段时间内帮忙存储完整的区块信息,以便所有平行链的收集者都可以获得区块信息。

验证者应该在对它们进行投票之前就验证好候选区块,但是我们要确保它们确实是这样做的。在Polkadot中存在许多称为钓鱼者的节点,它们可以验证区块并举报验证者的不当行为,例如在中继链中指出一个无效的平行链。

我们永远不希望最终选定的区块是无效区块或者是收集者无法重构的区块。通过在链端后面保留几个区块的可验性,我们可以让钓鱼者验证该区块是否正确并检验验证者是否尽职。

我们一直在讨论如何确定规范链,但是这些链的选择源自哪里?这就是BABE要回答的问题。请参阅本系列的第 3 部分。

原文链接:https://polkadot.network/polkadot-consensus-part-2-grandpa/

翻译 / Mike 编辑 / Dolly

关于 PolkaBase

PolkaBase 是以波卡技术为基础的区块链 3.0 生态,致力于打造一个能推动区块链技术与应用落地、产生优质内容和产品价值、并吸引区块链行业外部资源与团队的新一代社区;在技术普及、生态孵化、高校与产业联合、价值用户和国际化五大方面,弥补现有社群的不足,推动生态的深化与发展。

Polkadot 共识第 2 部分 : GRANDPA

来源链接:mp.weixin.qq.com