CBC Casper:安全性证明(二)

ETH中文网  2019-05-15  以太坊/以太坊(Ethereum)栏目  

  来源:hackingresear.ch

  作者:Barnabé Monnot

  在上一篇文章《CBC Casper:安全性证明(一)》中我们已经就CBC Casper的定义、协议及协议安全性作出了一些讨论,本文将继续深入探讨共识协议并且证明其安全性。

  目录

  1. CBC究竟是什么?

  2. 协议的空间

  2.1 信息的定义

  2.2 某状态的未来状态

  2.3 模棱两可错误

  3. 协议的安全性

  4. 共识协议的规范

  4.1 检查点!扼要论述

  5. 建立共识

  5.1 最新信息

  5.2 预估者接收的信息

  6. 最小程度的Casper 共识协议

  6.1 友好的二元共识

  6.2 友好的整数共识

  6.3 友好的GHOST

  7. 未来的讨论对象

  注:由于原文篇幅较长,本文将包含4-7章,1-3章参见上一篇文章。

  4. 对共识协议的规范

  我们从前文中可以得知,Casper CBC以抽象的方式定义了一个协议规范,内容由通过发送消息达成共识的验证者组成。一旦我们证明了这个共识协议大家庭具备着某些优质的属性,那么我们可以更进一小步,来定义这些机制中的某些成分,继而获得具体的协议案例。这就是CBC的魅力所在:通过在基础架构上下功夫,我们便能自上而下地获取收益。

  图9 CBC家族图谱

  要是从抽象的规范进行衍生,CBC Capser可以被优化以产生多种具象的共识协议。

  这一环节还将会按照我们在上文中给出的定义,展示具体协议的案例,目的是对总体框架进行阐述。然而,令人庆幸的是,我们在前面的章节中已经做了很多努力,所以这部分将通过示例,使一些更具难度的想法变得极其实际。在深入之前,我们先稍微回顾一下目前的进程。

  4.1 检查点!扼要论述

  有一组验证者试图就某对象达成共识,他们可以通过发送信息进行沟通。每当有验证者发送消息时,一个估计值必须被给出。换言之,验证者会认定一个值为共识值,并对其加以陈述,此外验证者还会通过参考某些先前的协议状态,为其消息提供证明。这个证明值不过是先前消息的集合,它作用于证实“我已经读取过这些消息,而我的新消息是原有消息的延续”。同时,节点会按照异步方式观察消息,并进行协议状态的转换:这样一来就有可能不是每个人都看到相同的状态,但所有状态都由引用先前状态的消息组成。

  现在,如果我是一个验证者,我通过如下行为就可以破坏一个协议。假设我发送m和m’两条不同的消息,并保证两条消息彼此互不为参考值,且估计值不同。在此,我基本是指:“我正在利用m延续历史消息,但是m’被用于在另一个世界里延续历史消息。”这就是一个模棱两可错误。因此这个协议现在以两个不同的版本(或者是说两条线程)运行,且两者互不兼容。

  模棱两可的问题在于,如果验证者开始传达任何内容及与其相悖的内容(tout et son cONTraire,一切命题以及与这一切命题意义相反的命题),那么就有可能无法达成共识。如果从某个状态开始,节点对某些他们认为是真实的事情加以决定,我们要如何保证这些决定不会不一致?

  答案在于安全性保障。我们给自己设置一个权重t,并假设在我们的节点观察到的所有状态中,已发生模棱两可错误的验证者总权重小于t。然后,通过安全性保证,我们知道节点拥有共同未来,因此节点不能做出相互矛盾的决定。如果要查阅阈值t如何确定最终决策方式的详细内容,请查看我们关于Inspector的文章!

  图10 未来锥的交汇

  两个节点A和B分别处于状态σ1和σ2。如果从它们现在各自的状态来看,它们可以达到一个共同状态σ1∪σ2,那么它们则享有共同未来状态。如果模棱两可验证者数量小于且持续小于t,在被决定的诸多属性一致的条件下,安全属性就会保证共同未来状态的存在。处于在未来锥σ’和σ”的交叉部位的每一个状态都是一个σ1∪σ2的超集。

  5.建立共识

  既然我们现在已经有了协议规范和安全性保障的坚实基础,是时候充分利用这些内容了。涉及和延申协议是为了达成共识,这也是接下来我们要集中讨论的对象。

  5.1 最新消息

  当验证者发送消息时,他们估计某个值应该被确定为共识。另一方面,不诚实的验证者可以通过产生两个不同的估计值来破坏协议。那么这样一来,就需要一个必要条件:诚实的验证者总是最多只有一条最新消息——如果他们从未发出任何消息,或者如果在特定状态下他们的消息没有被接收到,那么他们可以没有最新消息。然而,如果在状态内观察到它们,则只存在这样的一条最新消息。基于诚实验证者被接收到的一系列信息,在这种情况下共识才是可讨论的。

  图11 验证者的最新消息

  假设我们有A,B和C三个验证者。

  A和C发送了一条消息(处于状态σ1和σ2)

  B产生模棱两可错误,并发出了两条消息m以及m’

  在状态σ4下,我们有一条来自A(在观察中表现诚实的验证者)的最新消息,还有两条来自B的消息(在观察中模棱两可的验证者)还有一条来自C(未被观察的验证者)的0条消息。

  5.2 预估者接收的消息

  在被观察到的诚实验证者发出了最新消息,并为我们收集到后,我们的讨论对象可以从协议状态转移到共识值。我们可以将验证者映射到他们自己的估计值;如果没有观察到验证者,或者是没有办法判断验证者是否模棱两可,那么也可以映射到空集。他们在最新消息中所包含的共识值即为估计值。

  预估者会从协议状态返回一组共识值[10]。要是预估者只查看由一系列诚实验证者产生的最新估计值,他就会为此估计值所驱使,并在最新状态下表现为诚实。在下文中,我们所有的预估者都将是在最新状态下表现诚实、并为预估值所驱使的。因此,预估者会弥补协议状态与其自身所估计的共识值之间所缺乏的联系。

  6. 最小的Casper共识协议

  我们还有什么要做的?我们目前证明了:除非模棱两可的验证者权重过高,节点无法就相互矛盾的共识值作出决策。我们目前还观察到:有些验证者表现得很好,并且为某种协议状态所囊括,他们各自只发送一条最新消息。最后,我们将这些最新消息映射到预估中的共识值。

  现在我们应该确定:

  我们所讨论的值集究竟为何物?

  从被观察到的、表现诚实的验证者的估计值中如何达成共识。

  6.1 友好的二元共识

  对于最小的CBC Casper协议而言,存在一个最简族群,即二元共识。二元共识要求验证者在0和1两个值间做出选择。共识值则来自于一个简单的多数人规则。在此,我们给每个验证者v某个权重,记作w(v)。此外,还存在一个决定共识的最大集合,在此背景下,这些权重会被加起来算出总和。有的验证者估计值为0,有的为1,而这些权重的总和将用于对比这两类情况。请注意在平局情况下,两个值都会被撤回:预估者会撤回一个属于共识值集合的子集,而且这个子集可以包含多个元素在内,这一点我们应该牢记。

  图12 友好二元共识

  四位验证者将对共识值进行估计。其中模棱两可的B和未被观察的C没有权利进行最终决策。D的估计值为0,但他的权重为2,低于估计值为1的A。因此,最终得出共识值为1。

  6.2 友好的整数共识

  从符合逻辑的角度看,下一步是就一个拥有两个以上元素的集合达到共识。在这个版本内,验证者的估计值为整数。正如我们为二元共识协议所做的那样,我们可以再次经由最大验证者集合撤回这个数值。然而,这样可能无法完美展示和共识有关的想法,原因在于一个分布的众数(最高的峰位)可以和它的中位数和平均数截然不同。

  这篇文章选择了中位数进行估计。每个整数都是根据这些撤回该整数的验证者的总权重进行加权。预估者接下来会从这些加了权的整数中返回相应的中位数。通过返回一个整数,就能粗略得到一个加权中位数,以至于对于所有验证者的总权重而言,一半以下的总权重会比这个加权中位数小,还有一半以下的总权重会比大于这个加权中位数。下面的简图或许可以帮助理解。

  图13 友好整数协议

  第一个数据组给出了六位被观察到的诚实验证者的估计值及验证者对应的权重。第二个数据组则是每个整数估计值的总分数。在表格中,粉色代表累计分数分布,虚线代表验证者总权重的中线。由于小于2的整数的总分数小于7(蓝色箭头所示总分数为6)并且大于2的整数的总分数小于7(第二个蓝色箭头所示总分数为4),我们能够得到2是加权中位数,因此也是这里的共识值。您还可以尝试整数1不作为加权中位数的情况。您是否能举出加权中位数返回包含多个整数的集合的例子?

  6.3 友好的GHOST

  在本文论述阐发的开端和过程中,区块链议题本应该是首要的议题,然而我们仿佛游离于区块链之外。不管怎样,基于强大的推理演算,我们能够非常迅速地令Casper适应一个由区块链主导的框架。Casper的首要应用则是面向分叉选择规则,即GHOST,用来指代“贪婪子树协议”(Greedy Heaviest Observed Subtree,你能否看到它和Casper的关联呢?)。

  对于区块数量趋于暴增的区块链来说,GHOST尤为实用。比特币平均每10分钟增加一个区块。但是,以太坊和比特币不同,平均每10~20秒(如果按照写入的时间看,平均下来15秒)增加一个区块。这一不同的特性会增加叔伯率,换句话说,这一速度会导致新产生的有效合法区块不被纳入主链。在GHOST协议下,各个父块可以有多个子块,而这些所有的区块都被规范主链所包括。既然我是一个十足的视觉偏好者,我就将MichAEl Birch酷炫的动画演示分享给大家作为参考(参考文献13)。

  在这种情况下,可能性共识值的集合又是什么呢?答案是从创世区块g开始的所有可能区块的集合!这就还是有些像从几个整数开始步步攀升的活动,但是它既适应GHOST协议,也适用于其它几个我们先前所揭示的机制,这个过程的展开自然而然。当区块b属于某个状态时,会有一些验证者返回b’的某一衍生值并将其作为估计值。通过观察这些验证者权重的总和,人们就能计算出b’的分值。由于我们想要的恰恰是最大型的子树,这种做法是可行的。

  “贪婪”又是什么意思呢?我们从创世区块g开始,并且要得到它最好的子区块直到不可再进行分割。换句话说,也就是那些得分最高的子区块,以及这些子区块作为父块由递归方式得到的最佳子区块。至此,GHOST协议会返回由一系列最好区块组成的集合,这个集合恰恰是共识协议所需要的:该共识协议会告诉我们要在哪里建立下一个区块!

  从6.2整数共识的部分中,您对其中的共同点应该有所观察。在之前,我们从所有可能整数的集合(验证者估计值)中选择出加权中位数。在此,面向一系列候选区块,GHOST协议会返回一个区块,这与预估者的定义完全契合。

  7. 未来将继续讨论的对象

  未来我们将继续撰文探讨另一种Casper,即FFG(Friendly Finality Gadget)。如果您之前已经听说过它,那是因为以太坊社区目前正在积极地对它进行讨论研究。最初的时候,它是基于PoW的共识小工具,但是最近经过重新设计,它将允许在分片(sharding)之上提供完整的PoS。这是一个非常有趣的话题,Vitalik Buterin,Daniël Reijsbergen,Stefanos Leonardos和Georgios Piliouras最近联合发表了一篇论文,这篇论文从加密货币经济学的储蓄和奖励的角度进行论述,为以太坊的Casper确定性小工具提供了合理性根据。

  至于我们提到的分片(sharding),在实际状况下,将CBC Casper框架直接应用于分片上是完全可行的。Vlad Zamfir一直在为此开展一些工作,这些工作包括与来自NEAR Protocol的Alex Skidanov一起致力于研发另一款炫酷的视觉工具,通过这款视觉工具,母链和子链将能共同运行。

  最后,在某些区块链上验证者有可能无法访问协议状态的全部历史记录,针对这种轻量级客户端的需求,规范的CBC Casper能够保证此类区块链的安全性。CBC Casper不仅是一种极其强大的技术,也是目前十分热门的研究对象,它可以降低节点产生的存储要求和相关的计算运行成本。

  致谢: 

  Vlad Zamfir,Aditya Asgaonkar,Nate Rush和Sacha Yves Saint-Léger在本文的准备过程中提供了有益的评论,我们向他们致以感谢。

  开源:

  访问Github,可以找到我们的Javascript CBC库。

  参考文献可前往原文获取。

  原文链接:http://hackingresear.ch/cbc-safety/

  转载请注明ECN以太坊中文网

  欢迎大家从以下社区平台关注我们

  长按识别二维码关注ECN以太坊中文网公众号

  ECN以太坊中文网:ETHereum.cn

  长按识别二维码加入ECN以太坊中文社区

  交流前沿以太坊资讯

  若以上二维码失效,长按识别二维码添加ECN官方账号

  加入ECN以太坊中文社区

版权信息
作者:ETH中文网
来源:ETH中文网

关于我们

联系我们

作者进驻

手机版

Copyright © 2013 比特巴 www.btb8.com
始建于2013年,提供比特币 区块链及数字货币新闻、技术教程、测评、项目周报、人物等资讯
本页面提供的是以太坊新闻资讯,以太坊是一个平台和一种编程语言,意为“下一代加密货币与去中心化应用平台”,可以用来创建去中心化的程序、自治组织和智能合约.