详解Casper FFG共识算法

Casper FFG 是 Vitalik提出来的一个PoW/PoS混合的算法，目的是为了让Ethereum平滑过渡到纯PoS。论文在这里，Casper the Friendly Finality Gadget，本文主要讲解这篇论文的核心知识点。
本文配套视频：https://v.qq.com/x/page/f07704nx4iq.html ，因为视频超过了15分钟，无法直接嵌入文章中。
###Casper FFG算法流程
目前是2018年，Ethereum依旧是一个纯PoW算法的区块链，跟比特币一样。PoW是一个非常简洁的算法，也非常安全，例如这篇论文 Analysis of the Blockchain Protocol in Asynchronous Networks，证明了比特币其实是非常安全的。尽管如此，如果某个矿工拥有了超过51%的算理，理论上依旧是有可能重新改写以前的区块的。

PoW流程
上图中黄色的矿工突然算理大增，开始干坏事，从一个旧的区块出发，分叉出了一条新链，不断在上面挖矿，如果它的长度超过了左边，那么新的链条就能成功取代旧的链条，以前的旧区块被撤销，里面的交易也全部会被覆盖和改写。
Casper FFG在当前PoW的基础上，添加了一层PoS投票过程，进一步增强了Finality, 旧的区块理论上不可能被撤销。Casper FFG是一个没有侵入性的算法，它没有改变当前Ethereum的PoW算法，只是在这一层PoW上添加了BFT风格的PoS，也就是说所有的块，还是PoW矿工挖出来的，这条核心流程保留了下来。在这基础上，每挖出100个块，PoS的验证节点们会对最后一个块进行投票，2/3通过后，这最后一个块称为checkpoint(检查点)。凡是被finalized的检查点，不可撤销。总结一句话，就是保留了PoW出块的机制，同时每隔100个块来一次PoS投票，进一步增强了Ethereum的安全性(Safety，即Finality).
投票消息的字段如下：

如上表所示，每一个投票消息，包含5个字段，s表示源头检查点的区块哈希，t表示目标检查点的区块哈希，h(s)表示s的区块高度，h(t)表示t的区块高度，S表示签名，这5个字段，真正核心的只有3个，即 h(s), t, h(t)。
Casper FFG的这种投票消息，很巧妙地把二步融合到一个步骤里了，本质上它还是跟pBFT, Tendermint里的二阶段投票等价，pre-prepare->prepare, pre-vote -> pre-commit。
下图里解释了投票为什么需要两个阶段。

同时，Casper FFG的这种投票消息，跟Tendermint里的锁机制，有类似作用。
下面是Casper FFG算法里经常看见的几个术语的定义：

一条supermajority link，写成 a→b，指的是，如果有超过2/3的投票消息，都是从 a检查点出发，指向b检查点，那么a到b之间就有一条supermajority link。一条supermajority link，可以跨越若干个检查点，也就是说h(b)>h(a)+1是合法的。

两个检查点a和b互相冲突，指的是a和b在不同的分支上，也就是说a和b之间不在一条路径上。

一个检查点c要变成一个justified检查点，需要满足下列条件之一，(1)它是创世区块;(2)或者存在一条supermajority link指向它。

一个检查点c要变成一个finalized检查点，需要它是 justified 且存在一条以它为源头的supermajority link, c→c’，且c’是它的直接孩子(direct child)，即c’的高度是c的高度增1。

举个例子，如下图所示，

上图中绿色的检查点，在投票之前是一个justified状态，当有超过2/3投票，以这个justfied区块为源头，指向另一个更高的区块，那么原先的justified区块，就变成了finalized的了，再也不可撤销了，新的区块，就变成了justified状态。在finalized和justfied区块之间，形成了一条supermajority link。
###惩罚条件(Slash Condition)
Validator 如果违反了下面两个条件中的任何一条，就会被惩罚，没收所有押金。

No double vote: t1==t2。在同一个高度，不能投票给两个不同的块。这个比较容易理解，同一个高度，给两个不同的块都投一票，属于Nothing at stake的典型投机行为，这是要被惩罚的。

