💻 computer science

FairDAG: Consensus Fairness over Multi-Proposer Causal Design

本論文は、既存のリーダーベースのシステムにおけるスループットと操作の制限を克服するために、公平性プロトコルをDAGベースのコンセンサスと統合した新しいフレームワークであるFairDAGを提案し、それによってブロックチェーンネットワークにおける優れたトランザクション順序の公平性とパフォーマンスを実現するものである。

原著者： Dakai Kang, Junchao Chen, Tien Tuan Anh Dinh, Mohammad Sadoghi

公開日 2026-01-30

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Dakai Kang, Junchao Chen, Tien Tuan Anh Dinh, Mohammad Sadoghi

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

忙しいデジタル・マーケットプレイスを想像してみてください。そこでは、何千人もの人々が全く同時にアイテムを売買しようとしています。このマーケットプレイスでは、取引が行われる「順番」が極めて重要です。もしあなたが誰かより先にレアアイテムを購入できれば、それを手に入れることができます。しかし、もし後回しにされてしまえば、買い逃したり、より高い金額を支払うことになったりするかもしれません。

ブロックチェーン（暗号資産の背後にある技術）の世界では、ある問題が存在します。それは、取引の順番を決める責任者（「ブロック・プロポーザー」）が、不正を行う可能性があるということです。プロポーサーはリストを確認し、自分にとって利益のある動きを見つけると、リストを並べ替えて自分に有利に操作し、正直な人々を後回しにさせることができてしまいます。これは、店にVIP客が来た瞬間に列に割り込ませたり、あるいは、友人に最後の商品を先に売れるように列を組み替えたりするレジ係のようなものです。

既存の解決策は、単一の「メインのレジ係」（リーダー）が全員の希望を集めて順番を決めるという方法を試みてきました。しかし、これには2つの新たな問題が生じました。

ボトルネック： もしメインのレジ係の動きが遅かったり、処理能力を超えたりすると、店全体の動きが停滞してしまいます。
不正： もしそのメインのレジ係が不正な人物であれば、彼らがリストを独占しているため、依然として列を操作できてしまいます。

FairDAGの登場：「グループ・ライン」による解決策

この論文は、このマーケットプレイスを整理するための新しい方法である「FairDAG」を紹介しています。単一のレジ係に頼るのではなく、FairDAGは「マルチ・プロポーザー（複数提案者）」システムを採用しています。これは、巨大で相互に連結されたレジ係のネットワーク（レプリカ）が、それぞれ独自の取引リストを同時に叫び合っているようなものだと考えてください。

その仕組みは以下の通りです。簡単な例えを用いて説明します。

1. 信頼のウェブ（DAG）

単一の列を作る代わりに、イメージとしてはクモの巣（Directed Acyclic Graph、またはDAG）のような構造を持っています。レジ係が取引リストを書き込むたびに、彼らは単に一人に送るのではなく、最近耳にした他の複数のレジ係のリストに、自分のリストを紐付けます。

なぜこれが役立つのか： あるレジ係が取引を隠したり不正を行おうとしても、ウェブの構造によって、他の全員のリストが最終的に結合され、実際に何が起きたのかを裏付けることになります。ウェブから一つの糸を簡単に消し去ることはできず、そうしようとすれば構造全体がそれに気づいてしまいます。

2. 公平さへの2つのアプローチ

論文では、どの程度厳格にするかに応じて、列を並べるための2つの具体的な「ルール」を提案しています。

