For decades, research in distributed systems, especially in Byzantine consensus and state machine replication (SMR), has focused on two main goals: consistency and liveness. Consistency means all nodes agree on the same sequence of transactions, while liveness ensures the system continues to add new ones. Still, these properties do not stop bad actors from changing the order of transactions after they are received.
In public blockchains, that gap in traditional consensus guarantees has become a serious problem. Validators, block builders or sequencers can exploit their privileged role in block ordering for financial gain, a practice known as maximal extractable value (MEV). This manipulation includes profitable frontrunning, backrunning and sandwiching of transactions. Because transaction execution order determines validity or profitability in DeFi applications, the integrity of transaction ordering is vital for maintaining fairness and trust.
To address this critical security gap, transaction order-fairness has been proposed as a third essential consensus property. Fair-ordering protocols ensure that the final order of transactions depends on external, objective factors, such as arrival times (or receiving order) and is resistant to adversarial reordering. By limiting how much power a block proposer has to reorder transactions, these protocols move blockchains closer to being transparent, predictable, and MEV-resistant.
The Condorcet paradox and impossibility of ideal fairness
The most intuitive and strongest notion of fairness is Receive-Order-Fairness (ROF). Informally defined as “first received, first output,” ROF dictates that if a sufficient number of transactions (tx) arrive at a majority of nodes earlier than another transaction (tx′), then the system is required to order tx before tx′ for execution.
However, achieving this universally accepted “order fairness” is fundamentally impossible unless it is assumed that all nodes can communicate instantaneously (i.e., operating in an instant synchronous external network). This impossibility result stems from a surprising connection to social choice theory, specifically the Condorcet paradox.
The Condorcet paradox illustrates how, even when every individual node maintains a transitive internal ordering of transactions, the collective preference across the system can result in what are known as non-transitive cycles. For example, it is possible that a majority of nodes receive transaction A before B, a majority receive B before C, and a majority receive C before A. Hence, the three majority preferences form a loop (A→B→C→A). This means that no single, consistent ordering of the transactions A, B and C can ever satisfy all majority preferences simultaneously.
This paradox demonstrates why the goal of perfectly achieving Receive-Order-Fairness is impossible in asynchronous networks, or even in synchronous networks that share a common clock if external network delays are too long. This impossibility necessitates the adoption of weaker fairness definitions, such as batch order fairness.
Hedera Hashgraph and flaw of median timestamping
Hedera, which employs the Hashgraph consensus algorithm, seeks to approximate a strong notion of receive-order fairness (ROF). It does this by assigning each transaction a final timestamp computed as the median of all nodes’ local timestamps for that transaction.
However, this is inherently prone to manipulation. A single adversarial node can deliberately distort its local timestamps and invert the final ordering of two transactions, even when all honest participants received them in the correct order.
Consider a simple example with five consensus nodes (A, B, C, D and E) where Node E acts maliciously. Two transactions, tx₁ and tx₂, are broadcast to the network. All honest nodes receive tx₁ before tx₂, so the expected final order should be tx₁ → tx₂.
In this example, the adversary assigns tx₁ a later timestamp (3) and tx₂ an earlier one (2) to skew the median.
When the protocol computes the medians:
-
For tx₁, the timestamps (1, 1, 4, 4, 3) yield a median of 3.
-
For tx₂, the timestamps (2, 2, 5, 5, 2) yield a median of 2.
Because the final timestamp of tx₁ (3) is greater than that of tx₂ (2), the protocol outputs tx₂ → tx₁, thus reversing the true order observed by all honest nodes.
This toy example demonstrates a critical flaw: The median function, while appearing neutral, is paradoxically the actual cause of unfairness because it can be exploited by even a single dishonest participant to bias the final transaction order.
As a result, Hashgraph’s often-touted “fair timestamping” is a surprisingly weak notion of fairness. The Hashgraph consensus fails to guarantee receive-order fairness and instead depends on a permissioned validator set rather than on cryptographic guarantees.
Achieving practical guarantees
However, to circumvent the theoretical impossibility demonstrated by…
cointelegraph.com