Casper FFG:以實現權益證明為目標的共識協定

Casper FFG 如何運作?以太坊 2.0 如何整合 Casper FFG?

Juin Chiu
Juin Chiu
Aug 25, 2019 · 14 min read

前言

2017 年,Vitalik Buterin 與 Virgil Griffith 共同發表了 Casper the Friendly Finality Gadget(Casper FFG)。Casper FFG 是受 PBFT 啟發並經過改良的共識協定,它雖然被設計得很簡潔(Simple),但其對安全性的證明卻不簡單(Easy)

筆者將於本文解析 Casper FFG 的原理,讀者可以一窺權益證明共識所嘗試解決的問題及其設計理念。此外,Casper FFG 是以太坊 2.0 的共識機制,理解其運作也能幫助研究員與開發者進一步理解以太坊 2.0 的設計。

最後要特別感謝以太坊研究員 Chih-Cheng Liang (梁智程)提供重要素材並與筆者共同大量討論及給予回饋,沒有他的協助便不會有這篇文章的誕生。

Casper FFG 是怎麼開始的?

以太坊對權益證明(Proof-of-Stake, PoS)的研究最早可追朔至 2014 年的這篇文章。從此之後,以太坊研究員們便一直朝「實現基於 PoS 的共識協定」此一目標前進。PoS 共識的設計是一個跨領域且相當複雜的問題,其包含計算機科學 / 經濟學 / 密碼學等面向。以太坊擁有區塊鏈生態系中最跨領域的團隊,對 PoS 的研究可以說是相當透徹。

筆者於日前翻譯了一篇關於 Casper FFG 發展脈絡的重要文獻:

Casper FFG 受到 PBFT 的啟發,並可以被視為改良後的 PBFT — 它繼承了 PBFT 的重要設計,同時添加新的機制與簡化若干規則。若讀者對 PBFT 感到陌生,可以參考筆者日前針對 PBFT 的解析文:

簡而言之,PBFT 是一個具有二輪投票機制的共識協定,且具有下列特性:

  • 許可制的(Permissioned):只有被「允許」的節點能參與共識。
  • 基於領袖的(Leader-based):只由主導節點負責「提案」(Propose),其他節點只負責投票,因此需要視域變換(View Change)機制來節制不誠實的主導節點。
  • 基於通訊的(Communication-based):使用決定性的(Deterministic)多數決來形成共識,而不是非決定性的(Non-Deterministic)算力解謎賽局。
  • 安全性重於活躍性的(Safety-over-Liveness):無論網路是否延遲,協定都能保證共識的安全性(即不分岔),這賦予協定即時敲定(Instant Finality)的特性。

其中 PBFT 所具備的即時敲定性,或許是其受到 Vitalik 青睞的主因。Vitalik 在熟讀 PBFT 後也特撰文總結,並於其中提出日後演變成 Casper FFG 的重要想法。

Casper FFG 的前身:砍押金的 4 條規則

PBFT 雖然具有即時敲定性,但並不具有抵抗共謀的能力,因此需要一個懲罰機制來遏止作惡的行為,只要節點做出踰越規則的行為,便必須承受經濟損失 — 透過經濟學法則來調節節點的行為正是 PoS 的設計理念。 任何支付押金的節點,都可以加入網路參與共識,無需任何人的許可,因此基於 PoS 模型的共識都是非許可制的(Permissionless)。

在這裡要澄清一下「許可」這件事。我們會說他「非許可制」,是因為任何驗證節點可以加入和退出。但如果在他加入的時候,鏈要維持一個驗證節點清單,從這個角度看又有點是「許可制」。從 PBFT 的角度看,投票的驗證節點也必須從許可的清單中挑選。

那麼下一個問題是:哪些行為該被懲罰?Vitalik 仔細推敲 PBFT 後發現,PBFT 只需 4 條規則(PBFT 中的斷言)便能確保共識運作良好:

Vitalik 在這篇文章中總結了這 4 條規則,並把它們稱為 PBFT 的「最少的砍押金條件」(Minimal Slashing Conditions),任何違反此 4 條規則的行為都要被取走押金。這 4 條規則如下:

