詳解Casper FFG共識算法_ALI:FIN

原作者：靈魂機器；本文配套視頻：https://v.qq.com/x/page/f07704nx4iq.htmlCasperFFG是Vitalik提出來的一個PoW/PoS混合的算法，目的是為了讓Ethereum平滑過渡到純PoS。論文在這里，CaspertheFriendlyFinalityGadget，本文主要講解這篇論文的核心知識點。CasperFFG算法流程

目前是2018年，Ethereum依舊是一個純PoW算法的區塊鏈，跟比特幣一樣。PoW是一個非常簡潔的算法，也非常安全，例如這篇論文AnalysisoftheBlockchainProtocolinAsynchronousNetworks，證明了比特幣其實是非常安全的。盡管如此，如果某個礦工擁有了超過51%的算理，理論上依舊是有可能重新改寫以前的區塊的。PoW流程上圖中黃色的礦工突然算理大增，開始干壞事，從一個舊的區塊出發，分叉出了一條新鏈，不斷在上面挖礦，如果它的長度超過了左邊，那么新的鏈條就能成功取代舊的鏈條，以前的舊區塊被撤銷，里面的交易也全部會被覆蓋和改寫。CasperFFG在當前PoW的基礎上，添加了一層PoS投票過程，進一步增強了Finality,舊的區塊理論上不可能被撤銷。CasperFFG是一個沒有侵入性的算法，它沒有改變當前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)。CasperFFG的這種投票消息，很巧妙地把二步融合到一個步驟里了，本質上它還是跟pBFT,Tendermint里的二階段投票等價，pre-prepare->prepare,pre-vote->pre-commit。下圖里解釋了投票為什么需要兩個階段。同時，CasperFFG的這種投票消息，跟Tendermint里的鎖機制，有類似作用。下面是CasperFFG算法里經常看見的幾個術語的定義：一條supermajoritylink，寫成a→b，指的是，如果有超過2/3的投票消息，都是從a檢查點出發，指向b檢查點，那么a到b之間就有一條supermajoritylink。一條supermajoritylink，可以跨越若干個檢查點，也就是說h(b)>h(a)+1是合法的。兩個檢查點a和b互相沖突，指的是a和b在不同的分支上，也就是說a和b之間不在一條路徑上。一個檢查點c要變成一個justified檢查點，需要滿足下列條件之一，(1)它是創世區塊;(2)或者存在一條supermajoritylink指向它。一個檢查點c要變成一個finalized檢查點，需要它是justified且存在一條以它為源頭的supermajoritylink,c→c’，且c’是它的直接孩子(directchild)，即c’的高度是c的高度增1。舉個例子，如下圖所示：上圖中綠色的檢查點，在投票之前是一個justified狀態，當有超過2/3投票，以這個justfied區塊為源頭，指向另一個更高的區塊，那么原先的justified區塊，就變成了finalized的了，再也不可撤銷了，新的區塊，就變成了justified狀態。在finalized和justfied區塊之間，形成了一條supermajoritylink。懲罰條件(SlashCondition)

Topia發布首個Layer2 DA協議:金色財經報道，自從Celestia引入模塊化區塊鏈架構以來，數據可用性（DA）已經成為一個獨立的模塊來解決區塊鏈可擴展性的挑戰。隨著Ethereum的Layer2越來越豐富，Layer2的數據可用性問題也變得越來越緊迫。最近，Topia在Montenegro Edcon Super Demo上推出了第一個Layer2共享數據可用性層協議，旨在為Ethereum的Layer2帶來一個互聯的數據可用性層，并為未來成千上萬的Layer2連接數據可用性。[2023/5/20 15:15:52]

