Casper FFG算法及流程解析

Casper FFG 是 Vitalik提出來(lái)的一個(gè)PoW/PoS混合的算法，目的是為了讓Ethereum平滑過(guò)渡到純PoS。論文在這里，Casper the Friendly Finality Gadget，本文主要講解這篇論文的核心知識(shí)點(diǎn)。

Casper FFG算法流程

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

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

Casper FFG在當(dāng)前PoW的基礎(chǔ)上，添加了一層PoS投票過(guò)程，進(jìn)一步增強(qiáng)了Finality， 舊的區(qū)塊理論上不可能被撤銷(xiāo)。Casper FFG是一個(gè)沒(méi)有侵入性的算法，它沒(méi)有改變當(dāng)前Ethereum的PoW算法，只是在這一層PoW上添加了BFT風(fēng)格的PoS，也就是說(shuō)所有的塊，還是PoW礦工挖出來(lái)的，這條核心流程保留了下來(lái)。在這基礎(chǔ)上，每挖出100個(gè)塊，PoS的驗(yàn)證節(jié)點(diǎn)們會(huì)對(duì)最后一個(gè)塊進(jìn)行投票，2/3通過(guò)后，這最后一個(gè)塊稱(chēng)為checkpoint（檢查點(diǎn)）。凡是被finalized的檢查點(diǎn)，不可撤銷(xiāo)?？偨Y(jié)一句話，就是保留了PoW出塊的機(jī)制，同時(shí)每隔100個(gè)塊來(lái)一次PoS投票，進(jìn)一步增強(qiáng)了Ethereum的安全性（Safety，即Finality）。

投票消息的字段如下：

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

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

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

同時(shí)，Casper FFG的這種投票消息，跟Tendermint里的鎖機(jī)制，有類(lèi)似作用。

下面是Casper FFG算法里經(jīng)?？匆?jiàn)的幾個(gè)術(shù)語(yǔ)的定義：

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

· 兩個(gè)檢查點(diǎn)a和b互相沖突，指的是a和b在不同的分支上，也就是說(shuō)a和b之間不在一條路徑上。

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

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

舉個(gè)例子，如下圖所示，

上圖中綠色的檢查點(diǎn)，在投票之前是一個(gè)justified狀態(tài)，當(dāng)有超過(guò)2/3投票，以這個(gè)justfied區(qū)塊為源頭，指向另一個(gè)更高的區(qū)塊，那么原先的justified區(qū)塊，就變成了finalized的了，再也不可撤銷(xiāo)了，新的區(qū)塊，就變成了justified狀態(tài)。在finalized和justfied區(qū)塊之間，形成了一條supermajority link。

懲罰條件（Slash Condition）

Validator 如果違反了下面兩個(gè)條件中的任何一條，就會(huì)被懲罰，沒(méi)收所有押金。

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

2. No surround vote. t2 《 t1 《 s1 《 s2 。例如，一個(gè)validator首先投了一票， s1 -》 t1， 過(guò)了幾個(gè)塊后，繼續(xù)投票，s2 -》 t2， 由于區(qū)塊高度是隨著時(shí)間不斷遞增的，很顯然 s2 》 e1， 而第二個(gè)投票里如果 t2 《 t1， 比前一個(gè)投票的目標(biāo)區(qū)塊還低，這是有問(wèn)題的，因?yàn)?前面你投了s1 -》 t1 這一票，說(shuō)明你已經(jīng)認(rèn)可s1到t1之間的所有塊是正確的，但是第二票 s2-》t2，區(qū)間比 s1-》t1還小，被s1-》t1完全覆蓋，這一票把 s2到t2之間的塊又重復(fù)同意了一遍，仿佛你遺忘了之前的投票。這種遺忘行為也是會(huì)被懲罰的。

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

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

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

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

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

證明 Safety 和 Plausible Liveness

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

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

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

下面開(kāi)始詳細(xì)證明。

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

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

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

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

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

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

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

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

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

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

即使網(wǎng)絡(luò)分裂，PoW能夠在兩邊繼續(xù)出塊，但是這時(shí)候Validators節(jié)點(diǎn)再也無(wú)法在任何一個(gè)checkpoint上達(dá)成2/3投票了，因?yàn)橐贿呉话耄煌?a target="_blank">通信了，即使這樣，鏈條可以在不能finalize的情況下繼續(xù)增長(zhǎng)。在網(wǎng)絡(luò)切分為兩半的時(shí)候，依舊可以運(yùn)轉(zhuǎn)（Tendermint碰到網(wǎng)絡(luò)分裂，只能無(wú)限等待了），這種健壯的liveness，也許plausible的另一層含義。

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

舉個(gè)例子，如下圖：

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

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

動(dòng)態(tài)的驗(yàn)證節(jié)點(diǎn)集合

論文里為了簡(jiǎn)化，假設(shè)validator節(jié)點(diǎn)是一個(gè)固定的集合，實(shí)際上Casper FFG有一個(gè)動(dòng)態(tài)更新validator集合的機(jī)制，論文中沒(méi)有細(xì)講，這里也不詳細(xì)展開(kāi)了。因?yàn)檫@個(gè)知識(shí)點(diǎn)對(duì)理解Casper FFG的核心算法關(guān)系不大，不必深究。

無(wú)利益攻擊（Nothing At Stack Attack）

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

Casper FFG算法中，出塊是PoW負(fù)責(zé)的，這個(gè)部分不存在無(wú)利益攻擊。但是投票階段，是不需要成本的，為了防止無(wú)利益攻擊，做法也是類(lèi)似的，validator節(jié)點(diǎn)們?cè)谕镀鼻靶枰谎航?，投票中一旦發(fā)現(xiàn)違反了No double vote規(guī)則，銷(xiāo)毀該惡意節(jié)點(diǎn)的所有押金，因此可以有效阻止攻擊。

長(zhǎng)程攻擊（Long Range Attack）

長(zhǎng)程攻擊指的是下面3種情況：

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

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

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

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

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

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

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

總結(jié)起來(lái)，對(duì)付長(zhǎng)程攻擊，需要依賴外界的一點(diǎn)點(diǎn)知識(shí)，即可防止這種攻擊。

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

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

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

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

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

總結(jié)

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

Casper FFG的出塊機(jī)制是PoW（PoW based block proposal mechanism），未來(lái)會(huì)把出塊機(jī)制換成PoS的方式，這樣就是純PoS了。