原作者：原作者：圖片描述https://v.qq.com/x/page/f07704nx4iq.html
一級標題
Casper FFG算法流程
圖片描述
PoW流程
PoW流程
上圖中黃色的礦工突然算理大增，開始乾壞事，從一個舊的區塊出發，分叉出了一條新鏈，不斷在上面挖礦，如果它的長度超過了左邊，那麼新的鏈條就能成功取代舊的鏈條，以前的舊區塊被撤銷，裡面的交易也全部會被覆蓋和改寫。Casper FFG在當前PoW的基礎上，添加了一層PoS投票過程，進一步增強了Finality, 舊的區塊理論上不可能被撤銷。 Casper FFG是一個沒有侵入性的算法，它沒有改變當前Ethereum的PoW算法，只是在這一層PoW上添加了BFT風格的PoS，也就是說所有的塊，還是PoW礦工挖出來的，這條核心流程保留了下來。在這基礎上，每挖出100個塊，PoS的驗證節點們會對最後一個塊進行投票，2/3通過後，這最後一個塊稱為checkpoint(檢查點)。總結一句話，就是保留了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之間不在一條路徑上。justified一個檢查點c要變成一個
檢查點，需要滿足下列條件之一，(1)它是創世區塊;(2)或者存在一條supermajority link指向它。finalized檢查點，需要它是justified 且存在一條以它為源頭的supermajority link, c→c'，且c'是它的直接孩子(direct child)直接孩子(direct child)
一級標題
一級標題
一級標題
懲罰條件(SlashCondition)
1. No double vote: Validator 如果違反了下面兩個條件中的任何一條，就會被懲罰，沒收所有押金。
2. No surround vote.t1==t2。在同一個高度，不能投票給兩個不同的塊。這個比較容易理解，同一個高度，給兩個不同的塊都投一票，屬於Nothingat stake的典型投機行為，這是要被懲罰的。< t1,t2< t1 < s1 < s2 。例如，一個validator首先投了一票, s1 -> t1, 過了幾個塊後，繼續投票，s2 -> t2, 由於區塊高度是隨著時間不斷遞增的，很顯然s2> e1, 而第二個投票裡如果t2
比前一個投票的目標區塊還低，這是有問題的，因為前面你投了s1 -> t1 這一票，說明你已經認可s1到t1之間的所有塊是正確的，但是第二票s2 ->t2，區間比s1->t1還小，被s1->t1完全覆蓋，這一票把s2到t2之間的塊又重複同意了一遍，彷彿你遺忘了之前的投票。這種遺忘行為也是會被懲罰的。
下圖展示了一個違反了Nodouble vote 的例子，
PoW挖礦的時候，在同一個高度發生分叉是很正常的事情。這時候在4個validator節點中，有2個惡意節點，同時給兩個分叉都投了票，這樣導致兩個新塊都會變成justified狀態，這是不對的，這時候只要有一個validator舉報這種情況，那麼這兩個惡意節點就會被懲罰，銷毀押金，同時舉報的人會獲得一筆獎勵(finder'sfee)。
一級標題
一級標題
一級標題
證明Safety 和Plausible Liveness
這一節我們來證明Casper FFG的Safety(即Finality)和Liveness。
首先Casper FFG號稱是accountable safety 和plausibleliveness. 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。
如果j==m+1，同上；
如果j==m+1，同上；
如果i
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（包括起點，三個塊肯定在一條線上），這時可以投票給兩個中的任何一個，甚至兩個都投，都不會違反nodouble vote 和nosurround vote規則。也就是說可以越過多個塊，直接投更高的塊。下一個被justified的塊，可能是am也可能是bn，也有可能同時都是（兩個都獲得超過2/3個投票，此時必然有超過1/3的節點兩個都投了）這就是為什麼稱為plausible的原因吧。
即使網絡分裂，PoW能夠在兩邊繼續出塊，但是這時候Validators節點再也無法在任何一個checkpoint上達成2/3投票了，因為一邊一半，不通通信了，即使這樣，鏈條可以在不能finalize的情況下繼續增長。在網絡切分為兩半的時候，依舊可以運轉(Tendermint碰到網絡分裂，只能無限等待了)，這種健壯的liveness，也許plausible的另一層含義。從Plausible liveness可以推導出Casper FFG的分叉選擇規則(ForkChoice Rule)：總是選擇基於最高的justified區塊的最長鏈條(alwayschoose the longest chain on top of the justified checkpoint with highestheight.)。
也就是先找到最高的justified區塊，然後從該區塊出發，選擇最長的鏈條。比PoW算法單純的選擇最長的鏈，多了一個先決條件。
一級標題
一級標題
一級標題
一級標題
一級標題
一級標題
一級標題
一級標題
長程攻擊(LongRange Attack)
長程攻擊指的是下面3種情況：
純PoS情況下，由於純PoS出塊是沒有成本的，可以很容造一條比真鏈更長的分叉鏈。
PoW情況下，假設惡意節點擁有超過51%算力，也可以造一條比真鏈更長的分叉鏈。這種情況比較少見，因為PoW出塊是有成本的，有這麼大算力，還不如老老實實挖礦，獲得的獎勵更多。不過，如果惡意節點很久以前有一筆金額巨大的交易，利益驅動下，惡意節點也有動力重新分叉，雙花這筆錢，這種情況下惡意節點也會發動長程攻擊。
第三種情況，適用於PoS和PoW，如果一個新的全節點剛剛上線，不湊巧連接上了幾個惡意節點開始同步區塊，惡意節點給它發來偽造好的很長的鏈，比真鏈還長，這時候，即使後來連上了誠實的全節點，全節點發來的鏈條短一些，會被這個新節點拒絕。這就很尷尬了。Proof of Stake: How I Learned toLove Weak Subjectivity 針對第1種和第3種情況，本質上問題是一樣的，當收到一條更長的鏈，如何判斷它是真是假？ Vitalik在這篇文章
闡述了解決方案，還是需要從外界引入一點點知識，一點點信任，所謂的weak subjectivity，V神認為這種弱信任是很容易達到的，因而並沒有削弱區塊鏈的Safety。當一個新節點剛上線是，它需要從外界獲得以下知識並信任這些知識：
1. Theprotocol definition. 這個好辦，區塊鏈的協議就存在於代碼之中。一個新節點運行了哪個版本的代碼，就代表它默認信任這個代碼。
2. 最新的一個有效區塊。這個區塊不能太老，必須是最近N個之內。 N可以事先定義，只要確保足夠新鮮即可，比如對於比特幣來說，最近6個之內的任意一個區塊，都算是足夠新了，對於Ethereum來說，最近12個區塊，算是比較新了。
一級標題
一級標題
一級標題
大規模崩潰的情況（Castastrophic Crashes）
如果有超過1/3的驗證節點同時崩潰，或者網絡出現問題導致他們掉線，又或者網絡發生分裂，這時候投票的時候，不可能湊齊超過2/3的投票，也就是說從此刻開始，無法創建新的supermajoritylink, 即無法finalize任何新塊。 Inactivity leak 一級標題
總結
總結
總結
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。
二級標題
參考資料
參考資料
Casper the Friendly Finality Gadget
EthereumPoS: 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’sCasper
Consensus Compare: Casper vs.Tendermint - Medium
Proof of Stake: How I Learned toLove Weak Subjectivity
