Perfect fairness in blockchain transaction ordering is impossible

Researchers and protocol designers report that perfect fairness in transaction ordering on public blockchains cannot be achieved because nodes observe messages at different times and majority preferences can cycle. The inability to define a single universal receive order means protocols cannot enforce strict “first-come, first-served” across a distributed set of participants.

Receive-Order-Fairness (ROF) is the rule that if most nodes see transaction A before transaction B, then A should be processed first. In practice, message propagation delays and the absence of a shared clock cause different nodes to see transactions in different sequences. Voting theory’s Condorcet paradox further complicates the problem: pairwise majority preferences can form cycles so that a majority prefers A over B, a majority prefers B over C, and a majority prefers C over A. Those cycles make it impossible to produce one linear order that satisfies every pairwise majority.

Economic incentives increase the stakes. Transaction order affects which actors capture value on public blockchains. Validators, block builders and sequencers who control block contents can extract maximal extractable value (MEV) through behaviors such as frontrunning, backrunning and sandwiching. Traditional consensus guarantees-consistency and liveness-do not constrain a proposer’s choice of transaction order.

One technical response is the hashgraph approach used by Hedera. Nodes create events that include hashes of prior events and share them by gossip. The cryptographic links establish a directed acyclic graph that records causal ancestry; when one event is an ancestor of another, their order is fixed by that ancestry. For events with no causal link, the protocol assigns a round-received based on when a supermajority can be shown to have seen the event, and it orders ties by the median of node-reported timestamps. Under an asynchronous Byzantine assumption with fewer than one-third faulty nodes, the median timestamp falls on or between honest timestamps. Nodes still control when and to whom they gossip events, and those choices can influence first-seen patterns that feed median calculations.

An alternative family of designs treats fairness at the block level. Byzantine Order-Fairness (BOF), as in the Aequitas protocol, records pairwise ordering preferences and, when those preferences form cycles, collapses the transactions involved into a single block. Aequitas enforces a γ-BOF predicate that prevents honest nodes from outputting blocks in a way that contradicts a γ-fraction of observed orderings. Aequitas proved the fairness property but exhibited weak liveness because it could wait indefinitely for cycles to resolve.

Themis updated the BOF approach to preserve γ-BOF while providing bounded liveness. Themis builds the same dependency graph, collapses strongly connected components into batches and uses deferred ordering and batch unspooling to output components incrementally. An optimized variant, SNARK-Themis, replaces extensive peer-to-peer exchanges with succinct cryptographic proofs, reducing communication growth to linear in network size. Themis also allows a later honest proposer to finalize ordering from the verified dependency graph if a malicious proposer stalls.

Empirical comparisons report trade-offs: γ-BOF resists adversarial reordering more effectively than timestamp-based methods in geo-distributed settings but requires higher computation and communication. Hashgraph’s median-timestamp method operates in a fully asynchronous, leaderless aBFT setting and limits some adversarial influence but still permits strategic shaping of gossip propagation.

Researchers have developed these protocol families-causal DAGs with median timestamps, batch collapsing with BOF and optimized proof systems-as formal responses to the structural limits that arise when networks are asynchronous and clocks are not trusted.