4D Shoal フレームワークの説明: Aptos で Bullshark のレイテンシを短縮する方法?

オリジナル: アプトス研究所

編集：アプトス・グローバル

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-a5fdeca023-dd1a6f-62a40f)

＃＃＃ 概要

1. Aptos labs は、DAG BFT における 2 つの重要な未解決の問題を解決し、遅延を大幅に短縮し、決定論的な実際のプロトコルにおける一時停止の必要性を初めて排除しました。全体として、これにより、Bullshark のレイテンシーは、障害がない場合で 40%、障害がある場合で 80% 改善されます。

2. Shoal は、パイプライン化とリーダーの評判を通じて、Narwhal ベースのコンセンサス プロトコル (DAG-Rider、Tusk、Bullshark など) を強化するフレームワークです。パイプライン化は、ラウンドごとにアンカーを導入することで DAG 順序付けのレイテンシーを短縮し、リーダー レピュテーションはアンカーが最速のバリデーターに関連付けられるようにすることでレイテンシーをさらに改善します。さらに、リーダーの評判により、Shoal は非同期 DAG 構築を活用して、すべてのシナリオでタイムアウトを排除できます。これにより、Shoal は、通常必要とされる楽観的な応答を含む、Universal Response と名付けたプロパティを提供できるようになります。

3. 私たちの手法は非常に単純で、基礎となるプロトコルの複数のインスタンスを順番に実行する必要があります。したがって、Bullshark でインスタンス化すると、リレー レースを行っている「サメ」のグループが得られます。

＃＃＃ モチベーション

ブロックチェーン ネットワークの高性能を追求する中で、通信の複雑さを軽減することに常に焦点が当てられてきました。ただし、このアプローチではスループットが大幅に向上することはありませんでした。たとえば、Diem の初期バージョンでの Hotstuff 実装では 3500 TPS しか達成できず、100k+ TPS を達成するという目標をはるかに下回っていました。

しかし、最近のブレークスルーは、データ伝播がリーダーベースのプロトコルの主なボトルネックであり、並列化の恩恵を受けることができるという認識から生まれています。 Narwhal システムは、データ伝播をコアのコンセンサス ロジックから分離し、すべてのバリデーターが同時にデータを伝播し、コンセンサス コンポーネントが少量のメタデータのみを注文するアーキテクチャを提案します。イッカクの論文では、スループットが 160,000 TPS であると報告されています。

前回の記事では、Quorum Store について紹介しました。私たちの Narwhal 実装はデータ伝播をコンセンサスから切り離しており、これを使用して現在のコンセンサス プロトコルである Jolteon を拡張する方法を説明します。 Jolteon は、Tendermint の線形高速パスと PBFT スタイルのビュー変更を組み合わせて、Hotstuff の遅延を 33% 削減するリーダーベースのプロトコルです。ただし、リーダーベースのコンセンサス プロトコルでは、Narwhal のスループットの可能性を完全に活用できないことは明らかです。データ伝播をコンセンサスから分離しているにもかかわらず、Hotstuff/Jolteon のリーダーは、スループットが増加するにつれて依然として制限を受けています。

したがって、通信オーバーヘッドがゼロのコンセンサス プロトコルである Bullshark を Narwhal DAG 上にデプロイすることにしました。残念ながら、Bullshark の高スループットをサポートする DAG 構造には、Jolteon と比較して 50% の遅延ペナルティが伴います。

この投稿では、Shoal がどのようにして Bullshark の遅延を大幅に短縮することができたのかについて説明します。

DAG-BFT の背景

この記事の関連する背景を理解することから始めましょう。イッカクとブルシャークの詳細については、DAG meets BFT の投稿を参照してください。

Narwhal DAG の各頂点はラウンド番号に関連付けられます。ラウンド r に入るために、検証者はまずラウンド r-1 に属する nf 個の頂点を取得する必要があります。各ベリファイアはラウンドごとに 1 つの頂点をブロードキャストでき、各頂点は前のラウンドの少なくとも nf 個の頂点を参照します。ネットワークの非同期により、異なるバリデータがいつでも DAG の異なるローカル ビューを観察する可能性があります。以下に、考えられる部分ビューを示します。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-931319a954-dd1a6f-62a40f)

図 1: ラウンド 2 検証ノード 2 によって特定された頂点の因果関係の履歴が緑色で強調表示されています

DAG の重要な特性は曖昧さではありません。DAG のローカル ビューで同じ頂点 v を持っている場合、2 つのバリデーターは v のまったく同じ因果関係履歴を持ちます。

合計注文数

