PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking Cycles for Scalable Fair Ordering in Blockchain Systems

Jinchun He, Wangjie Qiu, Yizhong Liu, Shengda Zhuo, Kwok-Yan Lam

arXiv:2609.00837v1cs.DC

TL;DR

Existing fair-ordering protocols can suffer global SCC condensation when pairwise receive-order evidence forms Condorcet cycles, threatening scalable transaction ordering. FlashOrder localizes cyclic ambiguity through canonical embedding, clustering, and hierarchical serialization. Across prototype and adversarial evaluations, it reports higher throughput and lower rank displacement than Themis and Rashnu.

  • Problem

    Pairwise fair-ordering protocols can encounter Condorcet cycles that force global SCC condensation, causing delays, coarse batches, and scaling failures in blockchain transaction ordering.

  • Method

    FlashOrder embeds thresholded pairwise preferences into one-dimensional canonical positions, clusters nearby transactions as a partition hypergraph, and performs hierarchical inter- and intra-cluster serialization.

  • Results

    FlashOrder achieves up to 10.5× higher throughput than Themis and 4.8× higher than Rashnu, while reducing maximum rank displacement by 88.7%.

  • Takeaways & Limitations

    Localizing cyclic ambiguity shifts fair ordering from batch-wide SCC traversal to localized sorting and aggregation while improving reported fairness and performance.

  • Takeaways & Limitations

    FlashOrder does not claim unconditional γ-batch-order-fairness for arbitrary cyclic regions or preservation of every robust pair across clusters without an additional separation condition.

Abstract

from arXiv · show

In blockchain systems, transaction order directly determines financial outcomes: unfair ordering enables front-running and sandwich attacks that have extracted over \$686M from Ethereum users. Current fair-ordering protocols aggregate pairwise receive-order evidence from replicas. Under contention or adversarial manipulation, however, Condorcet cycles force them into global strongly connected component (SCC) condensation, causing delays, coarse batches, and scaling failures. We present FlashOrder, a deterministic fair-ordering engine that localizes cyclic ambiguity before it propagates across the batch. FlashOrder embeds pairwise preferences into one-dimensional canonical positions, clusters nearby transactions with a partition hypergraph, and performs hierarchical inter- and intra-cluster serialization, replacing batch-wide SCC condensation with localized sorting and aggregation. Evaluated against Themis (CCS '23) and Rashnu (VLDB '24) on a libhotstuff-based prototype, FlashOrder achieves up to 10.5$\times$ higher throughput than Themis and 4.8$\times$ higher than Rashnu, with the latency gap widening as network scales. In controlled adversarial simulation, it reduces maximum rank displacement by 88.7\%, and under Condorcet attacks it sustains 12.0$\times$ and 9.7$\times$ higher throughput than Themis and Rashnu on average. These results show that localizing cyclic ambiguity yields stronger fairness at substantially higher throughput.

1 INTRODUCTION

Fair ordering is needed because transaction sequencing determines economic outcomes, yet SCC-based protocols face scalability bottlenecks under cyclic ambiguity. FlashOrder localizes that ambiguity through canonical embedding, clustering, and hierarchical serialization, improving fairness and throughput.

  • More than $686M has been extracted from Ethereum users through ordering manipulation known as maximal extractable value.
  • Global SCC-based cycle resolution becomes the practical bottleneck under contention and Condorcet-style ambiguity.Prior systems aggregate pairwise evidence, construct dependency graphs, condense SCCs, and topologically sort the result.
  • FlashOrder embeds thresholded pairwise evidence into one-dimensional positions, clusters nearby transactions in a partition hypergraph, and serializes clusters hierarchically.
  • FlashOrder replaces batch-wide SCC condensation with localized sorting and aggregation without redesigning fairness or the consensus substrate.
  • Under 50 ms WAN Condorcet attacks at γ=0.6, FlashOrder sustains 12.0× higher throughput than Themis and 9.7× higher than Rashnu on average.

2 BACKGROUND

Fair-ordering protocols use pairwise receive-order evidence, but Condorcet cycles can force global SCC condensation and collapse transactions into coarse batches. FlashOrder instead confines cyclic conflicts to compact regions before ordering them.

  • BFT consensus ensures deterministic execution order but does not inherently prevent a malicious leader from manipulating transaction sequencing.
  • Themis-style protocols construct pairwise dependency graphs and collapse strongly connected components into indivisible batches.
  • 2.2 From Fairness to Bottleneck: Condorcet attacks create intransitive voting cycles by broadcasting conflicting transaction sequences to different honest replicas.
  • 2.2 From Fairness to Bottleneck: SCC-based protocols may then collapse all transactions into one indivisible batch, causing severe latency degradation or unresponsive ordering.
  • FlashOrder localizes cyclic conflicts into small, bounded regions and resolves them by sorting within and across compact clusters instead of traversing a dense O(m^2) graph.