FairDAG-AB（絶対的なルール）： これは、厳格な「先着順」ルールです。全員が「AさんがBさんより先に到着した」と同意しているなら、Aさんが必ず最初に行わなければなりません。システムは、正直なレジ係がその取引をいつ確認したかに基づいて、すべての取引に対して特定の「チケット番号」を算出します。たとえ不正な者がデッキをシャッフルしようとしても、数学的な仕組みによって、正直なチケット番号が優先されるようになっています。
FairDAG-RL（相対的なルール）： これはもう少し柔軟な、「グルーピング」ルールです。時には、二人が同時にドアを通ってきた時のように、正確にどちらが先に到着したかを判断するのが不可能な場合があります。その場合、このルールは正確な秒数を争うのではなく、彼らを一つのグループとして扱います。もし90%の正直なレジ係が「AさんがBさんより先」と判断していれば、Aを先にします。もし判断が割れた場合は、彼らを同じ「バッチ（一括）」に入れます。これはより高速で、複雑な状況にもうまく対処できます。

3. 不正を打ち破る

論文では、FairDAGが単一のリーダーではなく多くのレジ係を用いたウェブ構造を使用しているため、以下のことが示されています。

不正は隠せない： 不正な者は、正直な人々のリストを無視することができません。なぜなら、ウェブの構造によって、それらのリストが最終的に含まれることが強制されるからです。
スピード： 全員が同時にリストを叫んでいるため、システムは一人の遅い人物を待つために停滞することはありません。従来の「単一リーダー」方式よりもはるかに高速に取引を処理できます。

結果

著者らは、FairDAGを従来の手法（PompeやThemisなど）と比較検証しました。その結果、以下のことが判明しました。

より高速： 単一のボトルネックが存在しないため、FairDAGはより多くの取引を毎秒処理できます（スループット）。
より公平： 不正な者がリストを逆転させたり、特定の取引を遅延させたりして順番を操作しようとしても、FairDAGは従来よりもはるかに正確に順番を維持します。
より堅牢： インターネットが低速であったり、一部のレジ係の応答が遅かったりしても、システムはクラッシュすることなく動き続けます。

まとめ

FairDAGは、簡単に賄賂を受け取ってしまう単一のマネージャーを、民主的で相互に連結されたチームに置き換えるようなものです。全員が同時にリストを叫び、それらのリストをウェブのように編み合わせることで、悪意のある者が順番を操作することをほぼ不可能にします。これにより、システムは単一の不正者によってコントロールできないほど大きく、かつ密接に繋がったものになります。FairDAGは、システムを高速に動かし続けながら、「順序操作の危機」を解決するのです。

技術要約: FairDAG: マルチプロポーザー因果設計におけるコンセンサス・フェアネス

1. 問題提起

分散型金融（DeFi）の台頭は、ブロックチェーンのトランザクション順序付けにおける決定的な脆弱性、すなわち**最大抽出可能価値（MEV）**を浮き彫りにしました。悪意のあるブロックプロポーザーは、フロントランニング、サンドイッチ攻撃、または清算操作を実行するためにトランザクションの順序を操作し、他の参加者の犠牲の上に利益を抽出することができます。

PompeやThemisといった既存のフェアネス・プロトコルは、レプリカのクォーラムからローカルなトランザクション順序を集約することで、グローバルな順序を導出し、これを軽減しようと試みています。しかし、これらのプロトコルはリーダーベースのコンセンサス（例：PBFT、Hot Stuff）に依存しています。このアーキテクチャは、主に以下の2つの制限をもたらします。

単一障害点によるボトルネック: 単一のリーダーがローカルな順序リングを集約します。リーダーがビザンチン（悪意のある）である場合、最終的なシーケンスを操作するためにローカルな順序リングを選択的に収集したり、トランザクションを検閲したりすることができます。また、リーダーが正直であっても、メッセージ複雑性が参加者数に対して二次関数的に増加するため、単一のリーダーはパフォーマンスのボトルネックとなります。
操作に対する脆弱性: ビザンチン・リーダーは、特定の正しいレプリカからのローカルな順序リングを除外することで、有効なクォーラムサイズを縮小させ、トランザクションの依存関係の操作や特定のトランザクションの遅延を容易にすることができます。

