Shoal framework:改进Aptos上的Bullshark延迟

Aptos Labsは最近、DAG BFTにおける2つの重要なオープン問題を解決し、レイテンシを大幅に削減し、初めて決定的実際プロトコルでの一時停止の必要性を排除しました。全体的に見て、Bullsharkのレイテンシは無故障状態で40%改善され、故障状態で80%改善されました。

Shoalは、パイプラインとリーダーの評判を通じて、DAG-Rider、Tusk、Bullshark(など、Narwhalに基づくコンセンサスプロトコル)を強化するためのフレームワークです。パイプラインは各ラウンドにアンカーポイントを導入することでDAGのソート遅延を減少させ、リーダーの評判はアンカーポイントが最も速い検証ノードに関連付けられることを保証することで遅延をさらに改善します。さらに、リーダーの評判により、Shoalは非同期DAG構造を利用してすべてのシナリオにおけるタイムアウトを排除することができます。これにより、Shoalは通常必要とされる楽観的な応答を含む普遍的な応答と呼ばれる特性を提供することができます。

技術的に、Shoalは基盤プロトコルの複数のインスタンスを順番に実行します。したがって、Bullsharkをインスタンス化する際、リレーを行っている「サメ」の群れを得ることになります。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

动机

ブロックチェーンネットワークの高性能を追求する際、人々は通信の複雑性を低下させることに常に注目してきました。しかし、この方法では顕著なスループットの向上は実現されませんでした。例えば、初期バージョンのDiemで実装されたHotstuffは、3500 TPSにしか達せず、100k+ TPSの目標には遠く及びませんでした。

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

これまで、データの伝播と合意を分離するNarwhalの実装であるQuorum Storeを紹介し、それを使用して現在の合意プロトコル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框架:如何减少Aptos上的Bullshark延迟?

注文

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

DAG構造における集団の交差ロジックは異なるが、すべての既存のNarwhalに基づく合意プロトコルは以下の構造を持っている:

1. 予約されたアンカーポイント:数ラウンドごとに(、Bullsharkの二ラウンド)ごとに予め決定されたリーダーが存在し、リーダーの頂点はアンカーポイントと呼ばれる;

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

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

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

すべての検証者は、最初の順序付けられたアンカーポイントに同意します。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

オオメジロザメ

Bullsharkの遅延はDAG内の順序付きアンカーポイント間のラウンド数に依存します。Bullsharkの最も実用的な部分は、同期バージョンが非同期バージョンよりも優れた遅延を持っていますが、依然として最適とは言えません。

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

問題2:故障ケースの遅延。上記の遅延分析は無故障の状況に適用されますが、他方で、あるラウンドのリーダーが十分に速くアンカーをブロードキャストできなかった場合、アンカーの順序付けができず(スキップされることになります)。そのため、以前のラウンドで順序付けされていないすべての頂点は、次のアンカーが順序付けされるのを待たなければなりません。これは、特にBullsharkがタイムアウトを使用してリーダーを待機するため、地理的複製ネットワークの性能を著しく低下させる可能性があります。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

Shoalフレームワーク

Shoalはこの2つの遅延問題を解決しました。これは、Bullshark(またはその他のNarwhalベースのBFTプロトコル)をパイプラインで強化することにより、各ラウンドにアンカーを持たせ、DAG内のすべての非アンカーノードの遅延を3ラウンドに削減します。また、ShoalはDAGにゼロコストのリーダー評判メカニズムを導入し、選択が迅速なリーダーに偏るようにしています。

チャレンジ

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

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

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

問題の難易度の証拠として、私たちはBullsharkの実装、現在の生産環境での実装を含め、これらの機能をサポートしていないことに注意しました。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

协议

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

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

生産ライン

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

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

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

リーダーの評判

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

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

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

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

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

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

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

残念ながら、リーダーシップに基づいて