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

本文はShoalがBullsharkのレイテンシーを大幅にドロップする方法を紹介します。

DAG-BFTの背景

関連する背景についてまず理解しましょう。NarwhalとBullsharkの詳細な説明は、DAG meets 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において、私たちは上記のすべてのプロトコルについて以下の観察を行います:

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

Bullshark の遅延

BullsharkのレイテンシーはDAG内の順序付けされたアンカーポイント間のラウンド数に依存します。Bullsharkの最も実用的な部分である同期バージョンは非同期バージョンよりもレイテンシーが良好ですが、最適とは言えません。

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

問題2:故障ケースレイテンシー,上述のレイテンシー分析は無故障の状況に適用されます。一方で、もしリーダーが十分に速くアンカーポイントをブロードキャストできなかった場合、アンカーポイントをソートすることができず(スキップされます)そのため、前のラウンドでソートされていないすべての頂点は次のアンカーポイントがソートされるのを待たなければなりません。これは地理的複製ネットワークのパフォーマンスを著しくドロップさせます。特に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では、DAG上でローカル計算を実行する能力に依存し、以前のラウンドの情報を保存および再解釈する能力を実現しています。すべての検証者が最初の順序付きアンカーポイントに同意するという核心的な洞察に基づき、Shoalは複数のBullsharkインスタンスを順次組み合わせてパイプライン処理を行い、(1)最初の順序付きアンカーポイントはインスタンスの切り替え点であり、(2)アンカーポイントの因果関係の歴史がリーダーの評判を計算するために使用されます。

! Shoalフレームワークを説明する10,000語:Aptosで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のレイテンシーを減らす方法は?

リーダーの評判

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

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

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

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

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

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

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

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