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のレイテンシーを大幅にドロップする方法について紹介します。

DAG-BFTの背景

この記事の関連背景を理解することから始めましょう。

Narwhal DAGの各頂点は、特定のラウンドに関連付けられています。第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において、私たちは上記のすべてのプロトコルについて以下の観察を行っています:

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

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は、各インスタンスに対してFによって事前に決定されたアンカーを持つBullsharkのインスタンスを1つずつ実行します。各インスタンスはアンカーを注文し、これが次のインスタンスへの切り替えをトリガーします。

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

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