追加の通信オーバーヘッドなしで、DAG 内のすべての頂点の合計順序について合意することができます。この目的を達成するために、DAG-Rider、Tusk、および Bullshark のバリデーターは DAG の構造をコンセンサス プロトコルとして解釈し、頂点が提案を表し、エッジが投票を表します。

グループ交差ロジックは DAG 構造によって異なりますが、既存のすべての Narwhal ベースのコンセンサス プロトコルは次の構造を持っています。

1. 所定のアンカー。数ラウンド (たとえば、ブルシャークでは 2 ラウンド) ごとに所定のリーダーが存在し、リーダーの頂点はアンカーと呼ばれます。

２）アンカーを順序付けする。検証者は、どのアンカーを順序付けし、どのアンカーをスキップするかを独立して決定的に決定する。

3. 因果履歴を順序付けします。バリデーターは順序付けされたアンカーのリストを 1 つずつ処理し、アンカーごとに、因果関係履歴内の以前に順序付けされていないすべての頂点を何らかの決定論的なルールによって並べ替えます。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-51897602ab-dd1a6f-62a40f)

図 2: Bullshark プロトコルにおける DAG の考えられる部分図の図。この例では、赤と黄色のアンカーが並べ替えられ、緑 (DAG にない) はスキップされます。したがって、DAG を順序付けるために、バリデーターは最初に赤いアンカーの因果関係を決定論的に順序付けし、次に黄色のアンカーを順序付けます。

セキュリティを満たすための鍵は、上記のステップ (2) で、すべての正直なバリデーターが、すべてのリストが同じプレフィックスを共有するように順序付けられたアンカーのリストを作成することを保証することです。 Shoal では、上記のすべてのプロトコルについて次のような観察を行っています。

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

Bullshark のレイテンシ

Bullshark のレイテンシは、DAG 内の順序付けされたアンカー間のラウンド数によって異なります。 Bullshark の最も有用な部分同期バージョンは、非同期バージョンよりも遅延が優れていますが、最適とは程遠いです。

問題 1: 平均ブロック遅延。 Bullshark では、すべての偶数ラウンドにアンカーがあり、すべての奇数ラウンドの頂点が投票として解釈されます。通常、アンカーを順序付けるには DAG の 2 ラウンドが必要ですが、アンカーの因果関係履歴内の頂点は、アンカーが順序付けられるまで待機するのにさらに多くのラウンドがかかります。一般的なケースでは、奇数ラウンドの頂点には 3 ラウンドが必要ですが、偶数ラウンドの非アンカー頂点には 4 ラウンドが必要です (図 3 を参照)。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-94f64a51cc-dd1a6f-62a40f)

図 3: 一般的なケースでは、ラウンド i+1 のアンカーは 2 ラウンドにわたってソートする必要があります。ラウンド i の頂点は同時にソートされるため、待ち時間は 3 ラウンドになります。ただし、ラウンド i+1 の頂点は次のアンカー (ラウンド i+3 のアンカー) がソートされるまで待機する必要があるため、ソートの遅延は 4 ラウンドになります。

問題 2: 失敗ケースのレイテンシ。上記のレイテンシ分析は失敗のないケースに適用されます。一方、ラウンドのリーダーが十分な速さでアンカーをブロードキャストできない場合、アンカーは順序付けできません (したがってスキップされます)。前のラウンドでソートされていない頂点は、次のアンカーがソートされるまで待つ必要があります。これにより、特に Bullshark がリーダーを待機するタイムアウトを使用するため、地理的に複製されたネットワークのパフォーマンスが大幅に低下する可能性があります。

浅瀬フレームワーク

Shoal は、パイプライン化によって Bullshark (または他のイッカクベースの BFT プロトコル) を強化し、各ラウンドでアンカーを許可し、DAG 内のすべての非アンカー頂点のレイテンシを 3 ラウンドに短縮することで、これらのレイテンシの問題の両方を解決します。 Shoal はまた、DAG にゼロオーバーヘッドのリーダー評価メカニズムを導入し、高速リーダーを優先して選択にバイアスをかけます。

＃＃＃ チャレンジ

DAG プロトコルのコンテキストでは、パイプラインとリーダーの評判は次の理由から難しい問題とみなされます。

1. 以前のパイプライン処理では、Bullshark のコア ロジックを変更しようとしましたが、これは本質的に不可能であると思われます。

