Shoalフレームワーク: Aptosブロックチェーンの性能を向上させる革新的なソリューション

Aptos Labsは最近、Shoalフレームワークを提案しました。これは、DAG BFTコンセンサスにおける2つの重要な問題を解決することを目的としており、レイテンシを著しく低下させ、初めて決定論的非同期プロトコルにおけるタイムアウトへの依存を排除しました。全体として、Shoalは無故障の状況でBullsharkのレイテンシを40%向上させ、故障の状況では80%向上させました。

Shoalは、流水ラインとリーダーの評判メカニズムを通じて、Narwhalベースの合意プロトコル(を強化します。DAG-Rider、Tusk、Bullsharkなど)。流水ライン技術は、各ラウンドでアンカーポイントを導入することでDAGソート遅延を減少させ、リーダーの評判メカニズムは、アンカーポイントが最も速い検証ノードと関連付けられることを保証することで遅延をさらに改善します。さらに、リーダーの評判により、Shoalは非同期DAG構築を利用してすべてのシナリオにおけるタイムアウトを排除し、普遍的な応答性を実現しました。

Shoalのコアコンセプトは、基盤プロトコルの複数のインスタンスを順番に実行することです。Bullsharkを例に取ると、それはリレー競技をしている"サメ"の群れのように想像できます。

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

モチベーション

ブロックチェーンネットワークは常により高いパフォーマンスを追求しており、初期には主に通信の複雑さを減少させることに焦点を当てていました。しかし、このアプローチは顕著なスループットの向上をもたらしませんでした。例えば、Diemの初期バージョンで実装されたHotstuffはわずか3500 TPSに達し、10万+ TPSの目標には遠く及びませんでした。

最近のブレークスルーは、データ伝播がリーダー合意の主要なボトルネックであると認識され、それを並列化することで利益を得られることから生じています。Narwhalシステムはデータ伝播とコア合意ロジックを分離し、すべてのバリデーターが同時にデータを伝播し、合意コンポーネントが少量のメタデータのみをソートするアーキテクチャを提案し、16万TPSのスループットを実現しました。

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

したがって、AptosはNarwhal DAGの上にBullsharkを展開することを決定しました。Bullsharkはゼロ通信オーバーヘッドの合意プロトコルですが、高スループットのDAG構造をサポートすることによって50%の遅延コストがもたらされました。Shoalフレームワークの目的は、Bullsharkの遅延を大幅に削減することです。

! Shoalフレームワークを説明する10,000語:Aptosで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構造を合意プロトコルとして解釈しており、頂点は提案を表し、辺は投票を表します。

具体的なロジックは異なりますが、すべてのNarwhalベースのコンセンサスプロトコルは以下の構造を持っています:

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

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

3. 因果関係の履歴のソート: 検証者は順序付けられたアンカーポイントのリストを一つずつ処理し、各アンカーポイントの因果関係の履歴の中で未ソートの頂点をソートします。

安全性を満たす鍵は、すべての誠実な検証ノードが作成した順序付けられたアンカーポイントのリストが同じ接頭辞を共有していることを確保することです。Shoalは、これらすべてのプロトコルに対して重要な観察を行います: すべての検証者が最初の順序付けられたアンカーポイントに同意します。

Bullsharkのレイテンシーの問題

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

主に2つの問題があります:

1. 平均ブロック遅延:一般的な場合、奇数ラウンドの頂点は3ラウンドでソートする必要があり、偶数ラウンドの非アンカーポイント頂点は4ラウンドを必要とします。

2. 障害状況の遅延: もし一つのラウンドのリーダーがタイムリーにアンカーポイントを放送できなかった場合、そのアンカーポイントはスキップされ、前のラウンドのすべての未ソート頂点は次のアンカーポイントのソートを待たなければなりません。これは地理的に分散したネットワークの性能を著しく低下させます。特に、Bullsharkがリーダーを待つためにタイムアウトを使用しているためです。

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

Shoalフレームワーク

Shoalは、Bullshark(またはNarwhalベースのBFTプロトコル)をパイプラインで強化し、各ラウンドにアンカーを設けることで、すべての非アンカー頂点の遅延を3ラウンドに削減します。Shoalはまた、DAG内にゼロコストのリーダー評判メカニズムを導入し、迅速なリーダーを選択する傾向があります。

チャレンジ

DAGプロトコルにおいてパイプラインとリーダーの評判を実現することは困難であると考えられています:

1. 以前のBullsharkのコアロジックを変更しようとしましたが、うまくいかなかったようです。

2. リーダーの評判は異なる順位を引き起こす可能性があり、バリデーターは今後のアンカーポイントを選択するために順序のある履歴について合意する必要があります。

問題の難易度を証明するために、現在の生産環境におけるBullsharkの実装はこれらの機能をサポートしていません。

プロトコル

Shoalのソリューションは比較的単純です。これはDAG上でローカル計算を実行する能力を利用して、前のラウンドの情報を保存し再解釈する機能を実現しています。すべてのバリデーターが最初の順序のアンカーポイントに同意しているという洞察に基づいて、Shoalは複数のBullsharkインスタンスを順次組み合わせてパイプライン処理を行い、次のようにします:

1. 最初の順序付きアンカーポイントはインスタンスの切り替え点です。
2. アンカーポイントの因果歴史はリーダーの評判を計算するために使用されます

###パイプライン

Vがあります。ShoalはBullsharkインスタンスを順番に実行し、各インスタンスがアンカーポイントをソートし、次のインスタンスに切り替えるトリガーを発動します。

