Casper FFG 與 Casper CBC 的瑜亮情結

A tweet storm explaining the history and state of Ethereum’s Casper research

Juin Chiu
Juin Chiu
Aug 7 · 12 min read

前言

以太坊針對 PoS 共識模型的研究最早始於2014年,這些研究後來演變成目前廣為人知的 Casper the Fridenly Finality Gadget(FFG)/ Correct by Construction(CBC) 兩種共識模型,它們分別由兩個不同的團隊開發且存有不少差異。Vitalik 用一系列推文簡述了從2014以來 Casper 的開發脈絡,由於中文社群仍缺乏針對 Casper 開發路線相關的總結,因此譯者特將此系列推文翻譯成中文並且補上一些註解,希望可以成為開發者或研究員在學習 Casper 時的重要文獻,並期望讀者對 Casper 設計理念有更直覺的理解。

為了避免讀來生硬,建議讀者先大略掌握 PBFT / Casper FFG / GHOST 的重要概念,PBFT的部分可以參考譯者的這篇文章:若想搞懂區塊鏈就不能忽視的經典:PBFT。最後要特別感謝以太坊基金會研究員梁智程(Chih-Cheng Liang)提供諸多素材與協助校閱。

以下正文開始。


簡介

我將要用一系列的推文來解釋以太坊 Casper 共識協定的研究歷史/脈絡/進展,包括 FFG vs CBC 的爭論、混合模型到完全 PoS 的轉換、隨機性扮演的角色、共識機制的設計考量以及其他議題。


無利害關係問題與遠程攻擊

以太坊的權益證明研究始於 2014 年 1 月的 Slasher 協定。雖然 Slasher 演算法並不是非常理想,但它引入了一些重要觀念,特別是利用罰金來解決「無利害關係問題(Nothing-at-Stake Problem)」。然而,我所使用的罰金相當少,單只取消投票獎勵。Vlad Zamfir於 2014 年中加入了,他迅速引入驗證者必須押金的方法。押金是比獎勵還大的數字,做出錯誤的行為將會使押金被取走(這裡是Vlad的覆述)。

我們花了 2014 下半年的大部分時間試著解決「遠程攻擊(Long-Range Attack)」,攻擊者可以將他們的押金從主鏈提領出來,並且形成另一條具有更多簽名的攻擊鏈,如此欺騙新加入的節點,讓他們以為攻擊鏈是一條主鏈。如果攻擊鏈與主鏈分岔的時間點距離當前相當近,攻擊鏈不會造成問題,因為驗證者若在兩條鏈上同時對兩個互相抵觸的訊息簽名,則這個簽名可以當成懲罰驗證者的證據來沒收押金;但是若分岔發生在很久之前(因此被稱為遠程攻擊),攻擊者可以取出押金以避免被沒收。

我們最後得出:遠程攻擊是無法避免的,原因大致跟 PoW 擁護者所說的差不多。然而,我們沒有接受他們的結論。因為我們發現:我們可以引入兩個額外的安全假設來解決遠程攻擊:1. 節點至少每 4 個月要登入一次(押金要花 4 個月提領);2. 節點直接拒絕 4 個月以上的回朔。

這對 PoW 擁護者來說是個令人厭惡的肉中刺,因為這感覺是一個「信任假設」:每一次同步區塊時,你必須先信任某個來源以取得區塊鏈。但是對我們這些齷齪的主觀主義者來說,這不是大問題:不管在哪一種情況,你都需要某個可信來源告訴你區塊鏈所使用的共識規則(也別忘了軟體更新),所以 PoS 所需的額外信任並不大(這裡是Vlad的覆述)。

確立了押金及罰金的使用後,我們接下來要決定它們「是什麼」。我們知道我們希望的是「經濟敲定性」,驗證者將會基於以下方式對區塊簽名:一旦一個區塊被敲定,如果要敲定一個衝突的區塊,則必須要有大部分的驗證者簽出與自己先前訊息衝突的訊息。但對於這樣的訊息,可以被鏈偵測並懲罰。

