Shoalフレームワーク: Aptos上のBullshark遅延をどのように減らすか?

概要

Aptos LabsはDAG BFTにおける2つの重要なオープン問題を解決し、遅延を大幅に削減し、初めて決定論的実際のプロトコルにおける停止の必要性を排除しました。全体として、故障がない場合にBullsharkの遅延が40%改善され、故障がある場合には80%改善されました。

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

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

动机

ブロックチェーンネットワークの高性能を追求する際、人々は常に通信の複雑さの低減に注目してきました。しかし、このアプローチはスループットの顕著な向上をもたらしませんでした。例えば、Diemの初期バージョンで実装されたHotstuffは、目標の100k+ TPSを大きく下回る3500 TPSしか達成できませんでした。

最近の突破は、データ伝播がリーダー契約の主要なボトルネックに基づいていることを認識し、並行処理から利益を得られることに起因しています。Narwhalシステムはデータ伝播とコアコンセンサスロジックを分離し、すべての検証者が同時にデータを伝播し、コンセンサスコンポーネントが少量のメタデータのみを順序付けるというアーキテクチャを提案しています。Narwhal論文は160,000 TPSのスループットを報告しています。

以前紹介したQuorum Storeは、データの伝播と合意の分離を実現し、現在の合意プロトコルJolteonを拡張しました。Jolteonはリーダーに基づくプロトコルで、Tendermintの線形高速パスとPBFTスタイルのビュー変更を組み合わせ、Hotstuffの遅延を33%削減します。しかし、リーダーに基づく合意プロトコルはNarwhalのスループットの潜在能力を十分に活用できません。データの伝播と合意を分けても、スループットが増加するにつれて、Hotstuff/Jolteonのリーダーは依然として制限されています。

したがって、Narwhal DAGの上にBullsharkが展開されました。これは、ゼロ通信オーバーヘッドのコンセンサスプロトコルです。不幸にも、Jolteonと比較して、Bullsharkの高スループットをサポートするDAG構造は50％の遅延コストをもたらしました。

この記事では、ShoalがBullsharkの遅延を大幅に削減する方法について説明します。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

DAG-BFTの背景

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

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

总顺序

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

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

1. 予約アンカー: 数ラウンドごとに予め決定されたリーダーがいて、その頂点をアンカーと呼ぶ。

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

3. 因果関係の履歴の並べ替え: 検証者は順序付けられたアンカーポイントのリストを一つずつ処理し、各アンカーポイントの因果関係の履歴において、以前の無秩序な頂点を並べ替えます。

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

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

オオメジロザメ

Bullsharkの遅延は、DAG内の順序付きアンカーポイント間のラウンド数に依存します。Bullsharkの最も実用的な部分は、同期バージョンが非同期バージョンよりも優れた遅延を持っていますが、最適とは言えません。

問題1: 平均ブロック遅延。Bullsharkでは、各偶数ラウンドにアンカーポイントがあり、奇数ラウンドの頂点は投票として解釈されます。一般的な場合、アンカーポイントを注文するには2ラウンドのDAGが必要ですが、アンカーポイントの因果履歴における頂点は、アンカーポイントが並べ替えられるまでにさらに多くのラウンドを待つ必要があります。通常、奇数ラウンドの頂点は3ラウンド、偶数ラウンドの非アンカーポイントの頂点は4ラウンド必要です。

問題2:故障ケースの遅延。上記の遅延分析は無故障の状況に適用される。一方で、リーダーが十分に速くアンカーポイントをブロードキャストできない場合、(のアンカーポイントの順序付けができず、)がスキップされることになる。前のラウンドで未順序のすべての頂点は、次のアンカーポイントが順序付けられるのを待たなければならない。これは、Bullsharkがリーダーのタイムアウト待機を使用しているため、地理的複製ネットワークの性能を著しく低下させる。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

浅瀬の枠組み

Shoalはこの2つの遅延問題を解決しました。Bullshark(または他のNarwhalベースのBFTプロトコル)を通じてパイプライン化を強化し、各ラウンドにアンカーを持たせ、DAG内のすべての非アンカー頂点の遅延を3ラウンドに減少させます。Shoalはまた、DAG内にゼロコストのリーダーの評判メカニズムを導入し、迅速なリーダーを選択することに偏っています。

チャレンジ

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

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

