Shoalフレームワーク: Aptos上のBullsharkのレイテンシーをドロップする新しいソリューション

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

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

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

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

背景

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

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

私たちのNarwhal実装Quorum Storeは、データの伝播と合意を分離し、現在の合意プロトコルJolteonを拡張するために使用されます。Jolteonはリーダーベースのプロトコルであり、Tendermintの線形高速経路とPBFTスタイルのビュー変更を組み合わせて、Hotstuffのレイテンシーを33%低下させます。しかし、リーダーベースの合意プロトコルは、Narwhalのスループットの潜在能力を十分に活用できません。データの伝播と合意を分けても、スループットが増加するにつれて、Hotstuff/Jolteonのリーダーは依然として制限されています。

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

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

DAG-BFTの背景

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

DAGの一つの重要な属性は曖昧さではありません: もし二つの検証ノードがそれらのDAGのローカルビューにおいて同じ頂点vを持っているなら、それらは完全に同じv因果歴史を持っています。

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

一般的な注文

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

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

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

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

3. 因果履歴のソート: バリデーターは順序付きアンカーポイントのリストを1つずつ処理し、各アンカーポイントについて、決定的なルールに従ってその因果履歴内のすべての以前の無秩序な頂点をソートします。

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

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

Bullsharkのレイテンシー

BullsharkのレイテンシーはDAG内の順序付きアンカーポイント間のラウンド数に依存します。Bullsharkの最も実用的な部分では、同期バージョンが非同期バージョンよりも優れたレイテンシーを持っていますが、それでも最適とは言えません。

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

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

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

Shoalフレームワーク

Shoalはパイプライン処理を通じて、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のレイテンシーを減らす方法は? ])https://img-cdn.gateio.im/webp-social/moments-46d37add0d9e81b2f295edf8eddd907f.webp(

パイプライン処理

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-0b0928cb6240e994c1514c75e080a4b2.webp(

リーダーの評判

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

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

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

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

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

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

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

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

残念ながら、リーダーに基づくプロトコル)は、HotstuffやJolteon(など、本質的にタイムアウトを必要とし、リーダーが故障するたびに確認を行う必要があります。