Shoal框架：降低Aptos上Bullshark延遲的創新方案

Aptos Labs近期解決了DAG BFT中兩個重要的開放性問題,顯著減少了延遲,並首次消除了確定性實際協議中對超時的需求。總體而言,在無故障情況下將Bullshark的延遲改進了40%,在出現故障時改進了80%。

Shoal是一個通過流水線處理和領導者聲譽機制來增強基於Narwhal的共識協議(如DAG-Rider、Tusk、Bullshark)的框架。流水線處理通過每輪引入一個錨點來減少DAG排序延遲,領導者聲譽機制則通過確保錨點與最快的驗證節點相關聯來進一步改善延遲問題。此外,領導者聲譽使得Shoal可以利用異步DAG構建來消除所有場景中的超時機制。這使得Shoal能夠提供我們稱之爲"普遍響應"的特性,它包含了通常所需的樂觀響應性質。

Shoal的技術非常簡單,涉及按順序逐個運行底層協議的多個實例。因此,當使用Bullshark實例化時,我們得到的效果就像一羣正在進行接力賽的"鯊魚"。

背景和動機

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

近期的突破源於認識到數據傳播是基於領導者的協議的主要瓶頸,且可從並行化中受益。Narwhal系統將數據傳播與核心共識邏輯分離,提出了一種架構,所有驗證者同時傳播數據,而共識組件僅排序少量元數據。Narwhal論文報告了16萬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 DAG中的每個頂點都與一個輪次相關聯。爲進入第r輪,驗證者必須首先獲得屬於第r-1輪的n-f個頂點。每個驗證者每輪可以廣播一個頂點,每個頂點至少引用前一輪的n-f個頂點。由於網路異步性,不同驗證者可能在任何時間點觀察到DAG的不同本地視圖。

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

總序排序

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

雖然DAG結構上的羣體交集邏輯不同,但所有現有的基於Narwhal的共識協議都具有以下結構:

1. 預定錨點:每隔幾輪(如Bullshark中的兩輪)就會有一個預先確定的領導者,領導者的頂點稱爲錨點。

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

3. 排序因果歷史:驗證者逐個處理有序錨點列表,對於每個錨點,通過某些確定性規則對其因果歷史中所有先前無序的頂點進行排序。

滿足安全性的關鍵是確保在步驟2中,所有誠實的驗證節點創建一個有序錨點列表,以便所有列表共享相同的前綴。在Shoal中,我們對上述所有協議做出以下觀察:

所有驗證者都同意第一個有序的錨點。

Bullshark延遲

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

問題1:平均塊延遲。在Bullshark中,每個偶數輪都有一個錨點,每個奇數輪的頂點都被解釋爲投票。常見情況下,需要兩輪DAG才能排序錨點,然而,錨點的因果歷史中的頂點需要更多輪次來等待錨點被排序。在常見情況下,奇數輪中的頂點需要三輪,而偶數輪中的非錨點頂點需要四輪。

問題2:故障情況延遲。上述延遲分析適用於無故障情況,另一方面,如果某輪的領導者未能足夠快地廣播錨點,則無法對錨點進行排序(因此被跳過),導致前幾輪中所有未排序的頂點必須等待下一個錨點被排序。這會顯著降低地理復制網路的性能,特別是因爲Bullshark使用超時來等待領導者。

Shoal框架

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

挑戰

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

1. 以前的流水線處理嘗試試圖修改核心Bullshark邏輯,但這從本質上講似乎是不可能的。

2. 領導者聲譽在DiemBFT中引入並在Carousel中正式化,是根據驗證者過去表現動態選擇未來領導者(Bullshark中的錨點)的想法。雖然在領導者身分上存在分歧並不違反這些協議中的安全性,但在Bullshark中,它可能導致完全不同的排序,這引出了問題的核心,即動態和確定性地選擇輪錨是解決共識所必需的,而驗證者需要就有序歷史達成一致以選擇未來的錨點。

作爲問題難度的證據,我們注意到Bullshark的實現,包括目前在生產環境中的實現,都不支持這些特性。

協議

盡管存在上述挑戰,但事實證明解決方案隱藏在簡單之中。

在Shoal中,我們依靠在DAG上執行本地計算的能力,並實現了保存和重新解釋前幾輪信息的能力。憑藉所有驗證者都同意第一個有序錨點的核心洞察,Shoal按順序組合多個Bullshark實例對它們進行流水線處理,使得(1)第一個有序錨點是實例的切換點,以及(2)錨點的因果歷史用於計算領導者的聲譽。

流水線處理

與Bullshark類似,驗證者先驗地就潛在的錨點達成一致,即,有一個已知的映射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實現中起着至關重要的作用。然而,它們引入的復雜性增加了需要管理和觀察的內部狀態數量,這增加了調試過程的復雜性,並且需要更多的可觀察性技術。

超時也會顯著增加延