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

DAGの重要な特性はあいまいでないことです: もし2つの検証ノードがその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:故障ケースレイテンシー。上記のレイテンシー分析は無故障の状況に適用されますが、他方で、1ラウンドのリーダーが十分に迅速にアンカーポイントをブロードキャストできなかった場合、アンカーポイントをソートできなくなります(そのためスキップされます)、したがって前の数ラウンドでソートされていないすべての頂点は次のアンカーポイントがソートされるのを待たなければなりません。これは地理的レプリケーションネットワークの性能を著しく低下させ、特にBullsharkがリーダーを待つためにタイムアウトを使用するためです。

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

Shoalフレームワーク

Shoalはこれら二つのレイテンシー問題を解決し、Bullshark(または他のNarwhalベースのBFTプロトコル)をパイプラインによって強化し、各ラウンドにアンカーポイントを持たせ、DAG内のすべての非アンカーポイント頂点のレイテンシーを三ラウンドに減少させます。また、ShoalはDAG内にゼロコストのリーダー評価メカニズムを導入し、迅速なリーダーに選択が偏るようにしています。

チャレンジ

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

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

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

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

不幸にも、リーダーに基づくプロトコル(は、HotstuffやJolteon)のように、リーダーが故障するたびにプロトコルが進行することを保証するために、基本的にレイテンシーを必要とします。タイムアウトがなければ、崩壊したリーダーでさえも