1. 提交(commit_req):收到 2/3 節點的預備訊息後才能提交。2. 預備(prepare_req):每個預備訊息只能指向某個也具有 2/3 節點預備訊息的高度(Epoch),且這些預備訊息也必須都指向同一個高度。3. 預備提交一致性(prepare_commit_consistency): 任何新的預備訊息只能指向最後一個已提交的或其他比其更新的高度。4. 不重複預備(no_double_prepare):不能在同一個高度送出兩次預備。

這 4 條規則可以進一步簡化為 2 條:

某驗證節點 v 必不可發出兩個相異的投票:<ν, s1, t1, h(s1), h(t1)> 及 
<ν, s2, t2, h(s2), h(t2)>,
且使下列任一條件成立:1. h(t1) = h(t2)驗證節點必不可對某高度發出兩個相異投票。2. h(s1) < h(s2) < h(t2) < h(t1)驗證節點必不可投出高度圍繞/被圍繞於另一投票高度的投票。

這2條規則便是 Casper FFG 的最少砍押金條件 。

Casper FFG 如何運作?

Casper FFG: Checkpoint Tree

Casper FFG 是一個將出塊機制(Block Proposing Mechanism)抽象化的覆蓋鏈(Overlay),只負責形成共識。出塊機制由底層鏈實作,而來自底層鏈的出塊(Block Proposal)稱為檢查點(Checkpoints)。檢查點組成檢查點樹(Checkpoint Tree),例如:把高度為 0、50、100、150 的區塊雜湊值取出,形成一棵新的樹,如上圖所示。最底部的檢查點則稱為根檢查點(Root)。

每個節點都必須對檢查點送出投票(Vote),投票的內容是由兩個不同高度的檢查點組成的連結(Link),連結的起點高度較低,稱為源頭(Source);連結的終點高度較高,稱為目標(Target)。節點會將投票廣播到網路中,並同時收集來自其他節點的投票。其中若投票給某連結 L 的節點押金總和超過全部押金的 2/3,則稱 L 為絕對多數連結(Supermajority Link),以 s → t 表示。例如上圖中,b1 / b2 / b3 之間都形成了絕對多數連結,分別以 b1 → b2、b2 → b3 表示。

由根檢查點開始,若兩個檢查點之間形成絕對多數連結,則該連結的目標進入「已證成」( Justified) 狀態;而在連結建立當下已處於「已證成」狀態的源頭,則進入「已敲定」(Finalized)狀態;根檢查點則預設為「已證成」及「已敲定」狀態。由此可知,每個檢查點在經過兩次投票後,會先「證成」(Justify)而後「敲定」(Finalize),幾乎等同於 PBFT 的「預備」與「提交」。例如在上圖右邊的分支中,r / b1 / b2 皆為「已敲定」狀態,只有 b3 為「已證成」狀態。

那麼驗證節點該對哪些檢查點建立連結?每個節點都必須遵循分岔選擇規則(Fork Choice Rule)來選擇下一個要連接的檢查點,Casper FFG 的規則是:選擇最高的「已證成」狀態的檢查點

Casper FFG: Fork Caused by Largely Change of Validator Set

由於 Casper FFG 能讓任何存入押金的節點成為驗證節點,因此驗證節點集合(Validator Set)會動態地隨著時間變化。節點從退出網路至取出押金需要等待一段期間,該等待期間稱為提領延遲(Withdrawal Delay)。每個檢查點C都有其對應的朝代數(Dynasty),其定義為:從根檢查點開始至C為止的已敲定檢查點數量,例如上圖中,b3 的朝代數為 3。每一代檢查點都對應兩種驗證節點集合:前端(Front)驗證節點集合(包含於此代加入的節點) 以及後端(Rear)驗證節點集合(包含於此代退出的節點)。理論上每代檢查點的前端/後端集合會高度重複,但難保節點共謀造成前端/後端集合的大幅變化,若此情形發生,則出錯時可能會砍不到壞節點的押金(因為壞節點已退出)導致安全性受到威脅。例如上圖中,驗證節點 A 可以退出,代表對 C’ 分岔(綠色)來說 A 退出了,可是對 C 分岔(紫色)來說, A 卻從來沒退出過。因此 A 有辦法繼續投舊鏈 C,但新鏈 C’ 砍不到 A 的押金(因為已退出)。

