源质社区

 找回密码
 立即注册
搜索
热搜: 邀请码
查看: 55|回复: 0

干货:V神亲自撰文,详解以太坊CBC Casper

[复制链接]

79

主题

86

帖子

373

积分

中级会员

Rank: 3Rank: 3

积分
373
发表于 2018-12-11 09:58:03 | 显示全部楼层 |阅读模式

为了帮助更多的人理解“另一个Casper”(Vlad Zamfir的CBC Casper),具体来说,最适合区块链协议的实例,我想我会从一个不那么抽象、更接近具体使用的角度写一篇解释的文章。Vlad对CBC Casper的描述可以在这里这里以及这里找到,欢迎大家来查阅。

Casper的设计基本上是非常通用和抽象的,几乎在任何数据结构上都能达成共识;你可以使用CBC来决定是选择0还是1,你可以在CBC上运行一个简单的逐个区块的链,甚至可以将CBC用在292维超立方体DAG上。

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

绿色链是最长链,长度为6,因此被认为是“规范链(canonical chain)”

然而,这里我们比较在意的是增加一些“最终确认(Finality)”的概念——一些区块可以非常牢固地建立在链中,以至于它不能被竞争区块所取代,除非非常大比例(例如1/4)的验证者提交了一个可归因的错误——可以明显并以加密的方式验证是恶意的错误。如果很大一部分验证者确实采取恶意行动来逆转区块,那么可以将不当行为的证据提交给链,以没收那些验证者的全部保证金,使得最终确认的逆转非常昂贵(可能要花费数亿美元)。

LMD GHOST

我们将一步一步来。首先,我们替换分叉选择规则(在多条可能的链中选择哪条链是“规范链”,即用户应该关注的链),不再使用最长链规则而是使用“最新消息驱动GHOST(LMD GHOST)”。为了说明LMD GHOST如何运行,我们将修改上面的例子。为了使其更具体,假设验证者集的大小为5,我们将其标记为A、B、C、D、E,因此验证者A在slot0和slot5处生成区块,验证者B在slot1和6处生成区块,以此类推。评估LMD GHOST 分叉选择规则的客户端仅关注每个验证者签名的最新(即最高时隙)消息(即区块):

△最新消息以蓝色表示

现在,我们将仅使用这些消息作为“最贪婪的观察子树(Greedy Heaviest Observed Subtree,GHOST)”分叉选择规则的源数据:从创世块开始,然后每次都会有一次分叉,选择更多最新消息支持的那一侧区块的子树,并继续执行此操作,直到到达没有子区块的区块。我们可以为每个区块计算支持该区块或其后续区块的最新消息的子集:

现在,为了计算起始区块,我们从头开始,然后在每次分叉时选择更大的数字:首先,选择底部链,因为它有4个支持它的最新消息,而顶部链只有1个,然后在下次分叉支持中间链。结果与以前的最长链相同。实际上,在一个运行良好的网络中(即孤儿区的出现率很低),几乎所有的时间里LMD GHOST和最长链规则都会给出完全相同的结果。但在极端的情况下,情况并非总是如此。例如,考虑以下链,它有三区块分叉:

根据链的长度标号。如果我们遵循最长链规则,则上面为主链

按最新消息的数量并使用GHOST规则对来区块计数(来自每个验证者的最新消息以蓝色显示)。底部链具有更新消息的支持,因此如果我们遵循LMD GHOST规则,底部链获胜,但尚不清楚这三个区块中的哪一个优先。

LMD GHOST方法是有利的,部分原因在于它可以更好地在高延迟条件下提取信息。如果两个验证者创建具有相同父区块的两个区块,则它们实际上应该被计为父块合作投票,即使它们同时为自己竞争选票。最长链规则无法捕捉到这种细微差别;基于GHOST的规则可以。

检测最终确认

LMD GHOST方法还有另一个不错的特性:它具有粘性(sticky)。例如,假设在两轮中,4/5的验证者投票给同一条链(我们假设五个验证者中没有投给这条链的B正在攻击):

怎样才能成为规范链呢?五个验证者中的四个在E的第一个区块之上继续构建区块,并且所有四个验证者都承认E在LMD分叉选择中获得最大的序号。仅仅通过查看链的结构,我们就可以知道验证者必须在不同时间至少看到的一些消息。以下是四个验证者的视图:

每个验证者生产的区块以绿色表示,从每个其他验证者中看到的最新消息以蓝色表示。

注意,所有四个验证者都可以看到B的一个或两个区块,而D和E可以看到C的第二个区块,使得C的第二个区块成为他们视图中的最新消息;然而,链结构本身并没有给我们证明确实是这样。幸运的是,正如我们将在下面看到的,这种模糊性对我们来说无关紧要。

