原文：Aptos Labs
編譯：Aptos Global
https://arxiv.org/pdf/2306.03058.pdf
概述
1）Aptos labs 已經解決了DAG BFT中兩個重要的開放問題，大大地減少了延遲，並且首次消除了確定性實際協議中對暫停的需求。總的來說，在無故障情況下將Bullshark的延遲改進了40%，在故障情況下改進了80%。
2）Shoal 是一個框架，通過pipelining and leader reputation增強任何基於Narwhal 的共識協議（例如，DAG-Rider、Tusk、Bullshark）。流水線通過每輪引入一個錨點來減少DAG 排序延遲，領導者聲譽通過確保錨點與最快的驗證節點相關聯來進一步改善延遲問題。此外，領導者聲譽使Shoal 可以利用異步DAG 構造來消除所有場景中的超時。這允許Shoal 提供我們命名為普遍響應的屬性，它包含通常需要的Optimistic 響應。
3）我們的技術非常簡單，它涉及到按順序一個接一個地運行底層協議的多個實例。因此，當用Bullshark實例化時，我們得到一群正在進行接力賽的「鯊魚」。
動機
在追求區塊鍊網絡的高性能時，人們一直關注降低通信複雜性。然而，這種方法並沒有導致吞吐量的顯著提高。例如，在早期版本的Diem 中實現的Hotstuff 僅實現了3500 TPS，遠遠低於我們實現100k+ TPS 的目標。
然而，最近的突破源於認識到數據傳播是基於領導者的協議的主要瓶頸，並且它可以從並行化中受益。 Narwhal 系統將數據傳播與核心共識邏輯分離，並提出了一種架構，其中所有驗證者同時傳播數據，而共識組件僅訂購較少量的元數據。 Narwhal 論文報告了160,000 TPS 的吞吐量。
在之前的文章中，我們介紹了Quorum Store。我們的Narwhal 實現將數據傳播與共識分離，以及我們如何使用它來擴展我們當前的共識協議Jolteon。 Jolteon 是一種基於領導者的協議，結合了Tendermint 的線性快速路徑和PBFT 風格的視圖更改，可將Hotstuff 延遲降低33%。然而，很明顯，基於領導者的共識協議無法充分利用Narwhal 的吞吐量潛力。儘管將數據傳播與共識分開，但隨著吞吐量的增加，Hotstuff/Jolteon 的領導者仍然受到限制。
因此，我們決定在Narwhal DAG 之上部署Bullshark，一種零通信開銷的共識協議。不幸的是，與Jolteon 相比，支持Bullshark 高吞吐量的DAG 結構帶來了50% 的延遲代價。
在這篇文章中，我們介紹了Shoal 如何實現大幅減少Bullshark 延遲。
DAG-BFT 背景
讓我們從理解這篇文章的相關背景開始。關於Narwhal 和Bullshark 的詳細描述請參考DAG meets BFT 帖子。
https://decentralizedthoughts.github.io/2022-06-28-DAG-meets-BFT/
Narwhal DAG 中的每個頂點都與一個輪數相關聯。為了進入第r 輪，驗證者必須首先獲得屬於第r-1 輪的nf 個頂點。每個驗證者每輪可以廣播一個頂點，每個頂點至少引用前一輪的nf 個頂點。由於網絡異步性，不同的驗證者可能會在任何時間點觀察到DAG 的不同本地視圖。下面是一個可能的局部視圖的圖示：
圖1：第2 輪驗證節點2 識別的頂點的因果歷史以綠色突出顯示
DAG 的一個關鍵屬性不是模棱兩可的：如果兩個驗證節點在它們的DAG 本地視圖中具有相同的頂點v，那麼它們具有完全相同的v 因果歷史。
Total Order
可以在沒有額外通信開銷的情況下就DAG 中所有頂點的總順序達成一致。為此，DAG-Rider、Tusk 和Bullshark 中的驗證者將DAG 的結構解釋為一種共識協議，其中頂點代表提案，邊代表投票。
雖然DAG 結構上的群體交集邏輯不同，但所有現有的基於Narwhal 的共識協議都具有以下結構：
1）Predetermined anchors，每隔幾輪（例如，Bullshark 中的兩輪）就會有一個預先確定的領導者，領導者的頂點稱為錨點；
2）Ordering anchors， 驗證者獨立但確定性地決定訂購哪些錨點以及跳過哪些錨點；
3）Order causal histories，驗證者一個一個地處理他們的有序錨點列表，並且對於每個錨點，通過一些確定性規則對其因果歷史中所有先前無序的頂點進行排序。
圖二：Bullshark 協議中DAG 的可能局部視圖的圖示。在此示例中，紅色和黃色錨點被排序，而綠色（不在DAG 中）被跳過。因此，為了對DAG 進行排序，驗證節點確定性地首先對紅色錨點的因果歷史進行排序，緊隨其後的是黃色錨點。
滿足安全性的關鍵是確保在上面的步驟(2) 中，所有誠實的驗證節點創建一個有序錨點列表，以便所有列表共享相同的前綴。在Shoal，我們對上述所有協議做出以下觀察：
所有驗證者都同意第一個有序的錨點。
Bullshark 延遲
Bullshark 的延遲取決於DAG 中有序錨點之間的輪數。雖然Bullshark 最實用的部分同步版本比異步版本具有更好的延遲，但它遠非最佳。
問題1：平均塊延遲。在Bullshark 中，每個偶數輪都有一個錨點，每個奇數輪的頂點都被解釋為投票。常見情況下，需要兩輪DAG 才能訂購錨點，然而，anchor 的因果歷史中的頂點需要更多的輪次來等待anchor 被排序。在常見情況下，奇數輪中的頂點需要三輪，而偶數輪中的非錨點頂點需要四輪（見圖3）。
圖3：在常見情況下，第i+1 輪中的錨點需要排序兩輪。第i 輪中的頂點同時排序，因此它們的延遲為三輪。然而，第i+1 輪中的頂點必須等待下一個錨點被排序（第i+3 輪中的那個），因此它們的排序延遲為四輪。
問題2：故障案例延遲，上述延遲分析適用於無故障情況，另一方面，如果一輪的領導者未能足夠快地廣播錨點，則無法對錨點進行排序（因此被跳過），因此前幾輪中所有未排序的頂點必須等待下一個錨點被排序。這會顯著降低地理複製網絡的性能，特別是因為Bullshark 超時使用來等待領導者。
Shoal 框架
Shoal 解決了這兩個延遲問題，它通過pipelining 增強了Bullshark（或任何其他基於Narwhal 的BFT 協議），允許在每一輪中都有一個錨點，並將DAG 中所有非錨點頂點的延遲減少到三輪。 Shoal 還在DAG 中引入了零開銷領導者聲譽機制，這使得選擇偏向於快速領導者。
挑戰
DAG協議的背景下，流水線和領導者聲譽被認為是困難的問題，原因如下:
1）以前的pipelining試圖修改核心Bullshark 邏輯，但這從本質上講似乎是不可能的
2）Leader Reputation 在DiemBFT 中引入並在Carousel 中正式化，是根據驗證者過去的表現動態選擇未來領導者（Bullshark 中的錨）的想法。雖然在領導者身份上存在分歧並不違反這些協議中的安全性，但在Bullshark 中，它可能導致完全不同的排序，這引出了問題的核心，即動態和確定性地選擇輪錨是解決共識所必需的，而驗證者需要就有序歷史達成一致以選擇未來的錨。
作為問題難度的證據，我們注意到Bullshark的實現，包括目前在生產環境中的實現，都不支持這些特性。
協議
儘管存在上述挑戰，但正如俗話所說，事實證明解決方案隱藏在簡單的背後。
在Shoal 中，我們依靠在DAG 上執行本地計算的能力，並實現了保存和重新解釋前幾輪信息的能力。憑藉所有驗證者都同意第一個有序錨點的核心洞察力，Shoal 按順序組合多個Bullshark 實例對它們進行流水線處理，使得（1）第一個有序錨點是實例的切換點，以及（2）錨點的因果歷史用於計算領導者的聲譽。
Pipelining
與Bullshark 類似，驗證者先驗地就潛在的錨點達成一致，即，有一個已知的映射F：R -> V 將輪次映射到領導者。 Shoal 一個接一個地運行Bullshark 的實例，這樣對於每個實例，錨由映射F 預先確定。每個實例都訂購一個錨，這會觸發切換到下一個實例。
最初，Shoal 在DAG 的第一輪啟動Bullshark 的第一個實例並運行它直到確定第一個有序錨點，比如在第r 輪。所有驗證者都同意這個錨點。因此，所有驗證者都可以確定地同意從第r+1 輪開始重新解釋DAG。 Shoal 只是在第r+1 輪啟動了一個新的Bullshark 實例。
在最好的情況下，這允許Shoal 在每一輪都訂購一個錨。第一輪的錨點按第一個實例排序。然後，Shoal 在第二輪開始一個新的實例，它本身有一個錨點，該錨由該實例排序，然後，另一個新實例在第三輪中訂購錨點，然後該過程繼續。請參見下圖的說明：
圖4：與F 確定的領導者對應的頂點用皇冠標記，Bullshark 的第一個實例首先用第1、3 和5 輪中的錨點解釋DAG，Bullshark 確定第1 輪中的錨點（用綠色複選標記標記）是第一個在第一個實例中被排序的。 （請注意，在一般情況下，可以跳過此錨點，而其他一些錨點將首先被排序。）然後，第一個實例的其餘部分將被忽略，Bullshark 的新實例從第2 輪開始，錨點標記為在第2 輪和第4 輪中。
Leader reputation
在Bullshark 排序期間跳過錨點時，延遲會增加。在這種情況下，Pipelining技術無能為力，因為在前一個實例訂購錨點之前無法啟動新實例。 Shoal 通過使用信譽機制根據每個驗證節點最近活動的歷史為每個驗證節點分配一個分數來確保將來不太可能選擇相應的領導者來處理丟失的錨點。響應並參與協議的驗證者將獲得高分， 否則，驗證節點將被分配低分，因為它可能崩潰、緩慢或作惡。
其理念是在每次分數更新時，確定性地重新計算從回合到領導者的預定義映射F，偏向於得分較高的領導者。為了讓驗證者在新的映射上達成一致，他們應該在分數上達成一致，從而在用於派生分數的歷史上達成一致。
在Shoal 中，流水線和領導聲譽可以自然結合，因為它們都使用相同的核心技術，即在就第一個有序錨點達成一致後重新解釋DAG。
事實上，唯一的區別是，在第r 輪中對錨點進行排序後，驗證者只需根據第r 輪中有序錨點的因果歷史，從第r+1 輪開始計算新的映射F’。然後，驗證節點從第r+1 輪開始使用更新的錨點選擇函數F’ 執行Bullshark 的新實例。請參見下圖：
圖5. 與F 確定的領導者對應的頂點用透明冠標記。 Bullshark 的第一個實例在第1 輪中訂購了一個錨點，用綠色複選標記標記，然後，根據anchor 的因果歷史中的信息計算新的映射F’。由F’ 決定的領導人以彩色皇冠為標誌。
沒有更多超時
超時在所有基於leader的確定性部分同步BFT實現中起著至關重要的作用。然而，它們引入的複雜性增加了需要管理和觀察的內部狀態的數量，這增加了調試過程的複雜性，並且需要更多的可觀察性技術。
Timeout 也會顯著增加延遲，因為適當地配置它們非常重要，並且通常需要動態調整，因為它高度依賴於環境（網絡）。在轉移到下一個領導者之前，該協議會為有故障的領導者支付完整的超時延遲懲罰。因此，超時設置不能過於保守，但如果超時時間太短，協議可能會跳過好的領導者。例如，我們觀察到，在高負載情況下，Jolteon/Hotstuff 中的領導者不堪重負，並且在他們推動進展之前超時就已到期。
不幸的是，基於領導者的協議（如Hotstuff 和Jolteon）本質上需要超時，以確保每次領導者出現故障時協議都能取得進展。如果沒有超時，即使是崩潰的領導者也可能永遠停止協議。由於在異步期間無法區分有故障的領導者和緩慢的領導者，超時可能會導致驗證節點在沒有共識活躍度的情況下查看更改所有領導者。
在Bullshark 中，超時用於DAG 構造，以確保在同步期間誠實的領導者將錨點添加到DAG 的速度足夠快，以便對它們進行排序。
我們觀察到DAG 構造提供了一個估計網絡速度的“時鐘”。在沒有暫停的情況下，只要nf 個誠實的驗證者繼續向DAG 添加頂點，輪次就會繼續前進。雖然Bullshark 可能無法以網絡速度排序（由於領導者有問題），但DAG 仍然以網絡速度增長，儘管一些領導者有問題或網絡是異步的。最終，當一個無故障的領導者足夠快地廣播錨點時，錨點的整個因果歷史將被排序。
在我們的評估中，我們比較了Bullshark 在以下情況下有和沒有timeout：
1）快速領導者，意味著至少比其他驗證者更快。在這種情況下，兩種方法都提供相同的延遲，因為錨是有序的並且不使用超時。
2）錯誤的領導者，在這種情況下，沒有暫停的Bullshark 提供了更好的延遲，因為驗證節點將立即跳過它的錨點，而有暫停的驗證者將在繼續之前等待它們的到期。
3）緩慢的領導者，這是Bullshark 超時性能更好的唯一情況。這是因為，如果沒有暫停，錨點可能會被跳過，因為領導者無法足夠快地廣播它，而如果有暫停，驗證者將等待錨點。
在Shoal，避免超時和領導聲譽是密切相關的。重複等待緩慢的領導者會而增加延遲，領導者聲譽機制排除了緩慢的驗證者被選為領導者。通過這種方式，系統利用快速驗證節點在所有現實場景中以網絡速度運行。
請注意，FLP不可能性結果表明，沒有確定性共識協議可以避免超時。 Shoal不能規避這個結果，因為存在一個理論上的對抗性事件時間表，可以阻止所有錨被命令。相反，在可配置的連續跳過錨的數量之後，Shoal會退回到超時。實際上，這種情況極不可能發生。
普遍反應
Hotstuff 論文普及了樂觀響應的概念，雖然沒有正式定義，但直觀上它意味著協議可以在包括快速領導者和同步網絡的良好情況下以網絡速度運行。
Shoal提供了一個更好的屬性，我們稱之為普遍響應。具體來說，與Hotstuff相比，即使領導者在可配置的連續回合數或網絡經歷異步週期內失敗，Shoal也會繼續以網絡速度運行。請參閱下表中更詳細的比較。
請注意，普遍的響應性在異步期間和領導者出現故障時提供了嚴格更好的進度保證。在與慢速領導者同步期間，這些屬性是無法比較的，因為這取決於領導者有多慢。然而，鑑於領導者的聲譽，行動遲緩的領導者應該很少出現在Shoal中。
評估
我們在我們的Narwhal 實現Quorum Store 之上實現了Bullshark 和Shoal。 Shoal、Bullshark 和Jolteon 之間的詳細比較可以在Shoal 論文的評估部分找到，在這裡，我們提供了一些亮點。
首先，為了演示異步DAG構造的強大功能，我們比較了有暫停和沒有暫停的Bullshark。完整的Bullshark論文假設了一個異步網絡，但提供了快速路徑模式，因此在所有回合中都需要暫停。我們把這個版本稱為Vanilla Bullshark。我們觀察到，對於獨立的部分同步網絡假設版本，不需要投票輪中的暫停。我們把這個版本稱為沒有投票暫停的Vanilla Bullshark w/o Vote timeout，Baseline Bullshark 是沒有任何暫停的版本。
下圖比較了有無故障時超時對Bullshark 延遲的影響。顯然，Baseline Bullshark（無超時）在出現故障時表現最佳。在沒有失敗的情況下，Baseline Bullshark 與沒有投票暫停的Vanilla Bullshark 相當。這是因為，如前所述，如果沒有領導者信譽機制，超時可能在領導者好但慢的情況下具有優勢。
圖6.：超時對無故障（左）和有故障（右）的Bullshark 延遲的影響，失敗案例中有50 個驗證節點
接下來，我們使用Baseline Bullshark（無超時）實例化Shoal，並演示在有無故障的情況下流水線和領導者信譽機制的延遲改進，為了完整起見，我們還在無故障情況下將其與Jolteon 進行了比較。
下面的圖7 顯示了無故障情況，雖然流水線和領導聲譽都可以單獨減少延遲，但將它們組合在一起可以實現最佳延遲。
至於Jolteon，它無法擴展到超過20 個驗證節點，並且即使它運行在Quorum Store 之上，也只能達到Bullshark/Shoal 吞吐量的一半左右，這消除了數據傳播瓶頸。
結果表明，Shoal 極大地改善了Bullshark 延遲。至於Jolteon，重要的是要注意，儘管我們只測量了共識延遲。由於Jolteon 無法在DAG 之上本地運行，因此它需要額外的延遲來解耦數據傳播，我們沒有對此進行測量。因此，在高負載下，Shoal 應該與Jolteon 的端到端延遲相匹配。
圖7：無故障情況下的吞吐量和延遲，Shoal PL 和Shaol LR 分別僅支持流水線和領導聲譽。
下面的圖8 顯示了具有50 個驗證節點的失敗案例，其中領導者信譽機制通過降低失敗的驗證者被選為領導者的可能性來顯著改善延遲。請注意，在50 次失敗中有16 次失敗，Shoal 的延遲比Baseline Bullshark 低65%。
