Consensus protocols in blockchain systems guarantee two foundational properties: consistency and liveness. Consistency ensures that all nodes eventually agree on the same set and sequence of transactions, while liveness guarantees that the system continues to process new transactions without indefinite halting. However, these properties do not address a third critical dimension: transaction order-fairness. In public blockchains, the sequence in which transactions execute has direct economic consequences, determining who captures value and who incurs costs. This is especially salient in the context of maximal extractable value (MEV), where validators, block builders, or sequencers can exploit their privileged ordering role for financial gain through practices such as frontrunning, backrunning, and sandwich attacks.
Transaction order-fairness has therefore been proposed as an essential consensus property to mitigate such exploitation. A protocol is transaction order-fair if no participant can systematically bias the transaction order beyond what objective network conditions and protocol rules imply. By limiting the power of block proposers to reorder transactions, fair-ordering protocols move blockchains closer to being transparent, predictable, and MEV-resistant. Yet even this intuitive notion of fairness faces a fundamental structural limit in asynchronous distributed systems, where there is no globally defined reception order because nodes observe messages at different times and no shared clock exists. No protocol can guarantee execution strictly according to a single universal arrival sequence—a limitation rooted in the basic constraints of distributed consensus under asynchronous communication, not in any particular design choice.
The Condorcet Paradox and the Impossibility of Perfect Fairness
The strongest intuitive notion of fairness is Receive-Order-Fairness (ROF), which dictates that if the majority of nodes receive transaction A before transaction B, then A should be processed before B—a simple "first-come, first-served" principle. This sounds both simple and fair. However, the problem is that nodes do not all observe transactions at the same instant. Messages travel at different speeds; some computers may receive A first while others receive B first. Because of this, guaranteeing perfect first-come, first-served fairness is impossible unless every node can communicate instantly with zero delay—a condition that never holds in real networks.
A deeper issue is the Condorcet paradox, a concept borrowed from voting theory. It demonstrates that even when each node has a clear and consistent individual ordering, the collective set of preferences can result in an intransitive cycle. For example, suppose the majority of nodes see A before B, most see B before C, and most see C before A. This produces a majority preference cycle (A→B→C→A), meaning no single linear order satisfies the majority view across all pairs. The network cannot construct a sequence that matches what most nodes observed first. Because perfect ROF is unachievable under these conditions, practical systems must adopt weaker fairness guarantees.
Hashgraph’s Fairness Model: Graph of Hashes, Median Timestamps, and aBFT Consensus
Hedera’s 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) consensus. 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 the transaction 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 thus enforces causal order: once a node publishes an event, the ancestry embedded in that event proves which transactions preceded it. This linkage is represented as an edge in the DAG. If one event is a direct or indirect ancestor of another, a downward path exists between them, and the protocol provides a cryptographic guarantee that the ancestor event was created first.
Transactions connected by such causal paths are ordered according to their 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 (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, preventing 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. However, 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. Still, Hashgraph's fairness guarantees have a bounded adversarial surface. A node 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
Batch-Order-Fairness (BOF) protocols approach the problem by defining a “block” as the set of transactions forming a single Condorcet cycle, and then ordering these blocks fairly while ignoring the ordering inside the block. The BOF criterion was first introduced by Mahimna Kelkar et al. in 2020 in their paper “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 (SCC) 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, consider a Condorcet cycle of 30 transactions, all of which would be placed in a single block. Sorting by transaction hash might place transaction 30 before transaction 1 in the final order. Yet even though a γ-fraction of nodes observed transaction 1 before transaction 30, placing 30 before 1 is still considered “fair” under γ-BOF because both transactions are in the same block; this notion of fairness only considers the order of blocks, not the internal transaction order.
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: 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 SCC 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, delaying transaction delivery arbitrarily and creating a “freeze” risk that defines Aequitas's weak-liveness guarantee.
Themis was introduced to solve these issues. It preserves the same γ-BOF property while resolving the liveness and communication problems. Like Aequitas, Themis 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's 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, leading to communication complexity that grows roughly quadratically with 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 to scale linearly with the number of nodes, 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: 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, as any attempt to alter dependencies would break the verified graph consistency. In empirical analysis by the original authors, γ-BOF resists adversarial reordering more strongly than timestamp-based approaches in geo-distributed networks, though it requires significantly more computational and protocol complexity.
Practical Implications and Trade-offs
The impossibility of perfect fairness is not merely a theoretical curiosity; it has direct consequences for the design of real-world blockchain systems. Developers and researchers must decide which relaxation of fairness best suits their network’s assumptions about synchrony, adversarial power, and performance requirements. Hashgraph’s approach of leveraging a DAG structure and median timestamps works well for networks with low adversarial ratios and where gossip propagation is fast, making the vast majority of transactions causally linked. BOF protocols, on the other hand, provide strong guarantees against adversarial reordering at the cost of additional communication rounds and batch aggregation, which can increase latency for transactions caught in Condorcet cycles.
Both approaches embed fairness directly into the consensus mechanism rather than relying on trust or authority. Neither is inherently superior; rather, they represent different points on the fairness-liveness-complexity spectrum. For applications such as decentralized finance, where MEV can lead to significant value extraction, the choice between median-timestamp aggregation and batch-order collapsing reflects different but equally principled responses to the same underlying constraint: that without a global clock and instantaneous communication, perfect first-come, first-served fairness is structurally impossible.
Source: Cointelegraph News