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

探究以太坊 2.0 的分叉选择规则。

attachments-2018-03-9MDlTgOS5aa74ab46b850.png

作者:Alexander Skidanov

翻译:IAN LIU & 阿剑

来源:以太坊爱好者社区

原文链接:https://medium.com/nearprotocol/detailed-overview-of-ethereum-2-0-shard-chains-committees-proposers-and-attesters-a9992d2fd103

本文约5000字+,阅读(观看)需要25分钟

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


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

委员会及其构造

a9397e3e5664497292ed3222381864f8


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

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


4a4b9ae3dd524845a2266816302e2706



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

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

2b47dd169572423988346a98b00aa077


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

e6c77bd0b3cd4fdcb376e92f206f13d7


总是跟在较早创建的区块后面。这么一来,处在较早出块时段的恶意验证者就会延迟广播区块,直到下一个出块时段的区块被创建后再广播,导致后者就被忽略(如上图情景所述)。

总是跟在较晚创建的区块后面建块。这种情况下,在时段 X 出块的恶意验证者可以选择无视时段 X-1 创建的区块,并且能确保负责时段 X+1 的验证者一定会选择他的区块,而时段 X-1 创建的块就会被忽略。

总是跟在自己先接收到的区块后面建块。这种情况下,只要恶意验证者比下一个验证者的网速更快更稳,上述两种情形都有可能发生。

随机选择区块。这样恶意验证者就无法确定自己创建的区块会不会被接受(除非它们在一条网络中控制了多个出块时段);但是如果审查区块能获得高于出块的奖励,恶意验证者仍会尝试作恶,同时有 50% 的成功几率。

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

拜占庭方法


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

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

检查证明数量的方案


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

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

分叉选择规则


4af3f4105d664adba19cb29ce397caa4


我们分析一下上图所示的情形。每个区块中的字母表示该区块获得的证明,虚线的区块表示“跳过该区块”操作。现在发生分叉,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

87839ea5577042a68a3820871b00aae1


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

证明的条件


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

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

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

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

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

进一步分析


活跃性

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

抗审查性


5b46e7573735449c96886874c5c5daab



抗分叉性

在两种可能的累计证明数的方法中(最新消息驱动 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 ,我们仍无法完全避免分叉发生。我们考虑下面的例子:

531a0c21771b4b079aedacab8ea37663


假设有七个验证者,其中 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方法在内的其它拜占庭协议,最终仍有可能发生分叉。

e5821675b64f4617a895eaa1cfef6ee2

文章发布只为分享区块链技术内容,版权归原作者所有,观点仅代表作者本人,绝不代表区块链兄弟赞同其观点或证实其描述。

attachments-2018-02-kL1zBfXx5a7ffd0b78798.jpg

  • 发表于 2019-01-08 11:07
  • 阅读 ( 1478 )
  • 分类:以太坊

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
社区运营-小以

621 篇文章

作家榜 »

  1. 社区运营-小以 621 文章
  2. 社区运营-小链 238 文章
  3. 于中阳Mercina-zy 79 文章
  4. 涂晶 74 文章
  5. 李晓琼 44 文章
  6. 兄弟连区块链培训 42 文章
  7. 吴寿鹤 36 文章
  8. 刘旷 28 文章