我寫了一篇又臭又長又離題的「賭注共識」文章。賭注共識是一個有趣的提案:驗證者下注哪一個區塊會被敲定,而賭注決定了哪一個鏈會形成共識。PoW 也具有這樣的性質,因為挖礦是一種賭注。如果你賭注在對的鏈上,你會獲得獎勵;如果你賭注在錯的鏈上,你失去挖礦成本。但在 PoS 我們可以有更高的賠率:驗證者的賠率一開始很低,但是隨著驗證者看到彼此對於某個區塊的信心逐漸增加,所有人的賠率都會平行地指數上升,直到所有人都賭注同一個區塊,這就是敲定。


Casper CBC

同時,Vlad 開始大量研究機制設計,特別是讓 Casper 更能抵抗寡占。我們也開始研究受到古典拜占庭容錯(BFT)啟發的共識,例如 Tendermint。Vlad 認為古典 BFT 並沒有說服力(他特別不喜歡 BFT 當中的硬門檻,例如 2/3 的 PBFT 節點必須為誠實節點),他想透過一個他稱為「正確建構(Correct by Construction, CBC)」的方法嘗試重新發明 BFT( Vlad 的原話:連結1/連結2/連結3)。

正確建構的哲學與傳統 BFT 相當不同的點在於「敲定」是完全主觀的。CBC 的哲學是,驗證節點對訊息簽名,且若他們簽了與他們先前的訊息相抵觸的訊息,則他們必須提交一個「辯護(Justification)」以證明他們投票的新訊息與舊訊息相比之下有較多的支持,以取得「轉換」的權利。

為了偵測敲定性,節點尋求訊息的模式。這些訊息可以證明,多數驗證節點以一種方式可靠地對某區塊 B 投票,且偏離 B 必須大部分驗證者非法轉換投票。例如,若所有節點投給 B,則所有節點都投給「包含所有人對 B 的投票的區塊」,這證明了他們支持 B 且知道其他所有人都支持 B,因此他們不會有轉換的合法理由。

最後我放棄了賭注共識,因為這個方法似乎有根本上的風險。我也回頭試著理解 PBFT 是怎麼運作的。雖然這花了一點時間,但過了幾個月後我搞懂了。


Casper FFG

我試著簡化了 PBFT,將其放入區塊鏈的脈絡,並把它描述為 4 個「砍押金條件(Slashing Condition)」,這些規則闡述哪些訊息的組合是自我抵觸因此違反規則的。我定義了決定區塊是否敲定的規則並且證明了最關鍵的「安全性(Safety)」與「可行活躍性(Plausible Liveness)」:1. 若某區塊被敲定了,則無法在不少於 1/3 驗證者違反砍押金條件下敲定另一個抵觸的區塊; 2. 若某區塊被敲定了,2/3 誠實的驗證者總是可以合作以敲定新的區塊。因此只要有 2/3 誠實的驗證者,演算法就不會推翻之前的決定(安全性)或卡住(活躍性)。最後我將砍押金條件從 4 條簡化成 2 條,並發展成 Casper FFG — 被設計成為任何 PoW/PoS/其他類型區塊鏈提供敲定性的覆蓋層。

敲定性是一個非常重要的進展:一旦區塊被敲定,無論網路怎麼延遲都能保證安全(不像 PoW 需要多個區塊確認),而且回朔區塊需要超過1/3驗證者作弊,且可被檢測出來且並銷毀押金。因此,回朔敲定性的成本可能會高達數億美元。透過不同的方式,Casper CBC 以及 FFG 都達到了這個特性。

要注意的是:Casper CBC 和 FFG 都是抽象的覆蓋層,他們都需要建立在某個現有的分岔選擇規則之上。用大白話講,Casper CBC 是敲定覆蓋層(上層)適應分岔選擇規則(下層);而 Casper FFG 是分岔選擇規則(下層)適應敲定覆蓋層(上層)。


