Shoal Framework: Aptos での Bullshark のレイテンシーを劇的に削減

概要

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

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

DAGの重要な特性は曖昧ではありません: もし二つの検証ノードがそれらのDAGのローカルビューにおいて同じ頂点vを持っているなら、彼らは完全に同じvの因果関係の履歴を持っています。

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

一般的な注文

追加の通信コストなしにDAGのすべての頂点の総順序で合意に達することができます。そのために、DAG-Rider、Tusk、Bullsharkの検証者は、DAGの構造を合意プロトコルとして解釈し、頂点は提案を、辺は投票を表します。

DAG構造におけるグループの交差ロジックは異なるが、すべての既存のNarwhalベースのコンセンサスプロトコルは以下の構造を持っている:

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

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

3. 注文因果履歴: バリデーターは、順序付けられたアンカーポイントのリストを1つずつ処理し、各アンカーポイントの因果履歴におけるすべての以前の無秩序な頂点を並べ替えます。

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

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

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

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のインスタンスを一つずつ実行します。各インスタンスはアンカーを注文し、これが次のインスタンスへの切り替えを引き起こします。

最初,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内のリーダーは圧倒され、進捗を推進する前にタイムアウトが発生してしまうことを観察しました。

残念なことに