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

Casper FFG算法流程

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

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

Casper FFG在當前PoW的基礎上，添加了一層PoS投票過程，進一步增強了Finality， 舊的區(qū)塊理論上不可能被撤銷。Casper FFG是一個沒有侵入性的算法，它沒有改變當前Ethereum的PoW算法，只是在這一層PoW上添加了BFT風格的PoS，也就是說所有的塊，還是PoW礦工挖出來的，這條核心流程保留了下來。在這基礎上，每挖出100個塊，PoS的驗證節(jié)點們會對最后一個塊進行投票，2/3通過后，這最后一個塊稱為checkpoint（檢查點）。凡是被finalized的檢查點，不可撤銷。總結(jié)一句話，就是保留了PoW出塊的機制，同時每隔100個塊來一次PoS投票，進一步增強了Ethereum的安全性（Safety，即Finality）。

投票消息的字段如下：

如上表所示，每一個投票消息，包含5個字段，s表示源頭檢查點的區(qū)塊哈希，t表示目標檢查點的區(qū)塊哈希，h（s）表示s的區(qū)塊高度，h（t）表示t的區(qū)塊高度，S表示簽名，這5個字段，真正核心的只有3個，即 h（s）， t， h（t）。

Casper FFG的這種投票消息，很巧妙地把二步融合到一個步驟里了，本質(zhì)上它還是跟pBFT， Tendermint里的二階段投票等價，pre-prepare-》prepare， pre-vote -》 pre-commit。

下圖里解釋了投票為什么需要兩個階段。

同時，Casper FFG的這種投票消息，跟Tendermint里的鎖機制，有類似作用。

下面是Casper FFG算法里經(jīng)常看見的幾個術語的定義：

· 一條supermajority link，寫成 a→b，指的是，如果有超過2/3的投票消息，都是從 a檢查點出發(fā)，指向b檢查點，那么a到b之間就有一條supermajority link。一條supermajority link，可以跨越若干個檢查點，也就是說h（b）》h（a）+1是合法的。

· 兩個檢查點a和b互相沖突，指的是a和b在不同的分支上，也就是說a和b之間不在一條路徑上。

· 一個檢查點c要變成一個justified檢查點，需要滿足下列條件之一，（1）它是創(chuàng)世區(qū)塊;（2）或者存在一條supermajority link指向它。

· 一個檢查點c要變成一個finalized檢查點，需要它是 jusTIfied 且存在一條以它為源頭的supermajority link， c→c’，且c’是它的直接孩子（direct child），即c’的高度是c的高度增1。

舉個例子，如下圖所示，

上圖中綠色的檢查點，在投票之前是一個jusTIfied狀態(tài)，當有超過2/3投票，以這個justfied區(qū)塊為源頭，指向另一個更高的區(qū)塊，那么原先的jusTIfied區(qū)塊，就變成了finalized的了，再也不可撤銷了，新的區(qū)塊，就變成了jusTIfied狀態(tài)。在finalized和justfied區(qū)塊之間，形成了一條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， 過了幾個塊后，繼續(xù)投票，s2 -》 t2， 由于區(qū)塊高度是隨著時間不斷遞增的，很顯然 s2 》 e1， 而第二個投票里如果 t2 《 t1， 比前一個投票的目標區(qū)塊還低，這是有問題的，因為 前面你投了s1 -》 t1 這一票，說明你已經(jīng)認可s1到t1之間的所有塊是正確的，但是第二票 s2-》t2，區(qū)間比 s1-》t1還小，被s1-》t1完全覆蓋，這一票把 s2到t2之間的塊又重復同意了一遍，仿佛你遺忘了之前的投票。這種遺忘行為也是會被懲罰的。

下圖展示了一個違反了 No double vote 的例子，

PoW挖礦的時候，在同一個高度發(fā)生分叉是很正常的事情。這時候在4個validator節(jié)點中，有2個惡意節(jié)點，同時給兩個分叉都投了票，這樣導致兩個新塊都會變成justified狀態(tài)，這是不對的，這時候只要有一個validator舉報這種情況，那么這兩個惡意節(jié)點就會被懲罰，銷毀押金，同時舉報的人會獲得一筆獎勵（finder’s fee）。

