Shoalフレームワーク: 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は、データ伝播と合意を分離し、現在の合意プロトコルJolteonの拡張に使用されます。Jolteonはリーダーシップベースのプロトコルで、Tendermintの線形高速パスとPBFTスタイルのビュー変更を組み合わせることで、Hotstuffのレイテンシーを33%削減します。しかし、リーダーシップベースの合意プロトコルはNarwhalのスループットの潜在能力を十分に活用できません。

そのため、Narwhal DAGの上にBullsharkを展開することを決定しました。これは、ゼロ通信オーバーヘッドのコンセンサスプロトコルです。しかし、BullsharkのDAG構造は50%のレイテンシーコストをもたらします。

本文では、ShoalがBullsharkのレイテンシーを大幅に削減する方法について説明します。

DAG-BFTの背景

Narwhal DAGの各頂点は、1つのラウンドに関連付けられています。第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. 因果履歴のソート: 検証者は順序付けられたアンカーポイントのリストを1つずつ処理し、各アンカーポイントの因果履歴におけるすべての以前の無秩序な頂点をソートします。

安全性を満たすための鍵は、ステップ2で全ての誠実な検証ノードが順序付けられたアンカーポイントのリストを作成し、すべてのリストが同じプレフィックスを共有することを確認することです。Shoalでは、すべての検証者が最初の順序付けられたアンカーポイントに同意することを観察しました。

Bullsharkのレイテンシー

Bullsharkのレイテンシーは、DAG内の順序付きアンカーポイント間の回数に依存します。部分的な同期バージョンは非同期バージョンよりもレイテンシーが良好ですが、最適とは言えません。

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

1. 平均ブロックレイテンシー:一般的な場合、奇数ラウンドの頂点は3ラウンド、偶数ラウンドの非アンカーポイントの頂点は4ラウンド必要です。

2. 障害状況レイテンシー: あるラウンドのリーダーがタイムリーにアンカーポイントをブロードキャストできなかった場合、前のラウンドの未ソートの頂点は次のアンカーポイントのソートを待たなければならず、地理的複製ネットワークのパフォーマンスが著しく低下します。

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

Shoalフレームワーク

Shoalはパイプラインを通じてBullsharkを強化し、各ラウンドにアンカーポイントを設け、すべての非アンカーポイントの頂点のレイテンシーを3ラウンドに減少させます。Shoalはまた、迅速なリーダーを選択することを偏向するゼロコストのリーダー評判メカニズムを導入しました。

チャレンジ

DAGプロトコルにおいて、パイプラインとリーダーの評判は困難な問題と見なされています。

1. 以前のパイプラインはコアBullsharkロジックの修正を試みましたが、これは本質的に不可能なようです。

2. リーダーの評判は全く異なる順位を引き起こす可能性があり、バリデーターは将来のアンカーを選択するために整列された履歴で合意に達する必要があります。

問題の難易度の証拠として、現在の生産環境におけるBullsharkの実装はこれらの特性をサポートしていません。

プロトコル

ShoalはDAG上でローカル計算を実行することに依存しており、前のラウンドの情報を保存および再解釈する能力を実現しています。すべてのバリデーターが最初の順序付きアンカーポイントに同意する洞察を利用して、Shoalは複数のBullsharkインスタンスを順番に組み合わせてパイプライン処理を行い、次のことを可能にします:

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

流水ライン

Shoalは、Bullsharkインスタンスを1つずつ実行し、各インスタンスはアンカーを注文し、次のインスタンスへの切り替えをトリガーします。

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

理想的には、これによりShoalは各ラウンドで1つのアンカーポイントを注文することができます。

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

リーダーの評判

Bullsharkがアンカーポイントをスキップすると、レイテンシーが増加します。Shoalは評判メカニズムを通じて各検証ノードにスコアを割り当て、将来的に遅いリーダーが選ばれる可能性を低くします。

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

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

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

超過時間は必要ありません

リーダーに基づく決定論的部分同期BFT実装におけるタイムアウトは重要な役割を果たしますが、複雑さを引き起こし、レイテンシーを大幅に増加させます。

ShoalはDAG構造がネットワーク速度を推定する「時計」を提供することを観察しました。n-f個の誠実なバリデーターがDAGに頂点を追加し続ける限り、ラウンドは進行し続けます。最終的に、故障のないリーダーが十分に速くアンカーポイントをブロードキャストする際、アンカーポイントの全因果歴史が順序付けられます。

タイムアウトを避けることは、リーダーの評判と密接に関連しています。遅いリーダーを繰り返し待つことはレイテンシーを増加させ、評判メカニズムは遅い検証者がリーダーに選ばれることを排除します。

ユニバーサルレスポンス

Shoalは普遍的な応答特性を提供し、リーダーが失敗したりネットワークが非同期であってもネットワーク速度で動作します。これはHotstuffの楽観的な応答概念よりも優れています。

評価

BullsharkとShoalを実装し、Jolteonと比較しました。 主な調査結果:

1. タイムアウトのないベースライン・ブルシャークは、故障が発生した際に最も優れた性能を発揮します。

2. Shoalのパイプラインとリーダーの評判メカニズムはBullsharkレイテンシーを大幅に改善しました。

3. 50回の失敗のうち16回の失敗があった場合、ShoalのレイテンシーはBaseline Bullsharkより65%低い。

4. Jolteonは20の検証ノードを超えて拡張できず、スループットはBullshark/Shoalの約半分です。

総じて、ShoalはBullsharkのレイテンシーを大幅に改善し、高負荷時にJolteonのエンドツーエンドのレイテンシーに匹敵するはずです。

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

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

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

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

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