2. リーダーの評判はDiemBFTで導入され、Carouselで正式化されます。これにより、バリデーターの過去のパフォーマンスに基づいて将来のリーダー(Bullsharkのアンカー)を動的に選択します。リーダーシップの地位に関する意見の相違は、これらのプロトコルのセキュリティを侵害することはありませんが、Bullsharkでは全く異なる順序を引き起こす可能性があります。これは問題の核心を提起します: ダイナミックかつ決定的にローテーションアンカーを選択することは合意形成に必要であり、バリデーターは将来のアンカーを選択するために秩序ある歴史について合意に達する必要があります。

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

协议

上記の課題が存在するにもかかわらず、解決策はシンプルなところに隠れています。

Shoalでは、DAG上でローカル計算を実行する能力に依存して、前のラウンドの情報を保存し再解釈する能力を実現しています。すべてのバリデーターが最初の順序付けられたアンカーポイントに同意するという核心的な洞察をもとに、Shoalは複数のBullsharkインスタンスを順次組み合わせてパイプライン処理を行います。(最初の順序付けられたアンカーポイントはインスタンスの切り替えポイントであり、)アンカーポイントの因果履歴はリーダーの評判を計算するために使用されます。

流水ライン

Vが存在します。ShoalはBullsharkインスタンスを1つずつ実行し、それぞれのインスタンスのアンカーはマッピングFによって事前に決定されます。各インスタンスはアンカーを注文し、次のインスタンスへの切り替えをトリガーします。

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

最良のケースでは、これによりShoalは各ラウンドでアンカーを1つ注文できます。最初のラウンドのアンカーポイントは最初のインスタンスでソートされます。次に、Shoalは2回目のラウンドで新しいインスタンスを開始し、そのインスタンスには自身のアンカーポイントがあり、そのアンカーはそのインスタンスでソートされます。そして、3回目のラウンドでは別の新しいインスタンスがアンカーポイントを注文し、このプロセスは続きます。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

リーダーの評判

Bullsharkのソート中にアンカーポイントをスキップすると、遅延が増加します。この場合、パイプライン技術は無力です。なぜなら、前のインスタンスがアンカーポイントを注文する前に新しいインスタンスを起動できないからです。Shoalは、各検証ノードの最近の活動履歴に基づいてスコアを割り当てる評判メカニズムを使用することで、将来的に関連するリーダーが失われたアンカーポイントを処理する可能性が低くなることを保証します。プロトコルに応答し、参加する検証者は高得点を得ますが、そうでない場合は、検証ノードは低得点が割り当てられます。なぜなら、それはクラッシュする可能性がある、遅い、または悪意があるからです。

その理念は、スコアが更新されるたびに、リーダーに対する事前に定義されたマッピングFを確定的に再計算し、スコアが高いリーダーに偏ることです。検証者が新しいマッピングで合意に達するためには、スコアの合意に達し、スコアを導出するための履歴においても合意に達する必要があります。

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

実際のところ、唯一の違いは、rラウンドでアンカーポイントの並べ替えを行った後、検証者がrラウンドでの順序付けされたアンカーポイントの因果関係の歴史に基づいて、r+1ラウンドから新しいマッピングF'を計算する必要があるということです。その後、検証ノードはr+1ラウンドから更新されたアンカーポイント選択関数F'を使用してBullsharkの新しいインスタンスを実行します。

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

これ以上のタイムアウトはありません

リーダーに基づく決定的部分同期BFTの実装において、タイムアウトは非常に重要な役割を果たします。しかし、それらがもたらす複雑さは、管理および監視が必要な内部状態の数を増加させ、デバッグプロセスの複雑さを増し、より多くの可視化技術が必要になります。

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

残念ながら、リーダーのプロトコル(であるHotstuffやJolteon)は、本質的にタイムアウトを必要とし、リーダーが故障するたびにプロトコルが進行することを保証します。タイムアウトがなければ、クラッシュしたリーダーであってもプロトコルを永遠に停止させる可能性があります。同期間中に故障したリーダーと遅いリーダーを区別できないため、タイムアウトは検証ノードが合意のアクティビティなしにすべてのリーダーの変更を確認する原因となる可能性があります。

Bullsharkにおいて、タイムアウトはDAG構築に使用され、同期中に誠実なリーダーがDAGにアンカーポイントを追加することを保証します。