Shoalフレームワーク解析:大幅ドロップAptos上のBullsharkレイテンシー

Aptos Labsは最近、DAG BFTにおける2つの重要な問題を解決し、レイテンシーを大幅にドロップし、初めて決定論的リアルタイムプロトコルにおいてタイムアウトの必要性を排除しました。全体として、無障害の状況下でBullsharkのレイテンシーは40%改善され、障害の状況下では80%改善されました。

Shoalは、パイプラインとリーダーの評判メカニズムを通じて、Narwhalベースのコンセンサスプロトコル(を強化するフレームワークです。DAG-Rider、Tusk、Bullshark)のように、パイプラインは各ラウンドでアンカーポイントを導入することでDAGソートのレイテンシーを減少させ、リーダーの評判はアンカーポイントと最も速い検証ノードが関連付けられることを保証することでレイテンシーをさらに改善します。さらに、リーダーの評判により、Shoalはすべてのシナリオでタイムアウトを排除するために非同期DAG構築を利用できるようになります。これにより、Shoalは一般的な応答性を備え、通常必要とされる楽観的な応答性を含んでいます。

この技術は非常にシンプルで、基盤となるプロトコルの複数のインスタンスを順番に実行することに関係しています。Bullsharkをインスタンス化することは、"サメ"のグループがリレー競走を行っているのに相当します。

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

背景と動機

ブロックチェーンネットワークの高性能を追求する際、通信の複雑性をドロップすることは常に重要な焦点でした。しかし、このアプローチは顕著なスループットの向上をもたらしませんでした。例えば、初期のDiemで実装されたHotstuffは3500 TPSにしか達せず、10万+ TPSの目標を大きく下回っています。

最近の突破は、データ伝播がリーダー合意に基づく主要なボトルネックであることを認識し、並列化から利益を得ることができることに起因しています。Narwhalシステムはデータ伝播とコアコンセンサスロジックを分離し、すべての検証者が同時にデータを伝播し、コンセンサスコンポーネントが少量のメタデータを順序付けるアーキテクチャを提案しています。Narwhal論文では、スループットが16万TPSに達することが報告されています。

Aptosは以前、Quorum Store、つまりNarwhal実装を紹介しました。これはデータの伝播と合意を分離し、現在のJolteon合意プロトコルの拡張に使用されます。Jolteonは、Tendermintの線形高速パスとPBFTスタイルのビュー変更を組み合わせており、Hotstuffのレイテンシーを33%ドロップさせることができます。しかし、リーダーに基づく合意プロトコルはNarwhalのスループットのポテンシャルを十分に活用することができません。

そのため、AptosはNarwhal DAGの上にBullsharkを展開することを決定しました。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フレームワークを説明する10,000語:AptosでBullsharkのレイテンシーを減らす方法は?

総序ソート

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

すべてのNarwhalに基づくコンセンサスプロトコルは、以下の構造を持っています:

1. 予約されたアンカーポイント:数ラウンドごとに事前に決定されたリーダーがいて、その頂点はアンカーポイントと呼ばれます。

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

3. 因果履歴のソート: バリデーターは順次順序付けられたアンカーポイントのリストを処理し、各アンカーポイントの因果履歴の以前の無秩序な頂点をソートします。

安全性の鍵は、ステップ(2)において、すべての誠実な検証ノードが作成した順序付きアンカーポイントのリストが同じプレフィックスを共有することを保証することです。Shoalは、すべての検証者が最初の順序付きアンカーポイントに同意したことを観察しました。

Bullsharkのレイテンシー

BullsharkのレイテンシーはDAG内の順序付けされたアンカーポイント間のラウンド数に依存します。一部の同期版Bullsharkは非同期版よりもレイテンシーが優れていますが、依然として最適とは言えません。

主に2つの問題があります:

1. 平均ブロックレイテンシー:一般的な場合、奇数ラウンドの頂点は三ラウンド、偶数ラウンドの非アンカーポイントの頂点は四ラウンドでソートされる必要があります。

2. 障害状況レイテンシー: もしあるラウンドのリーダーがタイムリーにアンカーポイントをブロードキャストできず、アンカーポイントがソートできずにスキップされた場合、前のラウンドでソートされていない頂点は次のアンカーポイントのソートを待たなければなりません。これにより、地理的レプリケーションネットワークのパフォーマンスが大幅にドロップします。

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

Shoalフレームワーク

Shoalは、Bullshark(またはNarwhalに基づくBFTプロトコル)をパイプラインで強化し、各ラウンドにアンカーポイントを持たせることで、DAG内のすべての非アンカーポイントのレイテンシーを3ラウンドに低下させます。Shoalはまた、DAG内にゼロコストのリーダー評判メカニズムを導入し、迅速なリーダーを選択することを偏向させます。

チャレンジ

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

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

2. リーダーの評判はDiemBFTに導入され、Carouselで正式化され、バリデーターの過去のパフォーマンスに基づいて将来のリーダーを動的に選択します(Bullsharkのアンカー)。リーダーのアイデンティティの不一致はセキュリティに違反するわけではありませんが、Bullsharkでは完全に異なる順序を引き起こす可能性があります。

これらの課題により、現在の生産環境でのBullshark実装はこれらの機能をサポートしていません。

プロトコル

ShoalはDAG上でローカル計算を実行する能力に依存し、過去の数ラウンドの情報を保存し再解釈する能力を実現します。すべての検証者が最初の順序付けられたアンカーポイントに同意するという洞察に基づき、Shoalは複数のBullsharkインスタンスを順番に組み合わせてパイプライン処理を行います。

