Polkadot共识第3部分:BABE

2019-12-30 in  共识-zh-cn
Avatar by Joe Petrowski
Image

翻译:First.vip

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

本文为Polkadot共识系列文章的第3部分。有关简介的内容,请参见第1部分,有关GRANDPA 的讨论,请参见第2部分。

区块链扩展盲分配(BABE)是一种区块生成机制,其灵感来自另一种PoS协议Ouroboros Praos。由于它可提供概率确定性,因此它可以单独使用,也可以与GRANDPA这样的确定性小工具结合使用。

BABE是一种基于slot(插槽)的算法。它把时间划分成若干个epoch(纪元),每个epoch再划分成若干个slot。在Polkadot中,每个slot的持续时间为6秒,这也是我们的目标出块时间。BABE将选择一个(或多个)区块创建者在每个slot中创建区块。

BABE的时间被划分成若干epoch。每个epoch又包含若干个slot。

向这些slot分配区块创建者的其中一种方法就是通过简单轮流制。然而在循环模式中,攻击者总是能知道下一位创建者是谁,并可以使用该信息来协调发起攻击。而在理想情况下,应没人能够知晓该slot的创建者是谁,除非该创建者提供证据证明。

每个slot可以有主创建者和次创建者(或叫“slot领导者”)。slot主领导者是随机分配的。但由于函数是随机的,所以有时会出现有些slot没有领导者的情况。为了确保一致的出块时间,BABE使用循环系统来分配slot次领导者。

Slot主领导者

主领导者的分配基于可验证随机函数(VRF)的评估。关于区块链随机数的说法天花乱坠,简而言之,许多应用程序都依赖于随机数的生成,但是当所有链上操作都必须是确定的且可验证的时,就很难认定每个人都认可的随机性(而不是为了使生成器受益而进行的游戏)。

VRF会生成伪随机数及其正确生成的证明。其他VRF都将一些参数(包括私钥)作为输入。而我们的VRF则将epoch随机种子(事先通过所有节点认可)、slot编码和创建者私钥作为输入。由于节点不会拥有相同的私钥,所以每个节点都可以为每个slot生成唯一的伪随机值。

每个创建者要对每个epoch中每个slot的VRF进行评估。对于每个输出低于某个商定阈值的slot,验证者有权在该slot中创建区块。由于slot分配过程是随机的,因此可能会出现有些slot没有主领导者,或有些slot有多个主领导者的情况。接下来再说说如何处理这一问题。

BABE中的VRF以epoch随机性、slot编码和验证者私钥作为输入,并为epoch中的每个slot输出一个值。当区块创建者的输出低于网络阈值时,它将生成一个区块作为该slot的主要区块领导者。

Slot次领导者

为了处理空slot的问题,BABE使用了循环后退方式。每个slot都有次领导者。如果主领导者没有在slot开始时站出来,那么就由次领导者创建区块。这种后退方式将确保每个slot都有一个区块创建者,并有助于确保一致的出块时间。

将BABE与GRANDPA相结合

到目前为止,我们已经有可确定最终链的GRANDPA,以及可创建新块的BABE。由于单个slot可以有多个领导者,因此BABE的某些链也会产生分叉。

选择最佳延伸链的第一条规则很简单:BABE必须建立在由GRANDPA最终确定的那条链上。这是使用GRANDPA的要求之一。

使用GRANDPA的第二个更微妙要求是,区块生成算法必须能够选择“最佳”链。此属性使得BABE具有概率确定性(因此,你可以在不使用GRANDPA的情况下使用它)。

BABE中的最佳链就是由主领导者创建最多区块的那条链。

选择最佳链的BABE分叉选择规则示例

在BABE中,分叉十分常见。正如GRANPA一文所述,区块生成是O(n),这意味着创建者只需向所有人广播其区块,而不需要每个人都互发消息(就好比GRANDPA)。因此,并非每个人都对未最终确定的链看法一致(如图中黄色块)。

该系统使我们能够高效生成区块,并使GRANDPA进行最终确定。

那该依据谁的时钟?

我们根据时间分配slot,但我们没有单一的时间观念。每台计算机都有自己的时钟。我们不能使用中心化时间服务(称为NTP服务器),因为这会造成单点攻击。攻击者可以向NTP服务器发起攻击,可能切断它也可能夺取它的控制权,以达到更不道德的行为,比如向不同的节点发送不同的时间。

可以想象以下场景:
我收到你发来的信息,说现在是“8:42:00。”而我的时钟显示是8:42:03。那么有三种可能:
1.我们的时钟是同步的,网络传递你的消息只花了3秒钟。
2.实际上网络传递你的消息花了1秒钟。我们的时钟差了2秒钟。
3.你在骗我,你的时钟并不是这个时间。
现在假设我的时钟显示我8:41:59时收到了此信息。假如我相信你没有说谎,那么我就知道我们的时钟不同步,我必须把我的时钟往前调一点。但我仍然不知道通过网络传输需要花费多少时间,我也就不知道我们到底有多不同步。

而BABE则使用相对时间将slot编码与一台计算机的时钟对齐。当某节点收到一个区块时,它将检查接收时间和与该区块相关的slot编码。然后,它会将slot编码添加到每个区块上,并使用其数据中的中值来预测未来slot。请记住,验证者会预先知道要为其创建的slot编码,因此他们可以对此进行检查。

BABE中的区块创建者使用区块接收时间来创建网络时间视图。他们根据slot时间将接收时间映射到未来,以确定何时应创建并发起一个区块。

到目前为止,我们已经讨论了链是如何产生的(BABE)以及它们如何被最终确定(GRANDPA)。我们要解决的下一个问题是,如何使人们以正确的方式运行这些协议?本系列的最后一部分将讨论运行时如何为运行BABE和GRANDPA提供激励,以及发生错误时会有什么惩罚。

来源|波卡官方博客

翻译|头等仓Saline

编译|头等仓Mark

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

arrow_upward
Related articles
Polkadot-zh-cn
Gavin Wood 总结 Polkadot 近一年生态进展,展望 2020 年 Polkadot 2.0 最终设计

翻译:Qinwen、KIKO、Silvia 我在去年的年终总结开头陈列了一些数据,今年似乎也适合继续延续这个传统,首先可以报告一些今年的数据。总的来说,包括 Substrate、Grandpa、Cumulus 和一些其它支持代码在内的 Polkadot 已经拥有了超过 30 万行代码!这是去年完成代码量的 3 倍,而这还并未算上 UI 和智能合约代码库的代码。...

Polkadot-zh-cn
Polkadot年度总结|再见2019年,你好2020年!

为了总结这一年,我们邀请了致力于Polkadot启动工作的同事们来回顾他们在2019 年的工作,并分享2020年他们最期待的事。很高兴能与你一起分享他们的答案(既有严肃,也有轻松!) 提问的回答来自于三大洲的Web3基金会各个团队(从研究和通信到基础架构以及社区与成长)。我们还邀请了主要开发合作伙伴Parity Technologies的一些同事一起来回答。...

共识-zh-cn
Polkadot共识第4部分:安全性

到目前为止,我们已经讨论过BABE是如何创建区块链候选者和GRANDPA如何最终确定它们。我们知道我们需要超过三分之二的验证者来正确遵循协议。但是,到底有多少验证者呢?他们是如何被选择的呢?他们为什么要遵守规则?...

订阅我们的电子报,接收Polkadot最新消息和活动。
mail_outline