Validator如果違反了下面兩個條件中的任何一條，就會被懲罰，沒收所有押金。1.Nodoublevote:t1==t2。在同一個高度，不能投票給兩個不同的塊。這個比較容易理解，同一個高度，給兩個不同的塊都投一票，屬于Nothingatstake的典型投機行為，這是要被懲罰的。2.Nosurroundvote.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之間的塊又重復同意了一遍，仿佛你遺忘了之前的投票。這種遺忘行為也是會被懲罰的。下圖展示了一個違反了Nodoublevote的例子，PoW挖礦的時候，在同一個高度發生分叉是很正常的事情。這時候在4個validator節點中，有2個惡意節點，同時給兩個分叉都投了票，這樣導致兩個新塊都會變成justified狀態，這是不對的，這時候只要有一個validator舉報這種情況，那么這兩個惡意節點就會被懲罰，銷毀押金，同時舉報的人會獲得一筆獎勵(finder’sfee)。下圖展示一個違反了Nosurroundvote的例子，某個時刻，同時有兩條supermajoritylink,A->B,和A->C，于是A變成了finalized,B和C同時都是justified區塊。這種情況，說明有超過1/3的驗證節點，同時給B和C投了票，這是合法的，沒有違反nodoublevote規則，也沒有違反nosurroundvote規則。接下來，某個validator節點可以開始投票了，由于有兩個justified檢查點，所以它可以選擇任意一個作為源點，假設它一票是B->E，另一票是C->D，這是不合法的，違反了nosurroundvote規則。證明Safety和PlausibleLiveness

幣安：將與韓國檢察官合作并提供調查Do Kwon所需的任何幫助:金色財經報道，韓國檢察官稱Do Kwon已將非法資金從LUNA轉移到比特幣，這些操作使用了海外加密貨幣交易所而非進行直接的實物資產投資。據悉，目前韓國監管機構已要求幣安停止任何與Do Kwon相關的取款請求，幣安也證實，他們正在與韓國檢察官合作并提供他們所需要的任何幫助。（Cointelgraph）[2023/4/8 13:50:55]

這一節我們來證明CasperFFG的Safety(即Finality)和Liveness。首先CasperFFG號稱是accountablesafety和plausibleliveness.Accountable的意思是validator節點們需要交數量可觀的押金，有了押金，就有了初步的信任，可以指望的(accountable)了。Plausibleliveness實際上沒有新意，跟比特幣的liveness一模一樣，是指網絡發生分裂(partition)的時候，整個系統依舊可以寫入新交易，依舊可以出塊。下面開始詳細證明。AccountableSafety:兩個互相沖突的檢查點(checkpoint),am和bn不可能被終局化(finalized)證明：用反證法，假設am和bn互相沖突且終局化finalized了，且它們各自的有一個已經justified的子區塊am+1和bn+1。如果它們的高度m和n相等，則必然有1/3的驗證節點同時給兩個checkpoint都投了票，這些節點違反了Nodoublevote的這條規則，會被銷毀所有押金，失去了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的驗證節點違反了nodoublevote規則，會被懲罰，從而使得am和bn不可能會被finalized；如果j==m+1，同上；如果i<m,j>m+1，則說明有一條supermajoritylinkbi→bj,，完整包圍了am->am+1，這違反了nosurroundvote規則，會有1/3的節點會被懲罰，使得am和bn不可能會被finalized。有人會問bi,bj有可能沒有finalized,即便如此，起碼genesis→bn包圍了am->am+1，還是違反了nosurroundrule。綜上所述，任何情況下am和bn都不可能會被finalized，證明完畢。PlausibleLiveness:只要有超過2/3的validator節點遵守使用justified的區塊作為起點進行投票，那么就總是可以產生新的finalized的新塊。簡單的說，就是以一個justified了的塊作為起點，可以投任何一個比它高的節點，比如有兩個新快，一個am在高度m,一個bn在高度n，這時可以投票給兩個中的任何一個，甚至兩個都投，都不會違反nodoublevote和nosurroundvote規則。也就是說可以越過多個塊，直接投更高的塊。下一個被justified的塊，可能是am也可能是bn，也有可能同時都是這就是為什么稱為plausible的原因吧。即使網絡分裂，PoW能夠在兩邊繼續出塊，但是這時候Validators節點再也無法在任何一個checkpoint上達成2/3投票了，因為一邊一半，不通通信了，即使這樣，鏈條可以在不能finalize的情況下繼續增長。在網絡切分為兩半的時候，依舊可以運轉(Tendermint碰到網絡分裂，只能無限等待了)，這種健壯的liveness，也許plausible的另一層含義。從Plausibleliveness可以推導出CasperFFG的分叉選擇規則(ForkChoiceRule)：總是選擇基于最高的justified區塊的最長鏈條(alwayschoosethelongestchainontopofthejustifiedcheckpointwithhighestheight.)。也就是先找到最高的justified區塊，然后從該區塊出發，選擇最長的鏈條。比PoW算法單純的選擇最長的鏈，多了一個先決條件。舉個例子，如下圖：上圖中，從最高的一個finalized，有兩條supermajoritylink，指向了兩個justified檢查點，這時候，網絡在某一時刻發生了分裂，例如海底光纜斷了，將全球網絡一分為二。這時候兩邊的PoW會繼續正常出塊，只是每一個checkpoint投票的時候，都最多只能收到一半的票，因為validator節點一邊只有一半，即使100%同意一個新檢查點，也無法超過2/3。因此，在網絡發生分裂后，PoW會繼續不斷增長鏈條，只是所有的新塊都無法被finalized和justified。接著，過了一段時間后，網絡終于恢復了，這時候該選擇哪條分叉呢？上邊的還是下面？按照PoW的forkchoicerule,應該選擇最長的，就是上面那條。不過再CasperFFG里，規則略有變化，要先選擇justified區塊最高的那個，如果兩邊的justified區塊一樣高，再選擇最長的。根據這個規則，上面的分叉雖然最長，但是下面的分叉里，最新的justified區塊高度最高，所以應該優先選擇下面這條分叉。動態的驗證節點集合

