干货 | 探究以太坊 2.0 的分叉选择规则

Ajian   |     |   1024 次阅读

编者注:文章原题为“Detailed overview of Ethereum 2.0 shard chains: Committees, Proposers and Attesters(关于以太坊 2.0 分片链细节概述:委员会、提案者和证明者)”,但我认为,文章内容的实质是信标链的分叉选择规则(尽管还说不上完善),因此改名。读完这篇文章就更能理解:为什么权益证明无法使用最长链规则而必须采用其他规则,而这些规则又会有怎样的局限性。文章非常长,但不读你就错过了。有兴趣的读者可以结合文末超链接研究一下。

时至今日,许多关于以太坊 2.0 的工作细节已经公诸于众,同时还有许多团队在着手实现。但是 以太坊 2.0 还有一大块空白的部分还未规范,也没有披露什么讯息,那就是分片链技术。基本上所有关于规范的部分都展示在这里,而这篇博客会着重提供一些细节概述。

脚注:这篇文章的初版所述的方法,称作即时消息驱动(IMF, immediate message driven),现在已经被抛弃了。相关内容可以在这里找到。

委员会及其构造

只要将 32 个 ETH 放入现有主链(PoW chain)上指定的智能合约,任何以太坊网络中的参与者都能成为验证者节点。

-Image by Hsiao-Wei Wang-

参与者进入验证者池之后,就可以被分配给某个分片。分配过程是是完全随机的,可以通过可验证延时函数(VDFs,Verifiable Delay Functions)保证随机的无偏性。

如果有参与者质押的权益超过 32 ETH(假设是 320 ETH),他们就会获得相应比例的验证者席次。这些席次彼此之间无关,会被独立地分配给分片网络;所以对于投入 320 ETH 的参与者来说,最不理想的情况是在单个出块时段,成为十个不同分片网络的验证者。但如果不这么设计的话,就会增加竞争敌手接管某一个分片的可能性;一般来说,我们都预期那些拥有更多权益的人可以调用更多的资源以及算力(因此要防范这一点)。

在 proof-of-stake 系统中产出区块

以太坊 2.0 是 PoS 系统。在本章节,我们先回顾一下现有的且被推崇的 PoS 区块链中,是如何产生区块的:

在这样的框架中,生成区块的时间间隔是固定的。例如每五秒生成一个区块,并由一群验证者来进行创建和验证区块。在每五秒的出块时段内,会有一个验证者被指定来生产该时段(time slot)的区块。如果验证者彼此之间的权益数量不同,则有较多权益的验证者会有较高的概率成为区块生产者。

当分叉发生时,诚实的验证者会选择具有最多区块的那条链。只要诚实的验证者占全部验证者总数的一半以上,想要伪造一条最长链是非常困难的。假设所有少数恶意节点试图联合起来,私下创建一条分叉链,并且故意在诚实链的出块时段内不产出区块;即使如此,他们的恶意分叉仍然会比诚实链要来的短;这个论点类似 PoW 系统,只要超过一半以上的算力由诚实节点控制,要反转最长链的可能性极低。

然而如果直接实施这种架构,会存在许多问题。首先,短程分叉还是很有可能发生;只要少数节点控制了全部验证者中的 10% ,最后的几个区块,比如说六个,的回滚概率还是高的令人无法接受;第二,会出现各式各样的审查问题。举例来说,如果恶意节点碰巧在一条队列中获得连续两个出块时段的出块权力,他们就能审查前一个出块时段产生的区块:

上图中恶意验证者控制了第 3 和 第 4 个出块时段;它们能够紧接在 1 号块(即第 1 个出块时段所出的块)之后生成区块,实质上造成对 2 号块的审查。而诚实的验证者在第 5 个出块时段生产区块时,会选择被操控的包含第 3 和 第 4 区块的链,因为它们是较长链。

即便是单个恶意验证者也能试着去审查前一个时段的区块。如下图所示,X 轴表示时间轴,出块时段标记在底部,区块中的数字表示人们预期的该块的出块时段(标号1 即表示人们预期这个块会在第 1 个出块时段出块)。假设诚实的验证者被指派为第 0 和 2 时段生产区块;该诚实验证者将区块 0 广播出去之后,被指派为第 1 个时段出块的恶意验证者可以扣住区块不去广播,等到区块 2 被广播出去后再广播区块 1(由于负责出区块 2 的验证者没有收到区块 1 ,他们会紧接着区块 0 构建他们的区块;因此,区块 1 和区块 2 就变成了两条同样长的分叉链)。

