# 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的端到端延遲相匹配。
Shoal框架大幅提升Aptos區塊鏈性能 延遲降低40%-80%
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的共識協議都具有以下結構:
預定錨點:每隔幾輪有一個預先確定的領導者,領導者的頂點稱爲錨點。
排序錨點:驗證者獨立但確定性地決定訂購哪些錨點以及跳過哪些錨點。
排序因果歷史:驗證者一個一個處理有序錨點列表,對每個錨點的因果歷史中所有先前無序頂點進行排序。
滿足安全性的關鍵是確保在步驟2中,所有誠實驗證節點創建一個有序錨點列表,所有列表共享相同的前綴。在Shoal中,我們觀察到所有驗證者都同意第一個有序的錨點。
Bullshark延遲
Bullshark的延遲取決於DAG中有序錨點之間的輪數。雖然部分同步版本比異步版本延遲更好,但遠非最佳。
主要有兩個問題:
平均塊延遲:常見情況下,奇數輪頂點需要三輪,偶數輪非錨點頂點需要四輪才能排序。
故障情況延遲:如果一輪領導者未能及時廣播錨點,則前幾輪未排序頂點必須等待下一個錨點排序,顯著降低了地理復制網路的性能。
Shoal框架
Shoal通過流水線增強Bullshark,允許每輪有一個錨點,將所有非錨點頂點的延遲減少到三輪。Shoal還引入了零開銷領導者聲譽機制,偏向選擇快速領導者。
挑戰
在DAG協議中,流水線和領導者聲譽被認爲是困難問題:
之前的流水線嘗試修改核心Bullshark邏輯,但這本質上似乎不可能。
領導者聲譽可能導致完全不同的排序,而驗證者需要就有序歷史達成一致以選擇未來的錨。
作爲問題難度的證據,目前生產環境中的Bullshark實現都不支持這些特性。
協議
Shoal依靠在DAG上執行本地計算,實現了保存和重新解釋前幾輪信息的能力。利用所有驗證者都同意第一個有序錨點的洞察,Shoal按順序組合多個Bullshark實例進行流水線處理,使得:
流水線
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進行了比較。主要發現:
無超時的Baseline Bullshark在出現故障時表現最佳。
Shoal的流水線和領導者聲譽機制顯著改善了Bullshark延遲。
在50次失敗中有16次失敗時,Shoal的延遲比Baseline Bullshark低65%。
Jolteon無法擴展到超過20個驗證節點,吞吐量約爲Bullshark/Shoal的一半。
總的來說,Shoal極大地改善了Bullshark延遲,在高負載下應該可以與Jolteon的端到端延遲相匹配。