Consensus guarantees in distributed ledgers traditionally focus on two core properties: consistency and liveness. Consistency ensures that all honest nodes eventually agree on the same set and order of transactions. Liveness guarantees that the system continues to process new transactions. However, these properties do not address whether the agreed-upon transaction order is fair. In public blockchains, transaction ordering carries direct economic consequences. The sequence in which transactions execute determines who captures value and who bears cost, especially because validators, block builders, or sequencers can exploit their privileged position in block construction for financial gain. This practice is known as maximal extractable value (MEV) and includes techniques such as frontrunning, backrunning, and sandwich attacks.
To counter MEV, the concept of transaction order-fairness has been proposed as a third essential consensus property. A protocol is considered transaction order-fair if no participant can systematically bias transaction ordering beyond what objective network conditions and protocol rules dictate. By restricting the power of block proposers to reorder transactions, fair-ordering protocols aim to make blockchains more transparent, predictable, and resistant to MEV.
Yet even this intuitive notion of fairness faces a fundamental structural limit. In an asynchronous distributed system, there is no globally defined reception order because each node observes messages at different times and there is no shared clock. Consequently, no protocol can guarantee execution strictly according to a single universal arrival sequence. This limitation arises 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 strongest and most natural notion of fairness is Receive-Order-Fairness (ROF), which essentially means “first-come, first-served.” ROF dictates that if most nodes receive transaction A before transaction B, then A should be processed before B. This sounds simple and fair. However, nodes do not all see transactions at the exact same time. Message propagation speeds vary; some computers might receive A first, while others receive B first. Perfect first-come, first-served fairness would require instantaneous communication with no delays, which is impossible in real networks.
There is also a deeper problem known as the Condorcet paradox, a concept borrowed from voting theory. It shows that even when each individual (or node) has a clear and consistent order, the group as a whole can end up with a cyclic preference that defies a single linear order. 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 weaker fairness guarantees.
Hashgraph’s Fairness Model: Graph of Hashes, Median Timestamps, and aBFT Consensus
Hedera, which employs the Hashgraph algorithm, approaches fairness 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 agree 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 thus enforces causal order: once a node publishes an event, the ancestry embedded in that event proves which transactions preceded it.
This linkage creates edges 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 paths are ordered according to their causal relationships. 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. Importantly, 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—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.
Nevertheless, 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
Batch-Order-Fairness (BOF) protocols take a different approach. They 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. in 2020 in the 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 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; they would all be placed in a single block. Sorting by hash might place transaction 30 before transaction 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. 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: Gossip, Agreement, and Finalization. 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 due to its high communication cost and strict fairness constraints. The protocol requires waiting for the entire Condorcet cycle to complete before finalizing the collapsed SCC. Because Condorcet cycles can chain indefinitely, this waiting period can grow without bound, leading to arbitrarily long transaction delays and creating a “freeze” risk that defines Aequitas’ weak-liveness guarantee.
Themis was introduced to solve this problem. It preserves the same γ-BOF property while resolving the liveness and communication issues. 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’ weak liveness to standard liveness, guaranteeing 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 communication load grows roughly proportionally 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 linearly with 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. 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 be seen as a downside.
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 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.
Source:Cointelegraph News