FFG vs CBC

Vlad 最初對分岔選擇規則的偏好是「最新訊息驅動 GHOST(Latest Message-Driven GHOST, LMD GHOST)」 — 一種針對 PoS 的改版 GHOST;而我最初的偏好是先採取「混合式 PoS(Hybrid PoS)」,使用 PoW 作為基底的分岔選擇規則。

在最初版的 FFG 當中,PoW 將會逐個區塊地運作一條鏈,而 PoS 將會緊隨在後敲定區塊;Casper CBC 從一開始就是完整的 PoS。同時,Vlad 跟我各自提出了共識誘因的理論。

這裏有一個非常重要的區別是「唯一可歸責錯誤(Uniquely Attributable Faults)」 – 你可以知道出錯時誰應該負責而被懲罰,以及「非唯一可歸責錯誤(Non-uniquely Attributable Faults)」 – 一個錯誤可能是多方中的一方造成的。一個非唯一可歸責錯誤的經典案例是離線 vs 屏蔽(Censorship),也稱為「言者-聽者錯誤等效性」(譯按:到底是言者沒講,還是聽者沒聽到,無法判定是誰的錯)。

懲罰唯一可歸責錯誤(Casper FFG 砍押金條件)是容易的;懲罰非唯一可歸責錯誤則是困難的。如果你無法分辨區塊停止敲定是因為少數的節點離線或是因為多數的節點正在屏蔽少數會怎麼樣?針對這個議題目前有三種解法:1. 輕微地懲罰兩邊;2. 嚴厲地懲罰兩邊(Vlad 的偏好);3. 將鏈一分為二,各自懲罰兩條鏈的其中一邊,且讓市場決定哪條鏈較有價值(我的偏好)。或者可以參考我寫的這篇

2017 年 11 月,我把 Casper FFG 砍押金條件以及對由於「平方溢金(Quadratic Leak)」(譯按:隨著離線時間增加,對押金的少量扣減會平方增加)導致的1/3節點離線的問題的解法寫成論文

當然,我非常清楚訴諸社交層面來解決 51% 攻擊並不是很好,因此我開始尋求至少能讓鏈上節點能自動偵測「合法鏈」與「攻擊鏈」的方法。這是一個早期的想法。這想法還不錯,但是仍不是最理想的,除非網路毫無延遲,否則它只能保證節點之間嫌疑分數差異的上限,而並非所有節點完全同意。

同時,我對 Vlad 的模型的主要批判與「洩氣攻擊(Discouragement Attacks)」有關,攻擊者可以有效威脅要製造 51% 攻擊來造成所有人損失金錢,因而驅使所有其他人退出,因此只用極低的成本便能主導鏈。Vlad(以及Georgios Piliouras)開始建立經濟模型以評估在他的模型之下進行上述攻擊的實際成本。

值得一提的是,上述所有的議題並非為 PoS 獨有。事實上在 PoW 中,人們傾向直接放棄且假設預防 51% 攻擊幾乎不可能,且 51% 攻擊是必須不計代價避免的末日。但是,如同以太坊的傳統,Vlad 與我誤把「有野心的」這個詞當成讚美,而繼續研究減緩以及恢復 51% 攻擊的不同方法。

2018 年初,Vlad 在 CBC 的研究開始快速推進,包括安全性證明的進展。
— 看這個史詩般的 2 小時簡報以跟上 2018 年 3 月為止的研究進度同時,Casper FFG 也有了重大進展,以合約的方式實作的決定使開發工作變得容易。2017 年 12 月 31 日,我們發佈了 Python 版的測試網


Casper 與分片開發路線的整合

不幸地是,FFG 的開發慢了下來。以合約實作 FFG 雖然把一些事情變得更容易,卻讓未來要從 EVM 轉到 EWASM 以及從單鏈 Casper 轉到分片 Casper 的工作變得更困難。此外,團隊的研發工作被分成「主鏈 Casper」和「分片鏈Casper」,可想而知在這兩個團隊之間產生了大量不必要的重複工作。