2. DiemBFT で導入され、Carousel で正式化されたリーダー評判は、バリデーターの過去のパフォーマンスに基づいて将来のリーダー (Bullshark のアンカー) を動的に選択するというアイデアです。リーダーのアイデンティティに関する意見の相違は、これらのプロトコルではセキュリティに違反しませんが、Bullshark では、完全に異なる順序につながる可能性があり、これが問題の核心になります。ホイール アンカーの動的かつ決定論的な選択が、必要な合意の解決策であるということです。一方、バリデーターは将来のアンカーを選択するために順序付けされた履歴に同意する必要があります。

問題の難しさの証拠として、実稼働環境での現在の実装を含む Bullshark の実装がこれらの機能をサポートしていないことに注意してください。

＃＃＃ 合意

前述の課題にもかかわらず、ことわざにあるように、解決策はシンプルさの背後にあることがわかりました。

Shoal では、DAG 上でローカル計算を実行する機能に依存し、以前のラウンドからの情報を保存および再解釈する機能を実装しています。すべてのバリデーターが最初に順序付けされたアンカーに同意するという核となる洞察に基づいて、Shoal は、(1) 最初に順序付けされたアンカーがインスタンスの切り替えポイントとなり、(2) アンカーの因果関係が分かるように、複数の Bullshark インスタンスを順番に構成することでそれらをパイプライン化します。アンカーはリーダーの評判を計算するために使用されます。

パイプライン処理

Bullshark と同様に、バリデーターは潜在的なアンカーについてアプリオリに同意します。つまり、リーダーへのラウンドをマッピングする F:R -> V という既知のマッピングが存在します。 Shoal は、各インスタンスのアンカーがマップ F によって事前に決定されるように、Bullshark のインスタンスを次々に実行します。各インスタンスはアンカーを命令し、それが次のインスタンスへの切り替えをトリガーします。

最初に、Shoal は DAG の最初のラウンドで Bullshark の最初のインスタンスを起動し、最初に順序付けされたアンカーが特定されるまで (たとえばラウンド r で) 実行します。すべてのバリデーターはこのアンカーに同意します。したがって、すべてのバリデーターは、ラウンド r+1 から開始して DAG を再解釈することに決定的に同意できます。 Shoal はラウンド r+1 で Bullshark の新しいインスタンスを開始したところです。

最良のシナリオでは、これによりショールはラウンドごとにアンカーを注文できるようになります。最初のラウンドのアンカーは、最初のインスタンスによってソートされます。次に、Shoal は第 2 ラウンドで新しいインスタンスを開始し、インスタンス自体がインスタンスによって順序付けされたアンカーを持ち、次に別の新しいインスタンスが第 3 ラウンドでアンカーを順序付けし、プロセスが続行します。以下の図を参照してください。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-815c54edb-dd1a6f-62a40f)

図 4: F によって決定されたリーダーに対応する頂点は、王冠でマークされています。Bullshark の最初のインスタンスは、最初にラウンド 1、3、および 5 のアンカーを使用して DAG を解釈します。Bullshark はラウンド 1 でアンカーを決定します (緑色のチェックマーク)マーク）は、最初のインスタンスで最初に並べ替えられます。 (一般的なケースでは、このアンカーはスキップできますが、他のいくつかのアンカーが最初にソートされることに注意してください。) その後、最初のインスタンスの残りの部分は無視され、Bullshark の新しいインスタンスがラウンド 2 から開始され、アンカー ポイントがマークされます。ラウンド2と4で。

リーダーの評判

Bullshark の並べ替え中にアンカーをスキップするときの遅延が増加しました。この場合、前のインスタンスがアンカーを命令するまで新しいインスタンスを開始できないため、パイプライン手法は無力です。 Shoal は、レピュテーション メカニズムを使用して、最近のアクティビティの履歴に基づいて各バリデーターにスコアを割り当てることで、失われたアンカーに対処するために適切なリーダーが将来選出される可能性が低くなります。プロトコルに応答して参加するバリデーターには高いスコアが割り当てられますが、そうでない場合は、クラッシュしたり、速度が遅かったり、悪意がある可能性があるため、バリデーターには低いスコアが割り当てられます。

このアイデアは、スコアが更新されるたびに、ラウンドからリーダーまでの事前定義されたマッピング F を決定論的に再計算し、より高いスコアを持つリーダーを優先することです。バリデーターが新しいマッピングに同意するには、スコア、つまりスコアの導出に使用される履歴について同意する必要があります。

Shoal では、パイプライン処理とリーダーシップの評判を自然に組み合わせることができます。これは、どちらも最初に順序付けされたアンカーについて合意した後に DAG を再解釈するという同じコア技術を使用しているためです。

