Casper FFG 是 Vitalik提出來的一個PoW/PoS混合的算法，目的是為了讓Ethereum平滑過渡到純PoS。論文在這里，Casper the Friendly Finality Gadget，本文主要講解這篇論文的核心知識點。

Casper FFG算法流程

目前是2018年，Ethereum依舊是一個純PoW算法的區塊鏈，跟比特幣一樣。PoW是一個非常簡潔的算法，也非常安全，例如這篇論文 Analysis of the Blockchain Protocol in Asynchronous Networks，證明了比特幣其實是非常安全的。盡管如此，如果某個礦工擁有了超過51%的算理，理論上依舊是有可能重新改寫以前的區塊的。

上圖中黃色的礦工突然算理大增，開始干壞事，從一個舊的區塊出發，分叉出了一條新鏈，不斷在上面挖礦，如果它的長度超過了左邊，那么新的鏈條就能成功取代舊的鏈條，以前的舊區塊被撤銷，里面的交易也全部會被覆蓋和改寫。

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 如果違反了下面兩個條件中的任何一條，就會被懲罰，沒收所有押金。

1. No double vote： t1==t2。在同一個高度，不能投票給兩個不同的塊。這個比較容易理解，同一個高度，給兩個不同的塊都投一票，屬于Nothing at stake的典型投機行為，這是要被懲罰的。

2. No surround vote. t2 《 t1 《 s1 《 s2 。例如，一個validator首先投了一票， s1 -》 t1， 過了幾個塊后，繼續投票，s2 -》 t2， 由于區塊高度是隨著時間不斷遞增的，很顯然 s2 》 e1， 而第二個投票里如果 t2 《 t1， 比前一個投票的目標區塊還低，這是有問題的，因為 前面你投了s1 -》 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 《 m的情況證明過程一樣），從創世區塊到bn的路徑為genesis→b1→b2→…→bi→bj→…→bn，bi是第一個高度小于或等于am的區塊，即i≤m， bj是是第一個高度大于或等于am+1的區塊，即j≥m+1，下面分情況證明：

· 如果i==m，則有1/3的驗證節點違反了no double vote規則，會被懲罰，從而使得am和bn不可能會被finalized；

· 如果j==m+1，同上；

· 如果i《m，j》m+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。當一個新節點剛上線是，它需要從外界獲得以下知識并信任這些知識：

1. The protocol definition. 這個好辦，區塊鏈的協議就存在于代碼之中。一個新節點運行了哪個版本的代碼，就代表它默認信任這個代碼。

2. 最新的一個有效區塊。這個區塊不能太老，必須是最近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了。