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しか実現されず、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のレイテンシーを大幅に減少させる方法について紹介します。

! Shoalフレームワークを説明する10,000語:Aptosで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. 予約アンカー: 数ラウンドごとに事前に決定されたリーダーがいて、リーダーの頂点はアンカーと呼ばれます;

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

3. 因果関係の歴史の順序付け: バリデーターは、順序付けられたアンカーポイントのリストを一つずつ処理し、それぞれのアンカーポイントの因果関係の歴史におけるすべての以前の無秩序な頂点を順序付けます。

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

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

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

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. リーダーの評判はDiemBFTに導入され、Carouselで正式化され、検証者の過去のパフォーマンスに基づいて未来のリーダー(Bullsharkのアンカー)を動的に選択する考えです。リーダーの地位に関する意見の相違がこれらのプロトコルの安全性に違反するわけではありませんが、Bullsharkでは、まったく異なる順序を引き起こす可能性があり、これは問題の核心に繋がります。すなわち、動的かつ決定論的に輪のアンカーを選択することがコンセンサスを解決するために必要であり、検証者は未来のアンカーを選択するために順序の歴史について合意する必要があります。

問題の難易度の証拠として、Bullsharkの実装(には、現在の生産環境における実装)がこれらの機能をサポートしていないことが含まれています。

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

プロトコル

Shoalでは、DAG上でローカル計算を実行する能力に依存し、前のラウンドの情報を保存して再解釈する能力を実現しています。すべてのバリデーターが最初の順序付けられたアンカーポイントに同意するという核心的な洞察をもとに、Shoalは複数の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実装において非常に重要な役割を果たします。しかし、これらがもたらす複雑さは、管理と観察が必要な内部状態の数を増加させ、デバッグプロセスの複雑さを増し、より多くの可観察性技術が必要になります。

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