具有未知和動態參與的拜占庭將軍的即時終結

作者：Dahlia Malkhi (Chainlink Labs), Atsuki Momose (UIUC), Ling Ren (UIUC)

概要

我們為拜占庭將軍問題提出了一個非常簡單的解決方案 確定性和無條件的安全保證 在具有未知和動態參與的環境中，但沒有工作量證明的能源浪費 或最長鏈協議的長延遲。有了這個，我們消除了中本聰共識的最大障礙，即概率確定性、高延遲和工作量證明的能源浪費，同時保留了無許可模型的關鍵原則。

在第一次遇到時，上述情況似乎令人生畏：參與者來來去去，甚至沒有已知的積極參與者數量，如何達成一致？

去掉工作量證明， Pass 和Shi 推出的“Sleepy”模型 借用了無許可設置的兩個核心支柱。一是連續性，要求 同步 在當前活躍的參與者之間傳播消息，以便在面對流失時進行知識轉移。第二個是，在任何時刻，都有一個未知的 和動態 一組具有誠實多數的活躍（和同步連接）方。在這兩種假設下（下面更準確地描述），Sleepy Consensus 解決了拜占庭協議，但繼承了 概率安全 最長鏈協議的高延遲。

在類似的未知和動態參與模型下（對同步有更實際的假設，即沒有無限緩衝）， Atsuki 和Ren 最近的結果 通過展示拜占庭協議的解決方案開闢了新天地 確定性的 安全 保證和預期的恆定延遲。然而，只有當參與在足夠長的時間內停止動態時，才能保證活躍度。此外，即使在這樣的時間段內，延遲的常數因素也有些大。

通過要求稍高的誠實參與門檻——三分之二而不是誠實多數——我們展示了一個非常簡單的解決方案，用於未知和動態參與模型中的拜占庭協議。它有 確定性和無條件的安全性 保證和 （小）恆定的預期延遲，克服了上述缺點。此外，我們是否提到它非常簡單？事實證明 以下，該算法看起來與具有靜態且已知參與者集的經典設置中的異步協議協議相比並沒有太大的難度或不同！

在這裡，我們展示了我們的範式解決了一次性 二進制拜占庭協議. 在未來的文章中，我們將（i）擴展到多值共識，（ii）擴展到共識決策鏈（即原子廣播問題），以及（iii）利用基於領導者的範式來改進平均案例輪次復雜。

未知和動態參與模型

為了便於說明，我們將時間視為離散的“輪次”。實際上，模型可以定義為，我們的解決方案可以擴展到連續時間。

為了在協議中提供知識的連續性，無許可協議實際上進行了強同步 假設：有一個已知的上限 關於每對誠實參與者（稱為“節點”）之間的通道傳播延遲，封裝在我們的回合模型中。

同步通信。 如果誠實節點p 在第r 輪中發送消息，則在第r+1 輪中活躍的每個誠實節點q 都會收到該消息。

無許可共識協議通常假設在積極參與者中佔多數。在這裡，我們需要更高的誠實參與者門檻。事實證明，這大大簡化了結構。

誠實參與。 在每一輪中，都有未知數量的積極參與者，其中三分之二以上是誠實的。

參與假設值得進一步澄清。在動態設置中，參與者在回合之間流失，包括錯誤。我們必須假設如果一個故障節點出現故障，它的消息不會出現在未來的輪次中。這是一個比之前的工作更弱的假設，之前的工作假設所有有缺陷的各方在整個執行過程中都是活躍的。

簡而言之，未知和動態參與模型. 總而言之，我們有以下模型。每個時刻的活躍節點集合是未知的，它們的數量是未知的，並且在每一輪中，它們可能會被完全替換，但須符合以下假設：

• PKI：參與節點取自有限宇宙，每個節點都可以通過擁有私鑰的公鑰來識別。
  • 注意，只有VRF 和liveness 才需要PKI； 消息不需要 簽 由他們的發件人
• 活躍節點：每一輪r都有一組未知的活躍節點 節點，其（未知）計數 n_r 滿足 n_r ≥3f_r + 1.
• 同步通信：在第r 輪中，誠實節點和活躍節點接收到誠實節點在第r-1 輪廣播的所有消息。

拜占庭協議問題

這個問題已經被描述過很多次了。簡而言之，在二元協議變體中，一組參與者最初持有一個輸入值∈ {0,1} （一點）並就滿足以下條件的輸出值達成一致：

• 安全: 兩個誠實方的輸出是一樣的
• 有效性：如果所有誠實方都以相同的輸入值開始，則輸出就是該值
• 活力: 最終所有誠實方輸出一個值

未知和動態參與模型中的二元協議

我們介紹一種一次性解決方案 保證安全的二進制協議和預期的（小）恆定輪數終止。

我們首先深入了解我們使用的可轉移性的關鍵機制。

未知和動態仲裁屬性(UDQ)。 每個節點在第(r+1) 輪中接收在第r 輪期間發送的一組消息。我們觀察到以下關鍵事實：

• 用R 表示一個誠實節點在第(r+1) 輪中收到的未知數量的消息。我們有 R ≤ n_r
• 由於同步，在R 消息中，至少 ⅔ n_r ≥ ⅔ R 消息是從誠實的round-r 節點接收的。
• 未知號碼 噸_r ≤ ⅓ R 來自R 的消息來自故障的round-r 節點。

假設每個協議消息都攜帶一個值。以下保證成立：