下圖展示一個違反了No surround vote的例子，

某個時刻，同時有兩條supermajority link， A-》B， 和 A-》C，于是A變成了finalized， B和C同時都是justified區(qū)塊。這種情況，說明有超過1/3的驗證節(jié)點，同時給B和C投了票，這是合法的，沒有違反no double vote規(guī)則，也沒有違反no surround vote規(guī)則。

接下來，某個validator節(jié)點可以開始投票了，由于有兩個justified檢查點，所以它可以選擇任意一個作為源點，假設它一票是B-》E，另一票是C-》D，這是不合法的，違反了no surround vote規(guī)則。

證明 Safety 和 Plausible Liveness

這一節(jié)我們來證明 Casper FFG的 Safety（即Finality）和 Liveness。

首先 Casper FFG號稱是 accountable safety 和 plausible liveness. Accountable 的意思是validator節(jié)點們需要交數(shù)量可觀的押金，有了押金，就有了初步的信任，可以指望的（accountable）了。

Plausible liveness實際上沒有新意，跟比特幣的liveness一模一樣，是指網(wǎng)絡發(fā)生分裂（partition）的時候，整個系統(tǒng)依舊可以寫入新交易，依舊可以出塊。

下面開始詳細證明。

Accountable Safety： 兩個互相沖突的檢查點（checkpoint）， am和bn不可能被終局化（finalized）

證明：用反證法，假設am和bn互相沖突（即在兩個分支上，不存在同一條分支上）且終局化finalized了，且它們各自的有一個已經(jīng)justified的子區(qū)塊am+1和bn+1。

如果它們的高度m和n相等，則必然有1/3的驗證節(jié)點同時給兩個checkpoint都投了票，這些節(jié)點違反了 No double vote 的這條規(guī)則，會被銷毀所有押金，失去了1/3的驗證節(jié)點，am和bn不可能被finalized。

如果高度m和n不相等，令n 》 m（n 《 m的情況證明過程一樣），從創(chuàng)世區(qū)塊到bn的路徑為genesis→b1→b2→…→bi→bj→…→bn，bi是第一個高度小于或等于am的區(qū)塊，即i≤m， bj是是第一個高度大于或等于am+1的區(qū)塊，即j≥m+1，下面分情況證明：

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

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

· 如果i《m，j》m+1，則說明有一條supermajority link bi→bj， ，完整包圍了am-》am+1，這違反了 no surround vote規(guī)則，會有1/3的節(jié)點會被懲罰，使得am和bn不可能會被finalized。有人會問bi，bj有可能沒有finalized，即便如此，起碼genesis→bn包圍了am-》am+1，還是違反了no surround rule。

綜上所述，任何情況下am和bn都不可能會被finalized，證明完畢。

Plausible Liveness： 只要有超過2/3的validator節(jié)點遵守使用 justified的區(qū)塊作為起點進行投票，那么就總是可以產(chǎn)生新的finalized的新塊。

簡單的說，就是以一個 justified 了的塊作為起點，可以投任何一個比它高的節(jié)點，比如有兩個新快，一個am在高度m， 一個bn在高度n（包括起點，三個塊肯定在一條線上），這時可以投票給兩個中的任何一個，甚至兩個都投，都不會違反 no double vote 和 no surround vote規(guī)則。也就是說可以越過多個塊，直接投更高的塊。下一個被justified的塊，可能是am也可能是bn，也有可能同時都是（兩個都獲得超過2/3個投票，此時必然有超過1/3的節(jié)點兩個都投了）這就是為什么稱為plausible的原因吧。