為了讓每代檢查點在出錯時都能確實歸責,因此需要縫合機制(Stitching Mechanism)將檢查點的前端/後端集合「縫」起來,確保每個錯誤都必定能歸責(出錯的可能是前端集合或者後端集合)。

綜合以上,Casper FFG 幾乎針對 PBFT 的所有面向都做出改進:

  • 經濟上的制約:PBFT 是許可制的,它仰賴原本就存在信任基礎的組織共同運行協定;Casper FFG 則是非許可制的,它引入最少砍押金條件,利用經濟損失的風險來制約節點的行為,節點之間不需要任何信任基礎也能共同運行協定,實現真正的去中心化。
  • 抽象的出塊機制:PBFT 仰賴誠實的主導節點產生區塊並需要視域變換機制節制拜占庭節點;Casper FFG 不需理會底層的出塊機制,只需負責形成共識。出塊抽象的好處是:底層鏈的出塊頻率不必與覆蓋鏈的共識頻率一致,如此可以增加效率並降低網路的負擔。例如:每 100 個底層區塊只產生 1 個檢查點。
  • 流水線化的投票:PBFT 具有<Prepare>、<Commit>、<View-change>等數種投票訊息;Casper FFG 僅有<Vote>一種,且投票的內容並不是單一的區塊/請求,而是兩個形成連結的檢查點,這使 Casper FFG 能夠在不犧牲太多表達力的前提下變得簡潔許多。這些形成鏈式結構的檢查點,會於兩個不同高度分別經歷兩輪投票,由於每一輪投票都會敲定源頭與證成目標,因此共識能如流水線(Pipeline)般不斷推進。相似的設計理念也出現於 Hot-Stuff,有趣的是,該論文作者 Dahlia Malkhi 還撰文比較 Hot-Stuff 與 Casper FFG,其相似程度可見一斑。
  • 強健的抗攻擊性:PBFT 不具備對遠程攻擊(Long-range Attack)以及災難性崩潰(Catastrophic Crash)的抗性;Casper FFG 則具有特別的機制來防禦這兩種攻擊:針對遠程攻擊,節點必須定期同步區塊及禁止回朔(Revert)已敲定的區塊;針對災難性崩潰,Casper FFG 則引入「離線漏金」(Inactivity Leak)機制來應對。關於這兩種攻擊的說明,筆者將於日後另撰文論述。

由於 Casper FFG 相當簡潔,以太坊研究員一度實作了合約版本的 Casper FFG:

然而,這個合約版的 Casper FFG 後來被棄用了!在合約版中原本假設投票能夠被平行處理,但在計算投票報酬有很多中間狀態,不同投票處理的先後順序將會影響最後得到的狀態,這代表平行化將無法達成共識。而要修正這個問題則必須要在合約與客戶端做大量修改,失去了「邏輯用合約實作,避免修改客戶端」的精神。因此,為了能夠更好地整合 Casper FFG 與其他優化提案(例如分片),全新的以太坊 2.0 磅礴登場了。

以太坊 2.0 中的 Casper FFG

Ethereum 2.0: Sharding

以太坊 2.0 是一個基於 EVM 並整合 Casper FFG 與眾多優化提案(以分片為主)的分散式帳本。以太坊 2.0 除了想實現 PoS,還試圖將每秒交易數(TPS)擴展到 10000 筆的量級,使區塊鏈成為如網際網路一般的基礎建設(Infrastructure),並且讓任何存入 32 顆以太的押金的節點都能成為驗證節點。

分片(Sharding)即是為了增加可擴展性(Scalability)的重要設計,也是以太坊 2.0 最重要的目標。分片就是分工合作,我們可以用一個簡單的例子來說明分片的概念(實際上的解釋要比這複雜得多): 2 人寫 2 題作業,2 人各寫不同的 1 題再合起來一定比 2 人都各寫完 2 題來得更有效率。