Color Capital聯合創始人：ETH將在五年內成為集成到零售POS系統和數字結帳中的標準支付方式:金色財經報道，Color Capital聯合創始人Chris Cantino在社交媒體上稱，ETH將在五年內成為集成到零售 POS 系統和數字結帳中的標準支付方式。[2022/11/28 21:05:56]

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

純PoS出塊以及投票，都是不需要算力的，是沒有成本的，所以當區塊鏈發生分叉的時候，validator節點們不知道哪個分支是對的，為了獲得獎勵，最佳策略就是每一條分支都投一票。為了懲罰這種行為，PoS一般要求驗證節點們投票前需要交押金，一旦發現有人在每條分支上都投機，則沒收它的押金。CasperFFG算法中，出塊是PoW負責的，這個部分不存在無利益攻擊。但是投票階段，是不需要成本的，為了防止無利益攻擊，做法也是類似的，validator節點們在投票前需要交押金，投票中一旦發現違反了Nodoublevote規則，銷毀該惡意節點的所有押金，因此可以有效阻止攻擊。長程攻擊(LongRangeAttack)

長程攻擊指的是下面3種情況：純PoS情況下，由于純PoS出塊是沒有成本的，可以很容造一條比真鏈更長的分叉鏈。PoW情況下，假設惡意節點擁有超過51%算力，也可以造一條比真鏈更長的分叉鏈。這種情況比較少見，因為PoW出塊是有成本的，有這么大算力，還不如老老實實挖礦，獲得的獎勵更多。不過，如果惡意節點很久以前有一筆金額巨大的交易，利益驅動下，惡意節點也有動力重新分叉，雙花這筆錢，這種情況下惡意節點也會發動長程攻擊。第三種情況，適用于PoS和PoW，如果一個新的全節點剛剛上線，不湊巧連接上了幾個惡意節點開始同步區塊，惡意節點給它發來偽造好的很長的鏈，比真鏈還長，這時候，即使后來連上了誠實的全節點，全節點發來的鏈條短一些，會被這個新節點拒絕。這就很尷尬了。針對第1種和第3種情況，本質上問題是一樣的，當收到一條更長的鏈，如何判斷它是真是假？Vitalik在這篇文章ProofofStake:HowILearnedtoLoveWeakSubjectivity闡述了解決方案，還是需要從外界引入一點點知識，一點點信任，所謂的weaksubjectivity，V神認為這種弱信任是很容易達到的，因而并沒有削弱區塊鏈的Safety。當一個新節點剛上線是，它需要從外界獲得以下知識并信任這些知識：1.Theprotocoldefinition.這個好辦，區塊鏈的協議就存在于代碼之中。一個新節點運行了哪個版本的代碼，就代表它默認信任這個代碼。2.最新的一個有效區塊。這個區塊不能太老，必須是最近N個之內。N可以事先定義，只要確保足夠新鮮即可，比如對于比特幣來說，最近6個之內的任意一個區塊，都算是足夠新了，對于Ethereum來說，最近12個區塊，算是比較新了。對于2，問題很大，一個新的全節點上線，從哪里去獲取這個最新的一個有效區塊呢？這里需要引入額外的信任知識。舉個例子，對于CasperFFG來說，一個新節點上線，應該只信任交了押金的全節點，并且最好是連接多個節點，獲取最新的已經被finalized的區塊。當得到了最新的finalized的區塊，就可以放心開始同步了，即使收到了惡意節點的更長的鏈條，由于在同一高度，惡意節點的那個塊的哈希值必然不同，從而可以判斷必然是一條假的鏈條，把這條鏈丟棄掉。總結起來，對付長程攻擊，需要依賴外界的一點點知識，即可防止這種攻擊。論文第7頁底部有一段非正式的證明，我覺得有意義的一點是證明了退款延期時間需要大于網絡延遲時間的4倍，ω>4δ。大規模崩潰的情況