即使網(wǎng)絡分裂，PoW能夠在兩邊繼續(xù)出塊，但是這時候Validators節(jié)點再也無法在任何一個checkpoint上達成2/3投票了，因為一邊一半，不通通信了，即使這樣，鏈條可以在不能finalize的情況下繼續(xù)增長。在網(wǎng)絡切分為兩半的時候，依舊可以運轉(zhuǎn)（Tendermint碰到網(wǎng)絡分裂，只能無限等待了），這種健壯的liveness，也許plausible的另一層含義。

從Plausible liveness可以推導出Casper FFG的分叉選擇規(guī)則（Fork Choice Rule）：總是選擇基于最高的justified區(qū)塊的最長鏈條（always choose the longest chain on top of the justified checkpoint with highest height.）。也就是先找到最高的justified區(qū)塊，然后從該區(qū)塊出發(fā)，選擇最長的鏈條。比PoW算法單純的選擇最長的鏈，多了一個先決條件。

舉個例子，如下圖：

上圖中，從最高的一個finalized，有兩條supermajority link，指向了兩個justified檢查點，這時候，網(wǎng)絡在某一時刻發(fā)生了分裂，例如海底光纜斷了，將全球網(wǎng)絡一分為二。這時候兩邊的PoW會繼續(xù)正常出塊，只是每一個checkpoint投票的時候，都最多只能收到一半的票，因為validator節(jié)點一邊只有一半，即使100%同意一個新檢查點，也無法超過2/3。因此，在網(wǎng)絡發(fā)生分裂后，PoW會繼續(xù)不斷增長鏈條，只是所有的新塊都無法被finalized和justified。

接著，過了一段時間后，網(wǎng)絡終于恢復了，這時候該選擇哪條分叉呢？上邊的還是下面？按照PoW的fork choice rule， 應該選擇最長的，就是上面那條。不過再Casper FFG里，規(guī)則略有變化，要先選擇 justified 區(qū)塊最高的那個，如果兩邊的justified區(qū)塊一樣高，再選擇最長的。根據(jù)這個規(guī)則，上面的分叉雖然最長，但是下面的分叉里，最新的justified區(qū)塊高度最高，所以應該優(yōu)先選擇下面這條分叉。

動態(tài)的驗證節(jié)點集合

論文里為了簡化，假設validator節(jié)點是一個固定的集合，實際上Casper FFG有一個動態(tài)更新validator集合的機制，論文中沒有細講，這里也不詳細展開了。因為這個知識點對理解Casper FFG的核心算法關系不大，不必深究。

無利益攻擊（Nothing At Stack Attack）

純PoS出塊以及投票，都是不需要算力的，是沒有成本的（PoW中如果在短鏈上挖礦，挖到了也得不到獎勵，算力浪費了，是有成本的），所以當區(qū)塊鏈發(fā)生分叉的時候，validator節(jié)點們不知道哪個分支是對的，為了獲得獎勵，最佳策略就是每一條分支都投一票。為了懲罰這種行為，PoS一般要求驗證節(jié)點們投票前需要交押金，一旦發(fā)現(xiàn)有人在每條分支上都投機，則沒收它的押金。

Casper FFG算法中，出塊是PoW負責的，這個部分不存在無利益攻擊。但是投票階段，是不需要成本的，為了防止無利益攻擊，做法也是類似的，validator節(jié)點們在投票前需要交押金，投票中一旦發(fā)現(xiàn)違反了No double vote規(guī)則，銷毀該惡意節(jié)點的所有押金，因此可以有效阻止攻擊。

長程攻擊（Long Range Attack）

長程攻擊指的是下面3種情況：

· 純PoS情況下，由于純PoS出塊是沒有成本的，可以很容造一條比真鏈更長的分叉鏈。

· PoW情況下，假設惡意節(jié)點擁有超過51%算力，也可以造一條比真鏈更長的分叉鏈。這種情況比較少見，因為PoW出塊是有成本的，有這么大算力，還不如老老實實挖礦，獲得的獎勵更多。不過，如果惡意節(jié)點很久以前有一筆金額巨大的交易，利益驅(qū)動下，惡意節(jié)點也有動力重新分叉，雙花這筆錢，這種情況下惡意節(jié)點也會發(fā)動長程攻擊。

