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

本文では、Shoalが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. 順序因果履歴: バリデーターは、順序付けられたアンカーポイントのリストを1つずつ処理し、それぞれのアンカーポイントに対して、因果履歴の中のすべての以前の無秩序な頂点をいくつかの決定論的ルールに従って順序付けます。

安全性を満たす鍵は、ステップ(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はこれら2つのレイテンシー問題を解決し、Bullshark(または他のNarwhalベースのBFTプロトコル)をパイプラインで強化することによって、各ラウンドでアンカーを持つことを可能にし、DAG内のすべての非アンカーノードのレイテンシーを三ラウンドに削減しました。Shoalはまた、DAG内にゼロコストのリーダーの評判メカニズムを導入し、これにより迅速なリーダーを選択する傾向があります。

チャレンジ

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

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

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

問題の難易度の証拠として、私たちはBullsharkの実装に注意を払っていますが、現在の運用環境での実装もこれらの機能をサポートしていません。

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

プロトコル

上述の課題が存在するにもかかわらず、ことわざがあるように、解決策はシンプルな中に隠れていることが証明されています。

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

パイプライン

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実装において重要な役割を果たします。しかし、これらが導入する複雑さは、管理および観察が必要な内部状態の数を増加させ、デバッグプロセスの複雑さを高め、より多くの可観測性技術を必要とします。

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