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は3500 TPSしか達成せず、100k+ TPSの目標を大きく下回っています。

最近の突破は、データ伝播がリーダー協定に基づく主要なボトルネックであり、並行化から恩恵を受けることができるという認識から生まれました。Narwhalシステムはデータ伝播とコア合意ロジックを分離し、すべての検証者が同時にデータを伝播し、合意コンポーネントは少量のメタデータのみを注文するというアーキテクチャを提案しました。Narwhal論文は160,000 TPSのスループットを報告しています。

以前紹介したQuorum StoreはNarwhalの実装であり、データの伝播とコンセンサスを分離し、現在のコンセンサスプロトコルであるJolteonを拡張するために使用されます。Jolteonはリーダーベースのプロトコルで、Tendermintの線形高速パスとPBFTスタイルのビュー変更を組み合わせ、Hotstuffのレイテンシーを33%ドロップさせます。しかし、リーダーベースのコンセンサスプロトコルはNarwhalのスループットの潜在能力を十分に活用できません。

したがって、Narwhal DAGの上にBullsharkを展開することを決定しました。これは、ゼロ通信オーバーヘッドのコンセンサスプロトコルです。不幸にも、Bullsharkの高スループットをサポートするDAG構造は、Jolteonと比較して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構造を合意プロトコルとして解釈し、頂点は提案を、辺は投票を表します。

すべての既存のNarwhalベースのコンセンサスプロトコルは、以下の構造を持っています:

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

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

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

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

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

Bullsharkのレイテンシー

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

問題1: 平均ブロックレイテンシー。Bullsharkでは、各偶数ラウンドにアンカーポイントがあり、各奇数ラウンドの頂点は投票として解釈されます。一般的な場合、アンカーポイントの注文には二つのラウンドのDAGが必要ですが、アンカーポイントの因果履歴における頂点はアンカーポイントの順序待ちにさらに多くのラウンドが必要です。通常、奇数ラウンドの頂点は三つのラウンド、偶数ラウンドの非アンカーポイントの頂点は四つのラウンドが必要です。

問題2: 障害ケースレイテンシー。もし一ラウンドのリーダーが十分に速くアンカーをブロードキャストできなかった場合、アンカーの順序付けができず(がスキップされ)、前のラウンドのすべての未整理の頂点は次のアンカーの順序付けを待たなければなりません。これは地理的レプリケーションネットワークの性能を著しくドロップさせます、特にBullsharkがリーダーを待つためのタイムアウトを使用するため。

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

Shoalフレームワーク

Shoalは、各ラウンドにアンカーを持つことを許可するBullshark(または他のNarwhalベースのBFTプロトコル)をパイプラインで強化し、DAG内のすべての非アンカーノードのレイテンシーを3ラウンドに削減します。Shoalは、DAG内にゼロコストのリーダー評判メカニズムを導入し、迅速なリーダーの選択を偏向させます。

チャレンジ

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

1. 以前のラインは、コアBullsharkロジックを変更しようとしましたが、基本的には不可能なようです。

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

問題の難易度の証拠として、Bullsharkの実装(には、現在の生産環境において)がこれらの機能をサポートしていないことが含まれています。

プロトコル

ShoalはDAG上でローカル計算を実行する能力に依存し、前のラウンドの情報を保存および再解釈する能力を実現しました。すべての検証者が最初の順序付きアンカーの洞察に同意することで、Shoalは複数の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のレイテンシーを減らす方法は? ])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)は、本質的にタイムアウトを必要とし、リーダーが故障するたびにプロトコルが進行することを保証します。タイムアウトがなければ、故障したリーダーでさえ、プロトコルを永遠に停止させる可能性があります。非同期時に故障したリーダーと遅いリーダーを区別できないため、タイムアウトは検証ノードがコンセンサスのアクティビティなしにすべてのリーダーを変更する原因となる可能性があります。

Bullsharkでは、タイムアウトがDAG構築に使用され、同期中に誠実なリーダーが十分な速度でアンカーポイントをDAGに追加してソートできるようにします。

私たちは、DAG構造がネットワーク速度を推定するための「クロック」を提供することを観察しています。停止がない限り、n-fの誠実なバリデーターがDAGに頂点を追加し続ける限り、ラウンドは進み続けます。Bullsharkはリーダーの問題(のためにネットワーク速度で)をソートできないかもしれませんが、DAGは依然としてネットワーク速度で成長し続けます。いくつかのリーダーに問題があったり、ネットワークが非同期であったりしてもです。最終的に、故障のないリーダーが十分に速くアンカーポイントをブロードキャストすると、アンカーポイントの全因果関係の歴史がソートされます。

私たちの評価では、Bullsharkのタイムアウトの有無を以下の状況で比較しました:

1. クイックリーダー: 他のバリデーターよりも少なくとも速い。2つの方法は同じレイテンシーを提供しますが、アンカーは順序が付けられており、タイムアウトを使用しません。

2. エラーリーダー: タイムアウトなしのBullsharkは、検証ノードが即座にスキップするため、より良いレイテンシーを提供します。