· 第三種情況，適用于PoS和PoW，如果一個新的全節(jié)點剛剛上線，不湊巧連接上了幾個惡意節(jié)點開始同步區(qū)塊，惡意節(jié)點給它發(fā)來偽造好的很長的鏈，比真鏈還長，這時候，即使后來連上了誠實的全節(jié)點，全節(jié)點發(fā)來的鏈條短一些，會被這個新節(jié)點拒絕。這就很尷尬了。

針對第1種和第3種情況，本質(zhì)上問題是一樣的，當收到一條更長的鏈，如何判斷它是真是假？Vitalik在這篇文章Proof of Stake： How I Learned to Love Weak Subjectivity 闡述了解決方案，還是需要從外界引入一點點知識，一點點信任，所謂的 weak subjectivity，V神認為這種弱信任是很容易達到的，因而并沒有削弱區(qū)塊鏈的Safety。當一個新節(jié)點剛上線是，它需要從外界獲得以下知識并信任這些知識：

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

2. 最新的一個有效區(qū)塊。這個區(qū)塊不能太老，必須是最近N個之內(nèi)。N可以事先定義，只要確保足夠新鮮即可，比如對于比特幣來說，最近6個之內(nèi)的任意一個區(qū)塊，都算是足夠新了，對于Ethereum來說，最近12個區(qū)塊，算是比較新了。

對于2，問題很大，一個新的全節(jié)點上線，從哪里去獲取這個最新的一個有效區(qū)塊呢？這里需要引入額外的信任知識。舉個例子，對于Casper FFG來說，一個新節(jié)點上線，應該只信任交了押金的全節(jié)點，并且最好是連接多個節(jié)點，獲取最新的已經(jīng)被finalized的區(qū)塊。當?shù)玫搅俗钚碌膄inalized的區(qū)塊，就可以放心開始同步了，即使收到了惡意節(jié)點的更長的鏈條，由于在同一高度，惡意節(jié)點的那個塊的哈希值必然不同，從而可以判斷必然是一條假的鏈條，把這條鏈丟棄掉。

總結(jié)起來，對付長程攻擊，需要依賴外界的一點點知識，即可防止這種攻擊。

論文第7頁底部有一段非正式的證明，我覺得有意義的一點是證明了退款延期時間需要大于網(wǎng)絡延遲時間的4倍，ω》4δ。

大規(guī)模崩潰的情況（Castastrophic Crashes）

如果有超過1/3的驗證節(jié)點同時崩潰，或者網(wǎng)絡出現(xiàn)問題導致他們掉線，又或者網(wǎng)絡發(fā)生分裂，這時候投票的時候，不可能湊齊超過2/3的投票，也就是說從此刻開始，無法創(chuàng)建新的supermajority link， 即無法finalize任何新塊。

論文介紹了一種稱為 Inactivity leak 的技巧，來讓兩個子網(wǎng)各自獨立工作，能夠繼續(xù)獨立投票，finalize新塊。

為了讓投票能重新超過2/3，可以讓不活躍的validator節(jié)點的押金逐步“泄露”（要么burn銷毀要么返回給節(jié)點），比如每次投票，如果某個validator沒有投票，就認為它掉線了，將它的押金減少20%，這樣連續(xù)5次都不活躍，押金減少到0。這種機制相當于不斷地降低掉線節(jié)點的權(quán)重，增加在線節(jié)點的權(quán)重，使得在線節(jié)點超過2/3時，就能夠繼續(xù)產(chǎn)生新的checkpoint了。

總結(jié)

Casper FFG算法由3個部分組成：2個懲罰條件（slash condition），一個分叉選擇規(guī)則（fork choice rule）和動態(tài)的驗證節(jié)點集合。Casper FFG適用于任何PoW算法，提高PoW算法的安全性。

Casper FFG的出塊機制是PoW（PoW based block proposal mechanism），未來會把出塊機制換成PoS的方式，這樣就是純PoS了。