Shoalフレームワーク: Aptos上のBullsharkレイテンシーをどうドロップするか?

概要

1. Aptos labsはDAG BFTにおける2つの重要なオープン問題を解決し、レイテンシーを大幅に減少させ、初めて決定論的実際プロトコルにおけるタイムアウトの必要性を排除しました。全体として、無故障の状況下でBullsharkのレイテンシーを40%改善し、故障の状況下で80%改善しました。

2. Shoalは、パイプラインとリーダーの評判を通じて、DAG-Rider、Tusk、Bullshark(などのNarwhalベースのコンセンサスプロトコル)を強化するフレームワークです。パイプラインは各ラウンドでアンカーポイントを導入することによりDAGソートのレイテンシーをドロップし、リーダーの評判はアンカーポイントを最速の検証ノードに関連付けることによってレイテンシーの問題をさらに改善します。さらに、リーダーの評判によりShoalは非同期DAG構造を利用して、すべてのシナリオでタイムアウトを排除できます。これによりShoalは一般的な応答の特性を提供し、通常必要とされる楽観的な応答を含んでいます。

3. この技術は非常にシンプルで、基盤となるプロトコルの複数のインスタンスを順番に実行することに関わっています。したがって、Bullsharkをインスタンス化すると、リレー競技を行っている「サメ」のグループが得られます。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

モチベーション

ブロックチェーンネットワークの高性能を追求する際、通信の複雑さをドロップすることに常に注目してきました。しかし、このアプローチはスループットの顕著な向上にはつながりませんでした。例えば、初期バージョンのDiemで実装されたHotstuffは、目標の100k+ TPSを大きく下回る3500 TPSしか達成しませんでした。

最近の突破は、データ伝播がリーダー協定に基づく主要なボトルネックであることを認識したことに起因し、並列化から利益を得ることができることです。Narwhalシステムはデータ伝播とコアコンセンサスロジックを分離し、全てのバリデーターが同時にデータを伝播し、コンセンサスコンポーネントは少量のメタデータのみを順序付けるアーキテクチャを提案しています。Narwhal論文は160,000 TPSのスループットを報告しています。

以前にQuorum Storeを紹介しましたが、データの伝播とコンセンサスを分離し、現在のコンセンサスプロトコルJolteonを拡張する方法について説明しました。Jolteonはリーダーベースのプロトコルで、Tendermintの線形高速パスとPBFTスタイルのビュー変更を組み合わせることで、Hotstuffのレイテンシーを33%低下させることができます。しかし、リーダーベースのコンセンサスプロトコルはNarwhalのスループットの潜在能力を十分に活用できません。データの伝播とコンセンサスを分けても、スループットが増加するにつれて、Hotstuff/Jolteonのリーダーは依然として制限されています。

したがって、Narwhal DAGの上にBullsharkをデプロイすることを決定しました。これは、ゼロ通信オーバーヘッドのコンセンサスプロトコルです。不幸にも、Jolteonと比較して、Bullsharkの高スループットをサポートするDAG構造は、50%のレイテンシーコストをもたらしました。

本文では、ShoalがBullsharkのレイテンシーを大幅にドロップする方法を紹介します。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

DAG-BFTの背景

Narwhal DAGの各頂点はラウンドに関連付けられています。第rラウンドに入るためには、バリデーターはまず第r-1ラウンドに属するn-f個の頂点を取得する必要があります。各バリデーターは各ラウンドに1つの頂点をブロードキャストでき、各頂点は前のラウンドの少なくともn-f個の頂点を参照する必要があります。ネットワークの非同期性により、異なるバリデーターは任意の時点でDAGの異なるローカルビューを観察する可能性があります。

DAGの重要な特性の一つは明確性です: もし二つの検証ノードがDAGのローカルビューで同じ頂点vを持っているなら、それらは全く同じvの因果履歴を持っています。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

総注文数

追加の通信オーバーヘッドなしにDAG内のすべての頂点の総順序に合意することができます。これを実現するために、DAG-Rider、Tusk、BullsharkのバリデーターはDAG構造を合意プロトコルとして解釈し、頂点は提案を、辺は投票を表します。

DAG構造におけるグループインタセクションのロジックは異なるが、すべての既存のNarwhalベースのコンセンサスプロトコルは以下の構造を持っている。

