技術要約: Hermes: プレフィックス・コンセンサスによる低テールレイテンシ

1. 問題提起

リーダーベースのビザンチン障害耐性（BFT）プロトコルは、通常、指定されたリーダーが適時に動作する場合にのみトランザクションを確定させる。もしリーダーがクラッシュしたり遅延したりした場合、ビュー（view）を終了させるためにタイムアウトを用いる必要があるが、その結果、「無駄な」ビューが発生する。これは、タイムアウトの設定において根本的なトレードオフを生じさせる：

• 保守的なタイムアウト: 遅いリーダーを許容するが、リーダーがクラッシュするたびに長い停滞へと変換されてしまう。
• 積極的なタイムアウト: クラッシュしたリーダーを迅速にスキップできるが、単に「遅い」だけのリーダーのビューまで無効にしてしまう（これは地理的分散システムにおいてよくある現象である）。

どちらの場合も、期限切れとなったビューは無駄になり、リクエストはビュー変更と次のリーダーのラウンドトリップを待ってから確定しなければならない。このトレードオフが、システムの「グッドケース（正常時）」のパフォーマンスではなく、テールレイテンシを支配してしまう。さらに、現代のアーキテクチャでは、データの普及（DAG、レーンベースのデザインなど）とコンセンサスによる順序付けを分離することが多い。このような設定において、プロポーザルはストリームのプレフィックス（接頭辞）であり、同一ビュー内の正直なプロポーザルは、ネットワークのジッターによりサフィックス（接尾辞）のみが異なる場合が多い。既存のプロトコルは、これらの不一致を「不一致」として破棄してしまい、共有されている共通のプレフィックスを活用できていない。

2. 手法

Hermesは、部分同期条件下での $n = 5f + 1$ プロセスを対象とした、2ラウンド・ローテーティングリーダー・プロトコルである。これは、投票が値の順序関係（$\preceq$）によって保持される**プレフィックス・コンセンサス（Prefix Consensus）を導入しており、クォーラムには「等価性」ではなく「比較可能性（comparability）」**を要求する。

コアメカニズム

• 2ラウンド構造:

  1. ラウンド1 (プロポーザル): すべてのプロセスが正当化されたプロポーザルをブロードキャストする。ラウンドロビン形式のリーダーのプロポーザルは、$n$ 個のうちの1つである。
  2. ラウンド2 (投票): すべてのプロセスが単一の投票を行う。
     • リーダーのプロポーザルが適時に配信された場合、プロセスはそれに対して投票する。
     • タイムアウト（$2\Delta$）が発生し、$n-f$ 個の有効なプロポーザルを受信した場合、プロセスは利用可能なセットから選択されたフォールバック・プロポーザルに対して投票する。
  • 決定的なことに、nullify（無効化）投票は存在しない。

• クォーラムの定義:

  • M-notarization: 互いに比較可能な $2f+1$ 個の投票。これにより、ビューを次のビューへ進めることができる。
  • L-notarization: $n-f = 4f+1$ 個の有効な投票（これらは同一である必要はない）。このセットは、投票の**最重共通プレフィックス（Heaviest Common Prefix: HCP）**を確定させる。

• タイムアウトの処理:
  リーダーが遅い場合にビューを無効にする代わりに、Hermesはタイムアウト経路を利用して、$n-f$ 個の投票から得られるHCPを確定させる。積極的なタイムアウトを用いても、失われるのは投票が食い違っているサフィックスの部分のみであり、ビュー全体が失われることはない。HCPは $2\Delta + \delta$ で確定される。

• 値空間のインスタンス化:
  プロトコルは抽象的なプレフィックス順序空間上でインスタンス化され、以下の2つの具体的なシナリオに適用される：

  1. シングルレーン（ファイナリティ・ガジェット）: 動的に利用可能なチェーン（例：Ethereum）上。値はチェーンのチップ（tip）であり、プレフィックス関係は祖先関係である。
  2. マルチレーン（Autobahnスタイル）: 並行するデータレーンの順序付け。これには、以下の3つの課題への対処が含まれる：
     • 決定論的インターリービング: レーンの位置に関するグローバルな順序。
     • 親相対的なデルタ・チップカット（Parent-Relative Delta Tipcuts）: ヘテロジニアスなレーンスピードを扱うために、フル値を送信することなく、親の識別子と明示的なスキップマーカーを用いたコンパクトな表現。
     • 送信者インデックス付き消去符号化増幅（Sender-Indexed Erasure-Coded Amplification）: 通信複雑性を $O(n^3 \hat{m})$ に膨らませることなく可用性を確保するため、プロポーザルは消去符号によって増幅される。正当化（justification）は識別子を運び、断片（fragment）はオンデマンドで再構成される。