ShoalはDAGの第1ラウンドからBullsharkの最初のインスタンスを起動し、最初の順序付きアンカーポイント(が第rラウンド)に存在することを確認するまで進行します。すべてのバリデーターはこのアンカーポイントに同意し、したがってr+1ラウンドからDAGを再解釈することに確実に同意できます。Shoalはr+1ラウンドで新しいBullsharkインスタンスを起動します。

理想的には、これによりShoalは各ラウンドで1つのアンカーポイントをソートすることができます。最初のラウンドのアンカーポイントは最初のインスタンスによってソートされ、その後、2番目のラウンドでは新しいインスタンスがそのラウンドのアンカーポイントをソートするというように続きます。

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

リーダーの評判

Bullsharkがアンカーポイントをスキップすると、遅延が増加します。この場合、パイプライン技術は無力であり、前のインスタンスがアンカーポイントをソートするのを待たなければ新しいインスタンスを起動できません。Shoalは、各検証ノードに最近の活動履歴に基づいてスコアを割り当てるために評判メカニズムを使用します。迅速に応答する検証者は高得点を獲得し、そうでない場合は低得点を獲得します。

理念は、スコアが更新されるたびに、確定的にラウンドからリーダーへのマッピングFを再計算し、高得点のリーダーに偏ることです。バリデーターが新しいマッピングで合意に達するためには、彼らはスコアで合意に達し、さらにスコアを派生させるための履歴で合意に達する必要があります。

Shoalでは、パイプラインとリーダーの評判は自然に結びつくことができます。なぜなら、どちらも最初の順序付きアンカーで合意に達した後にDAGを再解釈することに基づいているからです。唯一の違いは、r回目の順序付きアンカーの後、検証者はそのアンカーの因果関係の履歴に基づいてr+1回目から新しいマッピングF'を計算することです。次に、r+1回目から更新されたF'を使用して新しいBullsharkインスタンスを実行します。

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

タイムアウトを解除する

タイムアウトは、すべてのリーダー主導型の決定的部分同期BFT実装において非常に重要です。しかし、それらは複雑性を増し、より多くの内部状態管理と観察を必要とし、デバッグをより困難にします。

タイムアウトは遅延を著しく増加させる可能性があり、正しい設定が重要であり、通常は動的に調整する必要があります。次のリーダーに切り替える前に、プロトコルは故障したリーダーに対して完全なタイムアウト遅延の罰則を支払わなければなりません。そのため、タイムアウトの設定はあまり保守的であってはならず、しかし短すぎると良いリーダーをスキップしてしまう可能性があります。

残念ながら、リーダーに基づくプロトコル(（HotstuffやJolteon)など）は、本質的にリーダーの障害時に進捗を確保するためにタイムアウトを必要とします。タイムアウトがない場合、崩壊したリーダーでさえもプロトコルを永遠に停止させる可能性があります。非同期の間に障害と遅いリーダーを区別できないため、タイムアウトは検証ノードがコンセンサスの活動がない状態で全てのリーダーを交換する原因となる可能性があります。

Bullsharkでは、DAG構築のためにタイムアウトが使用され、同期中に誠実なリーダーが十分に速くアンカーポイントをDAGに追加してソートできるようにします。

私たちはDAG構築がネットワーク速度を推定する「時計」を提供することに気付きました。n-f人の誠実な検証者がDAGに頂点を追加し続ける限り、ラウンドは進みます。Bullsharkはネットワーク速度で並べ替えることができないかもしれませんが、DAGはネットワーク速度で成長します。最終的に、障害のないリーダーが十分に速くアンカーポイントをブロードキャストすると、アンカーポイントの全ての因果歴史が並べ替えられます。

評価において、私たちはタイムアウトの有無でBullsharkを比較しました。

1. 高速リーダー:2つの方法は同じ遅延を持ち、アンカーポイントはソートされており、タイムアウトは使用されません。

2. 誤ったリーダー: 無超時Bullsharkは遅延が低く、検証ノードはそのアンカーポイントをすぐにスキップします。

3. スローペースのリーダー：タイムアウトのあるBullsharkは、バリデーターがアンカーポイントを待つため、タイムアウトがないとアンカーポイントをスキップする可能性があります。

Shoalでは、タイムアウトを避けることはリーダーの評判と密接に関連しています。遅いリーダーを繰り返し待つことは遅延を増加させ、一方で評判メカニズムは遅い検証者がリーダーに選ばれることを除外します。これにより、システムはすべての現実のシナリオでネットワーク速度で動作できます。

注意が必要なのは、FLP不可能性の結果が、決定論的合意プロトコルがタイムアウトを完全に回避することはできないことを示しているということです。Shoalはこの結果を回避することはできません。なぜなら、理論的にはすべてのアンカーポイントの順序付けを阻止する対抗的なイベントのタイムテーブルが存在するからです。逆に、設定可能な連続してスキップするアンカーポイントの数を超えた場合、Shoalはタイムアウトに戻ります。しかし、実際にはそのような状況が発生することは非常に稀です。

ユニバーサルな応答性

Hotstuff論文は楽観的応答の概念を普及させ、直観的にはプロトコルが良好な状況下で(、迅速なリーダーと同期ネットワーク)を含んでネットワーク速度で動作できることを意味します。

Shoalは、普遍的な応答性と呼ばれるより良い機能を提供します。具体的には、Hotstuffと比較して、リーダーが設定可能な連続ラウンド数内で失敗したり、ネットワークが非同期の周期を経験しても、Shoalはネットワークの速度で動作し続けます。

一般的な応答性は、非同期期間およびリーダー障害時に厳格に優れた進捗保証を提供します。遅いリーダーと同期している間、これらの特性はリーダーの速度に依存するため直接比較することはできません。しかし、リーダーの評判メカニズムを考慮すると、Shoalの中で遅いリーダーはほとんど存在しないはずです。

![万字詳解Shoalフレームワーク：どのように減