• UDQ 獨有： 在一輪中，如果一個節點p 接收到帶有值b 的絕大多數消息，而另一個節點q 接收到帶有值b’ 的絕大多數消息，則b = b’。請注意，UDQ-unique 提供與靜態設置中的quorum-intersection 類似的保證，但無法 轉移 一組簽名消息作為接收絕對多數的證明。
  
  UDQ-unique 成立，因為如果一個誠實節點p 在第(r+1) 輪中接收到絕大多數帶有值b 的第r 輪消息，那麼大多數誠實的第r 輪消息都帶有b。這是因為：
  ⅔ R – 噸_r = ⅔ (n_r – F_r +噸_r) – 噸_r = ½ (n_r – F_r) + ⅙ (n_r – F_r – 2噸_r) > ½ (n_r – F_r)

• UDQ 有效： 如果一個誠實節點在第(r+1)輪中接收到超過三分之一的輪r消息攜帶b，那麼某個誠實節點已經發送了攜帶b的消息。這與上述類似的推理成立：
  ⅓ (R – t_r) = ⅓ (n_r – F_r +噸_r) – t_r = ⅓ (n_r – F_r – 2噸_r) > 0

• UDQ 分級協議： 如果一個誠實節點p 在第(r+1) 輪中接收到絕大多數包含值b 的第r 輪消息，那麼超過三分之一的第r 輪消息被另一個誠實節點在第(r+1) 輪中接收包含b.

給定UDQ，很容易在兩個廣播步驟中構建一個單次、二進制協議協議。它的工作原理如下。

該協議以節點通告其輸入的一輪開始，然後繼續在 收集-GA 回合 和 決策GA 輪次。 在一輪中，活動節點監聽傳入的消息（在前一輪廣播），處理它們，並廣播一條消息。

節點p 的協議

初始化第0 輪：

• 一個節點向所有節點廣播（0，收集，輸入）

集合-GA r+1：

• 令S-collect 為接收到的消息集(r, collect,*)
• 一個節點向所有節點廣播：
  (r+1, proposal, b) 如果超過三分之二的S-collect 是(r, collect, b)
  (r+1, 提議, “空”) 否則
• 同時，一個節點向所有節點廣播：
  (r+1, VRF, c) 其中 c 是一個隨機位

決策-GA r+2：

• 令S-propose 為接收到的消息集合(r+1, proposal,*)
• 節點p 處理S-propose 如下：
  決定b：如果超過三分之二的S-propose是(r+1,proposal,b)
  採用 vp ← b：如果超過三分之一的S-propose是(r+1,proposal,b)
  採用 vp ← 值v in (r+1, VRF, v) 具有最高VRF：否則
• 一個節點p 向所有節點廣播：(r+2, collect, vp)

在收集-GA 輪中，節點收集包含其他節點採用的值的消息。在collection-GA輪結束時，如果一個節點收到超過三分之二的（collect，b）對於某個值b，那麼它廣播（propose，b）； 否則，它會廣播（提議，“空”）。同時，一個節點廣播(VRF, c)，其中VRF是一個唯一的偽隨機值，可以使用節點的公鑰和輪數進行驗證，c是本地拋硬幣。請注意，在執行的第一輪，節點發送帶有自己輸入的收集消息。

在決策GA 輪中，節點收集（提議，*）。接收超過三分之二（propose，b）消息的每個節點 決定 灣。接收超過三分之一的每個節點（提議，b） 採用 b 作為當前值。其他節點採用消息（VRF，b’）中的隨機值b’，其（已驗證）VRF 值是它們收到的所有VRF 中最高的。在決策GA 輪結束時，每個節點p 廣播（收集，vp) 載有其採用的價值。

正確性（草圖）

索賠-1 [Unique-adopt]. 在決策GA 中，最多可以強制採用一個值b。為了被採用，一個值必須被前一個集合GA的消息的三分之一以上接收到。通過UDQ-valid，它由一位誠實的發送者發送。然而，通過UDQ-unique，一個集合GA 中的誠實節點最多可以廣播一個值b。

索賠2 [Safety]. 如果一個誠實節點在決策GA 中決定b，那麼通過UDQ-GA，每個其他誠實節點都會收到超過三分之一的先前集合GA 攜帶的消息（提議，b）。通過Unique-adopt，只能強制採用b。因此，每個誠實方在決策-GA 中都採用b。很容易看出，從所有誠實節點採用b 開始的集合GA 和決策GA 迭代以所有誠實節點決定b 結束。

索賠 3 [Termination]. 再一次，如果所有誠實節點都以b 開頭，則終止很容易。如果沒有做出決定，通過UDQ-adopt，最多可以強制採用一個值b。在概率為½ 的情況下，b 將成為獲勝的VRF 值並被所有人採用。

具有未知和動態參與的解決方案

致謝

我們從與Lorenzo Alvisi、Ittay Eyal、Jacob Leshno、Kartik Nayak、Youer Pu 的討論中受益匪淺。

推薦閱讀

• [Pass, Shi, 2016] 昏昏欲睡的共識模型
• [Bagaria, Kannan, Tse, Fanti, Viswanath, 2019] 棱鏡：解構區塊鏈以接近物理極限。
• [Khanchandani, Wattenhofer, 2021] 與未知參與者和失敗的拜占庭協議
• [Lewis-Pye, Roughgarden, 2021] 無許可環境中的拜占庭將軍
• [Goyal, Li, Raizes, 2021] Sleepy 模型中的即時區塊確認
• [Deb, Kannan, Tse, 2021] PoSAT：工作證明的可用性和不可預測性，沒有工作
• [Pu, Alvisi, Eyal, 2022] 安全無許可共識
• [Guo, Ren, 2022] 比特幣的延遲安全分析變得簡單
• [Atsuki, Ren, 2022] Sleepy共識中的恆定延遲