Shoal框架:提升Aptos區塊鏈性能的創新方案

Aptos Labs近期提出了Shoal框架,旨在解決DAG BFT共識中的兩個關鍵問題,顯著降低延遲並首次消除了確定性異步協議中對超時的依賴。總體而言,Shoal在無故障情況下將Bullshark的延遲提高了40%,在故障情況下提高了80%。

Shoal通過流水線和領導者聲譽機制來增強基於Narwhal的共識協議(如DAG-Rider、Tusk、Bullshark等)。流水線技術通過每輪引入一個錨點來減少DAG排序延遲,領導者聲譽機制則通過確保錨點與最快的驗證節點相關聯來進一步改善延遲。此外,領導者聲譽使Shoal能夠利用異步DAG構建來消除所有場景中的超時,從而實現了普遍響應性。

Shoal的核心思路是按順序運行底層協議的多個實例。以Bullshark爲例,可以將其想象成一羣正在接力賽跑的"鯊魚"。

動機

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

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

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

因此,Aptos決定在Narwhal DAG之上部署Bullshark,一種零通信開銷的共識協議。但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. 排序因果歷史:驗證者逐個處理有序錨點列表,對每個錨點的因果歷史中之前未排序的頂點進行排序。

滿足安全性的關鍵是確保所有誠實驗證節點創建的有序錨點列表共享相同的前綴。Shoal對所有這些協議做出一個重要觀察:所有驗證者都同意第一個有序錨點。

Bullshark的延遲問題

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

主要存在兩個問題:

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

2. 故障情況延遲:如果一輪的領導者未能及時廣播錨點,該錨點將被跳過,前幾輪所有未排序頂點必須等待下一個錨點排序。這顯著降低了地理分布網路的性能,尤其是因爲Bullshark使用超時等待領導者。

Shoal框架

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

挑戰

在DAG協議中實現流水線和領導者聲譽被認爲是困難的:

1. 之前嘗試修改Bullshark核心邏輯似乎不可行。

2. 領導者聲譽可能導致不同的排序,而驗證者需要就有序歷史達成一致以選擇未來錨點。

作爲問題難度的佐證,目前生產環境中的Bullshark實現都不支持這些特性。

協議

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

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

流水線

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

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

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

領導者聲譽

當Bullshark跳過錨點時,延遲會增加。流水線技術在這種情況下無能爲力,因爲必須等前一個實例排序錨點才能啓動新實例。Shoal通過聲譽機制爲每個驗證節點分配分數,根據其最近活動歷史。響應迅速的驗證者獲得高分,否則獲得低分。

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

在Shoal中,流水線和領導者聲譽可以自然結合,因爲它們都基於在第一個有序錨點達成一致後重新解釋DAG。唯一的區別是,在第r輪排序錨點後,驗證者根據該錨點的因果歷史從r+1輪開始計算新映射F'。然後從r+1輪開始使用更新後的F'執行新的Bullshark實例。

消除超時

超時在所有基於領導者的確定性部分同步BFT實現中都很關鍵。然而,它們增加了復雜性,需要更多的內部狀態管理和觀察,使調試更加困難。

超時還會顯著增加延遲,因爲正確配置很重要,且通常需要動態調整。在切換到下一個領導者之前,協議要爲有故障的領導者支付完整的超時延遲懲罰。因此,超時設置不能過於保守,但如果太短又可能跳過好的領導者。

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

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

我們觀察到DAG構建提供了一個估計網路速度的"時鍾"。只要n-f個誠實驗證者繼續向DAG添加頂點,輪次就會前進。雖然Bullshark可能無法以網路速度排序,但DAG仍以網路速度增長。最終,當一個無故障領導者足夠快地廣播錨點時,錨點的整個因果歷史將被排序。

在評估中,我們比較了有無超時的Bullshark:

1. 快速領導者:兩種方法延遲相同,因爲錨點被排序且不使用超時。

2. 錯誤的領導者:無超時Bullshark延遲更低,因爲驗證節點會立即跳過其錨點。

3. 緩慢的領導者:有超時Bullshark表現更好,因爲驗證者會等待錨點,而無超時可能跳過錨點。

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

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

普遍響應性

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

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

普遍響應性在異步期間和領導者故障時提供了嚴格更好的進度保證。在與慢速領導者同步期間,這些特性無法直接比較,因爲取決於領導者的速度。但考慮到領導者聲譽機制,Shoal中緩慢領導者應該很少出現。

![萬字詳解Shoal框架：如何減