Shoal框架解析:大幅降低Aptos上的Bullshark延遲

Aptos Labs近期解決了DAG BFT中兩個關鍵問題,顯著降低了延遲,並首次在確定性實時協議中消除了對超時的需求。總體而言,在無故障情況下Bullshark的延遲改進了40%,在故障情況下改進了80%。

Shoal是一個框架,通過流水線和領導者聲譽機制增強基於Narwhal的共識協議(如DAG-Rider、Tusk、Bullshark)。流水線通過每輪引入錨點來減少DAG排序延遲,領導者聲譽通過確保錨點與最快的驗證節點關聯來進一步改善延遲。此外,領導者聲譽使Shoal能夠利用異步DAG構建來消除所有場景中的超時。這使Shoal具備了通用響應性,包含了通常需要的樂觀響應性。

該技術非常簡單,涉及按順序運行底層協議的多個實例。使用Bullshark實例化時,相當於一羣"鯊魚"在進行接力賽。

背景與動機

在追求區塊鏈網路高性能時,降低通信復雜性一直是關注重點。然而,這種方法並未帶來顯著的吞吐量提升。例如,早期Diem中實現的Hotstuff僅達到3500 TPS,遠低於10萬+ TPS的目標。

近期突破源於認識到數據傳播是基於領導者協議的主要瓶頸,可以從並行化中受益。Narwhal系統將數據傳播與核心共識邏輯分離,提出所有驗證者同時傳播數據、共識組件僅排序少量元數據的架構。Narwhal論文報告吞吐量達16萬TPS。

Aptos之前介紹了Quorum Store,即Narwhal實現,將數據傳播與共識分離,用於擴展當前的Jolteon共識協議。Jolteon結合了Tendermint的線性快速路徑和PBFT風格的視圖變更,可將Hotstuff延遲降低33%。然而,基於領導者的共識協議無法充分利用Narwhal的吞吐量潛力。

因此,Aptos決定在Narwhal DAG之上部署Bullshark,一種零通信開銷的共識協議。不過,相比Jolteon,支持Bullshark高吞吐量的DAG結構帶來了50%的延遲代價。

Shoal框架旨在大幅降低Bullshark延遲。

DAG-BFT背景

Narwhal DAG中每個頂點都與一個輪數關聯。進入第r輪,驗證者必須先獲得第r-1輪的n-f個頂點。每個驗證者每輪可廣播一個頂點,每個頂點至少引用前一輪的n-f個頂點。由於網路異步性,不同驗證者可能在任何時間點觀察到DAG的不同本地視圖。

DAG的一個關鍵屬性是無歧義性:如果兩個驗證節點在本地DAG視圖中具有相同頂點v,那麼它們具有完全相同的v因果歷史。

總序排序

可以在無額外通信開銷的情況下就DAG中所有頂點的總序達成一致。爲此,DAG-Rider、Tusk和Bullshark中的驗證者將DAG結構解釋爲一種共識協議,其中頂點代表提案,邊代表投票。

所有基於Narwhal的共識協議都具有以下結構:

1. 預定錨點:每隔幾輪就有一個預先確定的領導者,其頂點稱爲錨點。

2. 排序錨點:驗證者獨立但確定性地決定排序哪些錨點、跳過哪些錨點。

3. 排序因果歷史:驗證者依次處理有序錨點列表,對每個錨點的因果歷史中先前無序的頂點進行排序。

安全性的關鍵是確保在步驟(2)中,所有誠實驗證節點創建的有序錨點列表共享相同前綴。Shoal觀察到:所有驗證者都同意第一個有序的錨點。

Bullshark延遲

Bullshark的延遲取決於DAG中有序錨點之間的輪數。雖然部分同步版本的Bullshark比異步版本具有更好的延遲,但仍遠非最佳。

主要存在兩個問題:

1. 平均塊延遲:常見情況下,奇數輪頂點需要三輪,偶數輪非錨點頂點需要四輪才能排序。

2. 故障情況延遲:如果某輪領導者未能及時廣播錨點,導致錨點無法排序而被跳過,前幾輪未排序的頂點必須等待下一個錨點排序。這顯著降低了地理復制網路的性能。

Shoal框架

Shoal通過流水線增強Bullshark(或任何基於Narwhal的BFT協議),允許每輪都有一個錨點,將DAG中所有非錨點頂點的延遲降至三輪。Shoal還在DAG中引入零開銷的領導者聲譽機制,偏向選擇快速領導者。

挑戰

在DAG協議背景下,流水線和領導者聲譽被認爲是困難問題:

1. 之前的流水線嘗試修改核心Bullshark邏輯,但這本質上似乎不可能。

2. 領導者聲譽在DiemBFT中引入、Carousel中正式化,根據驗證者過去表現動態選擇未來領導者(Bullshark中的錨點)。雖然領導者身分分歧不違反安全性,但在Bullshark中可能導致完全不同的排序。

這些挑戰導致目前生產環境中的Bullshark實現都不支持這些特性。

協議