等到第 3 个出块时段,诚实的验证者应该接着哪个块创建新的区块呢?我们考虑以下四种可能的情况:

  1. 总是跟在较早创建的区块后面。这么一来,处在较早出块时段的恶意验证者就会延迟广播区块,直到下一个出块时段的区块被创建后再广播,导致后者就被忽略(如上图情景所述)。
  2. 总是跟在较晚创建的区块后面建块。这种情况下,在时段 X 出块的恶意验证者可以选择无视时段 X-1 创建的区块,并且能确保负责时段 X+1 的验证者一定会选择他的区块,而时段 X-1 创建的块就会被忽略。
  3. 总是跟在自己先接收到的区块后面建块。这种情况下,只要恶意验证者比下一个验证者的网速更快更稳,上述两种情形都有可能发生。
  4. 随机选择区块。这样恶意验证者就无法确定自己创建的区块会不会被接受(除非它们在一条网络中控制了多个出块时段);但是如果审查区块能获得高于出块的奖励,恶意验证者仍会尝试作恶,同时有 50% 的成功几率。

上面的四种情况都是我们不愿意见到的

拜占庭方法

针对上述问题,人们提出了一系列的提案,这些提案的想法是在验证者创建区块时,使用一种拜占庭共识算法。最早设想这个方法的论文是 ByzCoin ,而后又有许多基于它的协议被提出。它们的核心思想是:一旦区块经过委员会最终确定,只要恶意节点数量不超过 1/3,这个区块就是不可逆的,换句话说分叉和篡改无法成功。

这个方法有两个主要的缺点, a) 大多数拜占庭算法很慢,无法应对大量参与者要达成共识的场景; b) 掉线的节点会被视为恶意行为,因为如果少于 2/3 节点在线,区块共识就无法达成,进而导致系统总会在某些时候停滞不前。

查看证明(Attestations)数量的方案

以太坊 2.0 延续使用之前的方法,也就是在每个出块时段,会有一个验证者(又称作提案者,proposer)被指派产生区块。而且以太坊 2.0 还进行了拓展:委员会的其他验证者被激励去“证实(attest)”这个区块,也就是给它签名。这种签名使用了 BLS 群签名方法,可以避免随着签名增加而使得区块大小暴增。而且对于给定的出块时段,如果验证者没有看到新创建的区块,或是区块不在当前应该在的链上,验证者被鼓励去证明存在这个情况,又称作证明“跳过该区块”的操作。这样一来,诚实的验证者会证明每个出块时段都正好有一个区块产生;这可能是由提案者创建的真实区块,或是一个被跳过的区块(“跳过该区块”)。

借由证明者机制和分叉选择规则,以太坊 2.0 分片链避免了一般 PoS 方法和拜占庭共识算法的问题。

分叉选择规则

即时消息驱动(IMD)

从创世区块开始,每当我们面临分叉时,只要某个分支上具有的验证者(即为该分支的当前和以往区块做证实的验证者)比其它分支都要更多样,我们就认为它是应该被选择的分支(预告,后面会提到最新消息驱动 Latest Message Driven)。

4

我们分析一下上图所示的情形。每个区块中的字母表示该区块获得的证明,虚线的区块表示“跳过该区块”操作。现在发生分叉,Alice (A)、Bob (B)、Carol (C)、Dave (D) 和 Elaine (E) 已经证明过下分支的部分区块;而 Victor (V)、Xavier (X)、Yasmine (Y) 和 Zach (Z) 证明过上分支的区块。为了找出正确的那条链,我们得从创世区块开始往右推演。参与者必须在第 2 个出块时段对上下两条分支进行选择;而分叉选择规则告诉我们,要选择在其上有较多不重复的证明者的分支。我们可以看到,下分支有五个证明者(Alice, Bob, Carol, Dave and Elaine),上分支只有四个(Victor, Xavier, Yasmine and Zach),所以我们选择下分支。注意,其实在下分支里,并没有某个块是得到五个验证者证明的,甚至连得到四个证明的块都没有(在第 7 个出块时段之前的链,只有来自 Alice, Bob 和 Carol 的证明;如果链在第 8 个出块时段结束的话,也只有来自 Alice, Dave 和 Elaine 的证明)。但是下分支的累计证明数比上分支多,因此选择前者作为链

相似的,在第 6 个出块时段也要进行一次分叉选择;上面分支有三个证明者( Alice, Bob 和 Carol ),下面的只有两个( Dave 和 Elaine ),所以最终结果会选择包含出块时段 1 、2、4、6、7 所创块的链。

