Modern consensus mechanisms are built around two core guarantees: Consistency and Liveness. Consistency means that all participating nodes will ultimately converge on an identical set of transactions arranged in the same order, while liveness ensures that the system keeps making progress and accepting new transactions. What neither of these properties addresses is whether the resulting transaction sequence truly embodies fairness.
In public blockchain networks, the sequence in which transactions are processed carries immediate economic weight. The execution order determines who reaps value and who bears the cost — especially when validators, block builders, or sequencers can leverage their privileged position during block assembly to extract profit. This phenomenon is called maximal extractable value (MEV) and encompasses tactics such as frontrunning, backrunning, and sandwiching user transactions. At first glance, there is no straightforward way to curb MEV extraction, since block proposers wield unilateral authority over transaction ordering, and no built-in protocol rule inherently limits how they exercise that authority.
To tackle this gap, transaction order-fairness has been put forward as a third fundamental property of consensus. A protocol achieves transaction order-fairness when no participant can systematically skew the transaction sequence beyond what objective network conditions and the protocol’s own rules would naturally dictate. By curating how much discretion a block proposer has to rearrange transactions, fair-ordering protocols steer blockchains toward greater transparency, predictability, and resilience against MEV.
Yet even this seemingly straightforward notion of fairness runs into a structural ceiling. In an asynchronous distributed system, there is no universally agreed-upon reception order, because each node perceives messages at a different moment and no shared clock ties them together. Consequently, no protocol can promise that execution will follow a single global arrival sequence. This ceiling stems from the fundamental limits of distributed consensus under asynchronous communication — not from any particular engineering decision.
The Condorcet Paradox and the Impossibility of Perfect Fairness
The most natural and rigorous definition of fairness is known as Receive-Order-Fairness (ROF). In simple terms, it means “first-come, first-served.” ROF prescribes that if a majority of nodes witness transaction A before transaction B, then A should be finalized ahead of B.
That principle sounds both simple and equitable. The difficulty, however, is that nodes do not all observe transactions at precisely the same instant. Messages propagate at varying speeds. Some machines may register A first, while others register B first. Because of this, guaranteeing flawless “first-come, first-served” fairness is out of reach unless every node can communicate with zero delay — something no real-world network can deliver.
There is also a deeper obstacle known as the Condorcet paradox. This concept originates in social choice and voting theory. It demonstrates that even when every individual (or node, in this context) holds a clear and internally consistent ranking, the collective outcome can devolve into a circular contradiction.
Consider this scenario:
- A majority of nodes observe A before B
- A majority of nodes observe B before C
- A majority of nodes observe C before A
This yields a majority-preference cycle (A→B→C→A), meaning no single linear ordering satisfies the majority preference for every pair. The network cannot assemble one coherent sequence that reflects what most nodes saw first.
Because perfect ROF cannot be attained under these conditions, real-world systems settle for weaker — but still meaningful — fairness guarantees, as described in the sections that follow.
Hashgraph’s Fairness Model: Hash-Directed Graphs, Median Timestamps, and aBFT Consensus
Hedera, which runs on the hashgraph algorithm, tackles the fairness challenge through a directed acyclic graph (DAG) of cryptographically interconnected events. It is a leaderless consensus protocol that functions in a fully asynchronous environment and delivers Asynchronous Byzantine Fault Tolerance (aBFT). Within this framework, honest nodes are guaranteed to eventually converge on an identical transaction log, even when message delays are unbounded. Consensus ordering materializes from network-wide observation via a virtual voting procedure: the order is computed collectively by all nodes rather than dictated by a single block producer.
When a node receives a transaction, it wraps it into a data structure called an event and gossips that event to its peers. Each time a node creates a new event, it embeds the hashes of all events it has already received and then digitally signs the new event. This produces cryptographic evidence that the node was aware of those prior events before attesting to the new one. As a result, the hashgraph enforces a causal ordering: once a node publishes an event, the ancestry encoded within it proves which transactions came before it.
This ancestry relationship can be depicted as an edge in the DAG. Whenever one event is a direct or indirect ancestor of another, a downward path connects them in the graph, and the protocol supplies a cryptographic guarantee that the ancestor event was created first. Transactions linked by such paths are sequenced according to their causal dependencies in the graph. When two events share no ancestor-descendant relationship, they are deemed concurrent, and the protocol disambiguates their relative order through the round-received mechanism. Every event is assigned a round number based on when a supermajority of nodes — defined as more than two-thirds — can be demonstrated (via the DAG topology) to have strongly observed it. Events placed in earlier rounds are ordered ahead of those in later rounds.
For events that land in the same round-received, the protocol relies on median timestamps to establish their order. Each node logs a local timestamp at the moment it first receives an event. The consensus timestamp attributed to an event is the median value computed from the timestamps reported by the full set of nodes. This timestamp is not drawn from any single node’s clock in isolation. It is anchored by the gossip ancestry preserved inside the hashgraph: a node cannot plausibly claim to have received an event before its causal predecessors without introducing a detectable inconsistency in the DAG.
Under the standard aBFT assumption — that fewer than one-third of nodes are Byzantine — the median lands on an honest timestamp or falls between two honest timestamps, which stops adversarial nodes from pushing the median outside a bounded window.
The Condorcet paradox can still surface among concurrent events — specifically those with no ancestor-descendant link in the DAG — where different nodes may witness them in conflicting orders. The DAG structure removes this ambiguity for causally
Because every event’s ancestry is cryptographically set at creation, linked events prevent contradictory causal paths from forming. Gossip propagation typically causes new events to become descendants of earlier ones within fractions of a second, placing most transactions into clear causal chains. Any remaining concurrent events are resolved using round-received assignment and median timestamps as described above.
Nevertheless, the hashgraph’s fairness guarantees have a bounded adversarial surface. A node still decides when to gossip an event, which events to relay first, and how long to postpone relaying. These decisions reshape the “first-seen” patterns that feed into the median timestamp calculation. The DAG cannot misrepresent the causal order it records, yet 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 collection of transactions forming a single Condorcet cycle, then order these blocks fairly while disregarding the ordering inside each block. The BOF concept 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 demands that if a γ-fraction of nodes witness block (b) before block (b′), then no honest node may output (b) after (b′). The γ-fraction represents the proportion of nodes that must concur on a block ordering for that ordering to be deemed “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 unit of fairness. Under γ-BOF, the only prohibited outcome is placing tx′ in a strictly earlier block than tx when a directed constraint tx→tx′ exists. The protocol allows both transactions to occupy the same block and imposes no constraints on their internal ordering.
For instance, Figure 2 below depicts a Condorcet cycle of 30 transactions, so they all belong to one block. Sorting by hash could place 30 before 1 in the final arrangement. Yet a γ-fraction of nodes observed transaction 1 before transaction 30, but placing 30 before 1 is still considered “fair” under γ-BOF, because 1 and 30 share the same block, and this fairness notion applies only to the order of blocks, not to the order of transactions within a block.
When no cycles are present, BOF coincides with the strong form of ROF. When Condorcet cycles arise, all transactions participating in the cycle are placed into a single block, and a deterministic technique, 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.
During 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 view of transactions. Once gossiping stabilizes, the agreement stage commences, where nodes execute a Set Byzantine Agreement (Set-BA) protocol to reach consensus on a unified collection 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 overhead 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. Consequently, transaction delivery can be delayed for an arbitrarily long time, creating the “freeze” risk that defines Aequitas’ weak-liveness guarantee.
Themis was introduced to address 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 crucial distinction is that Themis does not wait for a full cycle to complete. Instead, it employs deferred ordering and batch unspooling to output SCCs incrementally while allowing new transactions to keep flowing. This preserves γ-BOF but upgrades Aequitas’ weak liveness to standard liveness, guaranteeing delivery within a bounded delay.
In its standard form, Themis requires each participant to exchange messages with most other nodes in the network. As the number of participants grows, the communication volume increases 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, enabling 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, thereby 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 demands significantly more computational and protocol complexity, which can also be viewed as a drawback.
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.
