Shoalフレームワーク:AptosでBullsharkのレイテンシーを減らす方法

概要

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

Shoalは、流水線とリーダーの評判を通じてNarwhalベースの合意プロトコル(を強化するフレームワークです。DAG-Rider、Tusk、Bullshark)のようなものです。流水線は各ラウンドでアンカーを導入することで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のスループットの潜在能力を十分に活用できません。データの伝播と合意を分けることができるにもかかわらず、スループットが増加するにつれて、Hotstuff/Jolteonのリーダーは依然として制限を受けます。

したがって、私たちはNarwhal DAGの上にBullsharkを展開することに決めました。これは、ゼロ通信オーバーヘッドのコンセンサスプロトコルです。残念ながら、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. 順序因果履歴: 検証者は順次、順序付けられたアンカーポイントのリストを処理し、それぞれのアンカーポイントについて、いくつかの決定論的なルールによってその因果履歴の中のすべての以前の無秩序な頂点を順序付けます。

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

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

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

Bullsharkのレイテンシー

BullsharkのレイテンシーはDAG内の順序付けられたアンカー間の回数に依存します。Bullsharkの最も実用的な部分は、同期バージョンが非同期バージョンよりもレイテンシーが良好ですが、最適とは程遠いです。

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

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

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

Shoalフレームワーク

Shoalはこれら2つのレイテンシー問題を解決しました。Bullshark(や他のNarwhalベースのBFTプロトコル)をパイプラインで強化し、各ラウンドにおいて1つのアンカーを持つことを可能にし、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のインスタンスを1つずつ実行し、各インスタンスに対してアンカーポイントがマッピングFによって事前に決定されます。各インスタンスはアンカーポイントをソートし、これが次のインスタンスへの切り替えをトリガーします。

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

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

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

リーダーの評判

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

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

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

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

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

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

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

タイムアウトはレイテンシーを大幅に増加させる可能性があり、適切に設定することが非常に重要であり、環境(ネットワーク)に強く依存しているため、通常は動的に調整する必要があります。次のリーダーに移行する前に、プロトコルは故障したリーダーに完全なタイムアウトのレイテンシー罰則を支払います。したがって、