目前的以太坊只有 1 條區塊鏈,所有節點必須各自處理所有交易(如同 2 人各自寫完 2 題作業);在以太坊 2.0 中,網路會分成 1024 個片(Shard),每片分別運行 1 條分片鏈(Shard Chain),它們將各自處理一部分的交易後再將結果交由 1 條信標鏈(Beacon Chain)統整(如同 2 人各做不同的 1題再合起來)。因此,以太坊 2.0 預計會有 1 條信標鏈以及 1024 條分片鏈。

值得注意的是:片是一個抽象層,並不特指某一群節點。為了更了解這個概念,筆者擴充一下上文的例子:假設寫作業有找答案抄答案兩個步驟,那麼 A / B 2 人寫 2 題作業,並用擲硬幣決定誰負責哪一題的哪個步驟。例如擲完後決定第 1 題由 A 找答案、由 B 抄答案;第 2 題由 B 找答案、由A抄答案。

同樣地,在以太坊 2.0 中,除了有 1024 個片,還會有 1024 個持續委員會(Persistent Committee)與 1024 個交聯委員會(Crosslink Committee)。每個片都會對應 1 個持續委員會與 1 個交聯委員會,且這兩個委員會各有不同任務:持續委員會負責維護分片鏈與產生分片區塊(Shard Block)、交聯委員會負責維護信標鏈與產生信標區塊(Beacon Block),如同上例中每個題目可以依照步驟來對應不同的個體,分別負責找答案與抄答案。

各委員會的分派以及各區塊的出塊節點(Block Proposer)由鏈上亂數(On-chain Random Number)決定,如同上例中用擲硬幣來分派題目(關於鏈上亂數的實作細節留待筆者日後詳述)。

換句話說,每個驗證節點都需維護 1 條唯一的信標鏈及 1 條所屬片的分片鏈,也都會隸屬於與該分片對應之 1 個交聯委員會與 1 個持續委員會。

Casper FFG 是運行於以太坊 2.0 之上的覆蓋鏈,這個覆蓋鏈同樣由檢查點構成,各檢查點之間的跨度稱為時期(Epoch),1 個時期(Epoch)切成 64 個時段(Slot),每個時段對應 16 個片(16 = 1024 ÷ 64),因此每片在每時期中都有對應的時段,並只能在輪到自己時才廣播其對檢查點的投票,且每分片只能 1 個時段中投出 1 票 — 也就是說,各分片需要先對投票內容形成共識,不過各片內部形成共識的方法仍尚未定論,近期最新的提案是使用聚合簽章。另外,Casper FFG 在以太坊 2.0 中的分岔選擇規則是最新訊息驅動 GHOST(Latest-Message Driven GHOST, LMD GHOST)

理論上,Casper FFG 於每個檢查點的投票應該要與底層出塊機制的投票分開;實際上,以太坊 2.0 的底層投票內容會同時包含頂層投票內容(檢查點的連結),如同頂層投票搭了底層投票的便車(Piggyback),藉此優化效能。如此在每個時期結束時,每個片都會收到所有其他片在該時期的投票,Casper FFG 活躍性得以維持。

結語

Casper FFG 是一個實現權益證明的大膽嘗試,它在以太坊 2.0 的表現值得期待。然而以太坊 2.0 還有許多難題留待解決,例如輕節點(Light Client)/ 鏈上亂數產生器(On-chain Random Number Generator)/ 跨片交易(Cross-shard Transaction)等等。與此同時,許多以太坊 2.0 的競爭者也提出新的共識協定與分片技術,例如 RapidChain / Harmony / Chainspace 等等。

Casper FFG 以及以太坊 2.0 是經過眾多研究員/開發者不斷激盪與迭代的重要結晶,但一直以來都缺乏提供系統性論述的中文材料,希望此文可以幫助中文世界的研究員/開發者快速理解 Casper FFG 與以太坊 2.0 的精要。

Taipei Ethereum Meetup

台北以太坊社群專欄

Juin Chiu

Written by

Juin Chiu

Blockchain/DLT researcher at Unitychain and Co-organizer of Taipei Ethereum Meetup, focusing on consensus protocol, sharding, DID/SSI and anonymity network.

Taipei Ethereum Meetup

台北以太坊社群專欄

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade