探究以太坊 2.0 的分叉选择规则 - 区块链技术 - BitMere

参与者进入验证者池之后，就可以被分配给某个分片。分配过程是是完全随机的，可以通过可验证延时函数（VDFs，VerifiableDelayFunctions）保证随机的无偏性。

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

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

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

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

当分叉发生时，诚实的验证者会选择具有最多区块的那条链。只要诚实的验证者占全部验证者总数的一半以上，想要伪造一条最长链是非常困难的。假设所有少数恶意节点试图联合起来，私下创建一条分叉链，并且故意在诚实链的出块时段内不产出区块；即使如此，他们的恶意分叉仍然会比诚实链要来的短；这个论点类似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个出块时段，诚实的验证者应该接着哪个块创建新的区块呢？我们考虑以下四种可能的情况：

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

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

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

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

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

拜占庭方法

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

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

查看证明（Attestations）数量的方案

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

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

分叉选择规则

即时消息驱动（IMD）

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

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

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

最新消息驱动LatestMessageDriven

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

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

证明的条件

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

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

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

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

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

####分析

活跃性

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

抗审查性

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

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

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

抗分叉性

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

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

假设有七个验证者，其中Alice(A)、Bob(B)、Carol©、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和Yasmineattesting要先知道他们证明的区块不会被选为主链，但这仍表示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的验证者发生抱团或中心化，需要大多数验证者共同为之，这在验证者基数足够大的情况下很难发生。