1. 予約アンカーポイント: 数ラウンドごとに(、Bullsharkの2ラウンド)ごとに事前に決定されたリーダーが存在し、その頂点をアンカーポイントと呼びます。

2. ソートアンカー: バリデーターは独立しているが、どのアンカーを注文し、どれをスキップするかを決定する。

3. 因果関係の履歴のソート: バリデーターは順序付けられたアンカーポイントのリストを1つずつ処理し、各アンカーポイントについて、決定論的ルールを使用してその因果関係の履歴にあるすべての以前の無秩序な頂点をソートします。

セキュリティを満たすための鍵は、ステップ(2)で、すべての誠実な検証ノードが順序付けられたアンカーポイントのリストを作成し、すべてのリストが同じプレフィックスを共有することを保証することです。Shoalでは、上記のすべてのプロトコルに対して以下の観察が行われます:

すべてのバリデーターは最初の順序付けられたアンカーポイントに同意します。

Bullsharkのレイテンシー

BullsharkのレイテンシーはDAG内の順序アンカー間のラウンド数に依存します。Bullsharkの最も実用的な部分は、同期バージョンが非同期バージョンよりもレイテンシーが良好ですが、最適ではありません。

問題1:平均ブロックレイテンシー。Bullsharkでは、各偶数ラウンドにアンカーポイントがあり、各奇数ラウンドの頂点は投票として解釈されます。一般的な状況では、アンカーポイントを注文するには2ラウンドのDAGが必要ですが、アンカーポイントの因果関係の歴史における頂点は、アンカーポイントが順序付けられるのを待つためにより多くのラウンドを必要とします。一般的な状況では、奇数ラウンドの頂点は3ラウンド、偶数ラウンドの非アンカーポイントの頂点は4ラウンドを必要とします。

問題2:故障ケースレイテンシー、上記のレイテンシー分析は無障害の状況に適用されます。一方、もし一ラウンドのリーダーが十分に速くアンカーポイントをブロードキャストできない場合、アンカーポイントのソートができず(スキップされます)、前のラウンドのすべての未ソートの頂点は次のアンカーポイントがソートされるのを待たなければなりません。これは地理的複製ネットワークの性能を著しくドロップさせます。特にBullsharkがタイムアウトでリーダーを待つためです。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

Shoalフレームワーク

Shoalはこれら2つのレイテンシー問題を解決しました。Bullshark(または他のNarwhalベースのBFTプロトコル)をパイプラインで強化することにより、各ラウンドにアンカーポイントを持たせ、DAG内のすべての非アンカーポイントの頂点のレイテンシーを3ラウンドに減少させます。Shoalはまた、DAG内にゼロコストのリーダーの評判メカニズムを導入し、これにより選択は迅速なリーダーに偏ります。

チャレンジ

DAGプロトコルの背景において、パイプラインとリーダーの評判は困難な問題と見なされています。その理由は次の通りです：

1. 以前のラインはコアBullsharkロジックを修正しようとしましたが、これは本質的に不可能のようです。

2. リーダーの評判はDiemBFTに導入され、Carouselで正式化されており、これは検証者の過去のパフォーマンスに基づいて将来のリーダー(Bullsharkのアンカー)を動的に選択するという考え方です。リーダーの地位に関して意見の不一致があっても、これらのプロトコルの安全性に違反することはありませんが、Bullsharkでは全く異なる順序を引き起こす可能性があります。これは問題の核心を引き出し、すなわち動的かつ決定論的にラウンドアンカーを選択することが合意形成に必要であり、検証者は将来のアンカーを選択するために秩序ある歴史について合意に達する必要があります。

問題の難易度の証拠として、Bullsharkの実装、現在の生産環境での実装を含め、これらの機能をサポートしていません。

プロトコル

これらの課題が存在するにもかかわらず、解決策はシンプルな背後に隠れています。

Shoalでは、DAG上でのローカル計算を実行する能力に依存し、前回の情報を保存して再解釈する能力を実現しています。すべてのバリデーターが最初の順序付けられたアンカーポイントに合意するという核心的な洞察を持ち、Shoalは複数のBullsharkインスタンスを順番に組み合わせてパイプライン処理を行います。(の最初の順序付けられたアンカーポイントがインスタンスの切り替え点となり、)のアンカーポイントの因果歴がリーダーの評判を計算するために使用されます。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