A的视图包含支持底链的四条最新消息,而没有一条消息支持B的区块。因此,在(我们的模拟)A眼中,有利于底链的得分至少为4-1。 C、D和E的视图描绘了类似的情况,其中有四条支持底链的最新消息。因此,所有四个验证者都处于不能改变主意的位置,除非另外两个验证者率先改变他们的想法,将得分改为2-3去支持B的区块。

请注意,我们对验证者视图的模拟是并非最新即时的,这是因为,举个例子,它没有捕获到D和E可能已经看到C更新的区块。但是,这不会改变顶链vs底链的支持情况,因为我们可以说任何验证者的新消息都会与之前的消息具有相同的意见,除非另外两个验证者已经先转换了支持对象。

最小可行攻击。 A和C非法转换到支持B的区块(并且可能因此受到惩罚),给它3-2的优势,此时D和E可以合法转换。

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

安全预言机

实际上,检测链卡在某个区块上的所有可能情况(在CBC术语中,区块是“决定的”还是“安全的”)是非常困难的,但我们可以提出一套启发式的思路(“安全预言机”)来帮助我们。其中最简单的是clique oracle。如果存在某个验证者子集V,构成总验证者集的p(p> 1/2),则所有区块都支持某个区块B,然后使另一轮区块仍然支持B(引用它们的第一轮区块),然后我们可以推理如下:

由于两轮消息传递,我们知道该子集V都支持B,B得到良好的支持,因此除非有足够的其他人首先转换,否则它们都不能合法地转换。为了让某个竞争B'击败B,B'可以合法拥有的支持最初最多为1-p(不属于clique的人),并且为了赢得LMD GHOST分叉选择,其支持需要达到1 / 2,所以至少1/2 - (1-p)= p - 1/2需要非法转化以使其达到LMD GHOST规则支持B'的程度。

举个例子,请注意p = 3/4 clique oracle提供1/4的安全级别,并且只要3/4的节点在线,就可以生成满足clique的一组区块。因此,在BFT的意义上,就活跃性和安全性而言,使用两轮clique oracle可以达到的容错水平是1/4。

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

未来拓展方向

CBC可以通过多种方式进一步扩展。首先,人们可以提出其他安全预言机;更完备的clique oracle可以达到1/3的容错能力。其次,我们可以添加验证者轮转机制。最简单的方法是每一次满足q = 3/4 clique oracle时允许验证者集改变一小部分,当然我们也可以做其他事情。第三,我们可以不局限于链式结构,关注一下增加每单位时间消息密度的结构,例如Serenity信标链的证明结构:

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

为了使CBC Casper的安全性“在加密经济层面上可执行”,我们需要增加有效性和削减条件。首先,我们将从有效性规则开始。一个区块包含父块和它知道的一组证明,但这些证明还不是链的一部分(类似于当前以太坊PoW链中的“叔块”)。考虑到链中和区块本身包含的信息,为了使区块有效,区块的父块必须是执行LMD GHOST 分叉选择规则的结果。

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

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

有效性和削减条件相对容易描述,虽然实际中实现它们需要检查哈希链并在共识中执行分叉选择规则,因此它不像接收两条消息并检查这些数字之间的几个不等式那么简单,就像你可以在Casper FFG中为NO_SURROUND和NO_DBL_VOTE的削减条件所做的那样。

CBC Casper的活跃性基于任何基础链算法的活跃性(例如,如果它是每个时隙一个区块,那么它取决于一个同步假设,即所有节点将在时隙N+1开始之前看到在时隙N中产生的所有内容)。链不可能以一种无法继续运行下去的方式“卡住”;有可能从任何情况到达最终确认新区块,即使有攻击者或者网络延迟高于底层链算法所需的延迟。

假设在某个时间T,网络“平静下来”并再次满足同步假设。然后,每个人都会汇聚在链的同一个视图上,带着同一个起始区块H。然后,验证者将开始签名支持H或H的后续区块的消息。于是,链就可以顺利运行,并最终满足一个clique oracle,此时H会被最终确定。

高延迟导致的混乱网络

网络延迟消退,大多数验证者在执行分叉选项时看到所有的相同区块或至少足够多的区块以获取同一个起始区块,并开始基于这个区块构建,进一步加强了它在分叉选择规则中的优势。

链在低延迟的情况下平稳运行。很快,会满足一个clique oracle。

这就是差不多所有内容了。在实施方面,可以说CBC比FFG复杂得多,但就解释协议及其提供的特点来看,它还是非常简单易懂的。


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|源质社区 ( 京ICP备17030519号-2 )

GMT+8, 2019-7-17 04:39 , Processed in 0.047706 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表