本文是对论文Combining GHOST and [Casper](https://learnblockchain.cn/article/1294)的解读。 并不是逐字的翻译，而是对每个章节内容的解释和一些思考。 本文分为3部分WHAT、WHY、PRACTICE, 大致对应论文的结构，分别讲Gasper协议的内容、协议有效性证明、beacon chain在实现Gasper时的一些tradeoff。<br /> 更多文章: [Bo1010 blockchain research](https://al3ul0osmp.feishu.cn/wiki/wikcnPaz9ZaBWWD0zm6f6Zf7iqd)<br /> # WHAT<br /> ## 概括<br /> Gasper 要解决的是Ethereum2.0 共识层的 Fork choice 和 block最终确定性(finality)的问题。<br /> 在POW时期，这个问题的解决比较简单，依赖区块的长度（block number）, 因为最长链上积累了最大的工作量，我们选择block number最大的block作为head, 以解决fork choice的问题； 我们通过某个block和block head之间的距离，评估这个block的确定性。 在POS中， 我们没有算力的支撑，就依赖数学算法解决这些问题。</p> <p>Gasper 是Casper FFG 算法（Casper the Friendly Finality Gadget， 下文称Casper）和 LLMD GHOST(下文称GHOST) 的组合。 Casper解决的是finality, GHOST解决的是Fork choice。<br /> ### Casper<br /> 构建区块链的参与者称为validator, 任意一个validator A， 它在本地他维护了当前区块链的视图G（有向无环）——blocks and the edge of two block ， 网络上的任意其他validator都可以传输任意看似合法的block到这个视图中， 那么本地validator, 如何确定一条全网共识的blocks路径。 这是一个区块链场景下的拜占庭容错（ Byzantine Fault Tolerance）问题。接下来就是Casper的方法。</p> <p>除了block 视图,还有attestations。 Attestation 是validator对the edge of two blocks 的投票， 投票的权重weight为validator质押的资产数量， 在Ethereum里，每个validator质押量是相同的，可以认为是1（实际是32ETH）。 全网的validator数为N， 则全网的质押量为N。 Validator 对edge进行投票， 即attestation，同时广播attestation。 对于validator A, 它选择weight > 2N/3的egde, 以构建出一条全网共识的区块链。 Casper定义了2个slashing condition, 符合这两个条件的任意一个，validator的质押资产将被惩罚掉。</p> <p>为了说明这两个重要的原则， 首先做几个定义：<br /> 1. Checkpoint: block number为H（整数）的倍数的block, 比如定义H=100， 则每100个block出现一个checkpoint block。<br /> 2. 函数h: 输入checkpoint， 返回 checkpoint_block_number / H , 即checkpoint的序号<br /> 3. s->t: 表示一个attestation, s 和 t 分别是一个checkpoint block, h(t) > h(s) </p> <p>Slashing conditions 是：<br /> > (S1) No validator makes two distinct attestations α1 and α2 corresponding to checkpoint edges s1 → t1 and s2 → t2 respectively with h(t1) = h(t2).<br /> > (S2) No validator makes two distinct attestations α1 and α2 corresponding respectively to checkpoint edges s1 → t1 and s2 → t2, such that h(s1) < h(s2) < h(t2) < h(t1).</p> <p>Casper里说了validator不应该怎样投票，并没有说validator应该怎样投票，这由使用Casper的协议决定。<br /> ### GHOST<br /> LMD- GHOST 输入本地区块视图G， 返回block head, 从而确定一条当前最可信的链。 </p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/RSU1wC0c632d386f5a3ba.png" width = "60%" height = "60%" alt="图片名称" align=center /></p> <p>如图， 圆圈表示validator, 方块表示block, block 中的数字表示区块上积累的投票数，子节点的投票会向上累加到父节点。 图中，蓝色区块为每一层上获得投票最多的区块，连在一起为当前视图中最可信的一条链。 </p> <p>非GHOST协议内容：<br /> 每个validator都会根据自己的本地视图G， 使用GHOST方法得到block head, 构造一个attestation 并广播，表示对该block的支持。 由于网络等原因， validator们的本地视图G不同，因此会做出不同的投票。</p> <p>### Gasper<br /> 现在，我们将Casper和GHOST结合，给出一版最简单的Gasper。 我们增加两个概念：<br /> 1. Justification: genesis block 为Justified。 一个投票s -> t， s一定是Justified； 如果s->t获得了2N/3的投票，则t成为Justified。<br /> 2. Finalization: 一个Justified block BJ之后如果连续产生了k个Justified block, 则BJ成为Finalized block。Finalized 是比Justified更强的确定性保证。 k越大，确定性越大。 </p> <p>描述一个简单的Gasper, 让区块链从一个checkpoint block （记BB，boundary block）发展到另一个checkpoint， 不能详细描述的地方用somehow代替：<br /> 1. 当前checkpoint block, 记为BB<br /> 2. somehow 每隔一段时间，产生一个new block, 并广播<br /> 3. validator 隔somehow的一段时间后，计算本地叶子节点B'，并找到链上最后一justified block J. 广播一个attestation， 包含两个投票:<br /> 3.1. GHOST Vote for B', （只能广播一次）。<br /> 3.2. Casper Vote for J -> BB （只能广播一次）。 </p> <p>我们希望step2和step3交替进行，在step3中能对step2中广播的new block投票。当J->BB获得2N/3投票后， BB变为Justified, J变为Finalization。<br /> 当我们去拓展方案中的不足之处时，就会能得到更完整的方案：<br /> 1. 问题1: 谁产生new block ? 为了让系统不被控制， 每次block producer应该是不同且随机的<br /> 2. 问题2: 在一个分布式系统中，如何让validators有step2 step3这样的有序行为呢？<br /> 3. 问题3: 每个validator对每个block投票，容易造成网络拥塞。 但是GHOST不需要2N/3投票。 所以valiator不需要对每个block投票<br /> 4. 问题4: 到底何时对J -> BB投票，如果同时投票，又造成网络拥塞。 一种方案是，每产出一个block, 则让一部分validator进行投票。这样可以将投票分散，但是BB justified的时间就取决于BB之后block的生产速度，这是不合理的，因为BB是否被justified, 已由BB之间视图决定。<br /> 5. 问题5: Ethererum2.0 希望validator是无审查的，可自愿加入，因此validators集合是变动的。 所以2N/3的值是跟具体的validator集合关联， validator 赏罚也需要跟具体validator集合关联。 </p> <p>Gasper 完整实现里， 有Epoch 和 Committees的概念以优化上述5个问题。</p> <p>## Gasper细节<br /> ### Honest Validator Behavior<br /> #### Epoch Boundary Blocks and Pairs<br /> 我们想让分布式系统按照一定的节奏协同工作，但是节点时钟不能保证一致，另外消息的延迟不能保证，我们应该怎样设计系统呢？<br /> 1. 同步系统<br /> 2. 异步系统：能处理任意延迟或者来自未来（时钟不同步）的消息的系统<br /> 3. 半异步系统： 假设消息的传输延迟有上限的系统。 t-synchronous 系统是指，在时刻T以及T之后的时间， T-t之前的消息已经同步到所有节点</p> <p>Gasper的设计采用“有边界的半异步系统”。 消息归属于一个时间片段，在这时间片开始的t个时间单位后，能同步到其他节点。 由于时钟不同步， validator可能收到时间戳大于本地时间的消息，Gasper要求validator不能把这样的消息放入本地视图中，直到消息的时间戳小于本地时间。 </p> <p>一个全局的景象是： 每个validator相信自己的时钟是对的，并按照Gasper要求的时钟节奏去运行。 但是，validators之间的时钟不同步，消息的传递有延迟，每个validator在一定程度上容忍收到的消息的时间戳与本地时间有差距。 Ethererum2.0 是否对时钟存在严重偏差的validator有惩罚呢？</p> <p>Gasper 使用Slots度量时间， 连续的C个slot为一个epoch, 在Eth2.0 beacon-chain, 1 slot=32s, 1 epoch = 64slots。 期望每个slot都有一个block, genesis block 的 slot = 0，epoch = 0。 Slot i 所属的epoch 定义为$$ep(i)=j=\lfloor i/C \rfloor$$。</p> <p>**Epoch boundary block and pairs:**<br /> 给定一个区块B, 我们有以下定义：<br /> 1. chain(B): B确定的一条链<br /> 2. EBB(B , j): chain(B) 在epoch j的epoch boundary block, 即slot编号不大于jC的编号最大的slot的block。<br /> 3. LEBB(B): chain(B) 中slot最大的epoch boundary block<br /> 4. ep(B): block所在epoch<br /> 5. (B, j): 即attestation epoch boundary pair , 虽然可能ep(B) != j, 但在一个attestation中，B可以作为epoch j的epoch boundary block。用于epoch的第一个slot缺少block的情况。<br /> 6. aep((B, j)) = j</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/jcNWOTIv632d39d777ac2.png" width = "60%" height = "60%" alt="图片名称" align=center /></p> <p>如图， ep(63)=0, 但是由于在chain(66)中，缺少slot=64的block, 所以block 63作为了chain(66)上epoch=1的bournday block, 记为(63, 1), aep((63,1)) = 1。 </p> <p>#### Committees<br /> 在每个epoch中， Gasper把validators尾随机分成C个committee，每个committee负责一个slot, 每个committee 内validator的数量尽量相等。每个committee中的第一个validator称为proposer。<br /> #### Blocks and Attestations<br /> 接下来，描述Validator V如何工作， V所在Committee负责slot i, 则i = jC + k, j是epoch编号，k为1~C-1的整数。 HLMD函数是Gasper对GHOST算法的实现。输入V本地slot=i的试图view(V, i), 返回叶子节点B'， 即B'=HLMD(view(V, i))。 </p> <p>在i slot的开始时刻， 如果V是proposer，计算出叶子节点B', 并构造且广播一个新的区块B, B包含：<br /> 1. slot(B) = i, 即slot编号<br /> 2. P(B) = B', 指向父节点B'的指针。<br /> 3. newattests(B)： 从B'到B这段时间内，V收到的attestations (即在slot i-1收到的attestations)<br /> 4. 执行层的数据</p> <p>在时间来到i+1/2 slot的时候， V计算出叶子节点B', 构建并广播一个attestation a, a包含：<br /> 1. slot(a) = jC + k, 当前slot号<br /> 2. GHOST vote: block(a) = B', 对本地叶子结点的投票<br /> 3. Casper vote, A checkpoint edge : LJ(a) -> LE(a)<br /> 3.1. LJ(a): view(block(a), i+1/2) 中的justified pair with highest attestation epoch。<br /> 3.2. LE(a): view(block(a), i+1/2) 中ep(slot(a)) 的 boundary pair, 即(LEBB(B'), ep(slot(a)))</p> <p>#### Justification & Finalization<br /> 跟“概括-Gasper"的描述相同，额外加几个定义：<br /> Attestation vote:<br /> $$(A, j) \xrightarrow{V} (B, j')$$<br /> Justified result:<br /> $$(A, j) \xrightarrow{J} (B, j')$$</p> <p>定义4.9 （Finalization） 对于视图G， 如果B0是Genesis block，或者存在整数k>=1 并且B1, ..., Bk 属于view(G), 并且满足以下条件，则称(B0, j)为finalized (or k-finalized)：<br /> 1. (B0, j), (B1, j+1), ..., (Bk, j+k) 是chain(Bk)的连续epoch boundary pairs<br /> 2. (Bo, j), (B1, j+1), ...., (Bk-1, j+k-1) 都被justified<br /> 3. $$(B0, j) \xrightarrow{J} (Bk, j+k)$$</p> <p>B是一个区块， 则在这条链上仅保留epoch boudary blocks, 形成的图为ffgview(B)。<br /> G是一个视图， 则仅保留Justified blocks, 形成的图为J(G)； 仅保留Finalized blocks, 形成的图为F(G)。<br /> (K+1)-finalized F(G) 是 k-finalized F(G)的子图。</p> <p>#### Hybrid LMD GHOST<br /> <img src="https://img.learnblockchain.cn/attachments/2022/09/FFtyezWt632d3a9f56b60.png" width = "60%" height = "60%" alt="图片名称" align=center /></p> <p>step1 (not line1): 获取所有叶子节点集合L。<br /> step2: 追溯所有叶子节点所在链上最大justified pair， 记为(BJ, j)。<br /> step3: 从L中删掉所有不以(Bj, j)作为justified pair的叶子节点，得到叶子节点集合L'。<br /> step4: L'中每一个节点确定一条链，把所有链放到一起，构成视图G'。<br /> setp5: 从Bj开始进行fork choice, 直到选出一个叶子节点。</p> <p>### Slashing Conditions<br /> 跟“概括-Casper”中的slashing conditions是一样，现在用形式得表达出来：</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/9CY4fUh9632d3ae3f1930.png" width = "60%" height = "60%" alt="图片名称" align=center /></p> <p>Gasper Honest Validator 应该如何工作已经在上文Gasper协议里描述过了，那么为什么honest validator不会违反这里的slashing Conditions呢？证明如下：</p> <p>在一个epoch中， 一个validator只会投票一次， 所以自然不会违反S1。 因此只需要证明Honest Validator 不违反S2。 用反证法，我们假设一个Honest Validator 违反了S2， 则存在4个epoch: r s t u, 满足r < s < t < u。 在epoch t, validator 作出attestation at, 其中 s -> t , s 为justified epoch。 在epoch u, validator 作出attestation au, 其中 r -> u, 根据HLMD算法，validator要先找到height最大的一个justified epoch, 根据au的定义， 它应该是r, 由于s的存在， r >= s, 这就跟S2中 r<s的条件矛盾了。综上，Gasper Honset Validator 不可能违反Slashing Conditions。</p> <p>### Rewards and Penalties<br /> 回报和惩罚机制，不通过Gasper实现，Gasper假设区块链的设计能做到：任何诚实的验证者看到违反slashing conditions的验证者都会惩罚不诚实的验证者。<br /> 在设计回报和惩罚机制时需要考虑：<br /> 1. 回报/惩罚的资产量如何确定？<br /> 2. 如何激励honest validator抓获dishonest validator？</p> <p># WHY<br /> 我们要证明的东西： 在真实的环境中, 有众多不利因素，例如存在dishonest validators(<1/3)， 网络有延迟，honest validators可能离线， 但是finalized block不可能存在冲突的block, 并且区块链能不断延展，不断产生新的finalized block。</p> <p>本章之后，我们将得到结论：虽然对于当前epoch boundary block的justification是概率性的，但是随着epoch数量的增多，区块链上产生finalized block的概率趋近于100%.</p> <p>我们把证明对象分成两部分：<br /> 1. Safety安全性。 如果一个block成为了finalized block, 则始终是finalized block, 并且没有冲突节点（等同于始终在权威链 canonical chain上）。 进一步的结论是， 任意honest validator的本地F(G)都是F(view(NW))的子图。 view(NW) 是指网络视图，NW是Network的意思，即汇总了全网数据的视图。<br /> 2. liveness活性：finalized block能不断延展。 论文中阐述了两种liveness: plausible liveness 和 probabilistic liveness。我理解为在没有不利因素的环境下的活性和在真实的有众多不利因素的环境下的活性。Plausible liveness 的证明比较直观，等同于把Gasper演绎一遍。下文只分析Probabilistic liveness的证明。 </p> <p>## Safety<br /> 为了证明Safety, 我们需要先阐述2个引理：</p> <p>**引理4.11.** 对于视图G， 任意epoch j, 只有一个pair (B, j) 属于J(G)。 否则将有1/3的Validator被惩罚，记为(1/3)-slashable。<br /> 证明：假设有两个block B1和B2， 并且(B1, j) 和 (B2, j) 都属于J(G)。支持(B1,j)的validator集合V1，V1 > 2N/3; 支持(B2, j)的validator集合V2, V2 > 2N/3。 V1 和 V2的交集V的大小至少为N/3。 V中validator都违反了S1， 所以都被惩罚。 </p> <p>**引理5.11** 对于视图G， (Bf, f) 属于F(G), (Bj, j)属于J(G), 则Bf一定是Bj的祖先。否则1/3的Validator被惩罚。<br /> 证明： 因为(Bf, f)属于F(G), 根据Finalization的定义，存在连续的Justified Pair (Bf+1, f+1) (Bf+2, f+2)...(Bf+k, f+k)。 因为(Bj, j)属于J(G), 则一定存在Justified Pair (Br, r) , (Br, r) -> (Bj, j)获得至少2N/3的投票。 使用反证法，假设Bj不是Bf的后代。如果r > f+k, 只需要证明Bf+k不是Br的祖先,，继续向前推演，我们只需要证明r<=f时，Bf不是Bj的祖先。 如果r=f, 违背了定理4.11。如果r<f，则 r < f < f+k < j， 两个attestation (Br, r) -> (Bj, j) 和 (Bf, f) -> (Bf+k, f+k) 分别获得了至少2N/3投票，则至少有1/3的validator对这个两edge都投了票, 这违背了S2。 </p> <p>**Safety定理** 对于视图G，则一定满足以下两个属性，否则1/3的validator被惩罚：<br /> 1. 对于F(G)中的任意pair (B, f), 不管G之后怎么变化, (B, f)始终属于F(G)<br /> 2. 对于F(G)中的任意pair (B, f), B始终属于权威链canonical chain</p> <p>证明： 根据Finalization的定义，属性1不需要证明。 现在证明属性2，根据HLMD算法，区块链总是在高度最大的justified block上延展，而F(G)是J(G)的子集，所以所有finalized block都在canonical chain上。</p> <p>## Probabilistic Liveness<br /> 我们最终要证明的是“Justified block被finalized的概率”， 为此分三步走：<br /> 1. 证明block获得多数票(>2N/3)的概率<br /> 2. 基于1证明，first Slot获得2N/3投票后，justified的概率<br /> 3. 基于2证明Justified block被Finalized的概率<br /> ### block获得2/3票的概率<br /> HLMD 算法可以保证honset validator作出一致的决策，但是叶子节点上不一定能否获得>2/3参与者的投票。这里要度量就是， 当网络中存在Dishonest Validator, 网络存在延迟的情况下，fork choice的结果获得不小于2/3参与者投票的概率。</p> <p>论文中没有数学证明这个概率，而是构造了一个模仿区块链fork choice过程的 Equivocation Game，通过模拟实验得出结论。</p> <p>**Equivocation Game:**<br /> 1. 给定(V, a, e1, e2): V是游戏参与者validator的集合, 数量为N，他们对选项O1和O2进行投票。V中的dishonest validators （or byzantine validators）记为b, 数量Nb < N/3。Honest validators记为h, 数量Nh。p = Nb/N<br /> 2. 游戏时间范围[0, 1] 。Validator 决定作投票的时间为t, 则其他节点收到这个投票的时间为 t + X + a + Y。 X为本地抖动的时间，范围[-e1, e1] ； a 为网络平均传输时长；Y为网络传输时间的抖动， 范围[-e2, e2]。 之所以有负向的抖动，是因为本地时钟与标准时钟可能存在偏差。<br /> 3. Honest validators (记为： h)的行为准则是： 在时间为0.5时，当本地O1 O2的票数不同时，给得票高的一票，如果O1 O2票数相同，则投O1。 最终，如果O1 O2中有任意一方的票数大于等于2N/3, 则honest validators获胜； 否则honest validators 失败。</p> <p>分别分析高网络延迟、低网络延迟、网络延迟中等的情况。 分析的方法是，站在攻击者b的角度，让投票数尽可能均匀，从而分析在最不利情况下的获胜概率。</p> <p>**情况一： 高网络延迟。 a远大于e1。**<br /> 由于a远大于e1, 所以honest validator在投票时不会收到其他honest validator的影响。 b可利用网络延迟高的特点，进行一种名为"smoke bumb attack"的攻击： b在t=0.5之前就发送投票，但是投票的时间戳是0.5, 想达到的效果是，honest validator在0.5秒收到了攻击者的投票，此时本地O1 O2 胜出的概率各50%， 从而迫使honest validators将投票数均分，为此b本身一定要把自己的票数均分。 现在看模拟实验的结果，并分析：</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/RTVwD7ZA632d3c0c9f859.png" width = "50%" height = "50%" alt="图片名称" align=center /></p> <p>第一组实验，可以用极限法分析它的结果，如果dishonest voting 发起的足够早，在honest validator开始投票时，每个honest validator收到了所有dishonest validators的投票，即本地O1 O2的票数相同，根据游戏规则，honest validator将把票投给O1， 最后获胜。 所以当dishonest voting time=0.2时，胜率接近100%；<br /> 第二、三组实验，dishonest voting time离0.5越来越近，当honest validator发起投票时，honest validator只能看到一部分dishonest voting, 相当于从dishonest voting中采样，而采样越少，O1:O2 就越偏离1:1, 而偏离方向的可能性是均等的，所以越有可能导致honest voting均分。 最终导致游戏失败。 所以dishonest voting time越靠近0.5，胜率越小。<br /> 第四组实验，honest voting 不受dishonest voting的影响，honest voting全部投O1, 最终获胜。</p> <p>**情况二： 无网络延迟**<br /> Validator voting可以被实时看到。 此时的效果等同于h和b轮流投票，我们假设一次投n>0张票，根据规则，h总是往同一个方向投票，b为了维持均衡，则往相反方向投相同的票数。由于b的票数少，当b投票耗尽时， 对b最好的结果是O1 O2的投票数均衡，b 和 h 分别投出Nb张票，O1 O2分别获得Nb张票。由于Nh > Nb, 之后h将把所有的票投给O1, 最终O1活着 Nb + (Nh-Nb)=Nh张票， Nh > 2N/3。 最终获胜。 即无网络延迟时，100%胜利。</p> <p>**情况三： 网络延迟中等**</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/iqsyf7GL632d3c5a5891f.png" width = "50%" height = "50%" alt="图片名称" align=center /></p> <p>实验过程跟一相同，但是改小了a和e1的差距，实验规律跟一相同。在t=0.5时，volidator之间投票有干扰，所以不再是100%,而是99%；</p> <p>Equivocation Game的结论是，在真实的网络延迟下, fork choice获得2N/3票的概率>=80%.<br /> ### first Slot block获得2/3票后，justified的概率<br /> 我们关注第j个epoch, 以slot为粒度的时间区间为[T, T+C], T=iC。 N为validator数量，每个Committee的validator数量为S = N/C。假设条件A(e)为：<br /> 1. 网络(1/2)-synchronous, 开始时间为T<br /> 2. 每个validator质押量和投票量均为1<br /> 3. Byzantine Validators(aka dishonest valisator)的数量为N/3-Ce, 等同于说每个Committee中，byzantine validators的数量为S-e<br /> 第i个committee中byzantine validators的数量记为bi, honest validators的数量记为hi, hi+bi = S。</p> <p>首先提出一个观点，它定义一些对hi的要求，并证明了所有要求满足时的概率下限。这个观点用于后续的证明。</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/5WyGcb5F632d3c9f8ca2a.png" width = "60%" height = "60%" alt="图片名称" align=center /></p> <p>观察结论，<br /> 1. 在S L固定时， e 越大， E1~EL成立的概率越大。即每committee里byzantine validators越少，越能满足这个proposition<br /> 2. E1~E2成立的概率很大。取C=64, S=900<br /> 1. 当e=30时，概率下限为85%<br /> 2. 当e=40时，概率下限为97%</p> <p>**定理7.4 (Justification 活性定理)**<br /> 在A(e)描述的条件下， 假设block获取2N/3多数票的概率是r。 Bj是J(view(NW, T))的最后一个justified block。 那么，在view(NW, T+C)中将justify Bj后代节点的概率是：</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/lEOGnFpX632d3cd84b286.png" width = "30%" height = "30%" alt="图片名称" align=center /></p> <p>从这个表达式可以清楚的看到在view(NW, T+C)中justify Bj后代的条件是：<br /> 1. 等待justify的block Bw获得了2S/3多数票，概率为r。 r的大小已在Equivocation Game分析。<br /> 2. Epoch 内满足proposition7.2, 对应表达式的中间项<br /> 3. 在aep(Bj), 至少还有一个Bj的子节点，因为如果没有子节点了，那么Bj就不是justified block, 在epoch j中要justify的就是Bj了。 对应表达式第三项。</p> <p>证明： 我们基于三个条件，设法得到概率公式，并证明Bw是Bj的后代。首先如果要破坏条件3，则aep(Bj)中后C-1个slot的proposer都是byzantine validator, byzantine validator的占比最大为1/3, 所以破坏条件3的概率是 $$ \frac{1}{3^{C-1}}$$。Bw 以概率r, 获得2N/3多数票，以满足条件1， 注意ep(Bw) 不一定等于j。 现在需要证明当满足proposition7.2时，slot(T+1) 到 slot(T+C-1)的所有honest validator都会把票投给Bw。<br /> 1. E1: 由于Slot(T)已经投了大于2S/3的票给Bw, 所以支持和反对的票数差大于S/3。E1中， h1 > 2S/3, 那么，及时E1这段时间内，所有byzantine validator提前投票，也不能把支持票的优势填平。所以E1所有honest validator的票一定投给了Bw。支持和反对票的差值是(1/3 + 1/3) S = 2S/3。 这里给Bw投票包含两个意思：<br /> 1.1. GHOST Vote: 投给当前子节点，向上传递给Bw<br /> 1.2. Casper Vate: (Bj, aep(Bj)) -> (Bw, j)<br /> 2. 同样的分析方法应用在E2 ~ EL, 可见，E2～EL所有dishonest validator都把票投给了Bw, 从而Bw收获的总票数为：</p> <p> <img src="https://img.learnblockchain.cn/attachments/2022/09/Zz3gFEpq632d3d9025db3.png" width = "40%" height = "40%" alt="图片名称" align=center /></p> <p>也就是说如果保证了Bw获得2/3多数票，并且满足proposition7.2, 则在proposition7.2划分的每个时间段内， byzantine validator总是不能把Bw的优势票抹平，honest validator 投票后又提高了Bw的优势，从而所有honest validator都把票投给了Bw。 </p> <p>### Finalization的概率<br /> **定理7.5 (Finalization 概率活性)** 假设每个epoch中，justified block的概率是p >= 1/2, 在接下来的n个epoch中没有finalized block(1-finalized)的概率随n的增大，以指数速度趋近于0。</p> <p>不同于论文中的方法，现在给一个简单的证明， 即找到概率上限。<br /> 通过Probabilistic Liveness的前两项证明，p>=1/2已经成立。 由于每个epoch中，有justified比没有justified block的概率更大，因此在n个连续epoch：<br /> 1. 为了没有finalized block, 不应该出现连续的justified epoch<br /> 2. 为了让最后的概率值足够大，每个epoch要尽可能包含justified block</p> <p>则当justified epoch和非justified epoch交替出现时， 概率最大，即:<br /> $$(1-p)^{n/2}p^{n/2} = ((1-p)*p)^{n/2}$$<br /> 这个概率上限是随n趋近于0的。<br /> # PRACTICE<br /> 这一章列举Ethereum2.0 beacon chain实现上跟理论Gasper不同的地方。<br /> ## Attestation Inclusion Delay<br /> Slot i Proposer validator 发送proposed block B时，它会把本地收到的attestations一并广播。 在Gasper 中，这些attestations就是来自slot i-1的。 但是beacon chain proposer发送的是最近n个slot的attestations。<br /> 这样做的目的是提高去中心化程度。 我们假设网络中的节点普遍网络速度低，且网络延迟高于1/2 slot，少数节点网速高(延迟小于1/2 slot)。 如果proposer只广播 slot i-1的attestations, 则区块链的走势将受少数节点控制，attestations奖励也只会给少数节点。所以通过引入attestations inclusion delay, 可以让普遍的节点收到奖励，并参与到节点建设。<br /> n是一个需要权衡的值，n小则效率高去中心化低； n大则效率低去中心化高。<br /> ## Attestation Consideration Delay<br /> beacon chain validator 所属的slot为i, 在i+1/2时刻，通过HLMD算法进行fork choice时，仅使用slot不大于i-1的attestations。目的就是彻底消除Equivocation Game中的smoke bumb attack。重新简述这个attack过程： 攻击者（dishonest validator）在i+1/2之前发送slot i的attestations, 将其投票均分给forked block, 从而误导honest validator， 发起攻击的时间离使用这些attestations的距离越远，攻击效果越低。在beacon chain中， slot i会忽略这些攻击attestations，而到了slot i+1, 根据Equivocation Game的分析，攻击已经失效了。<br /> ## Finalization Rules<br /> Beacon chain 在finalization的时候，只考虑最后的4个连续epoch。 采用1-finalized和2-finalized, 也就是说，接受两种程度的finalization， 尽量做到2-finalized。<br /> 四种finalization的情况：<br /> <img src="https://img.learnblockchain.cn/attachments/2022/09/POfCj19e632d3e3fc6f0c.png" width = "60%" height = "60%" alt="图片名称" align=center /></p> <p>## Safety - Dynamic Validator Sets<br /> 这里要说明的道理很简单且直观，不需要论文中的公式。我们在证明“Safety”的时候说，假设在F(G)中存在两个冲突的（即非同一条链）finalized epoch boundary pair, 则一定有至少1/3的validators被处罚。但是，前提是Validators的集合是不变的。 在beacon chain中，参与者是不需要审核的，所以Validators集合是动态变化的，那么冲突的两个epoch， 他们的validator不一定相同，所以可能出现dishonest validator作恶后，从validators中退出，从而逃脱惩罚。 validators集合的差异性，由两个因素决定： 动态调整validators set的策略以及时间。 因此beacon chain采取的措施是：<br /> 1. 权衡 validators sets的灵活性和惩罚作恶节点的能力， 给出合理的validators set变更策略<br /> 2. Validators 拒绝2个epoch之前的attestatisons，防止产生时间跨度大的冲突

本文参与区块链技术网 ，好文好收益，欢迎正在阅读的你也加入。