Shoal依靠在DAG上執行本地計算的能力,實現保存和重新解釋前幾輪信息的能力。基於所有驗證者都同意第一個有序錨點的洞察,Shoal按順序組合多個Bullshark實例進行流水線處理,使得:

1. 第一個有序錨點是實例的切換點
2. 錨點的因果歷史用於計算領導者聲譽

流水線

驗證者先驗地就潛在錨點達成一致,即有一個已知映射F: R -> V將輪次映射到領導者。Shoal依次運行Bullshark實例,每個實例的錨點由映射F預先確定。每個實例排序一個錨點,觸發切換到下一個實例。

Shoal最初在DAG第一輪啓動Bullshark第一個實例,運行到確定第一個有序錨點(假設在第r輪)。所有驗證者都同意這個錨點,因此可以確定性地同意從第r+1輪開始重新解釋DAG。Shoal在第r+1輪啓動新的Bullshark實例。

理想情況下,這允許Shoal每輪排序一個錨點。第一輪錨點由第一個實例排序,然後Shoal在第二輪開始新實例,排序該輪錨點,依此類推。

領導者聲譽

當Bullshark排序過程跳過錨點時,延遲會增加。在這種情況下,流水線技術無能爲力,因爲在前一個實例排序錨點之前無法啓動新實例。Shoal通過聲譽機制爲每個驗證節點分配分數,根據最近活動歷史確保將來不太可能選擇相應的慢速領導者。響應並參與協議的驗證者獲得高分,否則分配低分。

每次分數更新時,確定性地重新計算從輪次到領導者的預定義映射F,偏向於高分領導者。爲使驗證者在新映射上達成一致,他們需要在分數上達成一致,從而在用於派生分數的歷史上達成一致。

在Shoal中,流水線和領導聲譽自然結合,因爲都使用相同的核心技術:在就第一個有序錨點達成一致後重新解釋DAG。

唯一區別是,在第r輪排序錨點後,驗證者僅根據第r輪有序錨點的因果歷史,從第r+1輪開始計算新映射F'。然後驗證節點從第r+1輪開始使用更新的錨點選擇函數F'執行新的Bullshark實例。

消除超時

超時在所有基於領導者的確定性部分同步BFT實現中起關鍵作用。然而,它們引入的復雜性增加了需要管理和觀察的內部狀態數量,增加了調試復雜性,需要更多可觀察性技術。

超時也顯著增加延遲,因爲適當配置超時很重要,通常需要動態調整,高度依賴環境(網路)。在切換到下一個領導者之前,協議會爲有故障的領導者支付完整的超時延遲懲罰。因此,超時設置不能過於保守,但如果太短,協議可能跳過好的領導者。

不幸的是,基於領導者的協議(如Hotstuff和Jolteon)本質上需要超時,以確保每次領導者出現故障時協議都能取得進展。沒有超時,即使是崩潰的領導者也可能永遠停止協議。由於在異步期間無法區分有故障和緩慢的領導者,超時可能導致驗證節點在沒有共識活躍度的情況下輪換所有領導者。

在Bullshark中,超時用於DAG構造,以確保在同步期間誠實領導者足夠快地將錨點添加到DAG以便排序。

Shoal觀察到DAG構造提供了估計網路速度的"時鍾"。在無暫停情況下,只要n-f個誠實驗證者繼續向DAG添加頂點,輪次就會繼續前進。雖然Bullshark可能無法以網路速度排序(由於領導者問題),但DAG仍以網路速度增長,盡管一些領導者有問題或網路異步。最終,當無故障領導者足夠快地廣播錨點時,錨點的整個因果歷史將被排序。

在Shoal中,避免超時和領導者聲譽密切相關。重復等待緩慢領導者會增加延遲,領導者聲譽機制排除了緩慢驗證者被選爲領導者。通過這種方式,系統利用快速驗證節點在所有現實場景中以網路速度運行。

需要注意,FLP不可能性結果表明沒有確定性共識協議可以避免超時。Shoal不能規避這個結果,因爲存在理論上的對抗性事件時間表可以阻止所有錨被排序。相反,在可配置的連續跳過錨點數量後,Shoal會退回到超時。實際上,這種情況極不可能發生。

通用響應性

Hotstuff論文普及了樂觀響應的概念,雖未正式定義,但直觀上意味着協議可以在良好情況(快速領導者和同步網路)下以網路速度運行。

Shoal提供了更好的屬性,稱爲通用響應性。具體來說,與Hotstuff相比,即使領導者在可配置的連續輪數內失敗或網路經歷異步週期,Shoal也會繼續以網路速度運行。

通用響應性在異步期間和領導者出現故障時提供了嚴格更好的進度保證。在與慢速領導者同步期間,這些屬性無法比較,因爲取決於領導者有多慢。然而,考慮到領導者聲譽,Shoal中慢速領導者應該很少出現。

評估

Aptos在Narwhal實現Quorum Store之上實現了Bullshark和Shoal。下面提供一些評估亮點:

首先,爲演