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のスループットの潜在能力を十分に活用できません。データの伝播とコンセンサスを分離しているにもかかわらず、スループットが増加するにつれて、Hotstuff/Jolteonのリーダーは依然として制限を受けています。

したがって、私たちはNarwhal DAGの上にBullsharkを展開することを決定しました。これは、ゼロ通信オーバーヘッドのコンセンサスプロトコルです。不幸なことに、Jolteonと比較して、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. ソートアンカー: バリデーターは独立して決定的にどのアンカーを注文し、どのアンカーをスキップするかを決定します。

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

安全性の鍵は、ステップ(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プロトコル)をパイプラインで強化することで、各ラウンドにアンカーポイントを持たせ、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のインスタンスを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実装において重要な役割を果たします。しかし、それらがもたらす複雑性は、管理および観察する必要がある内部状態の数を増加させ、デバッグプロセスの複雑性を増し、さらに多くの可観測性技術を必要とします。

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