実際、唯一の違いは、ラウンド r でアンカーを並べ替えた後、バリデーターはラウンド r で順序付けされたアンカーの因果関係に基づいてラウンド r+1 から新しいマッピング F' を計算するだけでよいことです。次に、バリデーターは、更新されたアンカー選択関数 F' を使用して、ラウンド r+1 から始まる Bullshark の新しいインスタンスを実行します。以下の画像を参照してください。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-c1d8088bd3-dd1a6f-62a40f)

図 5. F で識別されるリーダーに対応する頂点は、透明なクラウンでマークされています。 Bullshark の最初のインスタンスは、緑色のチェックマークが付けられたラウンド 1 でアンカーを注文し、アンカーの因果関係履歴の情報に基づいて新しいマッピング F' を計算します。 F' によって決定されたリーダーは、色付きの王冠でマークされます。

タイムアウトはもうありません

タイムアウトは、すべてのリーダーベースの決定論的部分同期 BFT 実装において重要な役割を果たします。ただし、複雑さが導入されると、管理および監視する必要がある内部状態の量が増加するため、デバッグ プロセスが複雑になり、より多くの可観測性テクニックが必要になります。

タイムアウトは、環境 (ネットワーク) に大きく依存するため、適切に構成することが重要であり、通常は動的に調整する必要があるため、遅延が大幅に増加する可能性があります。プロトコルは、次のリーダーに移動する前に、障害のあるリーダーにタイムアウト遅延ペナルティの全額を支払います。したがって、タイムアウト設定を控えめにしすぎることはできませんが、タイムアウトが短すぎると、プロトコルが適切なリーダーをスキップする可能性があります。たとえば、高負荷下では、Jolteon/Hotstuff のリーダーが圧倒され、進捗を進める前にタイムアウトが切れてしまうことが観察されました。

残念ながら、Hotstuff や Jolteon などのリーダーベースのプロトコルでは、リーダーが失敗するたびにプロトコルを確実に進めるために、本質的にタイムアウトが必要です。タイムアウトがなければ、リーダーがクラッシュしてもプロトコルが永久に停止する可能性があります。非同期中は障害のあるリーダーと遅いリーダーを区別できないため、タイムアウトによりバリデーターはコンセンサスが活性化されていない状態ですべてのリーダーへの変更を認識する可能性があります。

Bullshark では、同期中に正直なリーダーが順序付けられるのに十分な速さでアンカーを DAG に追加することを保証するために、DAG の構築にタイムアウトが使用されます。

DAG 構造がネットワークの速度を推定するための「クロック」を提供していることがわかります。一時停止がない場合、nf の正直なバリデーターが DAG に頂点を追加し続ける限り、ラウンドは進行し続けます。 Bullshark は (リーダーに問題があるため) ネットワーク速度でソートできない場合がありますが、リーダーに問題があるかネットワークが非同期であるにもかかわらず、DAG は依然としてネットワーク速度で成長します。最終的に、欠陥のないリーダーが十分な速度でアンカーをブロードキャストすると、アンカーの因果関係全体が順序付けされることになります。

評価では、次のケースでタイムアウトありとタイムアウトなしの Bullshark を比較しました。

1. 高速リーダー。少なくとも他のバリデーターよりも速いことを意味します。この場合、アンカーが順序付けされ、タイムアウトが使用されないため、どちらの方法でも同じレイテンシーが得られます。

2. 偽のリーダー。この場合、一時停止のない Bullshark は、バリデーターがすぐにアンカーをスキップするため、レイテンシーが向上します。一方、一時停止のあるバリデーターは、Expect を続行する前に到着を待機します。

3. リーダーが遅い。これは、Bullshark のタイムアウト パフォーマンスが優れている唯一のケースです。これは、一時停止しないと、リーダーが十分な速度でアンカーをブロードキャストできないため、アンカーがスキップされる可能性があるのに対し、一時停止すると、バリデーターがアンカーを待つことになるためです。

ショールでは、タイムアウトの回避とリーダーシップの評判は密接に関連しています。遅いリーダーを繰り返し待つと待ち時間が増加し、リーダーの評判メカニズムにより、遅いバリデーターがリーダーとして選出されなくなります。このように、システムは高速検証ノードを利用して、現実世界のすべてのシナリオでネットワーク速度で実行します。

FLP 不可能という結果は、決定論的なコンセンサス プロトコルではタイムアウトを回避できないことを示していることに注意してください。すべてのアンカーが指揮されることを妨げる敵対的イベントの理論的なスケジュールが存在するため、ショールはこの結果を回避することができません。代わりに、Shoal は、設定可能な回数連続してアンカー スキップを行った後、タイムアウトに戻ります。実際には、これが起こる可能性は非常に低いです。

