减少Aptos上Bullshark延迟:Shoal框架详解

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

Shoalフレームワークは、流水線とリーダーの信頼性メカニズムを通じて、Narwhalベースのコンセンサスプロトコル(を強化します。DAG-Rider、Tusk、Bullshark)のように。流水線は各ラウンドでアンカーポイントを導入してDAGのソート遅延を削減し、リーダーの信頼性はアンカーポイントを最速の検証ノードに関連付け、遅延をさらに改善します。さらに、リーダーの信頼性により、Shoalは非同期DAG構造を利用してすべてのシナリオでタイムアウトを排除し、普遍的な応答性を実現します。

Shoalの技術は非常にシンプルで、基盤となるプロトコルの複数のインスタンスを順番に実行します。Bullsharkをインスタンス化すると、接力競技を行っている"サメ"の群れのようになります。

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

背景

ブロックチェーンネットワークの高性能を追求する際、人々は通信の複雑さを減少させることに注目してきましたが、これはスループットの顕著な向上にはつながりませんでした。例えば、初期のDiemで実装されたHotstuffは3500 TPSに達するだけで、100k+ TPSの目標には遠く及びません。

最近の突破は、データ伝播がリーダーシッププロトコルに基づく主要なボトルネックであることを認識したことから生じ、並列化から利益を得ることができます。Narwhalシステムはデータ伝播とコアコンセンサスロジックを分離し、すべての検証者が同時にデータを伝播し、コンセンサスコンポーネントは少量のメタデータのみをソートします。Narwhal論文は160,000 TPSのスループットを報告しています。

Aptosは以前にQuorum Store、すなわちNarwhalの実装を紹介しました。これはデータの伝播と合意を分離し、現在の合意プロトコルJolteonを拡張するために使用されます。JolteonはTendermintの線形高速パスとPBFTスタイルのビュー変更を組み合わせており、Hotstuffの遅延を33%削減します。しかし、リーダーベースの合意プロトコルはNarwhalのスループットの潜在能力を十分に活用できません。

そのため、AptosはNarwhal DAGの上にBullsharkを展開することを決定しました。Bullsharkは通信コストゼロの合意プロトコルです。不幸にも、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框架:如何减少Aptos上的Bullshark延迟?

総序ソート

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

DAG構造におけるグループインタラクションの論理は異なりますが、Narwhalに基づくすべての合意プロトコルには以下の構造があります:

1. 予約されたアンカーポイント: 数ラウンドごとに事前に決定されたリーダーがいて、その頂点をアンカーポイントと呼びます。

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

3. 因果履歴のソート：バリデーターは順序付きアンカーポイントリストを個別に処理し、各アンカーポイントの因果履歴において以前の順序のない頂点をソートします。

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

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

オオメジロザメ

Bullsharkの遅延は、DAG内の順序付けされたアンカーポイント間のラウンド数に依存します。一部の同期バージョンの遅延は非同期バージョンより優れていますが、依然として最適ではありません。

問題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はDAG上でローカル計算を実行する能力に依存しており、以前のラウンドの情報を保存し再解釈する能力を実現しました。すべての検証者が最初の順序付きアンカーポイントの洞察に同意することに基づいて、Shoalは複数のBullsharkインスタンスを順次組み合わせてパイプライン処理を行い、(1)最初の順序付きアンカーポイントはインスタンスの切り替え点であり、(2)アンカーポイントの因果歴史はリーダーの信用を計算するために使用されます。

流れる水

Vがあります。ShoalはBullsharkインスタンスを順次実行し、各インスタンスのアンカーはマッピング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にアンカーポイントを追加する速度が十分に速く、これらを順序付けることができるようにします。

私たちは、DAG構造がネットワーク速度を推定する「時計」を提供することを観察しました。停止することなく、n-f人の誠実な検証者がDAGに頂点を追加し続ける限り、ラウンドは進み続けます。Bullsharkはリーダーの問題(のため、ネットワーク速度で)をソートできないかもしれませんが、一部のリーダーに問題があったりネットワークが非同期であっても、DAGはネットワーク速度で成長し続けます。最終的に、故障のないリーダーが十分に速くアンカーポイントをブロードキャストすると、アンカーポイントの全因果履歴がソートされます。

評価中、Bullsharkが以下の状況でタイムアウトがあるかどうかを比較しました:

1. 高速リーダーは、他のバリデーターよりも少なくとも速い。この場合、2つの方法は同じ遅延を提供します。なぜなら、アンカーが順序付けられていて、タイムアウトを使用していないからです。

2. 誤ったリーダー、この場合、無休のBullsharkはより良い遅延を提供します。なぜなら、検証ノードはそのアンカーポイントをすぐにスキップするからです。一方、休止中の検証者は、それらが期限切れになるのを待ってから続行します。

3. スローペースのリーダー、これはBullsharkのタイムアウト性能がより良くなる唯一の状況です。なぜなら、無停止の時、アンカーポイントがスキップされる可能性があるため、リーダーがそれを十分に速くブロードキャストできないからです。そして、停止がある場合、バリデーターはアンカーポイントを待つことになります。

Shoalでは、タイムアウトを避けることはリーダーの信用と密接に関連しています。繰り返し待機すること