Vitalik 親述：CBC Casper 教程

由 熱鏈中的人 於 12 月 10, 2018

原文作者：Vitalik Buterin
本文翻譯：喏唄爾
來源：Unitimes 獨角時代

爲了幫助更多人理解「另一版本的 Casper」（Vlad Zamfir 所提出的 CBC Casper），尤其是最適合區塊鏈協議的實例化，我想我會親自撰寫一份解釋，從一個不那麼抽象並且更「接近於具體用法」的角度進行闡述。Vlad 關於 CBC Casper 的描述可以參閱此處 [1]。我們歡迎大家積極探討這些材料。

CBC Casper 的設計基礎非常全面且抽象，並且其幾乎對任何數據結構都能達成共識——你可以使用 CBC 來決定到底選擇 0 還是選擇 1；你可以在 CBC 上運行一條簡單的區塊相接的鏈，或者的 92 次方維超立方體纏結 DAG，以及它們之間的幾乎任何東西。

但爲了簡單起見，我們首先將注意力集中在一個具體的案例上：一個簡單的基於鏈的結構。我們假設有一個由 N 個驗證者組成的固定的驗證者集合（即傳說中的「押注節點」。我們還假設每個節點都押注相同數量的幣，對於不滿足這一假設的情形，我們可以通過給一些節點分配多個驗證者 ID 來進行模擬）。我們把時間分解爲長度爲十秒的時隙，並且驗證者 k 可以在 k，N + k，2N + k 等時隙中創建區塊。每個區塊指向一個特定的母區塊。顯然，如果我們想要創造一些最簡單的東西，我們只需採用這種結構，在它上面實施最長鏈規則，並稱之爲一天。

綠色的鏈是最長鏈（長度爲 6），因此它被認爲是「權威鏈」。

然而，在這裏我們的重點是要增加一些「最終化」的概念：即某些區塊能夠在鏈上得到極其穩固的認可，穩固到其無法被其它競爭區塊所取代，除非有數量極其龐大（比如 1/4）的驗證者作出某些獨特的可歸因的錯誤行爲（比如以某種明顯且可被密碼學驗證爲惡意的行爲行事）。如果很大一部分驗證者確實採取惡意行動來回滾區塊，那麼這一惡意行爲的證據將被提交到鏈，從而罰沒這些驗證者的全部保證金。如此一來，回滾敲定結果的成本將會非常昂貴（想想，白花花的幾億美金）。

LMD GHOST

這一部分的內容我們不妨徐徐展開。首先，我們替換了分叉選擇規則（在衆多選項中決定哪條鏈是「權威鏈」的規則，即哪條鏈應爲用戶所關注）。我們不再選用簡單的最長鏈規則，而是改用「由最新消息驅動的 GHOST」。爲了說明 LMD GHOST 的工作原理，我們將修改上述例子。爲了使其更加具體，我們不妨假設驗證者集合的大小爲 5，並將其中每一位驗證者分別標記爲 A，B，C，D，E。由此，驗證者 A 在第 0 個和第 5 個時隙生成區塊，驗證者 B 在第 1 個和第 6 個時隙生成區塊，依此類推。評估 LMD GHOST 分叉選擇規則的客戶端只關注由每一個驗證者簽署的最新（即最高時隙）消息（即區塊）：

藍色表示最新的消息，從左到右時隙依次遞增（例如，最左端的 A 的區塊位於第 0 個時隙，依此類推）

現在，我們僅使用這些消息作爲「貪婪的最重觀察子樹（GHOST）」的分叉選擇規則的源數據：從創世區塊開始，然後每次都要進行一次分叉選擇，選擇擁有更多最新消息支持的區塊的子樹的一側（即更多最新消息支持該區塊或者該區塊的其中一個後代），並繼續執行直到到達沒有子代的區塊。我們可以爲每個區塊計算支持其自身或者它其中一個後代的最新消息的子集：

現在，爲了計算頭部，我們從頭開始，然後在每一個分叉選擇更高的數字：首先，選擇底下的鏈，因爲相比起上面這條只有 1 條最新消息支持的單一區塊鏈條，底下的鏈有 4 條支持自己的最新消息，然後在下一個分叉支持中間的鏈。最終的結果與最長鏈相同。事實上，在一個運行良好（即孤兒率很低）的網絡中，大多數時候 LMD GHOST 和最長鏈規則都會給出完全相同的答案。但在更極端的情形中，就不一定是這樣了。例如，我們不妨考慮下述這條鏈，其發生了三區塊分叉：

