Consensus guarantees today, focus on two properties: Consistency and Liveness. Consistency requires that all nodes eventually agree on the same set and sequence of transactions, while liveness ensures the system continues to process new transactions. What they do not address is whether the agreed-upon transaction order totally reflects fairness.
In public blockchains, transaction ordering has direct economic consequences. The order in which transactions execute determines who captures value and who pays the cost, particularly as validators, block builders, or sequencers can exploit their privileged role in block construction for financial gain. This practice is known as maximal extractable value (MEV) and includes the profitable frontrunning, backrunning, and sandwiching of transactions. Prima facie, there is no obvious way to prevent MEV extracting practices because block proposers hold unilateral power over transaction ordering, and no protocol rule inherently constrains how they exercise that power.
To address this, transaction order-fairness has been proposed as a third essential consensus property. A protocol is transaction order-fair if no participant can systematically bias transaction ordering beyond what objective network conditions and protocol rules imply. By limiting how much power a block proposer has to reorder transactions, fair-ordering protocols move blockchains closer to being transparent, predictable, and MEV-resistant.
However, even this intuitive idea of fairness encounters a structural limit. In an asynchronous distributed system, there is no globally defined reception order because each node observes messages at different times, and no shared clock exists. Therefore, no protocol can guarantee execution strictly according to a single universal arrival sequence. This limitation follows from the basic constraints of distributed consensus under asynchronous communication, not from any particular design choice.
The Condorcet Paradox and the Impossibility of Perfect Fairness
The most intuitive and strongest notion of fairness is called Receive-Order-Fairness (ROF). It simply means “first-come, first-served.” ROF dictates that if most nodes receive transaction A before transaction B, then A should be processed before B.
That sounds simple and fair. However, the problem is that nodes do not all see transactions at the exact same time. Messages travel at different speeds. Some computers might receive A first. Others might receive B first. Because of this, it is impossible to guarantee perfect “first-come, first-served” fairness unless every node can communicate instantly with no delays. In real networks, that never happens.
There is also a deeper problem called the Condorcet paradox. This idea comes from voting theory. It shows that even when each person (or node in this case) has a clear and consistent order in their own mind, the group as a whole can end up with a loop that makes no sense.
For example:
- Most nodes see A before B
- Most nodes see B before C
- Most nodes see C before A
This produces a majority preference cycle (A→B→C→A), meaning no single ordering satisfies the majority view across all pairs. The network cannot construct one sequence that matches what most nodes observed first.
Because perfect ROF is unachievable under these conditions, practical systems adopt some weaker fairness guarantees as outlined in the sections below.
Hashgraph’s Fairness Model: Graph of Hashes, Median Timestamps, and aBFT Consensus
Hedera, which employs the hashgraph algorithm, approaches the fairness problem through a directed acyclic graph (DAG) of cryptographically linked events. It is a leaderless consensus algorithm that operates in a fully asynchronous setting and achieves Asynchronous Byzantine Fault Tolerant (aBFT). Under this model, honest nodes eventually reach agreement on the same transaction log even under unbounded message delays. Consensus ordering emerges from network-wide observation through a virtual voting process: the order is calculated collectively by nodes rather than assigned by a designated block producer.
When a node receives a transaction, it packages it into a message called an event and gossips it to peers. When another node creates a subsequent event, it records the hash of the events it has already seen and digitally signs the new event. This provides cryptographic proof that the node had seen prior events before signing the new one. The hashgraph, therefore, enforces causal order: once a node publishes an event, the ancestry embedded in that event proves which transactions preceded it.
This linkage can be represented as an edge in the DAG. If one event is a direct or indirect ancestor of another, a downward path exists between them in the graph, and the protocol provides a cryptographic guarantee that the ancestor event was created first. Transactions connected by such paths are ordered according to their causal relationships in the graph. When two events have no ancestor relationship, they are concurrent, and the protocol resolves their relative order through the round-received mechanism. Each event is assigned a round based on when a supermajority of nodes, defined as more than two-thirds, can be shown to have strongly seen it through the DAG structure. Events assigned to earlier rounds are ordered first.
For events that share the same round-received, the protocol uses median timestamps to determine ordering. Each node records a local timestamp when it first receives an event. The consensus timestamp assigned to an event is the median of the timestamps reported across the node set. This timestamp is not derived from arbitrary local clocks in isolation. It is constrained by the gossip ancestry preserved in the hashgraph: a node cannot claim to have received an event before its causal predecessors without producing a detectable inconsistency in the DAG.
Under the standard aBFT assumption that fewer than one-third of nodes are Byzantine, the median falls on an honest timestamp or between two honest timestamps, which prevents adversarial nodes from shifting the median beyond a bounded range.
The Condorcet paradox can still apply to concurrent events, specifically those with no ancestor relationship in the DAG, where different nodes may observe them in different orders. The DAG structure eliminates this ambiguity for causally linked events: no contradictory causal paths can exist because each event’s ancestry is cryptographically fixed at creation. Because gossip propagation typically causes new events to become descendants of prior events within fractions of a second, most transactions fall into clear causal chains. The remaining concurrent events are resolved through round-received assignment and median timestamps as described above.
However, the hashgraph’s fairness guarantees have a bounded adversarial surface. A node still determines when to gossip an event, which events to relay first, and how long to delay relaying. These choices reshape the first-seen patterns that feed into median timestamp computation. The DAG cannot misrepresent the causal order it records, but it can be strategically shaped by gossip behavior before that order is recorded.
BOF Protocols: Fairness Through Batch Aggregation
BOF protocols define a “block” as the set of transactions forming a single Condorcet cycle, and then order these blocks fairly while ignoring the ordering inside the block. The BOF criterion was first introduced by Mahimna Kelkar et al. (2020) in “Order-Fairness for Byzantine Consensus,” which formalized the Aequitas family of protocols. In Aequitas, BOF requires that if a γ-fraction of nodes observe block (b) before block (b′), then no honest node may output (b) after (b′). The γ-fraction is the proportion of nodes that must agree on a block ordering for that ordering to be considered “fair” and enforced by the consensus protocol.
For BOF, if the fairness predicate indicates that a transaction tx should precede tx′, then tx cannot appear in a later block than tx′. When the fairness relation becomes cyclic, the protocol collapses the entire strongly connected component into a single block, because BOF treats that block, not the individual transaction, as the atomic fairness unit. Under γ-BOF, the only forbidden outcome is placing tx′ in a strictly earlier block than tx when a directed constraint tx→tx′ exists. The protocol permits both transactions to appear in the same block and places no restrictions on their ordering inside that block.
For example, Figure 2 below, is a Condorcet cycle of 30 transactions, so they would be in a single block. Sorting by hash might place 30 before 1 in the final ordering. However, a γ-fraction of nodes observed transaction 1 before transaction 30, yet placing 30 before 1 is still considered “fair” under γ-BOF. Because 1 and 30 are in the same block, and this notion of fairness only considers the order of the blocks, not the order of the transactions within a block.
When no cycles exist, BOF coincides with the strong form of ROF. When Condorcet cycles emerge, all transactions participating in the cycle are placed into a single block, and a deterministic method, such as a hash-based rule, orders events within that batch.
The protocol proceeds through three coordinated stages to ensure consistent transaction ordering across the network: the Gossip stage, the Agreement stage, and the Finalization stage.
In the gossip stage, nodes use FIFO broadcast to disseminate transactions in the order they were locally received per sender, preserving per-sender sequence so that each peer maintains a comparable transaction view. Once gossiping stabilizes, the agreement stage begins, where nodes execute a Set Byzantine Agreement (Set-BA) protocol to reach consensus on a unified set of local orderings that will serve as the foundation for the global order. In the finalization stage, nodes construct a dependency graph that captures transaction ordering relationships. Any transactions forming a cycle within this graph are grouped into the same strongly connected component and finalized together within a block.
However, Aequitas suffers from weak liveness, as its high communication cost and strict fairness constraints require the protocol to wait for the entire Condorcet cycle before finalizing the collapsed SCC. Because Condorcet cycles can chain indefinitely, this waiting period can grow without bound. Thus, transaction delivery can be delayed for an arbitrarily long time, and creates the “freeze” risk that defines Aequitas’ weak-liveness guarantee.
Themis was introduced to solve this. It preserves the same γ-BOF property while resolving these liveness and communication issues. Like Aequitas, Themis also constructs a dependency graph and collapses SCCs during its “FairFinalize” stage. The SCCs represent the same non-transitive Condorcet cycles underlying the γ-BOF relaxation, and Themis uses the condensation graph to derive the batch structure of the final output. The key difference is that Themis does not wait for a full cycle to complete. Instead, it uses deferred ordering and batch unspooling to output SCCs incrementally while allowing new transactions to continue flowing. This preserves γ-BOF but upgrades Aequitas’ weak liveness to standard liveness, and guarantees delivery within a delay bound.
In its standard form, Themis requires each participant to exchange messages with most other nodes in the network. As the number of participants increases, the amount of communication grows rapidly, roughly proportional to the square of the network size. However, in its optimized version, SNARK-Themis, nodes use succinct cryptographic proofs to verify fairness without needing to communicate directly with every other participant. This reduces the communication load so that it grows only in direct proportion to the number of nodes, thus allowing Themis to scale efficiently even in large networks.
If a malicious proposer attempts to exploit the situation by proposing an empty block, Themis employs deferred ordering, where the partially ordered batch (B₁) is still accepted, and the final, precise order of its transactions is determined later by the next honest proposer. That proposer finalizes the order based on verifiable transaction relationships, not personal discretion. This design ensures finalization depends only on bounded network delay, not on the arbitrary behavior of the current proposer, thus closing a key liveness gap that Aequitas could not guarantee.
This structure guarantees that every transaction is both included and executed deterministically, even in the presence of conflicting arrival orders. Because Themis leverages the internal dependency graph and SCC condensation to extract a final ordering, it is resilient to adversarial manipulation. Attackers cannot simply reorder or front-run other users’ transactions once they are included in the batch. Any attempt to alter dependencies would break the verified graph consistency.
In an empirical analysis by Mahimna Kelkar et al., γ-BOF resists adversarial reordering more strongly than timestamp-based approaches in geo-distributed networks. However, it requires significantly more computational and protocol complexity, which can also be seen as a downside.
Conclusion:
Perfect fairness in transaction ordering is structurally unattainable in distributed systems that lack synchronized clocks and instantaneous communication. The Condorcet paradox ensures that majority preferences can conflict in ways no single linear order can satisfy. The real question is how to find the most realistic and useful trade-offs.
Hashgraph and BOF represent two coherent answers. Neither approach is inherently superior. Both embed fairness directly into the consensus mechanism rather than relying on trust or authority. Both approaches demonstrate that fairness is not a binary property but a spectrum of trade-offs defined by formal impossibility results. Where synchrony is unavailable, and clocks are untrusted, the choice between median-timestamp aggregation and batch-order collapsing reflects different but equally principled responses to the same underlying constraint.