3 SYSTEM MODEL AND PROBLEM SETUP

FlashOrder operates in a partially synchronous BFT model with up to f Byzantine replicas and uses thresholded pairwise evidence to formulate batch-order fairness. The setup distinguishes robust cross-batch ordering from unconstrained ordering within batches.

  • 3.1 System Model and Threat Model: The system has n known replicas, at most f of which may behave arbitrarily, including sending conflicting messages or manipulating transaction ordering.
  • 3.1 System Model and Threat Model: The network is partially synchronous: delays are bounded only after an unknown Global Stabilization Time, with no pre-stabilization bound.
  • 3.1 System Model and Threat Model: Each replica maintains a local transaction-receive sequence, and differences across sequences can arise from latency, reordering, or Byzantine manipulation.
  • 3.1 System Model and Threat Model: FlashOrder uses a stricter order-fairness feasibility condition than standard BFT because honest-majority order signals must be distinguished from Byzantine noise.
  • 3.2 Thresholded Pairwise Fairness Objective: The pairwise preference matrix P records how many replicas observe transaction tx_i before tx_j.
  • 3.2 Thresholded Pairwise Fairness Objective: γ-batch-order-fairness requires robust pairs to be ordered correctly across batches but makes no pairwise guarantee within a batch.
  • 3.2 Thresholded Pairwise Fairness Objective: When Condorcet cycles exist, no linear order can satisfy all robust pairwise preferences, motivating fairness mechanisms that avoid global cycle condensation.

4 THE FLASHORDER ENGINE

FlashOrder replaces batch-wide SCC condensation with a deterministic three-phase pipeline that embeds pairwise evidence, clusters nearby transactions, and resolves order hierarchically. This design localizes cyclic ambiguity while preserving deterministic tie-breaking and reducing the topological state space.

  • Overview: FlashOrder uses robust canonical embedding, adaptive hypergraph modeling, and hierarchical order resolution to replace global SCC condensation with localized sorting and aggregation.The engine is designed as a plug-and-play deterministic state machine for BFT consensus protocols.
  • Phase 1: Robust Canonical Embedding: Phase 1 condenses the dense preference matrix into a robust one-dimensional baseline without allocating expensive graph data structures.The threshold filters Byzantine manipulation and network jitter before canonical positions are computed.
  • Phase 1: Robust Canonical Embedding: Canonical Position counts how many other transactions robustly precede each transaction, producing a deterministic rank proxy through sequential scans.Transactions are then sorted by canonical position, with transaction identifiers breaking equal-position ties.
  • Phase 2: Adaptive Hypergraph Modeling: Adaptive clustering groups adjacent transactions in canonical order when their coordinate difference is within δ, forming a disjoint partition hypergraph.The threshold δ is parameterized by fairness relaxation, empirical network delay, and transaction generation interval.
  • Phase 2: Adaptive Hypergraph Modeling: The quotient graph represents clusters as nodes and inter-cluster preference dominance as directed edges, reducing the topological state space from m transactions to k macro-nodes.Persistent macro-cycles can still be detected and merged through SCC processing.
  • Phase 3: Hierarchical Order Resolution: Within clusters, deterministic score sorting refines contradictory or weakly separated relations, but fairness quality there is evaluated empirically rather than guaranteed unconditionally.FlashOrder remains Θ(m^2) in worst-case pairwise evidence processing while reducing the practical cost of cycle resolution through localized serialization.

5 CORRECTNESS ARGUMENTS

FlashOrder establishes deterministic replayability unconditionally, conditional cluster-order fairness under explicit separation assumptions, and exactness for acyclic well-separated inputs. Its correctness arguments therefore distinguish guaranteed properties from conditions required to preserve every robust pairwise relation.

  • Deterministic Replayability: FlashOrder guarantees that honest replicas produce the same total order for fixed parameters and identical certified observation input.The preference matrix, clustering, quotient processing, traversal, and tie-breaking are deterministic functions of that input.
  • Conditional Cluster-Order Fairness: Conditional cluster-order fairness requires n > 4f/(2γ−1) and explicit final-cluster or quotient-graph path conditions for each robust pair.Under these conditions, the batch-level relation β(tx_i) ≤ β(tx_j) holds for the pair.
  • Acyclic Exactness: Acyclic exactness holds when the robust preference graph and initial quotient graph are acyclic, CP ordering is topological, and clustering does not merge robustly separated pairs.Under these assumptions, the output linear order satisfies every robust pair.
  • Verification: Replayable verification uses n−f signed observation sequences as a certificate, with consensus rejecting any replica whose replayed order mismatches.This verification mechanism operates on the agreed certified input.

6 EVALUATION