依據鏈的長度爲區塊賦予權重。如果我們遵循最長鏈規則，那麼由於頂鏈更長，所以頂鏈獲勝。

依照支持該鏈的最新消息的數量，並使用 GHOST 規則對區塊賦予權重（最新消息來自圖中用藍色標示的驗證者）。底下的鏈當前獲得更多驗證者的支持。因此，如果我們遵循 LMD GHOST 規則，那麼底下的鏈將獲勝，儘管我們暫不清楚這三個區塊誰處於優先狀態。

LMD GHOST 方法在某些情形中具有過人的優勢，它可以更好地在高延遲條件下提取信息。如果兩個驗證者分別創建出一個共享同一個母代的區塊，那麼實際上它們可以被認爲是對母區塊表示共同支持，即使它們同時也在爲自己競爭選票。最長鏈規則無法捕捉到這種細微的差別，而基於 GHOST 的規則可以。

檢測最終化

LMD GHOST 方法還有另外一個很棒的特性：它的黏性很大。例如，假設在兩輪投票中，4/5 的驗證者都投票給同一條鏈（我們假設這五個驗證者中的驗證者 B 沒有進行投票，此刻 B 正在進行攻擊）：

如果想要成爲權威鏈，最上面的鏈需要做什麼？已經有四個驗證者基於 E 的第一個區塊來構建新的區塊，並且這四個驗證者都確認了 E 在 LMD 分叉選擇中擁有最高的權重。僅僅通過查看這條鏈的結構，我們就可以知道，驗證者必須在不同時間內至少看到某些消息。以下是我們所獲知的這四個驗證者的視圖：

A\’s View

C\’s View

D\’s View

E\’s View

綠色表示每個驗證者所生成的區塊，藍色表示我們所知道的他們從其他驗證者處看到的最新消息。

需要注意的是，這四個驗證者都可以看到 B 的其中一個甚至兩個區塊，而 D 和 E 可以看到 C 的第二個區塊，因此他們把這而不是 C 的第一個區塊作爲視圖中的最新消息。然而，我們無法通過鏈的結構本身來證明他們確實是這麼做的。所幸的是，正如我們將在下面看到的，這種模糊狀況對於我們來說無關緊要。

A 的視圖包含支持底鏈的四條最新消息，而沒有支持 B 的區塊的消息。因此，在（我們模擬的） A 的眼中，支持底鏈的權重至少爲 4 比 1。 C，D 和 E 的視圖描繪了類似的情形，即均有四條支持底鏈的最新消息。因此，這四個驗證者都無法輕易改變主意，除非另外兩個驗證者首先改變他們的想法，將得分改爲 2 比 3，從而支持 B 的區塊。

請注意，我們對驗證者的視圖的模擬是「過時的」。例如，他並不知情 D 和 E 已經看到 C 最新的區塊。然而，這並不會改變頂鏈和底鏈對決的計算結果。因爲我們可以非常普遍地認爲，任何驗證者的新消息都會與其之前的消息具有相同的意見，除非另外兩個驗證者已經先切換了隊列。

最小的可行攻擊。A 和 C 非法切換隊列，改爲支持 B 的區塊（並且可能因此受到懲罰）。這一行爲最終導致頂鏈和底鏈 3 比 2 的結果，這時 D 和 E 就可以合法切換隊列了。

由於諸如 LMD GHOST 之類的分叉選擇規則在這一方面的黏性很大，並且客戶端可以檢測到分叉選擇規則何時「黏在」特定的區塊上，因此我們可以使用這種方法作爲實現異步安全共識的方式。

安全性預言機

事實上，檢測鏈條黏在某個區塊上的所有可能情況（在 CBC 術語中，這一區塊「已被確定」或者「是安全的」）是非常困難的，但我們可以提出一套啓發式方法（「安全性預言機」）來幫助我們檢測可能會發生這種情況的案例。其中最簡單的是團預言機（clique oracle）。如果存在一個驗證者子集 V，並且該子集在支持某個區塊 B 的總驗證者集合中佔比爲 p （p> 1/2），並且在下一輪中，使區塊通過引用其在第一輪中的選擇依舊支持 B，那麼我們可以推理如下：

