Research
Fair on the Surface: Transaction-Ordering Bias and MEV in Mysticeti DAG-based BFT Protocol
DAG-based BFT protocols such as Mysticeti are widely assumed to order transactions fairly, because many validators propose blocks in parallel and because Sui re-sorts committed transactions by gas…

- arXiv
- 2607.13378
- Published
- 2026-07-15
- Authors
- Iliya Mirzaei, Mohammad Javad Amiri
AI summary
Overview
- Research area: Distributed systems and blockchain consensus security — specifically transaction-ordering fairness and maximal extractable value (MEV) in DAG-based Byzantine fault-tolerant (BFT) protocols.
- Technical level: Intermediate. Readers need a working understanding of BFT state machine replication, DAG-based consensus, and how transaction ordering translates into financial extraction; the paper itself is written for consensus researchers rather than cryptographers.
- Scope (one sentence): The paper identifies, measures, and partially fixes three transaction-ordering weaknesses in Mysticeti (the DAG-based BFT consensus protocol powering Sui) that arise from legitimate protocol behavior rather than any consensus-safety violation.
What This Paper Is About
DAG-based BFT protocols such as Mysticeti are widely assumed to order transactions fairly, because many validators propose blocks in parallel and because Sui re-sorts committed transactions by gas price before execution. The authors show that this assumption fails: the rule that flattens the committed DAG into a total order breaks same-round ties by validator index, and the gas-price re-sort is a stable sort that preserves that biased order whenever fees are tied (the common case). The goal is to measure how much ordering advantage this leaks, show who can exploit it using only protocol-legal actions, and propose a minimal fix that preserves safety and liveness.
Key Contributions
- Identification and measurement of three order-manipulation opportunities in Mysticeti and Sui, each verified against the current source code: a structural low-index head start, a stable-sort tie loophole in the gas-price re-sort, and a legitimate-action "strategic silence" amplifier.
- A demonstration that the advertised gas-price defense is a no-op at tied fees, since the re-sort (
order_by_gas_priceinpost_consensus_tx_reorder.rs, a single call to Rust'ssort_by_key) preserves consensus order on equal keys, letting an attacker profit without paying any premium. - A minimal, safety-preserving fix: replacing the validator-index tiebreak in
sort_sub_dag_blocks(commit.rs) and the gas-price tie with an unpredictable, per-commit key derived from the committed-leader digest and the block or transaction digest — implemented (env-gated) and measured on a 13-validator cluster. - A placement of the finding against prior order-fairness and DAG-MEV work, arguing the bias is a property of the linearization tiebreak shared by any DAG-based BFT protocol that breaks same-round ties by a fixed validator order.
Main Findings
-
Low-index head start is structural and needs no attacker. On a 13-validator network with no attack, in the same round the lower-indexed validator's blocks sort first about 89% of the time (89.5% versus 10.5% when labels are swapped). The advantage is per-pair, not a coalition effect: a sweep over all 78 validator pairs shows the lower index wins in every pair, mean 87.4%. Even with a narrow index gap (validators 4–5 labeled attacker versus 6–7 labeled victim), the low-index side wins 92.0% of same-round pairs, flipping to 8.0% when labels are swapped.
-
The bias is invisible to aggregate metrics. All-pairs Attack Success Rate (ASR) stays at approximately 50% because cross-round pairs cancel; the authors note that all-pairs ASR equals 1/2 + 1/(2R) for R rounds. Only the same-round ASR, which isolates the linearization tiebreak, reveals the bias.
-
The gas-price re-sort is a no-op at tied fees. With no re-sort, the attacker's transaction executes first about 89% of the time; at a tied fee, applying the re-sort leaves the number unchanged. The defense works only when the victim strictly outbids — and because ordinary transactions pay the reference gas price, ties are the common case, so the bias is exploitable at the minimum fee.
-
Strategic silence amplifies the advantage using only legal behavior. A validator that stays silent on every round except its leader rounds emits only early blocks. At n = 13, this lifts all-pairs ASR to 94.6% over a 10-commit window (roughly one second) and 61.5% over a 40-commit window; at n = 25 with the stake fraction held fixed, the figures are 80.8% and 77.3%. These rates assume the attacker controls approximately 31% of the stake, just under the Byzantine bound.
-
The paper's own test suite misses the flaw. Sui's test for the re-sort checks only the textual form (identity) of output transactions, which is identical for equal-fee transactions, so it confirms stability without checking fairness.
-
The core is not broken. Below the BFT threshold, standard in-protocol attacks (excluding victim blocks, delaying one's own proposals, withholding blocks from peers, bribing a minority) leave all-pairs ASR within about one point of 50%. Safety and liveness hold; the problem is one arbitrary tiebreak applied at the two points where order is finalized.
-
The proposed fix works for two of three flaws. On the 13-validator cluster, the seeded tiebreak drops same-round ASR from 89.3% (median) to 44.8%, essentially the 50% fair line. It barely moves strategic silence (all-pairs ASR 95.7% to 92.3%; same-round component 100% to 78%), because silence wins through round position and linearization is round-first out of causality.
-
A latent unchecked clock exists. Block verification never bounds a block's timestamp against the local clock; a validator signing a far-future timestamp trips Sui's minimum-round-delay throttle (a saturating subtraction) and is forced to skip rounds, reaching the same early-only block pattern through a bug rather than a choice. Impact today is limited because the committed timestamp is a stake-weighted median a minority cannot move.
Methodology in Plain English
The authors take the current Sui consensus code, deploy it on a cluster of 13 validators, and treat validators 0–3 as rational attackers and 10–12 as victims. Each run collects 60 commits, and results are reported as the median over 5 independent runs; a run with the attack disabled serves as the baseline.
Because the metric is block-level ordering rather than execution, transaction contents are irrelevant, so the workload is deliberately content-neutral: 5n distinct 32-byte transactions submitted round-robin, giving each validator exactly five and ensuring the input favors nobody. For the two structural flaws, any advantage therefore comes from the linearization rule, not from skewed input; strategic silence keeps the same symmetric input but lets the attacker choose when to propose.
The core measurement is Attack Success Rate, computed two ways. Same-round ASR restricts to attacker–victim block pairs sharing a round and isolates the tiebreak. All-pairs ASR counts every pair across rounds and would reveal a genuine across-round advantage. To prove the head start comes from index position rather than behavior, they re-label the same no-attack data — calling low-index validators "attacker," then flipping the labels — and show the result mirrors around 50%. The fix is then implemented as an env-gated alternative path (default unchanged) and evaluated on the same cluster.
Why This Matters
The paper reframes a piece of code most people would call an implementation detail — the tiebreak in a linearization rule — as the place where fairness is actually decided. It also explains why the problem has gone unnoticed: aggregate all-pairs metrics average the effect away, and the existing unit test checks transaction identity rather than fairness. For research on order fairness in DAG ledgers, this is a concrete, deployed counterexample that supports the argument that the linearization rule determines fairness.
Real-world implications:
- On-chain trading on Sui. MEV already extracts roughly $18,000 a day from users on Sui mainnet under normal operating conditions; sandwich and front-running victims against a shared object (e.g., the same trading pool) are the direct losers.
- Validator economics and stake centralization. A permanent index-based head start gives lower-indexed validators a recurring, unearned edge, which can distort competition for stake and delegation.
- Protocol and client engineering. The proposed fix is confined to two functions and leaves gas-price priority, safety, and liveness untouched, making it a low-risk patch for chains running similar linearization rules.
- Auditing and test design. The paper shows why fairness tests must check ordering rather than transaction identity, and why benchmarks should report same-round metrics alongside all-pairs aggregates.
Industry relevance is direct: Sui has a market capitalization of roughly $3 billion and more than $150 billion in cumulative on-chain exchange volume, and the paper states the flaws are live on mainnet with no special configuration. The authors note the bias generalizes to any DAG-based BFT protocol that breaks same-round ties by fixed validator order. They also observe that Sui's own (currently gated) reputation-based leader schedule already replaced a fixed tiebreak with a per-epoch seeded shuffle for the same reason, so this style of fix is already acceptable in the codebase.
Future Directions
- Closing strategic silence. The tiebreak fixes the structural bias but not the round-position advantage; a round-level mitigation is needed and is explicitly left to future work. Because linearization is round-first out of causality, a block cannot precede its ancestors, which bounds but does not eliminate the gain.
- Bounding timestamp drift. Adding a single drift-bound check at block verification would close the unchecked-clock path that enables the buggy variant of strategic silence, and would pre-empt future features that read raw block timestamps.
- Designing round-level fairness mechanisms. Since silence front-loads a validator's block mass, open questions include how to schedule or weight rounds so that emitting fewer, earlier blocks cannot be converted into ordering advantage.
- Re-examining fairness metrics and test suites. The results argue for evaluating deployed DAG chains with same-round positional metrics and for tests that verify fair tie-breaking, not merely deterministic output; the authors suggest this extends across the DAG-based BFT family rather than being Sui-specific.
Target Audience
Consensus protocol researchers and graduate students working on BFT and DAG-based ordering; blockchain security auditors and MEV researchers; and protocol engineers at chains that derive a total order from a DAG — particularly those responsible for linearization rules, transaction reordering, or fairness test suites. Readers without a consensus background can follow the problem framing and results but will need supplementary reading on DAG construction, leader commitment, and BFT thresholds to engage with the mechanics.
Authors’ abstract
Distributed systems deployed in untrustworthy environments agree on a common transaction order through Byzantine fault-tolerant (BFT) consensus protocols, and that order has real financial value in many decentralized applications: whoever influences it can profit at other users' expense, a problem known as maximal extractable value (MEV). Mysticeti is a state-of-the-art DAG-based BFT protocol in which many validators propose blocks in parallel, and the total order is derived…
The full abstract on arXiv