Shoalフレームワーク: Aptos上のBullsharkのドロップを減少させる方法

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

Shoalは、流水ラインとリーダーの評判を通じて、Narwhalに基づくコンセンサスプロトコル(を強化するフレームワークであり、DAG-Rider、Tusk、Bullshark)などのプロトコルを含みます。流水ラインは、各ラウンドでアンカーポイントを導入することでDAGの並び替えレイテンシーを低下させ、リーダーの評判は、アンカーポイントが最も速い検証ノードに関連付けられることを保証することで、レイテンシーの問題をさらに改善します。加えて、リーダーの評判により、Shoalは非同期DAG構造を利用してすべてのシナリオにおけるタイムアウトを排除することができます。これにより、Shoalは一般的な応答と呼ばれる特性を提供でき、通常必要とされる楽観的な応答を含んでいます。

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

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

背景

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

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

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

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

この記事では、ShoalがどのようにBullsharkのレイテンシーを大幅にドロップするかを紹介します。

DAG-BFTの背景

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

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

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

総序ソート

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

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

1. 予約されたアンカーポイント:数ラウンドごとに(、Bullsharkの2ラウンド)ごとに、あらかじめ決められたリーダーが存在し、リーダーの頂点はアンカーポイントと呼ばれます。

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

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

安全性を満たすための鍵は、上記の手順(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はこれらの二つのレイテンシー問題を解決しました。Bullshark(または他のNarwhalベースのBFTプロトコル)をパイプラインで強化することにより、各ラウンドにアンカーポイントを持たせ、DAG内のすべての非アンカーポイントの頂点のレイテンシーを三ラウンドに減少させます。Shoalはまた、DAG内にゼロコストのリーダーの評判メカニズムを導入し、選択を迅速なリーダーに偏らせることができます。

チャレンジ

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

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

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

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

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

プロトコル

上述の課題が存在するにもかかわらず、古い言葉にあるように、解決策は単純な裏に隠れていることが証明されています。

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

( 流水ライン

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

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

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

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

( もう超過はありません

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

タイムアウトもレイテンシーを大幅に増加させます。なぜなら、それらを適切に設定することが非常に重要であり、環境)ネットワーク###に高度に依存しているため、通常は動的に調整する必要があります。次のリーダーに移行する前に、プロトコルは故障したリーダーに対して完全なタイムアウトレイテンシーの罰を支払います。したがって、タイムアウトの設定は過度に保守的であってはいけませんが、タイムアウト時間が短すぎるとプロトコルが