經過兩輪的消息傳遞，我們知道該子集 V 都（i）支持 B；（ii）知道 B 得到大量支持。因此，除非有足夠數量的其他驗證者率先切換，否則他們都不能合法地進行切換。對於擊敗 B 的競爭者 B\’，B\’ 可以合法擁有的支持最多爲 1-p （每個驗證者都不屬於團的一部分），但爲了贏得 LMD GHOST 分叉選擇，其支持率需要達到 1/2，所以至少需要有 1/2 – (1-p) = p – 1/2 的驗證者非法切換隊列，以實現 LMD GHOST 規則支持 B\’ 的目的。

作爲一個具體案例，請注意 p = 3/4 團預言機提供了 1/4 級別的安全性，並且只要有 3/4 的節點在線，我們就可以生成（在正常情況中）滿足團的區塊集合。因此，從 BFT 的角度來看，就活性和安全性而言，使用兩輪團預言機可以達到的容錯閾值爲 1/4。

這種達成共識的方法有很多優勢。首先，短期鏈選擇算法和「最終化算法」這兩個組件並沒有被笨拙地組合在一起（這也是 Casper FFG 的一大缺憾）。相反，它們都是同一個連貫整體的一部分。其次，由於安全性檢測是在客戶端一側進行的，因此我們無需在協議中選擇任何閾值。客戶端可以自行決定什麼級別的安全性足以將區塊視爲最終確定。

進一步探討

CBC 可以通過多種方式來進一步擴展。首先，人們可以提出其它安全性預言機，比如更高輪次的團預言機可以達到 1/3 的容錯能力。其次，我們可以添加驗證者輪換機制。最簡單的方法就是每次 q = 3/4 團預言機得到滿足時，就改變驗證者集合的一小部分。我們也可以使用其它方案。第三，我們不一定拘泥於鏈式結構，我們可以查看增加每單位時間消息密度的結構，例如 Serenity 信標鏈的證明結構：

在這一情形中，將證明與區塊分開是值得的。區塊是使底層 DAG 增長的對象，而證明則有助於分叉選擇規則。在 Serenity 信標鏈規範 [2] 中，每個區塊可能有成百上千個與之對應的證明。但是，無論你採用哪種方式，CBC Casper 的核心邏輯都是一樣的。

爲了使 CBC Casper 的安全性「滿足加密經濟效益」，我們需要增加有效性和削減條件。首先，我們將從有效性規則開始。區塊包含母區塊和它所知道的一組證明，這些證明還不是鏈的一部分（類似於當前以太坊 PoW 鏈中的「叔區塊」）。爲了使區塊生效，區塊的母代必須是執行 LMD GHOST 分叉選擇規則的結果，並且這一結果必須依據被包含在包括該區塊的特定鏈中的信息來進行計算。

虛線是叔鏈接。例如，當 E 創建一個區塊時，E 注意到 C 還不是鏈的一部分，因此其包含對 C 的引用。

現在我們可以只用一個削減條件來保證 CBC Casper 的安全性：你不能同時做兩個證明 M1 和 M2，除非 M1 在 M2 證明的鏈中或 M2 在 M1 證明的鏈中。

Not OK

有效性和削減條件相對容易描述，儘管實際實現中需要檢查哈希鏈 , 並執行滿足共識的分叉選擇規則，因此它不像接收兩條消息並檢查這些消息所提交的數字之間的不等式那麼簡單（這是 Casper FFG 中 NO_SURROUND 和 NO_DBL_VOTE 削減條件 [3] 的做法）。

CBC Casper 的活性疊加了基礎鏈算法的活性（例如，如果它是每個時隙出一個區塊，那麼它將依賴於所有節點將在時隙 N+1 開始之前看到在時隙 N 中所產生的所有內容這一同步假設）。這種方法不存在網絡卡死的狀況。在任何情形下，我們都可以對新區塊進行最終化，即使網絡中存在攻擊者和 / 或網絡延遲高於底層鏈算法的閾值。

假設在某個時刻 T，網絡「獲得安寧」並再次滿足同步假設。然後，每個驗證者都會對同一條鏈的視圖趨於一致，並且擁有同一個頭部 H。從那裏開始，驗證者將簽署支持 H 或 H 的後代的消息，並且鏈條將順利發展，最終滿足團預言機，即 H 被最終敲定。