1. 最初の順序アンカーはインスタンスの切り替えポイントです
2. アンカーポイントの因果歴史はリーダーの評判を計算するために使用されます

パイプライン

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

Shoalは最初にDAGの第1ラウンドでBullsharkの最初のインスタンスを起動し、最初の順序付けられたアンカーポイント(を確定するまで実行されます。第rラウンドで)を仮定します。全てのバリデーターはこのアンカーポイントに同意するため、第r+1ラウンドからDAGを再解釈することに確定的に同意します。Shoalは第r+1ラウンドで新しいBullsharkインスタンスを起動します。

理想的には、これによりShoalは各ラウンドで1つのアンカーポイントをソートできます。最初のラウンドのアンカーポイントは最初のインスタンスによってソートされ、その後Shoalは2ラウンド目に新しいインスタンスを開始し、そのラウンドのアンカーポイントをソートし、これを繰り返します。

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

リーダーの評判

Bullsharkのソートプロセスがアンカーポイントをスキップすると、レイテンシーが増加します。この場合、パイプライン技術は無力であり、前のインスタンスのソートアンカーポイントが完了する前に新しいインスタンスを開始することはできません。Shoalは、評判メカニズムを通じて各検証ノードにスコアを割り当て、最近の活動履歴に基づいて将来の遅いリーダーが選ばれる可能性を低くします。プロトコルに応答し、参加した検証者は高得点を獲得し、そうでない場合は低得点が割り当てられます。

スコアが更新されるたびに、ラウンドからリーダーへの事前定義されたマッピングFを確定的に再計算し、高スコアのリーダーに偏ります。バリデーターが新しいマッピングで合意に達するためには、スコアに関して合意に達する必要があり、その結果、派生スコアに使用される履歴に合意に達することになります。

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

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

タイムアウトを解消する

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

タイムアウトはレイテンシーを著しく増加させる。適切にタイムアウトを設定することが重要であり、通常は動的に調整する必要があり、環境(ネットワーク)に高度に依存する。次のリーダーに切り替える前に、プロトコルは故障したリーダーに対して完全なタイムアウトレイテンシーのペナルティを支払う。したがって、タイムアウトの設定はあまり保守的であってはいけないが、あまりにも短いとプロトコルは良いリーダーをスキップしてしまう可能性がある。

残念ながら、リーダーに基づくプロトコル(は、HotstuffやJolteon)のように、本質的にタイムアウトを必要とします。これは、リーダーが故障するたびにプロトコルが進行することを保証するためです。タイムアウトがなければ、崩壊したリーダーでさえ、プロトコルを永遠に停止させる可能性があります。非同期の期間中に故障したリーダーと遅いリーダーを区別できないため、タイムアウトは検証ノードがコンセンサスのアクティブさなしにすべてのリーダーをローテーションする原因となることがあります。

Bullsharkでは、DAG構築のためにタイムアウトが使用され、同期中に誠実なリーダーが十分に速くアンカーポイントをDAGに追加して順序付けできるようにします。

Shoalは、DAG構造がネットワーク速度の"クロック"を提供することを観察しました。停止なしで、n-fの正直なバリデーターがDAGに頂点を追加し続ける限り、ラウンドは進み続けます。Bullsharkはリーダーの問題(のためにネットワーク速度で)をソートできないかもしれませんが、DAGは一部のリーダーに問題があるか、ネットワークが非同期であるにもかかわらず、ネットワーク速度で成長しています。最終的に、故障のないリーダーが十分に速くアンカーポイントをブロードキャストすると、アンカーポイントの全因果歴史がソートされます。

Shoalでは、タイムアウトを回避することとリーダーの評判が密接に関連しています。遅いリーダーを繰り返し待つことはレイテンシーを増加させ、リーダーの評判メカニズムは遅い検証者がリーダーに選ばれることを排除します。このようにして、システムはすべての現実のシナリオでネットワーク速度で動作するために迅速な検証ノードを利用します。

注意が必要です。FLP不可能性の結果は、タイムアウトを回避する確定的な合意プロトコルは存在しないことを示しています。Shoalはこの結果を回避することはできません。なぜなら、すべてのアンカーが順序付けられるのを妨げる理論上の対抗的なイベントスケジュールが存在するからです。逆に、設定可能な連続したアンカーポイントの数を超えると、Shoalはタイムアウトに戻ります。実際、この状況は非常に起こりにくいです。

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

汎用レスポンシブ

Hotstuff論文は楽観的応答の概念を普及させましたが、正式には定義されていません。しかし直感的には、プロトコルは良好な状況(において、迅速なリーダーシップと同期ネットワーク)の下でネットワークの速度で動作できることを意味します。

Shoalは、一般的な応答性と呼ばれるより良い属性を提供します。具体的には、Hotstuffと比較して、リーダーが設定可能な連続ラウンド内で失敗したり、ネットワークが非同期周期を経験しても、Shoalはネットワーク速度で動作し続けます。

一般的な応答性は、非同期中およびリーダーが故障した際に厳密に良好な進捗保証を提供します。遅いリーダーとの同期中、これらの属性は比較できません。なぜなら、どれだけリーダーが遅いかによるからです。しかし、リーダーの評判を考慮すると、Shoalにおいて遅いリーダーはほとんど現れないはずです。

評価

AptosはNarwhalの上にQuorum Storeを実装し、BullsharkとShoalを実現しました。以下にいくつかの評価のハイライトを提供します:

まず、演