パイプライン

Vがあります。ShoalはBullsharkのインスタンスを一つずつ実行し、各インスタンスのアンカーはマッピングFによって事前に決定されます。各インスタンスはアンカーを注文し、これにより次のインスタンスへの切り替えがトリガーされます。

最初、ShoalはDAGの第一ラウンドでBullsharkの最初のインスタンスを起動し、最初の順序付けられたアンカーポイントを特定するまでそれを実行します、例えば第rラウンドのように。すべての検証者はこのアンカーポイントに同意します。したがって、すべての検証者は第r+1ラウンドからDAGを再解釈することに確実に同意できます。Shoalは第r+1ラウンドで新しいBullsharkインスタンスを起動しました。

最良のシナリオでは、Shoalは各ラウンドで1つのアンカーを注文できます。最初のラウンドのアンカーポイントは最初のインスタンスに基づいてソートされます。その後、Shoalは2回目のラウンドで新しいインスタンスを開始し、それ自体にアンカーポイントを持ち、そのアンカーはそのインスタンスによってソートされます。次に、別の新しいインスタンスが3回目のラウンドでアンカーポイントを注文し、このプロセスは続きます。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

リーダーの評判

Bullsharkのソート中にアンカーをスキップすると、レイテンシーが増加します。この場合、パイプライン技術は無力であり、前のインスタンスがアンカーを注文する前に新しいインスタンスを起動できません。Shoalは、各検証ノードの最近の活動履歴に基づいて各検証ノードにスコアを割り当てる評判メカニズムを使用することで、将来的に失われたアンカーを処理するリーダーが選ばれる可能性を低く保ちます。プロトコルに応答し、参加する検証者は高いスコアを獲得し、それ以外の場合は、検証ノードは低いスコアを割り当てられます。なぜなら、それはクラッシュする可能性があるか、遅いか、悪意がある可能性があるからです。

その理念は、スコアが更新されるたびに、確定的にラウンドからリーダーへの事前定義されたマッピングFを再計算し、高いスコアを持つリーダーを優先することです。バリデーターが新しいマッピングで合意に達するためには、スコアについて合意に達し、スコアを派生させるための履歴で合意に達する必要があります。

Shoalでは、パイプラインとリーダーの評判が自然に結びつくことができます。なぜなら、両者は同じコア技術、つまり最初の順序付きアンカーポイントに合意した後にDAGを再解釈することを使用しているからです。

実際の違いは、rラウンドでアンカーポイントがソートされた後、バリデーターはrラウンドで順序付けられたアンカーポイントの因果的歴史に基づいて、新しいマッピングF'をr+1ラウンドから計算するだけです。それから、バリデーションノードはr+1ラウンドから更新されたアンカーポイント選択関数F'を使用してBullsharkの新しいインスタンスを実行します。

! Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

もう超過時間はありません

タイムアウトは、すべてのリーダーに基づく決定的部分同期BFT実装において重要な役割を果たします。しかし、それらがもたらす複雑さは、管理および観察が必要な内部状態の数を増加させ、デバッグプロセスの複雑さを増し、より多くの可観測性技術を必要とします。

タイムアウトはレイテンシーを著しく増加させる可能性があります。なぜなら、適切にそれらを設定することが非常に重要であり、通常は環境(ネットワーク)に高度に依存しているため、動的に調整する必要があるからです。次のリーダーに移行する前に、プロトコルは故障したリーダーに対して完全なタイムアウトレイテンシーの罰金を支払います。したがって、タイムアウトの設定はあまり保守的であってはならず、しかしタイムアウトの時間が短すぎると、プロトコルは良いリーダーをスキップする可能性があります。例えば、高負荷の状態では、Jolteon/Hotstuffのリーダーが負荷に耐えられず、彼らが進展を推進する前にタイムアウトが経過してしまうことを観察しました。

残念ながら、リーダーに基づくプロトコル(（HotstuffやJolteon)など）は、本質的にタイムアウトを必要とします。これは、リーダーが故障するたびにプロトコルが進行することを保証するためです。タイムアウトがなければ、故障したリーダーであってもプロトコルが永遠に停止する可能性があります。非同期の期間中は、失敗を区別することができません。