本論文は、優れたフェアネス・プロトコルは、順序操作に対する耐性を達成し、正しい参加者の要件を最小限に抑え、高いパフォーマンス（スループットと低レイテンシ）を維持しなければならないと断じています。

2. メソドロジー: FairDAGフレームワーク

著者らは、フェアネス・プロトコルをDAGベースのコンセンサス・プロトコル（例：Tusk、DAG-Rider、Bullshark）の上で動作させることで、コンセンサス層とフェアネス層を分離するフレームワークであるFairDAGを提案しています。

コア・アーキテクチャ

FairDAGは、2つの明確なレイヤーで動作します。

DAGレイヤー（コンセンサス）: 全てのレプリカがラウンド内でブロック（頂点）を並行して提案する、マルチプロポーザー設計を利用します。これらの頂点は前のラウンドを参照し、有向非巡回グラフ（DAG）を形成します。
- マルチプロポーザー設計: 単一リーダーのボトルネックを排除し、並列的なブロック提案と高いスループットを可能にします。
- 妥当性（Validity）プロパティ: DAGの因果構造により、正しいレプリカが頂点をブロードキャストした場合、全ての正しいレプリカは最終的にそれをコミットします。これにより、ビザンチン・リーダーが正しいレプリカからの順序リングを選択的に無視することを防ぎます。
フェアネス・レイヤー: DAGレイヤーからコミットされたローカルな順序リング（サブDAG）を処理し、最終的かつ公平なトランザクション順序を生成します。

プロトコル・バリアント

本論文では、それぞれ異なるフェアネス特性を保証する2つのFairDAGバリアントを導入しています。

A. FairDAG-AB (絶対的フェアネス / Absolute Fairness)

目標: **順序線形化可能性（Ordering Linearizability）**を保証します。全ての正しいレプリカがトランザクション $T_1$ を $T_2$ よりも先に受信した場合、 $T_1$ は $T_2$ よりも前に順序付けられなければなりません。
メカニズム:
- 各トランザクションには**割り当て順序インジケータ（AOI）**が割り当てられます。
- プロトコルは、既知およびコミットされた順序インジケータを追跡するために**順序インジケータ・マネージャー（OIM）**を使用します。
- DAGのコミット・レイテンシに対処するため、未コミットのトランザクションに対して**最小可能AOI（LPAOI）**を計算します。トランザクションは、そのAOIが他の保留中のトランザクションのLPAOIよりも厳密に低い場合にのみ確定されます。
- 最終的な順序は、AOIに基づいてトランザクションをソートすることによって決定されます。

B. FairDAG-RL (相対的フェアネス / Relative Fairness)

目標: ** $\gamma$ -バッチ順序フェアネス（ $\gamma$ -Batch-Order-Fairness）**を保証します。正当なレプリカの割合 $\gamma$ が $T_1$ を $T_2$ よりも先に受信した場合、 $T_1$ は $T_2$ より遅れて順序付けられることはありません。
メカニズム:
- ノードがトランザクションであり、エッジがローカルな順序リングから導出された順序の好みを表す**依存グラフ（Dependency Graph）**を構築します。
- 閾値の最適化: リーダー排除（潜在的なリーダー排除による）のために $n-2f$ のコミットされた順序リングに依存するThemisのようなリーダーベースのプロトコルとは異なり、FairDAG-RLはDAGの妥当性プロパティを活用して、少なくとも $n-f$ の順序リングがコミットされることを保証します。その結果、エッジ作成の閾値を $\frac{n-2f}{2}$ から $\frac{n-f}{2}$ へと引き上げます。
- グラフ凝縮（Graph Condensation）: プロトコルは、依存グラフにおける強連結成分（SCC）を特定します。プロトコルは「ソリッド（固定的）」なノード（十分なコミットされた順序リングを持つノード）の順序を確定させ、「シェイディッド（影の付いた）」ノードを、それらがソリッドになるまで後続のグラフに再追加します。
- このアプローチにより、フェアネスを保証するために必要な正しいレプリカの最小数が減少します（例： $\gamma=1$ の場合、 $n > 4f$ ではなく $n > 3f$ を要求）。

