Shoal框架:如何減少Aptos上的Bullshark延遲?

概述

Aptos labs解決了DAG BFT中兩個重要的開放問題,大幅減少了延遲,首次消除了確定性實際協議中對暫停的需求。總體上,在無故障情況下將Bullshark的延遲改進了40%,在故障情況下改進了80%。

Shoal是一個通過流水線和領導者聲譽增強基於Narwhal的共識協議的框架。流水線通過每輪引入錨點來減少DAG排序延遲,領導者聲譽通過確保錨點與最快的驗證節點關聯來進一步改善延遲。此外,領導者聲譽使Shoal可以利用異步DAG構造來消除所有場景中的超時。這允許Shoal提供普遍響應的屬性,包含通常需要的樂觀響應。

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

動機

在追求區塊鏈網路高性能時,人們一直關注降低通信復雜性。然而,這種方法並沒有導致吞吐量顯著提高。例如,Diem早期版本中實現的Hotstuff僅實現了3500 TPS,遠低於100k+ TPS的目標。

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

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

因此決定在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. 排序因果歷史:驗證者一個一個處理有序錨點列表,對每個錨點的因果歷史中所有先前無序頂點進行排序。

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

Bullshark延遲

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

主要有兩個問題:

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

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

Shoal框架

Shoal通過流水線增強Bullshark,允許每輪有一個錨點,將所有非錨點頂點的延遲減少到三輪。Shoal還引入了零開銷領導者聲譽機制,偏向選擇快速領導者。

挑戰

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

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

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

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

協議

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

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

流水線

Shoal一個接一個運行Bullshark實例,每個實例訂購一個錨,觸發切換到下一個實例。

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

理想情況下,這允許Shoal每輪訂購一個錨點。

領導者聲譽

當Bullshark跳過錨點時,延遲會增加。Shoal通過聲譽機制爲每個驗證節點分配分數,確保將來不太可能選擇緩慢的領導者。

在每次分數更新時,確定性地重新計算從輪次到領導者的映射F,偏向高分領導者。爲了讓驗證者在新映射上達成一致,他們應該在分數上達成一致。

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

無需超時

超時在基於leader的確定性部分同步BFT實現中起關鍵作用,但引入了復雜性並顯著增加延遲。

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

避免超時和領導聲譽密切相關。重復等待緩慢領導者會增加延遲,而聲譽機制排除了緩慢驗證者被選爲領導者。

普遍響應

Shoal提供了普遍響應的屬性,即使在領導者失敗或網路異步的情況下也能以網路速度運行。這優於Hotstuff的樂觀響應概念。

評估

實現了Bullshark和Shoal,並與Jolteon進行了比較。主要發現:

1. 無超時的Baseline Bullshark在出現故障時表現最佳。

2. Shoal的流水線和領導者聲譽機制顯著改善了Bullshark延遲。

3. 在50次失敗中有16次失敗時,Shoal的延遲比Baseline Bullshark低65%。

4. Jolteon無法擴展到超過20個驗證節點,吞吐量約爲Bullshark/Shoal的一半。

總的來說,Shoal極大地改善了Bullshark延遲,在高負載下應該可以與Jolteon的端到端延遲相匹配。