2018 年 6 月,我們做了一個重大的決定:放棄以合約實作的 Casper FFG,取而代之的是追求以一條獨立鏈運作的 Casper,如此的設計將使分片變得更加容易。

完全 PoS 的轉換導致我開始更認真思考 PoS 的分岔選擇規則。Casper FFG 與 CBC 都需要全部的驗證節點在每個「時期(Epoch)」投票以敲定區塊,這代表每秒將會數以萬計的簽章傳向每個驗證節點。BLS 簽名聚合使其在計算成本上是可行的。但是我想試著利用這些額外的簽名以讓鏈更加穩固,在幾秒內取得等同於「100 個確認」的安全性。這裡是我初步的想法(連結1/連結2)。

然而,所有這些分岔選擇的方法都有一個缺點:它們都將驗證節點分為「見證節點(Attesters)」與「出塊節點(Proposers)」,而這些負責產生區塊的出塊節點擁有過大的權力。這樣做不太好,主要是因為它需要我們有一個很安全的鏈上亂數產生器以公平地挑選出塊節點,而鏈上亂數產生器很困難,而且一些簡單的方法例如 RANDAO 似乎有愈來愈多問題。Justin Drake 跟我開始解決這個問題:Justin 使用 VDF,這是一個輸出具有確定性與可驗證的函數,但需要大量不可平行化處理的序列時間進行運算,使提前竄改變得不可能;而我對 Vlad 教妥協,使用基於 GHOST 的分岔選擇規則以大幅減少對出塊節點的依賴,允許在惡意出塊節點大於90%且誠實見證節點大於50%的狀況下,鏈仍能不受干擾地成長。Vlad 很開心,但還沒開心到極點:他偏好 LMD GHOST,而我偏好 IMD GHOST

大約同一時間,我也試著想出一個方法來「流水線化」(Pipelining)Casper FFG,將敲定時間從 2.5 個時期減至理論上最佳的 2 個時期。我對 RPJ 分岔選擇規則(後來更名為 IMD GHOST)能夠很好地相容於FFG這件事感到開心。它還有一個很重要的「穩定性」:分岔選擇是一個對未來分岔選擇的好預測。這看起來很明顯,但我們卻很容易做出不具有這種特性的分岔規則。最近的進展是:LMD GHOST 可能由於技術細節只能在 2 回合中有25% 容錯,但是 IMD GHOST 仍可以有完整的 33% 容錯(目前沒有文件)。(譯按:在譯文完成時, 以太坊 2.0 採用的是LMD GHOST)

FFG 與 CBC 之間主要的取捨是:CBC 似乎有較好的理論性質;而 FFG 似乎比較容易實作。同時,VDF 也取得了許多進展

還有,我最近決定研究 Leslie Lamport 1982 年的老論文,在這邊論文中他提出了一個共識演算法:若假設所有節點,包括觀察者,皆在線上且具有很低的網路延遲,則具有 99% 容錯。網路延遲的假設按理來說會使其不適合作為主要的共識算法。然而,它可以在某一個情境運作相當良好:作為 51% 屏蔽偵測的嫌疑分數替代方案:基本上,如果 51% 共謀團體開始屏蔽區塊,其他驗證節點以及一般節點可以偵測到屏蔽的發生,並且使用 99% 容錯的共識演算法來達成屏蔽正在發生的共識,並協調少數分岔。關於這個研究的長期目標就是要盡可能減少對社交層的依賴,並將破壞鏈穩定的成本最大化,使其利用社交層回朔的可能性最小化。

還有什麼?FFG的部分還有形式化證明,規格的完善,以及實作的持續進展(已經有超過3個團隊開始著手了!),並著眼於安全及迅速的開發。CBC的部分也差不多。接下來讓我們勇往直前吧!

Taipei Ethereum Meetup

台北以太坊社群專欄

Thanks to Chih-Cheng Liang

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