一般的な対応

Hotstuff の論文は、楽観的応答の概念を広めました。この概念は、正式には定義されていませんが、直観的には、高速リーダーや同期ネットワークなどの良好な条件下でプロトコルがネットワーク速度で実行できることを意味します。

Shoal は、ユニバーサル レスポンスと呼ばれる、さらに優れた特性を提供します。具体的には、Hotstuff とは対照的に、Shoal は、ネットワークが通過する構成可能な数の連続ラウンドまたは非同期サイクル中にリーダーが失敗した場合でも、ネットワーク速度で実行し続けます。以下の表で詳細な比較をご覧ください。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-b87c1b94cb-dd1a6f-62a40f)

ユニバーサル応答性は、非同期期間中およびリーダーが失敗した場合に、厳密に優れた進捗保証を提供することに注意してください。遅いリーダーとの同期中は、リーダーの速度に依存するため、これらの特性は比較できません。ただし、リーダーの評判を考えると、動きの遅いリーダーがショールに現れることはほとんどありません。

＃＃＃ 評価

イッカク実装クォーラム ストアの上に Bullshark と Shoal を実装しました。 Shoal、Bullshark、Jolteon の詳細な比較は、Shoal 論文の評価セクションに記載されており、いくつかのハイライトが示されています。

まず、非同期 DAG 構築の威力を実証するために、Bullshark を一時停止ありとなしで比較します。 Bullshark の完全な論文は非同期ネットワークを前提としていますが、高速パス モードを提供しているため、すべてのラウンド中に一時停止が必要です。このバージョンをバニラ ブルシャークと呼びます。独立した部分同期ネットワークの仮想バージョンでは、投票ラウンドの一時停止が必要ないことがわかります。このバージョンを、投票タイムアウトなしの Vanilla Bullshark (投票タイムアウトなし) と呼びます。ベースライン Bullshark は、タイムアウトなしのバージョンです。

以下のグラフは、障害が発生した場合と発生しなかった場合の、Bullshark レイテンシに対するタイムアウトの影響を比較しています。どうやら、ベースライン Bullshark (タイムアウトなし) は、障害が発生した場合に最高のパフォーマンスを発揮します。失敗がなければ、Baseline Bullshark は投票停止のない Vanilla Bullshark に匹敵します。これは、前述したように、リーダー評価メカニズムがないと、リーダーが優れているが遅い状況ではタイムアウトが有利になる可能性があるためです。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-d49abda989-dd1a6f-62a40f)

図 6.: 障害なし (左) と障害あり (右) の Bullshark レイテンシーに対するタイムアウトの影響 (障害の場合は 50 個のバリデーターあり)

次に、Baseline Bullshark (タイムアウトなし) を使用して Shoal をインスタンス化し、パイプライン処理とリーダー評価メカニズムのレイテンシの改善を障害ありとなしで実証します。また、完全を期すために、Jolteon と障害ありと障害なしで比較します。

以下の図 7 は、障害が発生していない場合を示しています。パイプライン処理とリーダー レピュテーションは両方とも個別にレイテンシーを削減できますが、それらを組み合わせることで最高のレイテンシーが得られます。

Jolteon に関しては、20 を超えるバリデータに拡張することはできず、Quorum Store で実行したとしても、データ伝播のボトルネックを取り除く Bullshark/Shoal の約半分のスループットしか達成できません。

結果は、Shoal が Bullshark の遅延を大幅に改善することを示しています。 Jolteon に関しては、コンセンサス レイテンシを測定しただけであることに注意することが重要です。 Jolteon は DAG 上でネイティブに実行できないため、データ伝播を切り離すために追加のレイテンシが必要ですが、これは測定していません。したがって、高負荷下では、Shoal は Jolteon のエンドツーエンドのレイテンシと一致する必要があります。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-2ccc6874f4-dd1a6f-62a40f)

図 7: 障害のないスループットとレイテンシー。Shoal PL と Shaol LR は、それぞれパイプラインとリーダー レピュテーションのみをサポートします。

以下の図 8 は、50 個のバリデーターによる失敗ケースを示しています。リーダー レピュテーション メカニズムは、失敗したバリデーターがリーダーとして選出される確率を低減することで、レイテンシを大幅に改善します。 50 回中 16 回の失敗で、Shoal のレイテンシはベースライン Bullshark より 65% 低かったことに注意してください。

!【Shoalフレームワークを詳しく解説：AptosでBullsharkのレイテンシーを減らすには？ ](https://img.gateio.im/social/moments-69a80767fe-729e379b05-dd1a6f-62a40f)