Vitalik 亲述:CBC Casper 教程

unitimes.io

全球视角,独到见解

Unitimes 是本文在中国大陆区中文版首发平台,英文原文见文章底部链接。Casper 是以太坊版本的PoS,也是以太坊2.0的关键共识基础。其中,CBC(建构修正)是由以太坊研究者 Vlad Zamfir 主导的 Casper 版本。本文系 Vitalik Buterin 自今年8月在 twitter 连发75条推文阐述 Casper 复杂的发展历程以后又一关于 Casper 的深度探讨,我们不妨看看Vtialik眼中的 CBC Casper。

特别感谢 Vlad Zamfir,Aditya Asgaonkar,Ameen Soleimani 和 Jinglan Wang 的审阅。

为了帮助更多人理解“另一版本的Casper”(Vlad Zamfir 所提出的 CBC Casper),尤其是最适合区块链协议的实例化,我想我会亲自撰写一份解释,从一个不那么抽象并且更“接近于具体用法”的角度进行阐述。Vlad 关于 CBC Casper 的描述可以参阅此处[1]。我们欢迎大家积极探讨这些材料。

CBC Casper 的设计基础非常全面且抽象,并且其几乎对任何数据结构都能达成共识——你可以使用 CBC 来决定到底选择0还是选择1;你可以在 CBC 上运行一条简单的区块相接的链,或者2的92次方维超立方体缠结 DAG,以及它们之间的几乎任何东西。

但为了简单起见,我们首先将注意力集中在一个具体的案例上:一个简单的基于链的结构。我们假设有一个由N个验证者组成的固定的验证者集合(即传说中的“押注节点”。我们还假设每个节点都押注相同数量的币,对于不满足这一假设的情形,我们可以通过给一些节点分配多个验证者ID来进行模拟)。我们把时间分解为长度为十秒的时隙,并且验证者k可以在k,N + k,2N + k等时隙中创建区块。每个区块指向一个特定的母区块。显然,如果我们想要创造一些最简单的东西,我们只需采用这种结构,在它上面实施最长链规则,并称之为一天。

绿色的链是最长链(长度为6),因此它被认为是“权威链”。

然而,在这里我们的重点是要增加一些“最终化”的概念:即某些区块能够在链上得到极其稳固的认可,稳固到其无法被其它竞争区块所取代,除非有数量极其庞大(比如1/4)的验证者作出某些独特的可归因的错误行为(比如以某种明显且可被密码学验证为恶意的行为行事)。如果很大一部分验证者确实采取恶意行动来回滚区块,那么这一恶意行为的证据将被提交到链,从而罚没这些验证者的全部保证金。如此一来,回滚敲定结果的成本将会非常昂贵(想想,白花花的几亿美金)。

LMD GHOST

这一部分的内容我们不妨徐徐展开。首先,我们替换了分叉选择规则(在众多选项中决定哪条链是“权威链”的规则,即哪条链应为用户所关注)。我们不再选用简单的最长链规则,而是改用“由最新消息驱动的 GHOST”。为了说明 LMD GHOST 的工作原理,我们将修改上述例子。为了使其更加具体,我们不妨假设验证者集合的大小为5,并将其中每一位验证者分别标记为A,B,C,D,E。由此,验证者A在第0个和第5个时隙生成区块,验证者B在第1个和第6个时隙生成区块,依此类推。评估 LMD GHOST 分叉选择规则的客户端只关注由每一个验证者签署的最新(即最高时隙)消息(即区块):

蓝色表示最新的消息,从左到右时隙依次递增(例如,最左端的A的区块位于第0个时隙,依此类推)

现在,我们仅使用这些消息作为“贪婪的最重观察子树(GHOST)”的分叉选择规则的源数据:从创世区块开始,然后每次都要进行一次分叉选择,选择拥有更多最新消息支持的区块的子树的一侧(即更多最新消息支持该区块或者该区块的其中一个后代),并继续执行直到到达没有子代的区块。我们可以为每个区块计算支持其自身或者它其中一个后代的最新消息的子集:

现在,为了计算头部,我们从头开始,然后在每一个分叉选择更高的数字:首先,选择底下的链,因为相比起上面这条只有1条最新消息支持的单一区块链条,底下的链有4条支持自己的最新消息,然后在下一个分叉支持中间的链。最终的结果与最长链相同。事实上,在一个运行良好(即孤儿率很低)的网络中,大多数时候 LMD GHOST 和最长链规则都会给出完全相同的答案。但在更极端的情形中,就不一定是这样了。例如,我们不妨考虑下述这条链,其发生了三区块分叉:

依据链的长度为区块赋予权重。如果我们遵循最长链规则,那么由于顶链更长,所以顶链获胜。

依照支持该链的最新消息的数量,并使用 GHOST 规则对区块赋予权重(最新消息来自图中用蓝色标示的验证者)。底下的链当前获得更多验证者的支持。因此,如果我们遵循 LMD GHOST 规则,那么底下的链将获胜,尽管我们暂不清楚这三个区块谁处于优先状态。

LMD GHOST 方法在某些情形中具有过人的优势,它可以更好地在高延迟条件下提取信息。如果两个验证者分别创建出一个共享同一个母代的区块,那么实际上它们可以被认为是对母区块表示共同支持,即使它们同时也在为自己竞争选票。最长链规则无法捕捉到这种细微的差别,而基于 GHOST 的规则可以。

检测最终化

LMD GHOST 方法还有另外一个很棒的特性:它的黏性很大。例如,假设在两轮投票中,4/5的验证者都投票给同一条链(我们假设这五个验证者中的验证者B没有进行投票,此刻B正在进行攻击):

如果想要成为权威链,最上面的链需要做什么?已经有四个验证者基于E的第一个区块来构建新的区块,并且这四个验证者都确认了E在 LMD 分叉选择中拥有最高的权重。仅仅通过查看这条链的结构,我们就可以知道,验证者必须在不同时间内至少看到某些消息。以下是我们所获知的这四个验证者的视图:

绿色表示每个验证者所生成的区块,蓝色表示我们所知道的他们从其他验证者处看到的最新消息。

需要注意的是,这四个验证者都可以看到B的其中一个甚至两个区块,而D和E可以看到C的第二个区块,因此他们把这而不是C的第一个区块作为视图中的最新消息。然而,我们无法通过链的结构本身来证明他们确实是这么做的。所幸的是,正如我们将在下面看到的,这种模糊状况对于我们来说无关紧要。

A的视图包含支持底链的四条最新消息,而没有支持B的区块的消息。因此,在(我们模拟的)A的眼中,支持底链的权重至少为4比1。 C,D和E的视图描绘了类似的情形,即均有四条支持底链的最新消息。因此,这四个验证者都无法轻易改变主意,除非另外两个验证者首先改变他们的想法,将得分改为2比3,从而支持B的区块。

请注意,我们对验证者的视图的模拟是“过时的”。例如,他并不知情D和E已经看到C最新的区块。然而,这并不会改变顶链和底链对决的计算结果。因为我们可以非常普遍地认为,任何验证者的新消息都会与其之前的消息具有相同的意见,除非另外两个验证者已经先切换了队列。

最小的可行攻击。A和C非法切换队列,改为支持B的区块(并且可能因此受到惩罚)。这一行为最终导致顶链和底链3比2的结果,这时D和E就可以合法切换队列了。

由于诸如 LMD GHOST 之类的分叉选择规则在这一方面的黏性很大,并且客户端可以检测到分叉选择规则何时“黏在”特定的区块上,因此我们可以使用这种方法作为实现异步安全共识的方式。

安全性预言机

事实上,检测链条黏在某个区块上的所有可能情况(在 CBC 术语中,这一区块“已被确定”或者“是安全的”)是非常困难的,但我们可以提出一套启发式方法(“安全性预言机”)来帮助我们检测可能会发生这种情况的案例。其中最简单的是团预言机(clique oracle)。如果存在一个验证者子集V,并且该子集在支持某个区块B的总验证者集合中占比为p(p> 1/2),并且在下一轮中,使区块通过引用其在第一轮中的选择依旧支持B,那么我们可以推理如下:

