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

Aptos labsは最近、DAG BFTにおける2つの重要なオープン問題を解決し、レイテンシーを大幅に削減し、初めて決定論的実用プロトコルにおいてタイムアウトの必要性を排除しました。全体的に、Shoalフレームワークは、故障がない場合にBullsharkのレイテンシーを40%改善し、故障がある場合には80%改善しました。

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

Shoalのコア思想は非常にシンプルで、基盤プロトコルの複数のインスタンスを順番に実行することです。したがって、Bullsharkをインスタンス化すると、リレー競技を行っている「サメ」の群れが得られます。

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

モチベーション

ブロックチェーンネットワークの高性能を追求する過程で、人々は常に通信の複雑性をドロップすることに注目してきました。しかし、このアプローチはスループットの著しい向上をもたらしませんでした。例えば、初期バージョンのDiemで実装されたHotstuffは3500 TPSにしか達せず、10万+ TPSの目標には遠く及びませんでした。

最近のブレークスルーは、データ伝播がリーダー協定に基づく主要なボトルネックであり、並列化によって利益を得ることができるという認識から生まれました。Narwhalシステムは、データ伝播をコアコンセンサスロジックから分離し、すべての検証者が同時にデータを伝播し、コンセンサスコンポーネントは少量のメタデータのみを順序付けるというアーキテクチャを提案しました。Narwhal論文は16万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の各頂点は、あるラウンドに関連付けられています。第rラウンドに入るためには、バリデーターはまず第r-1ラウンドに属するn-f個の頂点を取得しなければなりません。各バリデーターは各ラウンドで1つの頂点をブロードキャストでき、各頂点は前のラウンドのn-f個の頂点を少なくとも参照する必要があります。ネットワークの非同期性のため、異なるバリデーターは任意の時点でDAGの異なるローカルビューを観察する可能性があります。

DAGの重要な属性の1つは無矛盾性です: もし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:故障ケースレイテンシー。上述のレイテンシー分析は正常な状態に適用されます。一方、あるラウンドのリーダーがアンカーポイントを十分に速くブロードキャストできなかった場合、アンカーポイントをソートできず(スキップされます)。そのため、前のラウンドでソートされていないすべての頂点は次のアンカーポイントがソートされるのを待たなければなりません。これは地理的レプリケーションネットワークの性能を著しくドロップさせる可能性があります。特に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つずつ実行します。各インスタンスは1つのアンカーを順序付け、次のインスタンスに切り替えるトリガーを引きます。

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

最良のシナリオでは、これによりShoalは各ラウンドでアンカーをソートすることができます。最初のラウンドのアンカーポイントは最初のインスタンスに基づいてソートされます。次に、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のようです。