FlashOrder is evaluated as a deterministic fair-ordering engine against HotStuff, Themis, and Rashnu in deployment and simulation settings. Across growing networks and stressful workloads, it maintains higher throughput and better scalability by localizing cyclic ambiguity.

  • Evaluation Setup: FlashOrder is implemented on libhotstuff and compared with HotStuff, Themis, and Rashnu using shared pairwise-evidence assumptions.Themis and Rashnu are selected as open-source, HotStuff-integrated fair-ordering baselines.
  • Evaluation Setup: The evaluation combines CloudLab deployment experiments with algorithm-level simulation for larger networks and controlled adversarial sweeps.Deployment uses SmallBank with extreme Zipfian skew and high interaction probability to produce dense write-write conflicts.
  • End-to-End Scalability: 10.5× higher throughput than Themis and 4.8× higher than Rashnu at n=9, while FlashOrder achieves 30,680 txs/s and 32.6 ms average latency.At n=101, FlashOrder sustains 5,696 txs/s with 77.2% throughput retention at peak node count.
  • Interpretation: FlashOrder scales better than SCC-based fair-ordering engines because its ordering path remains localized while global graph processing grows with cyclic ambiguity.The evaluation frames contention, batch size, and WAN delay as regimes where global SCC-style resolution becomes expensive.
  • Stress and Network Conditions: FlashOrder’s throughput advantage widens with contention and network latency across normal, heavy-contention, and geo-distributed workloads.These experiments vary batch size from 100 to 800 with n=21 replicas and include 50 ms inter-node latency.

6.4 Sensitivity to Order-Fairness Parameter

The sensitivity study tests stricter robust-pair admission by lowering γ. FlashOrder remains stable while Themis and Rashnu incur substantial degradation under the resulting high-confidence cyclic structures.

  • Threshold Sensitivity: Lowering γ from 1.0 to 0.6 raises the evidence threshold required to declare a precedence relation robust.The threshold is τ = ⌊n(1−γ)⌋ + f + 1.
  • Baseline Degradation: Themis throughput drops from 3.0 × 10^3 txs/s to 2.4 × 10^3 txs/s as γ decreases, while latency rises from 334.3 ms to over 411.4 ms.Rashnu incurs approximately a 35% latency penalty, reaching 205.8 ms, under severe topological stress.
  • FlashOrder Stability: Over 21.6 × 10^3 txs/s and 31.4–37.3 ms latency are maintained by FlashOrder at γ=0.6.The localized path remains stable when only stronger pairwise evidence is admitted.

6.5 Fairness Quality under Thresholded Pairwise Constraints

FlashOrder improves fairness under thresholded pairwise constraints by preserving more robust precedence relations and limiting worst-case rank displacement than prior SCC-based approaches.

  • Metrics: RPS measures the fraction of strongly agreed-upon transaction pairs correctly ordered in the protocol output.A pair is robust when its pairwise evidence exceeds the consensus threshold τ.
  • RPS advantage: At γ=0.8, FlashOrder achieves RPS 0.873, improving 7.4% over Themis and 10.5% over Rashnu.At γ=0.51 with n=401, FlashOrder reaches RPS=0.996, compared with 0.915 for Themis and 0.853 for Rashnu.
  • Metrics: MaxDisp captures the worst-case positional shift between protocol output and the ascending send-time reference order.It complements RPS by measuring the largest displacement available to an adversary.
  • MaxDisp advantage: 88.7%: FlashOrder reduces maximum rank displacement at γ=0.8 to 34 positions, versus 301 for Themis and 287 for Rashnu.At γ=0.51 with n=401, the displacement is 10 positions for FlashOrder versus 300 for the baselines.
  • Structural decomposition: At γ=0.8, Themis absorbs 339 of 400 transactions into one SCC, while FlashOrder’s largest cluster contains 54 transactions and achieves Cov.=0.815.Rashnu has MaxGrp=4 but Cov.=0.462 across all robust pairs; its conflict-restricted Cov.c=0.816 is near FlashOrder’s 0.812.
  • Scalability effect: At γ=0.51, FlashOrder’s RPS rises from 0.873 to 0.996 and MaxDisp falls from 34 to 10 as network scale increases to n=401.Themis’s MaxDisp remains approximately 300 across these settings.

6.6 Robustness under Condorcet Attacks

