Shoalフレームワーク: Aptos上のBullshark遅延をどのように減少させるか?

概要

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

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

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

! 万字详解Shoal框架:如何减少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のリーダーは依然として制限を受けています。

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

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

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

DAG-BFTの背景

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

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

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

总顺序

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

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

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

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

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

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

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

オオメジロザメ

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

問題1: 平均ブロック遅延。Bullsharkでは、各偶数ラウンドにアンカーポイントがあり、各奇数ラウンドの頂点は投票として解釈されます。一般的な場合、アンカーポイントを順序付けるには2ラウンドのDAGが必要ですが、アンカーポイントの因果関係の歴史の頂点は、アンカーポイントが順序付けられるのを待つためにより多くのラウンドを必要とします。一般的な場合、奇数ラウンドの頂点は3ラウンドが必要であり、偶数ラウンドの非アンカーポイントの頂点は4ラウンドが必要です。

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

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

浅瀬の枠組み

Shoalは、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のリーダーが過負荷になり、彼らが進捗を促進する前にタイムアウトすることが観察されました。