经过两轮的消息传递,我们知道该子集V都(i)支持B;(ii)知道B得到大量支持。因此,除非有足够数量的其他验证者率先切换,否则他们都不能合法地进行切换。对于击败B的竞争者B',B'可以合法拥有的支持最多为1-p(每个验证者都不属于团的一部分),但为了赢得 LMD GHOST 分叉选择,其支持率需要达到1/2,所以至少需要有1/2 - (1-p) = p - 1/2的验证者非法切换队列,以实现 LMD GHOST 规则支持B'的目的。

作为一个具体案例,请注意p = 3/4团预言机提供了1/4级别的安全性,并且只要有3/4的节点在线,我们就可以生成(在正常情况中)满足团的区块集合。因此,从 BFT 的角度来看,就活性和安全性而言,使用两轮团预言机可以达到的容错阈值为1/4。

这种达成共识的方法有很多优势。首先,短期链选择算法和“最终化算法”这两个组件并没有被笨拙地组合在一起(这也是 Casper FFG 的一大缺憾)。相反,它们都是同一个连贯整体的一部分。其次,由于安全性检测是在客户端一侧进行的,因此我们无需在协议中选择任何阈值。客户端可以自行决定什么级别的安全性足以将区块视为最终确定。

进一步探讨

CBC 可以通过多种方式来进一步扩展。首先,人们可以提出其它安全性预言机,比如更高轮次的团预言机可以达到1/3的容错能力。其次,我们可以添加验证者轮换机制。最简单的方法就是每次q = 3/4团预言机得到满足时,就改变验证者集合的一小部分。我们也可以使用其它方案。第三,我们不一定拘泥于链式结构,我们可以查看增加每单位时间消息密度的结构,例如 Serenity 信标链的证明结构:

在这一情形中,将证明与区块分开是值得的。区块是使底层DAG增长的对象,而证明则有助于分叉选择规则。在 Serenity 信标链规范[2]中,每个区块可能有成百上千个与之对应的证明。但是,无论你采用哪种方式,CBC Casper 的核心逻辑都是一样的。

为了使 CBC Casper 的安全性“满足加密经济效益”,我们需要增加有效性和削减条件。首先,我们将从有效性规则开始。区块包含母区块和它所知道的一组证明,这些证明还不是链的一部分(类似于当前以太坊PoW链中的“叔区块”)。为了使区块生效,区块的母代必须是执行 LMD GHOST 分叉选择规则的结果,并且这一结果必须依据被包含在包括该区块的特定链中的信息来进行计算。

虚线是叔链接。例如,当E创建一个区块时,E注意到C还不是链的一部分,因此其包含对C的引用。

现在我们可以只用一个削减条件来保证 CBC Casper 的安全性:你不能同时做两个证明M1和M2,除非M1在M2证明的链中或M2在M1证明的链中。

有效性和削减条件相对容易描述,尽管实际实现中需要检查哈希链,并执行满足共识的分叉选择规则,因此它不像接收两条消息并检查这些消息所提交的数字之间的不等式那么简单(这是 Casper FFG 中NO_SURROUND和NO_DBL_VOTE削减条件[3]的做法)。

CBC Casper 的活性叠加了基础链算法的活性(例如,如果它是每个时隙出一个区块,那么它将依赖于所有节点将在时隙N+1开始之前看到在时隙N中所产生的所有内容这一同步假设)。这种方法不存在网络卡死的状况。在任何情形下,我们都可以对新区块进行最终化,即使网络中存在攻击者和/或网络延迟高于底层链算法的阈值。

假设在某个时刻T,网络“获得安宁”并再次满足同步假设。然后,每个验证者都会对同一条链的视图趋于一致,并且拥有同一个头部H。从那里开始,验证者将签署支持H或H的后代的消息,并且链条将顺利发展,最终满足团预言机,即H被最终敲定。

高延迟导致网络混乱。

网络延迟消退,大多数验证者在执行分叉选择时看到所有相同的区块,或者至少足够数量的区块以到达同一个头部,并基于该头部进行后续搭建,以进一步加强自身在分叉选择规则中的优势。

链条以低延迟方式“和平地”发展。很快,团预言机就会被满足。

到此为止啦!在具体实施方面,CBC 可能比 FFG 要复杂得多,但就推理协议的能力及其提供的属性而言,它确实十分简单。

参考材料

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181210A1H4VR00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券