Technical Summary: FairDAG: Consensus Fairness over Multi-Proposer Causal Design

1. Problem Statement

The rise of decentralized finance (DeFi) has highlighted a critical vulnerability in blockchain transaction ordering: Maximal Extractable Value (MEV). Adversarial block proposers can manipulate the order of transactions to execute front-running, sandwich attacks, or liquidation manipulation, extracting profits at the expense of other participants.

Existing fairness protocols, such as Pompe and Themis, attempt to mitigate this by aggregating local transaction orderings from a quorum of replicas to derive a global order. However, these protocols rely on leader-based consensus (e.g., PBFT, HotStuff). This architecture introduces two primary limitations:

1. Single-Point-of-Failure Bottleneck: A single leader collects local orderings. If the leader is Byzantine, they can selectively collect orderings to manipulate the final sequence or censor transactions. Even if honest, a single leader becomes a performance bottleneck as message complexity grows quadratically with the number of participants.
2. Vulnerability to Manipulation: A Byzantine leader can exclude local orderings from specific correct replicas, reducing the effective quorum size and making it easier to manipulate transaction dependencies or delay specific transactions.

The paper posits that a well-designed fairness protocol must achieve resilience against ordering manipulation, minimize the requirement for correct participants, and maintain high performance (throughput and low latency).

2. Methodology: The FairDAG Framework

The authors propose FairDAG, a framework that decouples the consensus layer from the fairness layer, running fairness protocols atop DAG-based consensus protocols (e.g., Tusk, DAG-Rider, Bullshark).

Core Architecture

FairDAG operates in two distinct layers:

1. DAG Layer (Consensus): Utilizes a multi-proposer design where all replicas concurrently propose blocks (vertices) in rounds. These vertices reference previous rounds, forming a Directed Acyclic Graph (DAG).
   • Multi-Proposer Design: Eliminates the single-leader bottleneck, allowing parallel block proposals and higher throughput.
   • Validity Property: The causal structure of the DAG ensures that if a correct replica broadcasts a vertex, all correct replicas eventually commit it. This prevents Byzantine leaders from selectively ignoring orderings from correct replicas.
2. Fairness Layer: Processes the committed local orderings (sub-DAGs) from the DAG layer to generate a final, fair transaction ordering.

Protocol Variants

The paper introduces two variants of FairDAG, each guaranteeing a different fairness property:

A. FairDAG-AB (Absolute Fairness)

• Goal: Guarantees Ordering Linearizability. If all correct replicas receive transaction $T_1$ before $T_2$, $T_1$ must be ordered before $T_2$.
• Mechanism:
  • Each transaction is assigned an Assigned Ordering Indicator (AOI).
  • The protocol uses an Ordering Indicator Manager (OIM) to track seen and committed ordering indicators.
  • To handle the latency of DAG commit, it calculates a Lowest Possible AOI (LPAOI) for uncommitted transactions. A transaction is only finalized if its AOI is strictly lower than the LPAOI of all other pending transactions.
  • The final order is determined by sorting transactions based on their AOIs.

B. FairDAG-RL (Relative Fairness)

• Goal: Guarantees $\gamma$-Batch-Order-Fairness. If a fraction $\gamma$ of correct replicas receive $T_1$ before $T_2$, then $T_1$ is ordered no later than $T_2$.
• Mechanism:
  • Constructs a Dependency Graph where nodes are transactions and edges represent ordering preferences derived from local orderings.
  • Threshold Optimization: Unlike leader-based protocols (Themis) that rely on $n-2f$ committed orderings (due to potential leader exclusion), FairDAG-RL leverages the DAG validity property to ensure at least $n-f$ orderings are committed. Consequently, it raises the edge-creation threshold from $\frac{n-2f}{2}$ to $\frac{n-f}{2}$.
  • Graph Condensation: The protocol identifies Strongly Connected Components (SCCs) in the dependency graph. It finalizes the ordering of "solid" nodes (those with sufficient committed orderings) and re-adds "shaded" nodes to subsequent graphs until they become solid.
  • This approach reduces the minimum number of correct replicas required to guarantee fairness (e.g., requiring $n > 3f$ instead of $n > 4f$ for $\gamma=1$).

3. Key Contributions

1. Novel Framework: The proposal of FairDAG, the first framework to integrate fairness protocols with multi-proposer DAG-based consensus, addressing the throughput and manipulation vulnerabilities of leader-based systems.
2. FairDAG-AB: An absolute fairness protocol that guarantees Ordering Linearizability using an adaptive LPAOI mechanism compatible with DAG commit rules.
3. FairDAG-RL: A relative fairness protocol that improves upon Themis by leveraging DAG validity to lower the threshold for dependency graph construction, thereby reducing the requirement for correct participants and improving performance.
4. New DAG Construction Rules: Introduction of specific rules (e.g., including weak edges for slower replicas, maintaining strong edges to previous local vertices) to ensure fairness properties are preserved against adversarial participants.
5. Comprehensive Evaluation: Extensive analytical proofs of safety, liveness, and fairness, alongside experimental validation.

4. Experimental Results

The authors implemented FairDAG in Apache ResilientDB and compared it against baselines: PBFT, Pompe, Themis, RCC, and Tusk.

• Throughput:
  • FairDAG significantly outperforms leader-based fairness protocols (Pompe and Themis).
  • FairDAG-AB achieved 30.2% to 52.6% higher throughput than Pompe.
  • FairDAG-RL achieved 5.1% to 7.5% higher throughput than Themis in single-region settings, with gains increasing to 42.1% in geo-distributed settings due to the robustness of the underlying DAG consensus.
• Latency:
  • FairDAG-AB has slightly higher latency than Pompe (due to Tusk's underlying commit latency) but remains competitive.
  • FairDAG-RL demonstrates lower latency than Themis as the number of faulty replicas ($f$) increases, because Themis requires more correct replicas to guarantee fairness, increasing overhead.
• Resilience to Adversarial Behavior:
  • Leader Failure: In experiments where the leader was made faulty, Pompe and Themis suffered throughput drops during view-changes. FairDAG variants showed no performance degradation due to the multi-proposer design.
  • Ordering Manipulation: Under "Reversing Order" and "Targeted Delay" attacks by Byzantine replicas, FairDAG-AB and FairDAG-RL consistently maintained a higher ratio of correctly ordered transaction pairs compared to Pompe and Themis. The DAG layer's validity property effectively mitigated the ability of Byzantine actors to selectively exclude orderings.

5. Significance and Claims

The paper claims that FairDAG represents a significant advancement in blockchain fairness by resolving the trade-off between performance and fairness inherent in leader-based systems.

• Resilience: By removing the single leader, FairDAG prevents adversaries from manipulating the final order through selective collection of local orderings.
• Efficiency: The multi-proposer design alleviates the throughput bottleneck, allowing fairness protocols to scale better with network size and workload.
• Reduced Requirements: The validity property of DAGs allows FairDAG-RL to achieve fairness guarantees with fewer correct participants compared to state-of-the-art leader-based protocols like Themis.

The authors conclude that FairDAG effectively constrains adversarial manipulation of transaction ordering while achieving superior performance in both normal and adversarial conditions, making it a viable solution for fair transaction ordering in decentralized finance and other critical blockchain applications.