作者：Dahlia Malkhi (Chainlink Labs), Atsuki Momose (UIUC), Ling Ren (UIUC)
概要
在一個 以前的帖子，我們提出了一個簡單的解決方案 一發， 二進制 與隨時可能被替換的未知/動態參與者達成的拜占庭協議，條件是三分之二的活躍參與者是誠實的，保證確定性和無條件的最終性，並具有（小）恆定的預期延遲。
在這篇文章中，我們將方法擴展到對一系列值的多值共識，即解決 拜占庭原子廣播(BAB) 問題。我們的協議繼承了上一篇文章相對於現有解決方案的以下優勢：1） 小3 輪延遲， 2) 確定性和無條件的安全性，3) 不需要最終穩定參與，4) 允許故障節點的波動參與。
模型回顧。 活躍參與者的集合（也稱為節點）是未知的，它們的數量是未知的，並且在每一輪中，它們可能會被完全替換，但須符合以下假設：
- 公鑰基礎設施。 參與節點取自有限的宇宙，每個節點都可以通過它擁有私鑰的公鑰來識別。
- 注意，只有VRF 和liveness 才需要PKI； 消息做 不是 需要由他們的發件人簽名
- 活動節點。 每一輪r 都有一組未知的活躍 節點，其（未知）計數 nr 滿足 nr ≥ 3fr + 1 ， 在哪裡 Fr 是拜占庭.
- 同步通信。 在第r 輪中，誠實和活躍的節點接收到誠實節點在第r-1 輪中廣播的所有消息。
我們還注意到，來自故障節點的任何消息都不能延遲到未來的輪次。
原子廣播。 該協議允許節點就不斷增長的值序列（節點輸入）達成一致，這樣：
- 安全。 兩個誠實節點不會決定序列相同位置的值。
- 活潑。 誠實節點的輸入值最終確定。
我們的協議
鏈接。 我們使用區塊鏈的常用技術。每個塊都包含一些值（例如，新交易）以及前一個塊的散列。第一個塊包括一個特殊的預定義塊的哈希值，稱為“創世”塊。我們說塊B’ 延伸 如果以B 結尾的序列是以B 結尾的序列的前綴，則為塊B。如果兩個塊不相互擴展，我們說它們是 矛盾的.
分級協議(GA)。 我們在上一篇文章中的BA 協議有兩個非常相似的通信步驟。每個步驟都實現了一個稱為分級協議(GA) 的抽象。我們首先介紹這個GA 構建塊，然後用它來構建我們的原子廣播協議。
在未知且動態參與的情況下，這一輪（GA）開始時的活躍節點集合可能與GA結束時的活躍節點集合（下一輪活躍節點）不同。 GA 開始處的每個活動節點都有一個輸入塊B。 GA 結束處的每個（新）活動節點確定塊B 和等級位g 對的集合{ (B, g) } 作為輸出GA。我們再次強調，我們使用了區塊鏈，所以一個區塊B 唯一地標識了從genesis 開始到B 結束的整個區塊序列。
我們的GA 協議
在GA 開始時，每個活動節點p 為其輸入B 發送(vote, B)。
（從GA 開始的活動節點集現在可以被替換，即，不同的節點集現在可以接收並統計選票。）
在GA 結束時，每個活躍節點都會統計選票。如果B’ 擴展了B，那麼對B’ 的投票也算作對B 的投票。來自同一選民的衝突塊的投票將被忽略。
- 如果超過2/3 的已收到選票投給B，則輸出(B, 1)。
- 如果超過1/3 的已收到選票投給B，則輸出(B, 0)。
遺傳算法的屬性。 通過上一篇文章中的UDQ 屬性，我們有以下保證。
- 分級一致性。 如果一個誠實節點輸出（B，1），那麼所有誠實節點都輸出（B，*）。
- 正直。 如果一個誠實節點輸出(B, *)，那麼至少有一個誠實節點輸入擴展B 的B’。
- 有效性。 令B 為誠實節點輸入的最高共同祖先。然後，所有誠實節點輸出(B, 1)
- 獨特性。 如果一個誠實節點輸出(B, 1) 而另一個誠實節點輸出(B’, 1)，則B 和B’ 不會相互衝突。
- 有界分歧。 每個節點最多輸出（0 級）兩個衝突塊。
我們的原子廣播協議。 我們現在給出我們的原子廣播協議。變量 C, 大號 被初始化為創世。 (C： 候選人， 大號： 鎖）
每個視圖有兩個回合。在第一個視圖v = 1 開始之前有一個額外的初始回合。
首輪0： 發送（提議，B，VRF），其中B 是擴展創世的塊。
第1 輪視圖v：
如果v > 1：
決定任何塊B 使得視圖v-1 的GA2 輸出(B, 1)
放 大號 到最高塊，使得視圖v-1 的GA2 輸出 (大號*)
向GA1 輸入上一輪“提議”消息中VRF 最高的區塊，該區塊擴展 大號.
如果沒有這樣的塊，輸入 大號 到GA1。
第2 輪視圖v：
將B 設置為最高塊，以便GA1 輸出(B, 1)。
放 C 到一個最高塊，這樣GA1 輸出（C, *)。 （如果有兩個這樣的 C，隨機選擇一個。 ）
將B 輸入到GA2。
發送（提議，B’，VRF），其中B’ 擴展 C.
校樣草圖
安全。 假設一個誠實的活動節點在視圖v 的第1 輪中決定塊B，即它從視圖v-1 中開始的GA2 輸出(B, 1)。由於分級一致性，在視圖v 的第1 輪中活躍的任何誠實節點p 都必須輸出(B, *)。還要觀察視圖v-1 的GA2 不能輸出任何衝突塊。這是因為沒有誠實節點可以向視圖v-1 的GA2 輸入任何衝突塊（由於GA1 的唯一性），並且GA2 不能在沒有某些誠實節點輸入的情況下輸出任何衝突塊（由於完整性）。因此p 必須在視圖v 的第一輪中將L 設置為擴展B 的塊。視圖v 中的兩個GA 以及在v 之後的所有視圖中歸納地僅輸出擴展B 的塊（由於有效性）。所以沒有誠實的節點決定任何衝突的塊。
活潑。 讓我們將視圖v-1 中發送最高VRF 的節點稱為視圖v 的領導者。顯然，如果所有誠實的活動節點都向視圖v 的GA1 輸入誠實領導者的提議，則必須決定提議的塊。一個誠實的節點p 沒有將領導者的提議輸入到GA1 的唯一原因是它與它的鎖L 衝突。節點p 必須具有從前一個視圖v-1 開始的GA2 的輸出(L, *)。那麼，某個誠實節點q 在視圖v-1 的GA1 中輸出(L, 1) 後，必須有輸入L（或擴展L 的塊）到GA2。因此，視圖v 的領導者在視圖v-1 的GA1 中輸出（L，0）（由於分級一致性）。由於有界分歧，領導者最多從視圖v-1 的GA1 輸出一個其他衝突塊。因此，領導者以至少1/2 的概率提議擴展L 的塊，並且所有誠實節點都接受領導者的提議。
討論
在本文開頭列出的四個基本優勢中， 我們強調了與現有解決方案相比的兩個重要的實際優勢。
3 輪延遲。 我們協議的一個重要實際優勢是實際延遲：只有3 輪。相比之下，之前最先進的 [Momose-Ren 2022] 花費16輪。這種改善歸因於兩個因素。首先，我們通過犧牲½ 到1/3 的容錯性，將GA 的延遲從3 輪提高到1 輪。其次，更重要的是，我們通過將GA 調用次數從5 次減少到2 次來改進原子廣播協議。
故障節點波動。 如上一篇文章所述，我們的協議不僅允許誠實節點，還允許故障節點在執行期間加入/離開。這是一個重要的實際優勢，因為所有沒有工作量證明（或可驗證延遲函數）的現有解決方案都假設故障節點一直在線（如圖所示） [Deb-Kannan-Tse, 2021]）。這種對對手的限制很難證明是合理的。假設一開始只有10 個節點處於活動狀態，但10 年後，有一百萬個節點處於活動狀態。然後，現有的解決方案將不得不假設攻擊者最多控制100 萬個活動節點中的10 個。我們的協議仍然可以容忍⅓ 百萬故障活動節點。
有關區塊鏈、智能合約和預言機的最新研究， 訂閱Chainlink 時事通訊 和 關注Chainlink 官方推特。