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在當(dāng)前PoW的基礎(chǔ)上，添加了一層PoS投票過程，進一步增強了Finality， 舊的區(qū)塊理論上不可能被撤銷。Casper FFG是一個沒有侵入性的算法，它沒有改變當(dāng)前Ethereum的PoW算法，只是在這一層PoW上添加了BFT風(fēng)格的PoS，也就是說所有的塊，還是PoW礦工挖出來的，這條核心流程保留了下來。在這基礎(chǔ)上，每挖出100個塊，PoS的驗證節(jié)點們會對最后一個塊進行投票，2/3通過后，這最后一個塊稱為checkpoint（檢查點）。凡是被finalized的檢查點，不可撤銷。總結(jié)一句話，就是保留了PoW出塊的機制，同時每隔100個塊來一次PoS投票，進一步增強了Ethereum的安全性（Safety，即Finality）。
投票消息的字段如下：
如上表所示，每一個投票消息，包含5個字段，s表示源頭檢查點的區(qū)塊哈希，t表示目標(biāo)檢查點的區(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)?？匆姷膸讉€術(shù)語的定義：
· 一條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)，當(dāng)有超過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， 比前一個投票的目標(biāo)區(qū)塊還低，這是有問題的，因為 前面你投了s1 -》 t1 這一票，說明你已經(jīng)認(rèn)可s1到t1之間的所有塊是正確的，但是第二票 s2-》t2，區(qū)間比 s1-》t1還小，被s1-》t1完全覆蓋，這一票把 s2到t2之間的塊又重復(fù)同意了一遍，仿佛你遺忘了之前的投票。這種遺忘行為也是會被懲罰的。
下圖展示了一個違反了 No double vote 的例子，
PoW挖礦的時候，在同一個高度發(fā)生分叉是很正常的事情。這時候在4個validator節(jié)點中，有2個惡意節(jié)點，同時給兩個分叉都投了票，這樣導(dǎo)致兩個新塊都會變成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檢查點，所以它可以選擇任意一個作為源點，假設(shè)它一票是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)絡(luò)發(fā)生分裂（partition）的時候，整個系統(tǒng)依舊可以寫入新交易，依舊可以出塊。
下面開始詳細(xì)證明。
Accountable Safety： 兩個互相沖突的檢查點（checkpoint）， am和bn不可能被終局化（finalized）
證明：用反證法，假設(shè)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)絡(luò)分裂，PoW能夠在兩邊繼續(xù)出塊，但是這時候Validators節(jié)點再也無法在任何一個checkpoint上達成2/3投票了，因為一邊一半，不通通信了，即使這樣，鏈條可以在不能finalize的情況下繼續(xù)增長。在網(wǎng)絡(luò)切分為兩半的時候，依舊可以運轉(zhuǎn)（Tendermint碰到網(wǎng)絡(luò)分裂，只能無限等待了），這種健壯的liveness，也許plausible的另一層含義。
從Plausible liveness可以推導(dǎo)出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)絡(luò)在某一時刻發(fā)生了分裂，例如海底光纜斷了，將全球網(wǎng)絡(luò)一分為二。這時候兩邊的PoW會繼續(xù)正常出塊，只是每一個checkpoint投票的時候，都最多只能收到一半的票，因為validator節(jié)點一邊只有一半，即使100%同意一個新檢查點，也無法超過2/3。因此，在網(wǎng)絡(luò)發(fā)生分裂后，PoW會繼續(xù)不斷增長鏈條，只是所有的新塊都無法被finalized和justified。
接著，過了一段時間后，網(wǎng)絡(luò)終于恢復(fù)了，這時候該選擇哪條分叉呢？上邊的還是下面？按照PoW的fork choice rule， 應(yīng)該選擇最長的，就是上面那條。不過再Casper FFG里，規(guī)則略有變化，要先選擇 justified 區(qū)塊最高的那個，如果兩邊的justified區(qū)塊一樣高，再選擇最長的。根據(jù)這個規(guī)則，上面的分叉雖然最長，但是下面的分叉里，最新的justified區(qū)塊高度最高，所以應(yīng)該優(yōu)先選擇下面這條分叉。
動態(tài)的驗證節(jié)點集合
論文里為了簡化，假設(shè)validator節(jié)點是一個固定的集合，實際上Casper FFG有一個動態(tài)更新validator集合的機制，論文中沒有細(xì)講，這里也不詳細(xì)展開了。因為這個知識點對理解Casper FFG的核心算法關(guān)系不大，不必深究。
無利益攻擊（Nothing At Stack Attack）
純PoS出塊以及投票，都是不需要算力的，是沒有成本的（PoW中如果在短鏈上挖礦，挖到了也得不到獎勵，算力浪費了，是有成本的），所以當(dāng)區(qū)塊鏈發(fā)生分叉的時候，validator節(jié)點們不知道哪個分支是對的，為了獲得獎勵，最佳策略就是每一條分支都投一票。為了懲罰這種行為，PoS一般要求驗證節(jié)點們投票前需要交押金，一旦發(fā)現(xiàn)有人在每條分支上都投機，則沒收它的押金。
Casper FFG算法中，出塊是PoW負(fù)責(zé)的，這個部分不存在無利益攻擊。但是投票階段，是不需要成本的，為了防止無利益攻擊，做法也是類似的，validator節(jié)點們在投票前需要交押金，投票中一旦發(fā)現(xiàn)違反了No double vote規(guī)則，銷毀該惡意節(jié)點的所有押金，因此可以有效阻止攻擊。
長程攻擊（Long Range Attack）
長程攻擊指的是下面3種情況：
· 純PoS情況下，由于純PoS出塊是沒有成本的，可以很容造一條比真鏈更長的分叉鏈。
· PoW情況下，假設(shè)惡意節(jié)點擁有超過51%算力，也可以造一條比真鏈更長的分叉鏈。這種情況比較少見，因為PoW出塊是有成本的，有這么大算力，還不如老老實實挖礦，獲得的獎勵更多。不過，如果惡意節(jié)點很久以前有一筆金額巨大的交易，利益驅(qū)動下，惡意節(jié)點也有動力重新分叉，雙花這筆錢，這種情況下惡意節(jié)點也會發(fā)動長程攻擊。
· 第三種情況，適用于PoS和PoW，如果一個新的全節(jié)點剛剛上線，不湊巧連接上了幾個惡意節(jié)點開始同步區(qū)塊，惡意節(jié)點給它發(fā)來偽造好的很長的鏈，比真鏈還長，這時候，即使后來連上了誠實的全節(jié)點，全節(jié)點發(fā)來的鏈條短一些，會被這個新節(jié)點拒絕。這就很尷尬了。
針對第1種和第3種情況，本質(zhì)上問題是一樣的，當(dāng)收到一條更長的鏈，如何判斷它是真是假？Vitalik在這篇文章Proof of Stake： How I Learned to Love Weak Subjectivity 闡述了解決方案，還是需要從外界引入一點點知識，一點點信任，所謂的 weak subjectivity，V神認(rèn)為這種弱信任是很容易達到的，因而并沒有削弱區(qū)塊鏈的Safety。當(dāng)一個新節(jié)點剛上線是，它需要從外界獲得以下知識并信任這些知識：
1. The protocol definition. 這個好辦，區(qū)塊鏈的協(xié)議就存在于代碼之中。一個新節(jié)點運行了哪個版本的代碼，就代表它默認(rèn)信任這個代碼。
2. 最新的一個有效區(qū)塊。這個區(qū)塊不能太老，必須是最近N個之內(nèi)。N可以事先定義，只要確保足夠新鮮即可，比如對于比特幣來說，最近6個之內(nèi)的任意一個區(qū)塊，都算是足夠新了，對于Ethereum來說，最近12個區(qū)塊，算是比較新了。
對于2，問題很大，一個新的全節(jié)點上線，從哪里去獲取這個最新的一個有效區(qū)塊呢？這里需要引入額外的信任知識。舉個例子，對于Casper FFG來說，一個新節(jié)點上線，應(yīng)該只信任交了押金的全節(jié)點，并且最好是連接多個節(jié)點，獲取最新的已經(jīng)被finalized的區(qū)塊。當(dāng)?shù)玫搅俗钚碌膄inalized的區(qū)塊，就可以放心開始同步了，即使收到了惡意節(jié)點的更長的鏈條，由于在同一高度，惡意節(jié)點的那個塊的哈希值必然不同，從而可以判斷必然是一條假的鏈條，把這條鏈丟棄掉。
總結(jié)起來，對付長程攻擊，需要依賴外界的一點點知識，即可防止這種攻擊。
論文第7頁底部有一段非正式的證明，我覺得有意義的一點是證明了退款延期時間需要大于網(wǎng)絡(luò)延遲時間的4倍，ω》4δ。
大規(guī)模崩潰的情況（Castastrophic Crashes）
如果有超過1/3的驗證節(jié)點同時崩潰，或者網(wǎng)絡(luò)出現(xiàn)問題導(dǎo)致他們掉線，又或者網(wǎng)絡(luò)發(fā)生分裂，這時候投票的時候，不可能湊齊超過2/3的投票，也就是說從此刻開始，無法創(chuàng)建新的supermajority link， 即無法finalize任何新塊。
論文介紹了一種稱為 Inactivity leak 的技巧，來讓兩個子網(wǎng)各自獨立工作，能夠繼續(xù)獨立投票，finalize新塊。
為了讓投票能重新超過2/3，可以讓不活躍的validator節(jié)點的押金逐步“泄露”（要么burn銷毀要么返回給節(jié)點），比如每次投票，如果某個validator沒有投票，就認(rèn)為它掉線了，將它的押金減少20%，這樣連續(xù)5次都不活躍，押金減少到0。這種機制相當(dāng)于不斷地降低掉線節(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了。
下載文檔