最新消息驱动 Latest Message Driven

在(最新消息驱动)这种分叉选择规则中,(在确认哪条分支有多少验证者时)我们只考虑这些验证者在最新的出块时段提交的证明。举例来说,在下图中的第 3 个出块时段(也就是最新的出块时段), Alice 提交了对上分支区块的证明,因此我们认定 TA 选择了上分支。换言之,Alice 在第 2 个出块时段的证明将被忽略掉,因此我们在第 0 个出块时段进行分叉选择的时候,上分支有三个证明者( Alice, Bob 和 Elaine ),下分支只有两个( Carol 和 Dave),我们选择上面的分支:

5

要注意的是,此种分叉选择规则只看 Alice 在最新的出块时段(出块时段 3)的选择,这和 Alice 最先提交哪个证明或是特定观察者最先接收到哪个证明无关

证明的条件

只有在区块满足某些条件时,诚实的证明者才会对区块进行证明:

  1. 区块属于证明者认定的当前被选择的链上;

  2. 证明者在同一个出块时段内,没有对其他区块进行过证明。

注意:我们相信诚实的提案者不会在同一个出块时段内创建两个区块;因此,这种分叉选择规则只要配合罚没规则便可使用:当出现恶意提案者试图在同个出块时段创建多个块,以此分叉区块链的时候,它的权益会被立即罚没掉。

如果证明者没有收到特定出块时段的区块,则证明者会采取证明“跳过该区块”的操作。由证明者自行选择等待时间,直到他们决定停止等待并证明“跳过该区块”操作。Danny Ryan 建议诚实的证明者应该等到出块时段过了一半之后,再进行最终他们认为正确的证明(不论是对实际区块或是跳过的区块进行证明)——因为大多数证明者都会这么做。

分析

活跃性

不同于其他拜占庭共识算法,在上述方法中,即使超过 1/3 占比的节点掉线,出块过程也能继续正常运行。网络中的参与者会仔细检查只得到少于 2/3 证明的区块,并对这些区块更加小心,直到有其他附加的安全条件被满足(比如,等到这些区块被交叉关联(cross-link)到信标链(The Beacon Chain),并且由 Casper FFG 进行过确认......这些就超出本文讨论范围了)。不过最重要的是,系统会持续出块,而不会延宕。

抗审查性

回顾一下上面提到的两种审查场景,在第一种情形中,拥有连续两个时段出块权的验证者想审查前一个区块就不可能成功了,因为分叉选择与链长度不再有任何关系。

如果没有限制验证者只能在相应的出块时段内做证明,那么第二种场景(提案者延迟出块,直到下个出块时段的区块被创建出来)仍然可能发生:出块时段 X 中的恶意验证者可以延到 X+1 块被创建后,再广播他们的区块。对于证明者来说,他们无法区分恶意攻击或仅仅是网络延时的区别,而且一旦证明没有限定的时间窗口,人们就可以在后来证实 X,有效地审查 X+1。

要求在特定时间窗口进行证明可以解决上述问题,只要所有参与者的时钟都是同步的。如果无法保持同步(但仍然在数秒钟的时间范围内),基于时间差的攻击就有可能发生;当然发生的可能性极低。

抗分叉性

在两种可能的累计证明数的方法中(最新消息驱动 LMD,只有在最新的出块时段中的证明会被采纳;及时消息驱动 IMD ,采纳所有的证明),后者提供较好的抗分叉性保证(详见此文关于分叉性的章节),但相比于其他拜占庭共识算法仍然不够好。

本文描述了以太坊 2.0 中的 LMD 方法,虽然这种方法对分叉性的抵抗较弱。 为了更好了解这一点,假设某条分支中有 60 个证明者,其中有部分恶意节点;另外一条分支有 40 个证明者。在 IMD 场景下,需要在那 60 个证明者中出现 21 个恶意证明者为具有 40 个证明者的分支做证明,才能改变原有主链选择的结果(最终为 61 个证明数 vs 60个证明数,原来被选择的主链上只有 60 个证明);在 LMD 场景下,只要出现 11 个恶意节点就能达到分叉目的(最终为 51 个证明数 vs 49 个证明数,原来被选择的主链上只有 49 个证明)。尽管 LMD 能够减少分叉发生,加上主链有超过 2/3 占比的证明数且恶意节点占比不到 1/3 ,我们仍无法完全避免分叉发生。我们考虑下面的例子:

假设有七个验证者,其中 Alice (A)、Bob (B)、Carol (C)、Dave (D) 和 Elaine (E) 是诚实节点,而 Xavier (X) 和 Yasmine (Y) 是恶意节点。