Under explicit Condorcet attacks, FlashOrder preserves ordering quality while sustaining higher throughput and generally lower latency than Themis and Rashnu.

  • Attack setting: The attack study evaluates adversarial service robustness in simulation and in a geo-distributed prototype deployment.The deployment uses 50 ms inter-node latency and injects contradictory three-group orders forming A>B, B>C, and C>A cycles.
  • Ordering resilience: At Dist=1, FlashOrder limits successfully flipped pairs to 49 in standard scenarios and 63 under peak adversarial load.The distance metric measures the receive-order vote margin between two relative orders.
  • Ordering resilience: 23.15×: FlashOrder reduces execution time from 13.015 s to 0.562 s versus Themis in the simulation.The structural cluster graph avoids the cycle explosion associated with O(m^2) binary dependency graphs.
  • Throughput under attack: At γ=0.6, FlashOrder averages 1121 TPS across cycle lengths, 12.0× higher than Themis and 9.7× higher than Rashnu.The compared cycle lengths are 3, 10, and 20 in the 50 ms WAN experiment.
  • Latency and failure modes: FlashOrder keeps client latency below Themis and Rashnu in almost all settings, with ranges of 867–1292 ms at γ=0.6 and 790–814 ms at γ=1.0.The main outlier is 1292 ms at γ=0.6 and cycle length 3.
  • Latency and failure modes: At γ=1.0 and cycle length 20, Themis abandons fair ordering and Rashnu triggers fallback instead of completing its intended ordering procedure.These are explicit ordering failures observed in the same 50 ms sweep.
  • Overall finding: FlashOrder degrades more gracefully than SCC-based baselines across performance and fairness dimensions under ordering manipulation.The reported improvements combine stronger robust-precedence preservation, tighter displacement bounds, and higher service capacity.

7 RELATED WORK

Prior work addresses order fairness through definitions, graph-based ordering engines, consensus architectures, and sequencing designs, while FlashOrder targets evidence serialization.

  • Fairness definitions: Order-fairness research includes pairwise receive-order constraints, timestamp-style fairness, efficiency boundaries, decentralized clocks, bounded unfairness, and composable cryptographic abstractions.Aequitas formalized batch order-fairness through pairwise constraints later adopted by Themis.
  • Ordering engines: Themis and Rashnu retain pairwise evidence but use graph-based aggregation, with Rashnu reducing graph size by focusing on data-dependent transactions.These systems share an SCC-based execution path for cycle resolution.
  • Protocol architectures: DAG-based BFT systems improve dissemination and proposal but do not themselves solve fair ordering.FairDAG, DAG of DAGs, and Fides integrate fair ordering into DAG-based proposer layers.
  • Protocol architectures: FlashOrder rewrites the ordering engine that serializes accumulated pairwise evidence into a final order, complementing dissemination and proposal improvements.This positioning is distinct from systems that primarily change consensus or DAG communication.
  • Layer 2 sequencers: FlashOrder is orthogonal to centralized or decentralized sequencer designs because it targets deterministic fair-order construction regardless of sequencing control.Layer 2 mitigations include auction-based priority and decentralized sequencer networks.

8 LIMITATIONS

FlashOrder’s fairness guarantees are conditioned on cluster-level quotient construction and do not extend unconditionally to arbitrary cyclic regions.

  • Scope of correctness: Preserving a robust pair across clusters requires either the correct quotient edge or absorption into the same final cluster.This separation condition aligns correctness claims with the quotient graph actually constructed.
  • Scope of correctness: FlashOrder does not claim unconditional γ-batch-order-fairness for arbitrary cyclic regions.The limitation concerns the hard case of general Condorcet cycles.
  • Intra-cluster ordering: Its intra-cluster Net-Preference Score supplies a deterministic total order for ambiguous or cyclic regions, while fairness quality is evaluated empirically.The stated metrics are robust-pair satisfaction and rank displacement.

9 CONCLUSION

FlashOrder addresses the global SCC-condensation bottleneck in BFT transaction sequencing by localizing cyclic ambiguity through canonical embedding, adaptive clustering, and hierarchical serialization. It improves throughput, latency, and fairness metrics across prototype and adversarial evaluations.

  • 9 CONCLUSION: 10.5× higher throughput than Themis and 4.8× higher than Rashnu demonstrates FlashOrder’s performance advantage across prototype deployment and controlled simulation.FlashOrder retains 77.2% throughput relative to the non-fairness baseline at n=101.
  • 9 CONCLUSION: 12.0× and 9.7× higher average throughput than Themis and Rashnu under Condorcet attacks shows resilience to cyclic adversarial workloads.In a 50 ms WAN, ordering latency falls from 13.0 s over Themis to 0.56 s.
  • 9 CONCLUSION: 88.7% lower maximum rank displacement at γ=0.8 indicates improved ordering fairness under controlled adversarial simulation.FlashOrder reduces displacement from 301 and 287 to 34 positions and achieves an RPS of 0.873.
  • 9 CONCLUSION: At γ=0.51, FlashOrder reaches near-perfect RPS of 0.996 and MaxDisp of 10, strengthening its fairness results at stricter settings.These values are reported for the stricter γ=0.51 setting.
Loading 2609.00837v1…