Combining GHOST and Casper以太坊2.0共识机制Gasper:part 1

Eth2.0的共识算法设计目标就是让PoS就有一定的安全性和可用性(certain safety and liveness claims).对应着这个目标,提出了两大组件来定义分叉规则和最终性

共识机制设计理念

正如以太坊基金会成员Vald zamfir,所说的Casper的设计出发点,源于对系统 最差情况的经济分析,这也是是公链PoS共识算法的 唯一路径。也因此,Casper希望通过引入惩罚措施来最大化拜占庭容错。

并且,Casper是为轻节点而生,为此需要提供两大特性:

  • 最终性(敲定的块就不能再改了)
  • 低延迟

那么针对这些特性,就需要在指定分叉规则的同时,还要有最终性的共识算法,那么这该如何解决呢?

在2020年5月修改版的《Combining GHOST and Casper》一文中,V神的团队给出了详细的答案及解释。

设计目标

Eth2.0的共识算法设计目标就是让PoS就有一定的安全性和可用性(certain safety and liveness claims).

对应着这个目标,提出了两大组件来定义分叉规则和最终性:

1 最终性规则Casper FFG

Buterin 和Griffith提出了Casper the Friendly Finality Gadget (FFG),引入验证和敲定(justification and finalization)来定义最终性,什么意思呢?其实有点像检查点,简单来说就是,在特定的区块高度需要有验证节点的签名信息A->B(其中A,B代表检查点区块),表明我A举手赞成B成为下一任党委书记,也就是赞成B成为下一个检查点,这样就不要再从创世区块去算状态保证安全性了,因为检查点之后的就改不了了。道理其实很简单,当上了党委书记就有话语权了,政策就不能再由着下面的人乱改了嘛。

同时,Casper也引入了惩罚条件(slashing conditions),来判定谁是坏人谁是好人,违反这两个规则的人就得被开罚单:

  1. 验证者对同一个高度的检查点,只能给一个完全一致的证明
  2. 验证者在两个不相邻的检查点之间只能给一个完全一致的证明,也就是说这两个检查点之间的检查点不能再给不一样的证明了

可以看出,Casper只是规定了检查点是怎么确定下来的,也就是说最终性是如何确定的,而把分叉规则单独最为一个组件,这么做也是为了解耦这两部分。

2 分叉规则LMD GHOST

LMD由Sompolinsky等人提出的The Greediest Heaviest Observed SubTree rule (参见通俗的解释GHOST)改进而来,由于PoS的共识算法需要消息驱动来获取投票的权重,因此称之为Latest Message Driven Greediest Heaviest Observed SubTree(LMD GHOST).

算法如下所示:

1.png

*LMD GHOST算法规则*

举例来说就是,假设每个人拥有一个stake代表一票的权重(下图中用圆圈表示),那么按照这个算法就确定了途中蓝色的主链:

2.png

*LMD GHOST举例*

那么这两个协议是如何结合到一起的呢,以太坊提出了Gasper(Ghost第一个字母G+Casper的后四个字母)协议:

Gasper

为了理解Gasper,我们先要了解三个基本概念:

  • 纪元边界(Epoch boundary):Gasper把12秒定义为了一个基本时间槽(slot),然后把64个slot定义为一个纪元(epoch).那么每个纪元开始的那个区块就成为边界区块,用EBB(B,j)=C表示,第j个epoch的区块B的边界区块是区块C
  • 委员会:所有的验证者被分配到每一个epoch中,构成了一个大的委员会,并且对于每一个slot从这个大的委员会选出一个特定的委员会。再每一个slot中,由一个验证者来打包出块,该委员会的其他成员使用HLMD GHOST(LMD GHOST的一个轻微变种,后面会讲)附上认可这个区块的证明。
  • 验证和敲定(Justification and Finalization):这个其实和Casper FFG很像,不过这里不是对单个检查点操作,而是对所有的纪元边界区块进行操作。

纪元边界区块验证

验证规则定义,如果这个投票的总和大于总staking的2/3,那么就认为边界区块被验证了。

具体而言,对于下面的例子:

3.png

*这是一个验证者的视图,由于网路延迟等问题,他之前很多区块没收到,因此64号区块就是193号区块Epoch1和Epoch2的边界区块,因此他再这里写入投票α,表示(64,2)是(180,3)的边界区块。同时根据GHOST规则可以看出需要投193号区块为当前的链头。*

敲定

而敲定相对于验证是一个更强一点的概念,如果说区块B0构成的边界区块(B0,j)被敲定了,那么要么他是创世区块,要么存在一个k>=1的数满足以下三个条件:

  1. (B0, j), (B1, j + 1), . . . , (Bk, j + k) 是相邻的epoch边界
  2. (B0, j), (B1, j + 1), . . . , (Bk−1, j + k − 1) 都已经被验证了
  3. (B0, j)被 (Bk, j + k)验证了

其实总的来说就是B0,需要被其他区块验证!

举个例子:

4.png

蓝色的区块代表被敲定了,带箭头的边表示被验证了(思考k=2时,B1为什么没有被敲定?)

分叉规则Hybrid LMD GHOST(HLMD)

验证了边界区块之后,只要没有超过1/3的攻击者stake就不能篡改这个区块,在这个假设基础上就能唯一确定边界区块,从而定义epoch内部的分叉规则了,算法如下:

5.png

这个算法思路其实表简单,就是先选取最新验证的epoch边界区块Bj,然后再根据GHOST规则来找到当前主链的链头区块。

细心的你可能发现这里有个问题就是,最新被验证的区块可能会变,因为被验证了不等于finalize了,只要还没被完全敲定就有可能会变;同时,每个验证节点的视图可能不一致,就导致我们自己的这个区块Bj可能跟别人的不一样!

那么对于这两个问题如何解决呢?还有整个系统的安全性和可用性如何呢?且听下回分解...

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-07-09 15:03
  • 阅读 ( 677 )
  • 学分 ( 80 )
  • 分类:以太坊

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PHD

10 篇文章, 1257 学分