(i) 现在出现了分叉,第 2 和 3 出块时段都接着第 1 个出块时段的区块出块,而 Alice 和 Bob 看到第 2 个出块时段生成的区块,并为它提供证明;

(ii) Carol 没有看到第 2 个出块时段的区块和证明,而只看到第 3 个出块时段创建的区块。于是 Carol 和恶意节点 Xavier、Yasmine 替区块 3 提供证明;

(iii) 现在区块 3 拥有三个证明,所以 Alice 和 Bob 就会认为包含第 3 个出块时段的分支才是主链,因此他俩也对区块 3 进行证明(假设证明时间窗口还没结束)。现在区块 3 具有超过 2/3 占比的证明数,理应不可逆;

(iv) 但其实 Dave 和 Elaine 在有效期间也对区块 2 进行证明,却因为网络延迟问题没有及时被看到(Alice 和 Bob 也没看到);

(v) 这时候,恶意节点 Xavier 和 Yasmine 选择在第 4 个出块时段创建块,并接续在原本应该被抛弃的区块 2 上。一时之间,上分支证明数(Dave, Elaine, Xavier 和 Yasmine)反超下分支的证明数(Carol, Alice 和 Bob),前者成为主链(即使下分支一度存在超过 2/3 占比的证明数);

(vi) 现在所有诚实的证明者都会对区块 4 进行证明。

注意,上述的攻击很难成立(比如 Dave 和 Elaine 出现延迟的情况;在有数百验证者的网络中很难发生,除非攻击者控制了整个网络通信),这对作恶手段也有很高的要求(Xavier 和 Yasmine attesting 要先知道他们证明的区块不会被选为主链,但这仍表示 LMD 方法不如拜占庭共识算法来的强健)。

和 TxFlow 比较

TxFlow 是 Near 用于其分片链的共识算法,关于 TxFlow 的细则可以在这里找到。

以太坊采取的方法的两个缺点是:即便积累大量证明,理论上分叉仍然可能发生,而且非常依赖验证者之间的时间同步。目前协议中,出块速度为 8 秒,所以要求时间同步精度在数秒以内。以太坊基金会进行过的测试表明,若时间差在 10 秒以内,链仍然会继续增长。大多数证明会变成“跳过该区块”操作,但仍然能指向正常的区块,使得链稳定增长。

TxFlow 继承了大多数以太坊方法中的特点,但是不依赖时间同步;只要求恶意节点少于 1/3 则正常区块就是不可逆的。然而,在目前的设计中,只要超过 1/3 的验证者掉线,整个链就会丧失活跃性。

注脚:请注意,当分片数量很多,且恶意身份能灵活切换时,假设恶意节点少于 1/3 占比是不合理的。所以包含 TxFlow方法在内的其它拜占庭协议,最终仍有可能发生分叉。

值得一提的是,EthResearch 在 TxFlow 上测试时,Vitalik 指出 TxFlow 方法中决定什么时候出块的设计(“网速多快,就出多快”)有其他缺点:这会促使节点们抱团,以减少延时。对此指控的反驳是, TxFlow 方法的瓶颈来自“速度最慢的 1/3 节点里,其中最快的验证者的延时”。也就是说,除非超过 2/3 占比的验证者联合起来,不然无法有效提高出块速度(也无法增加出块奖励)。所以 TxFlow 的验证者发生抱团或中心化,需要大多数验证者共同为之,这在验证者基数足够大的情况下很难发生。

下表将 TxFlow 方法和 证明( Attestations)框架进行简化对比:

7

结语

如果你对分片的去中心化账本有兴趣,请关注我们的进展:

最后,请订阅我们的频道。我们会在未来几周内公开主要的 GitHub 代码库,敬请期待。

非常感谢 Vitalik Buterin, Justin DrakeDanny Ryan 进行无数的答疑,并明确了证明框架;还要感谢 Bowen Wang 和 David Stolp 校对本文。


原文链接: https://medium.com/nearprotocol/detailed-overview-of-ethereum-2-0-shard-chains-committees-proposers-and-attesters-a9992d2fd103
作者: Alexander Skidanov
翻译&校对: IAN LIU & 阿剑

本文由作者授权 EthFans 翻译及再出版。


你可能还会喜欢:

干货 | Vitalik:Casper 的过去、现在和未来
干货 | PoS 区块链共识算法中的同步和时序假设
引介 | VDF 不是工作量证明

 
0 人喜欢