美聯儲喬治：盡管通脹可能正在緩和，但仍處于高位:8月19日消息，美聯儲喬治表示，盡管通脹可能正在緩和，但仍處于高位。到目前為止，核心通脹的緩解程度“很難令人寬慰”。上個月的通脹數字“令人鼓舞”，但還不是勝利的時候。美國的需求和供給之間仍然存在“相當嚴重的不平衡”。預計美國經濟增長將持續放緩，通脹預期看起來得到了充分錨定。美國勞動力市場緊張的狀況需要一段時間來緩解，需求仍處在一個相對較高的水平。[2022/8/19 12:34:54]

如果有超過1/3的驗證節點同時崩潰，或者網絡出現問題導致他們掉線，又或者網絡發生分裂，這時候投票的時候，不可能湊齊超過2/3的投票，也就是說從此刻開始，無法創建新的supermajoritylink,即無法finalize任何新塊。論文介紹了一種稱為Inactivityleak的技巧，來讓兩個子網各自獨立工作，能夠繼續獨立投票，finalize新塊。為了讓投票能重新超過2/3，可以讓不活躍的validator節點的押金逐步“泄露”，比如每次投票，如果某個validator沒有投票，就認為它掉線了，將它的押金減少20%，這樣連續5次都不活躍，押金減少到0。這種機制相當于不斷地降低掉線節點的權重，增加在線節點的權重，使得在線節點超過2/3時，就能夠繼續產生新的checkpoint了。總結

CasperFFG算法由3個部分組成：2個懲罰條件(slashcondition)，一個分叉選擇規則(forkchoicerule)和動態的驗證節點集合。CasperFFG適用于任何PoW算法，提高PoW算法的安全性。CasperFFG的出塊機制是PoW(PoWbasedblockproposalmechanism)，未來會把出塊機制換成PoS的方式，這樣就是純PoS了。關于網絡通信復雜度，在PoW階段，是O(n)，在BFT投票階段，是O(n2)。一般驗證節點由于有資金門檻，數量相比全網節點來說很小，所以即使是O(n2)，由于n很小，通信量還是比較小的。關于最大容錯，在PoW階段，能夠容忍惡意節點算力小于50%，在BFT投票階段，需要惡意節點的資金數量小于1/3，簡單粗暴的總結，可以認為最大容錯是1/3。關于網絡假設，在PoW階段是同步的，在BFT投票階段，是存異步的，總的來說，網絡假設是同步的。關于Finality,在PoW階段是Probabilistic的，在BFT投票后，變成了Deterministic，總的來說是Deterministic的。關于Liveness，CasperFFG在網絡分裂的情況下，依舊可以正常出塊，寫入新的交易，它的Liveness跟PoW是一樣的。參考資料

Optimism觸及1.97美元后回落，24小時漲幅22.81%:7月30日消息，據行情數據顯示，Optimism（OP）于今晨觸及1.97美元后回落，現報價1.84美元，24小時漲幅22.81%。[2022/7/30 2:47:37]

CaspertheFriendlyFinalityGadgetEthereumPoS:CasperFFGInDepth-YouTubeEthereumPoSOverview:CasperFFGCasperFFGwithonemessagetype,andsimplerforkchoiceruleEthereumCasper101ASimplifiedLookatEthereum’sCasperConsensusCompare:Caspervs.Tendermint-MediumProofofStake:HowILearnedtoLoveWeakSubjectivity

Tags：ALIFINPOWCASalien幣在哪個交易所Rhinos FinanceglobalhashpowerZero Knowledge Podcast

TUSD