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にしか達せず、10万+ TPSの目標を大きく下回っています。

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

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

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

本文では、ShoalがBullsharkのレイテンシーを大幅に削減する方法について説明します。

DAG-BFTの背景

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

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

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

全体的な順序

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

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

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

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

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

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

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

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

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

流水ライン処理

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

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

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

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

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

残念ながら、リーダーに基づくプロトコル(は、HotstuffやJolteon)のように、本質的にタイムアウトを必要とし、リーダーが故障するたびにそれを保証します。