Shoalフレームワーク：Aptos上のBullsharkレイテンシーをドロップする革新的なソリューション

Aptos Labsは最近、DAG BFTにおける2つの重要なオープン問題を解決し、レイテンシーを大幅にドロップし、初めて決定論的実際プロトコルにおけるタイムアウトの必要性を排除しました。全体として、無故障の場合にBullsharkのレイテンシーを40%改善し、故障時には80%改善しました。

Shoalは、流水ライン処理とリーダーの評判メカニズムを通じて、Narwhalに基づくコンセンサスプロトコル(であるDAG-Rider、Tusk、Bullshark)のフレームワークを強化します。流水ライン処理は、各ラウンドでアンカーポイントを導入することによりDAGのソートレイテンシーを削減し、リーダーの評判メカニズムは、アンカーポイントを最も速い検証ノードと関連付けることでレイテンシー問題をさらに改善します。加えて、リーダーの評判によりShoalは非同期DAG構築を利用して、すべてのシナリオにおけるタイムアウトメカニズムを排除できます。これにより、Shoalは「普遍的な応答」と呼ばれる特性を提供でき、これは通常求められる楽観的な応答の特性を含んでいます。

Shoalの技術は非常にシンプルで、順番に複数のインスタンスを実行することを含んでいます。したがって、Bullsharkをインスタンス化すると、私たちが得られる効果は、リレー競技を行っている「サメ」の群れのようになります。

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

背景と動機

ブロックチェーンネットワークの高性能を追求する過程で、人々は通信の複雑さをドロップすることに注目してきました。しかし、この方法はスループットの顕著な向上をもたらしませんでした。例えば、Diemの初期バージョンで実装されたHotstuffは3500 TPSを達成したに過ぎず、私たちの目標である10万+ TPSを大きく下回っています。

最近のブレイクスルーは、データ伝播がリーダーのプロトコルに基づく主要なボトルネックであり、並列化から利益を得られることを認識したことに起因しています。Narwhalシステムはデータ伝播とコアコンセンサスロジックを分離し、すべてのバリデーターが同時にデータを伝播し、コンセンサスコンポーネントは少量のメタデータを並べ替えるというアーキテクチャを提案しています。Narwhal論文は16万TPSのスループットを報告しています。

以前の記事では、データの伝播とコンセンサスを分離する私たちのNarwhal実装である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の各頂点は、1つのラウンドに関連付けられています。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において、私たちは上記のすべてのプロトコルに対して以下の観察を行います:

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

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

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フレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

プロトコル

上述の課題が存在するにもかかわらず、解決策はシンプルな中に隠れていることが証明されています。

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

( パイプライン処理

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

最初,ShoalはDAGの第一ラウンドでBullsharkの最初のインスタンスを立ち上げ、最初の順序付きアンカーポイントが第rラウンドのように決定されるまでそれを実行します。すべてのバリデーターはこのアンカーポイントに同意します。したがって、すべてのバリデーターは第r+1ラウンドからDAGを再解釈することに確定的に同意できます。Shoalは第r+1ラウンドで新しいBullsharkインスタンスを立ち上げただけです。

最良のシナリオでは、これによりShoalは各ラウンドでアンカーポイントをソートすることができます。最初のラウンドのアンカーポイントは最初のインスタンスによってソートされます。その後、Shoalは第二ラウンドで新しいインスタンスを開始し、それ自体にアンカーポイントがあり、そのアンカーポイントはそのインスタンスによってソートされます。そして、別の新しいインスタンスが第三ラウンドでアンカーポイントをソートし、このプロセスは続きます。

! [Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は? ])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp###

( リーダーの評判

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

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

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

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

! [Shoalフレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は? ])https://img-cdn.gateio.im/webp-social/moments-1baf540693f376d93cb18ef3193593cc.webp###

( タイムアウトを消去

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

超時も顕著にレイテンシーを増加させる