No surround vote. t2 t1, 过了几个块后，继续投票，s2 -> t2, 由于区块高度是随着时间不断递增的，很显然 s2 > e1, 而第二个投票里如果 t2 t1 这一票，说明你已经认可s1到t1之间的所有块是正确的，但是第二票 s2->t2，区间比 s1->t1还小，被s1->t1完全覆盖，这一票把 s2到t2之间的块又重复同意了一遍，仿佛你遗忘了之前的投票。这种遗忘行为也是会被惩罚的。

下图展示了一个违反了 No double vote 的例子，

PoW挖矿的时候，在同一个高度发生分叉是很正常的事情。这时候在4个validator节点中，有2个恶意节点，同时给两个分叉都投了票，这样导致两个新块都会变成justified状态，这是不对的，这时候只要有一个validator举报这种情况，那么这两个恶意节点就会被惩罚，销毁押金，同时举报的人会获得一笔奖励(finder’s fee)。
下图展示一个违反了No surround vote的例子，

某个时刻，同时有两条supermajority link, A->B, 和 A->C，于是A变成了finalized, B和C同时都是justified区块。这种情况，说明有超过1/3的验证节点，同时给B和C投了票，这是合法的，没有违反no double vote规则，也没有违反no surround vote规则。
接下来，某个validator节点可以开始投票了，由于有两个justified检查点，所以它可以选择任意一个作为源点，假设它一票是B->E，另一票是C->D，这是不合法的，违反了no surround vote规则。
###证明 Safety 和 Plausible Liveness
这一节我们来证明 Casper FFG的 Safety(即Finality)和 Liveness。
首先 Casper FFG号称是 accountable safety 和 plausible liveness. Accountable 的意思是validator节点们需要交数量可观的押金，有了押金，就有了初步的信任，可以指望的(accountable)了。
Plausible liveness实际上没有新意，跟比特币的liveness一模一样，是指网络发生分裂(partition)的时候，整个系统依旧可以写入新交易，依旧可以出块。
下面开始详细证明。
Accountable Safety: 两个互相冲突的检查点(checkpoint), am和bn不可能被终局化(finalized)
证明：用反证法，假设am和bn互相冲突（即在两个分支上，不存在同一条分支上）且终局化finalized了，且它们各自的有一个已经justified的子区块am+1和bn+1。
如果它们的高度m和n相等，则必然有1/3的验证节点同时给两个checkpoint都投了票，这些节点违反了 No double vote 的这条规则，会被销毁所有押金，失去了1/3的验证节点，am和bn不可能被finalized。
如果高度m和n不相等，令n > m(n
如果im，则有1/3的验证节点违反了no double vote规则，会被惩罚，从而使得am和bn不可能会被finalized；
如果jm+1，同上；
如果im+1，则说明有一条supermajority link bi→bj, ，完整包围了am->am+1，这违反了 no surround vote规则，会有1/3的节点会被惩罚，使得am和bn不可能会被finalized。有人会问bi,bj有可能没有finalized,即便如此，起码genesis→bn包围了am->am+1，还是违反了no surround rule。
综上所述，任何情况下am和bn都不可能会被finalized，证明完毕。
###Plausible Liveness: 只要有超过2/3的validator节点遵守使用 justified的区块作为起点进行投票，那么就总是可以产生新的finalized的新块。
简单的说，就是以一个 justified 了的块作为起点，可以投任何一个比它高的节点，比如有两个新快，一个am在高度m, 一个bn在高度n（包括起点，三个块肯定在一条线上），这时可以投票给两个中的任何一个，甚至两个都投，都不会违反 no double vote 和 no surround vote规则。也就是说可以越过多个块，直接投更高的块。下一个被justified的块，可能是am也可能是bn，也有可能同时都是（两个都获得超过2/3个投票，此时必然有超过1/3的节点两个都投了）这就是为什么称为plausible的原因吧。
即使网络分裂，PoW能够在两边继续出块，但是这时候Validators节点再也无法在任何一个checkpoint上达成2/3投票了，因为一边一半，不通通信了，即使这样，链条可以在不能finalize的情况下继续增长。在网络切分为两半的时候，依旧可以运转(Tendermint碰到网络分裂，只能无限等待了)，这种健壮的liveness，也许plausible的另一层含义。
从Plausible liveness可以推导出Casper FFG的分叉选择规则(Fork Choice Rule)：总是选择基于最高的justified区块的最长链条(always choose the longest chain on top of the justified checkpoint with highest height.)。也就是先找到最高的justified区块，然后从该区块出发，选择最长的链条。比PoW算法单纯的选择最长的链，多了一个先决条件。
举个例子，如下图：

上图中，从最高的一个finalized，有两条supermajority link，指向了两个justified检查点，这时候，网络在某一时刻发生了分裂，例如海底光缆断了，将全球网络一分为二。这时候两边的PoW会继续正常出块，只是每一个checkpoint投票的时候，都最多只能收到一半的票，因为validator节点一边只有一半，即使100%同意一个新检查点，也无法超过2/3。因此，在网络发生分裂后，PoW会继续不断增长链条，只是所有的新块都无法被finalized和justified。
接着，过了一段时间后，网络终于恢复了，这时候该选择哪条分叉呢？上边的还是下面？按照PoW的fork choice rule, 应该选择最长的，就是上面那条。不过再Casper FFG里，规则略有变化，要先选择 justified 区块最高的那个，如果两边的justified区块一样高，再选择最长的。根据这个规则，上面的分叉虽然最长，但是下面的分叉里，最新的justified区块高度最高，所以应该优先选择下面这条分叉。
###动态的验证节点集合
论文里为了简化，假设validator节点是一个固定的集合，实际上Casper FFG有一个动态更新validator集合的机制，论文中没有细讲，这里也不详细展开了。因为这个知识点对理解Casper FFG的核心算法关系不大，不必深究。
###无利益攻击(Nothing At Stack Attack)
纯PoS出块以及投票，都是不需要算力的，是没有成本的（PoW中如果在短链上挖矿，挖到了也得不到奖励，算力浪费了，是有成本的），所以当区块链发生分叉的时候，validator节点们不知道哪个分支是对的，为了获得奖励，最佳策略就是每一条分支都投一票。为了惩罚这种行为，PoS一般要求验证节点们投票前需要交押金，一旦发现有人在每条分支上都投机，则没收它的押金。
Casper FFG算法中，出块是PoW负责的，这个部分不存在无利益攻击。但是投票阶段，是不需要成本的，为了防止无利益攻击，做法也是类似的，validator节点们在投票前需要交押金，投票中一旦发现违反了No double vote规则，销毁该恶意节点的所有押金，因此可以有效阻止攻击。
###长程攻击(Long Range Attack)
长程攻击指的是下面3种情况：

纯PoS情况下，由于纯PoS出块是没有成本的，可以很容造一条比真链更长的分叉链。

PoW情况下，假设恶意节点拥有超过51%算力，也可以造一条比真链更长的分叉链。这种情况比较少见，因为PoW出块是有成本的，有这么大算力，还不如老老实实挖矿，获得的奖励更多。不过，如果恶意节点很久以前有一笔金额巨大的交易，利益驱动下，恶意节点也有动力重新分叉，双花这笔钱，这种情况下恶意节点也会发动长程攻击。

第三种情况，适用于PoS和PoW，如果一个新的全节点刚刚上线，不凑巧连接上了几个恶意节点开始同步区块，恶意节点给它发来伪造好的很长的链，比真链还长，这时候，即使后来连上了诚实的全节点，全节点发来的链条短一些，会被这个新节点拒绝。这就很尴尬了。
针对第1种和第3种情况，本质上问题是一样的，当收到一条更长的链，如何判断它是真是假？Vitalik在这篇文章Proof of Stake: How I Learned to Love Weak Subjectivity 阐述了解决方案，还是需要从外界引入一点点知识，一点点信任，所谓的 weak subjectivity，V神认为这种弱信任是很容易达到的，因而并没有削弱区块链的Safety。当一个新节点刚上线是，它需要从外界获得以下知识并信任这些知识：

The protocol definition. 这个好办，区块链的协议就存在于代码之中。一个新节点运行了哪个版本的代码，就代表它默认信任这个代码。
最新的一个有效区块。这个区块不能太老，必须是最近N个之内。N可以事先定义，只要确保足够新鲜即可，比如对于比特币来说，最近6个之内的任意一个区块，都算是足够新了，对于Ethereum来说，最近12个区块，算是比较新了。
对于2，问题很大，一个新的全节点上线，从哪里去获取这个最新的一个有效区块呢？这里需要引入额外的信任知识。举个例子，对于Casper FFG来说，一个新节点上线，应该只信任交了押金的全节点，并且最好是连接多个节点，获取最新的已经被finalized的区块。当得到了最新的finalized的区块，就可以放心开始同步了，即使收到了恶意节点的更长的链条，由于在同一高度，恶意节点的那个块的哈希值必然不同，从而可以判断必然是一条假的链条，把这条链丢弃掉。
总结起来，对付长程攻击，需要依赖外界的一点点知识，即可防止这种攻击。
论文第7页底部有一段非正式的证明，我觉得有意义的一点是证明了退款延期时间需要大于网络延迟时间的4倍，ω>4δ。
大规模崩溃的情况（Castastrophic Crashes）
如果有超过1/3的验证节点同时崩溃，或者网络出现问题导致他们掉线，又或者网络发生分裂，这时候投票的时候，不可能凑齐超过2/3的投票，也就是说从此刻开始，无法创建新的supermajority link, 即无法finalize任何新块。
论文介绍了一种称为 Inactivity leak 的技巧，来让两个子网各自独立工作，能够继续独立投票，finalize新块。
为了让投票能重新超过2/3，可以让不活跃的validator节点的押金逐步“泄露”（要么burn销毁要么返回给节点），比如每次投票，如果某个validator没有投票，就认为它掉线了，将它的押金减少20%，这样连续5次都不活跃，押金减少到0。这种机制相当于不断地降低掉线节点的权重，增加在线节点的权重，使得在线节点超过2/3时，就能够继续产生新的checkpoint了。
总结
Casper FFG算法由3个部分组成：2个惩罚条件(slash condition)，一个分叉选择规则(fork choice rule)和动态的验证节点集合。Casper FFG适用于任何PoW算法，提高PoW算法的安全性。
Casper FFG的出块机制是PoW(PoW based block proposal mechanism)，未来会把出块机制换成PoS的方式，这样就是纯PoS了。

关于网络通信复杂度，在PoW阶段，是O(n)，在BFT投票阶段，是O(n2)。一般验证节点由于有资金门槛，数量相比全网节点来说很小，所以即使是O(n2)，由于n很小，通信量还是比较小的。
关于最大容错，在PoW阶段，能够容忍恶意节点算力小于50%，在BFT投票阶段，需要恶意节点的资金数量小于1/3，简单粗暴的总结，可以认为最大容错是 1/3。
关于网络假设，在PoW阶段是同步的，在BFT投票阶段，是存异步的，总的来说，网络假设是同步的。
关于Finality, 在PoW阶段是 Probabilistic的，在BFT投票后，变成了Deterministic，总的来说是Deterministic的。
关于Liveness，Casper FFG在网络分裂的情况下，依旧可以正常出块，写入新的交易，它的Liveness跟PoW是一样的。
参考资料
Casper the Friendly Finality Gadget
Ethereum PoS: Casper FFG In Depth - YouTube
Ethereum PoS Overview: Casper FFG
Casper FFG with one message type, and simpler fork choice rule
Ethereum Casper 101
A Simplified Look at Ethereum’s Casper
Consensus Compare: Casper vs. Tendermint - Medium
Proof of Stake: How I Learned to Love Weak Subjectivity

浏览过的版块