3. 主な貢献

新しいフレームワーク: リーダーベースのシステムに固有の、パフォーマンスとフェアネスのトレードオフを解決する、マルチプロポーザーDAGベースのコンセンサスとフェアネス・プロトコルを統合した初のフレームワークであるFairDAGの提案。
FairDAG-AB: DAGのコミット・ルールと互換性のある適応型LPAOIメカニズムを使用して、順序線形化可能性を保証する絶対的フェアネス・プロトコル。
FairDAG-RL: DAGの妥当性を利用して依存グラフ構築の閾値を下げ、正しい参加者の要件を減らし、パフォーマンスを向上させるThemisに対する改善。
新しいDAG構築ルール: フェアネス特性が敵対的な参加者に対して保持されることを確実にするための、特定のルール（例：遅いレプリカのための弱いエッジの包含、以前のローカル頂点への強いエッジの維持）の導入。
包括的な評価: 安全性、生存性（liveness）、およびフェアネスに関する広範な分析的証明と、実験的検証。

4. 実験結果

著者らはApache ResilientDBにFairDAGを実装し、PBFT、Pompe、Themis、RCC、Tuskと比較しました。

スループット:
- FairDAGは、リーダーベースのフェアネス・プロトコル（PompeおよびThemis）を大幅に上回りました。
- FairDAG-ABは、Pompeよりも**30.2%から52.6%**高いスループットを達成しました。
- FairDAG-RLは、シングルリージョン設定においてThemisよりも**5.1%から7.5%高いスループットを達成し、基礎となるDAGコンセンサスの堅牢性により、地理分散設定ではその差が42.1%**まで拡大しました。
レイテンシ:
- FairDAG-ABは（Tuskの基礎となるコミット・レイテンシのため）Pompeよりもわずかに高いレイテンシを示しますが、競争力のある水準を維持しています。
- FairDAG-RLは、故障レプリカ数（ $f$ ）が増加するにつれて、Themisよりも低いレイテンシを示します。これは、Themisがフェアネスを保証するために、より多くの正しいレプリカを必要とし、オーバーヘッドが増大するためです。
敵対的挙動への耐性:
- 「順序反転（Reversing Order）」および「標的遅延（Targeted Delay）」攻撃によるビザンチン・レプリカの実験において、FairDAG-ABおよびFairDAG-RLは、PompeおよびThemisと比較して、正しく順序付けられたトランザクション・ペアの高い比率を一貫して維持しました。DAGレイヤーの妥当性プロパティが、ビザンチン・アクターによる順序リングの選択的除外能力を効果的に抑制しました。

5. 重要性と主張

本論文は、FairDAGが、リーダーベースのシステムに内在するパフォーマンスとフェアネスの間のトレードオフを解決することにより、ブロックチェーンのフェアネスにおける重要な進歩を象徴していると主張しています。

耐性: 単一のリーダーを排除することで、FairDAGは、ローカルな順序リングを選択的に収集することを通じて、敵対者が最終的な順序を操作することを防ぎます。
効率性: マルチプロポーザー設計により、スループットのボトルネックが緩和され、フェアネス・プロトコルがネットワーク規模やワークロードに合わせてより良くスケールすることを可能にします。
要件の削減: DAGの妥当性プロパティにより、FairDAG-RLは、Themisのような最先端のリーダーベース・プロトコルと比較して、より少ない正しい参加者でフェアネスの保証を達成できます。

著者らは、FairDAGが、正常時および敵対的な状況の両方において優れたパフォーマンスを達成しながら、トランザクション順序付けに対する敵対的な操作を効果的に制約できると結論付けており、分散型金融やその他の重要なブロックチェーン・アプリケーションにおける公平なトランザクション順序付けのための実行可能なソリューションであることを示しています。