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

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

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

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

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

背景

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

最近のブレークスルーは、データの伝播がリーダーのプロトコルに基づく主要なボトルネックであり、並列化から利益を得ることができるという認識から生まれました。Narwhalシステムは、データ伝播とコアコンセンサスロジックを分離し、すべてのバリデーターが同時にデータを伝播し、コンセンサスコンポーネントは少量のメタデータのみを順序付けるというアーキテクチャを提案します。Narwhal論文は160,000 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個の頂点を取得しなければなりません。各バリデーターは各ラウンドで1つの頂点をブロードキャストでき、各頂点は前のラウンドのn-f個の頂点を少なくとも参照する必要があります。ネットワークの非同期性により、異なるバリデーターは任意の時点でDAGの異なるローカルビューを観察する可能性があります。

DAGの重要な属性の1つは明確である: もし2つの検証ノードがそれらのDAGのローカルビューで同じ頂点vを持っているなら、彼らは完全に同じvの因果歴史を持っている。

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

総注文数

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

DAG構造における群体交差ロジックは異なりますが、すべての既存のNarwhalベースのコンセンサスプロトコルは以下の構造を持っています:

1. 予約アンカーポイント: 数ラウンドごとに事前に決定されたリーダーが存在し、リーダーの頂点はアンカーポイントと呼ばれる;

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

3. 因果履歴のソート: 検証者は順序付けられたアンカーポイントのリストを一つずつ処理し、各アンカーポイントに対して、いくつかの決定論的ルールを使用して因果履歴の中のすべての以前の無秩序な頂点をソートします。

安全性を満たすための鍵は、ステップ(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のインスタンスを1つずつ実行し、それぞれのインスタンスについて、アンカーはマッピング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ラウンドで順序付けられたアンカーポイントの因果関係の履歴に基づいて、r+1ラウンドから新しいマッピングF'を計算するだけです。次に、バリデーションノードはr+1ラウンドから更新されたアンカーポイント選択関数F'を使用してBullsharkの新しいインスタンスを実行します。

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

これ以上のタイムアウトはありません

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

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

残念ながら、リーダーに基づくプロトコル(は、HotstuffやJolteon)のように、本質的にタイムアウトを必要とし、リーダーが毎回確認できるようにします。