3. 主な貢献

1. Hermesプロトコル: nullificationパスを持たない、$n=5f+1$ の2ラウンド・ローテーティングリーダー・プロトコル。
   • グッドケース: 適時な正直なリーダーの下で $2\delta$ での確定。
   • バッドケース: いかなる $n-f$ 個の投票のHCPも $2\Delta + \delta$ で確定。
   • 安全性と生存性: 抽象的なプレフィックス値空間上で証明されている。
2. シングルレーン・インスタンス化: 値がチェーンのチップである利用可能なチェーンのためのファイナリティ・ガジェット。
3. マルチレーン・インスタンス化: 以下の特徴を持つAutobahnスタイルのレーンのための設計：
   • 決定論的インターリービング。
   • 明示的なスキップ認証を伴う、親相対的なデルタ・チップカット。
   • 送信者インデックス付き消去符号化増幅。
   • 複雑性: ビューあたり $O(n^2 \hat{m} + \lambda n^3)$ ビットおよび $O(n^2)$ メッセージ（ここで $\hat{m}$ はレーンの数、$\lambda$ はセキュリティパラメータ）。
4. 実装と評価: 本論文には実装と評価（セクション8）が含まれているが、提供されたテキスト内では具体的な数値結果は「結果を追加」とマークされている。

4. 結果とパフォーマンス

• レイテンシ:
  • 適時なリーダー: $2\delta$ で確定。
  • 遅延またはクラッシュしたリーダー: HCPを $2\Delta + \delta$ で確定。これは、遅いリーダーが完全なビュー変更とそれに続く $2\delta$ のラウンド、合計で $2\Delta + 3\delta$ 以上を要する従来のプロトコルと比較して、大幅な改善である。
• 通信:
  • 増幅を用いるマルチレーン設定において、プロトコルはフル値を転送することに伴う 4 次の複雑性（$O(n^3 \hat{m})$）を回避する。
  • グッドケースでは $O(n^2)$ メッセージを維持する。障害発生時には、増幅トラフィックによりメッセージ複雑性が $O(n^3)$ に上昇する場合があるが、ビット複雑性は制御されている。
• テールレイテンシ: タイムアウト経路を生産的にすることで、Hermesは「無駄なビュー」のペナルティを排除する。悪いビューに当たったリクエストは、タイムアウトとHCPの確定を支払うだけで済み、完全なビュー変更サイクルを待つ必要はない。

5. 意義

本論文は、Hermesが応答性（いかに速くビューが変わるか）と安定性（どれだけのビュー変更が進行を生むか）の間のトレードオフを根本的に変えるものであると主張している。

• 生産的なタイムアウト: タイムアウトがビューの無効化を意味する従来の設計とは異なり、Hermesは失敗したリーダーを含むビューであっても、データストリームの有用なプレフィックスを確定させることを保証する。
• 現代のアーキテクチャへの適合性: DAGやレーンベースのシステムのような、利用可能なデータ普及層とコンセンサスの間の溝を埋め、ファイナリティ・ガジェットが、普及層で既に伝播しているものの、わずかに分岐している可能性があるブロックを順序付けることを可能にする。
• 最適性: Hermesは、グッドケースにおける理論的下限である $2\delta$ を達成しつつ、別途のリカバリプロトコルやレースメカニズムを必要とせずに、リーダーベースのBFTに長年存在してきたテールレイテンシの問題を解決する。

Hermesは、失敗したリーダーのビュー自体が確定するという点において、そのクラスの中で唯一のプロトコルとして位置づけられている。これは、そのようなビューを無効化するMinimmitや、プレフィックス投票を可用性のために用いるものの単一のリーダーのプロポーザル内に留まるRaptrといったプロトコルとは対照的である。