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 that all nodes agree on the same sequence of transactions, while activity ensures that the system continues to add new ones. Still, these properties do not prevent bad actors from changing the order of transactions once they are received.
On public blockchains, that gap in traditional consensus guarantees has become a serious problem. Validators, block creators, or sequencers can exploit their privileged role in block ordering for financial gain, a practice known as maximum extractable value (MEV). This manipulation includes profitable initial execution, subsequent execution and combination of trades. Because transaction execution order determines validity or profitability in DeFi applications, the integrity of transaction order is vital to maintaining fairness and trust.
To address this critical security gap, fairness in transaction order has been proposed as a third essential consensus property. Fair ordering protocols ensure that the final order of transactions depends on external and objective factors, such as arrival times (or order receipt), and are resistant to conflicting reorderings. By limiting the amount of power a block proponent has to reorder transactions, these protocols bring blockchains closer to being transparent, predictable, and MEV-resistant.
Condorcet’s paradox and the impossibility of ideal justice
The most intuitive and robust notion of fairness is order receipt fairness (ROF). Informally defined as “first received, first result,” the ROF dictates that if a sufficient number of transactions are made (tx) reach most nodes before another transaction (tx′)then the system must place the order tx before tx′ for its execution.
However, achieving this universally accepted “order justice” is fundamentally impossible unless it is assumed that all nodes can communicate instantaneously (i.e., operate in an instantaneous synchronous external network). This impossibility results from a surprising connection to social choice theory, specifically Condorcet’s paradox.
Condorcet’s paradox illustrates how, even when each individual node maintains a transitive internal order of transactions, collective preference throughout the system can result in what are known as non-transitive cycles. For example, most nodes may receive transactions TO before bmost receive b before doand most receive do before TO. Therefore, the three majority preferences form a loop (TO→b→do→TO). This means that no single, consistent order of transactions A, B, and C can satisfy all majority preferences simultaneously.
This paradox demonstrates why the goal of perfectly achieving fairness in order receipt is impossible in asynchronous networks, or even in synchronous networks that share a common clock if the external network delays are too long. This impossibility requires the adoption of weaker fairness definitions, such as batch order fairness.
Hedera Hashgraph and Median Timestamp Failure
Hedera, which employs the Hashgraph consensus algorithm, seeks to approximate a robust notion of received order fairness (ROF). It does this by assigning each transaction a final timestamp calculated as the median of the local timestamps of all nodes for that transaction.
However, this is inherently prone to manipulation. A single adversary node can deliberately distort its local timestamps and reverse the final order 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 transmitted 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 timestamp (2) to skew the median.
When the protocol calculates the medians:
-
For tx₁, the timestamps (1, 1, 4, 4, 3) return a median of 3.
-
For tx₂, the timestamps (2, 2, 5, 5, 2) return 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, although appearing neutral, is paradoxically the real cause of unfairness because it can be exploited by even a single dishonest participant to skew the final order of the transaction.
As a result, Hashgraph’s much-touted “fair time stamp” is a surprisingly weak notion of fairness. Hashgraph consensus does not guarantee the fairness of the receiving order and instead relies on a set of authorized validators rather than cryptographic guarantees.
Achieve practical guarantees
However, to get around the theoretical impossibility demonstrated by Condorcet, practical fair ordering schemes must relax the definition of equity in some way.
The Aequitas protocols introduced the block order fairness (BOF) criterion, or batch order fairness. BOF dictates that if enough nodes receive a transaction tx before another transaction tx′, then tx must be delivered in a block before or at the same time as tx′, meaning that no honest node can deliver tx′ in a block after tx. This relaxes the rule from “must be delivered earlier” (the ROF requirement) to “must be delivered later.”
Consider three consensus nodes (A, B, and C) and three transactions: tx₁, tx₂, and tx₃. A transaction is considered “received early” if at least two of the three nodes (the majority) observe it first.
If we apply majority voting to determine a global order:
-
tx₁ → tx₂ (agreed upon by A and C)
-
tx₂ → tx₃ (agreed upon by A and B)
-
tx₃ → tx₁ (agreed upon by B and C)
These preferences create a loop: tx₁ → tx₂ → tx₃ → tx₁. In this situation, there is no single order that can satisfy everyone’s vision at once, which means that a strict ROF is impossible to achieve.
BOF solves this by grouping all conflicting transactions into the same batch or block instead of forcing one to precede the other. The protocol simply generates:
Block B₁ = {tx₁, tx₂, tx₃}
This means that, from a protocol perspective, all three transactions are treated as if they occurred at the same time. Within the block, a deterministic tiebreaker (such as a hash value) decides the exact order in which they will be executed. By doing this, BOF ensures fairness for each pair of transactions and keeps the final transaction log consistent for everyone. Each one is processed no later than the one preceding it.
This small but important adjustment allows the protocol to handle situations where transaction orders conflict, by grouping those conflicting transactions into the same block or batch. Importantly, this does not result in a partial order, as each node must still agree on a single linear sequence of transactions. Transactions within each block are still organized in a fixed order of execution. In cases where such conflicts do not occur, the protocol still achieves the strongest ROF property.
While Aequitas successfully achieved BOF, it faced significant limitations, particularly because it had very high communication complexity and could only guarantee weak life. Weak life implies that delivery of a transaction is only guaranteed after the entire Condorcet cycle of which it is a part is completed. This could take an arbitrarily long time if the cycles are “chained”.
The Themis protocol was introduced to enforce the same strong BOF property, but with improved communication complexity. Themis achieves this using three techniques: batch unrolling, deferred ordering, and stronger intra-batch guarantees.
In its standard form, Themis requires each participant to exchange messages with most other nodes in the network. The amount of communication required increases with the square of the number of network participants. However, in its optimized version, SNARK-Themis, nodes use concise cryptographic proofs to verify fairness without needing to communicate directly with other participants. This reduces the communication load to grow only linearly, allowing Themis to scale efficiently even on large networks.
Suppose five nodes (A – E) participating in the consensus receive three transactions: tx₁, tx₂ and tx₃. Due to network latency, your local orders differ:
As in Aequitas, these preferences create a Condorcet cycle. But instead of waiting for the entire loop to resolve, Themis keeps the system moving using a method called batch unrolling. It identifies all the transactions that are part of the cycle and groups them into a set, called a strongly connected component (SCC). In this case, all three transactions belong to the same SCC, which Themis generates as a batch in progress, called Batch B₁ = {tx₁, tx₂, tx₃}.
By doing this, Themis allows the network to continue processing new transactions even while the internal order of batch B₁ is still being finalized. This ensures that the system remains active and prevents it from crashing.
Overview:
The concept of perfect fairness in the ordering of transactions may seem simple. The transaction of whoever reaches the network first must be processed first. However, as Condorcet’s paradox demonstrates, this ideal cannot hold in real distributed systems. Different nodes view transactions in different orders, and when those views conflict, no protocol can construct a single, universally “correct” sequence without compromise.
Hedera’s Hashgraph attempted to approximate this ideal with medium timestamps, but that approach is based more on trust than proof. A single dishonest participant can distort the median and change the order of transactions, revealing that a “fair timestamp” is not really fair.
Protocols like Aequitas and Themis advance the debate by recognizing what can and cannot be achieved. Instead of pursuing the impossible, they redefine fairness in a way that still preserves the integrity of order under real network conditions. What emerges is not a rejection of justice, but its evolution. This evolution draws a clear line between perceived justice and probable justice. It shows that the true integrity of transaction order in decentralized systems cannot depend on reputation, validator trust, or authorized control. It must come from a cryptographic verification built into the protocol itself.
This article does not contain investment advice or recommendations. Every investment and trading move involves risks, and readers should conduct their own research when making a decision.
This article is for general information purposes and is not intended to be and should not be taken as legal or investment advice. The views, thoughts and opinions expressed here are solely those of the author and do not necessarily reflect or represent the views and opinions of Cointelegraph.
Cointelegraph does not endorse the content of this article or any products mentioned in it. Readers should do their own research before taking any action related to any product or company mentioned and take full responsibility for their decisions.
