Why Achieving True Fairness in Transaction Sequencing Remains Fundamentally Impossible
Achieving true fairness in how transactions are ordered remains fundamentally impossible within distributed networks lacking perfectly synchronized time references and zero-latency communication. The challenge lies in identifying the most practical and effective compromises.
Contemporary consensus mechanisms emphasize two fundamental properties: Consistency and Liveness. The consistency requirement demands that every node in the network ultimately reaches agreement on an identical collection and ordering of transactions, whereas liveness guarantees that the system maintains its ability to accept and process incoming transactions without halting. However, these properties fail to address a crucial question: does the final transaction sequence genuinely reflect principles of fairness?
Within public blockchain networks, the sequence in which transactions are processed carries significant economic ramifications. The execution order directly influences which participants gain value and which bear costs, especially given that validators, block constructors, or sequencers possess the ability to leverage their privileged position during block assembly for personal financial benefit. This exploitation is commonly referred to as maximal extractable value (MEV) and encompasses profitable strategies including frontrunning, backrunning, and sandwiching of user transactions. On its face, preventing these MEV extraction techniques appears impossible because block proposers wield unilateral authority over how transactions are sequenced, with no inherent protocol constraint governing their exercise of this power.
In response to this challenge, transaction order-fairness has emerged as a proposed third fundamental consensus property. A protocol achieves transaction order-fairness when no actor can systematically manipulate transaction sequencing beyond what objective network conditions and protocol specifications would naturally produce. Through constraining the extent of power held by block proposers to resequence transactions, fair-ordering protocols push blockchains toward greater transparency, predictability, and resistance to MEV extraction.
Nevertheless, even this seemingly straightforward conception of fairness confronts a fundamental structural barrier. Within an asynchronous distributed environment, no universally defined reception sequence exists because individual nodes witness message arrivals at distinct moments, with no synchronized clock available across the system. Consequently, no protocol design can ensure execution strictly following a singular universal arrival order. This constraint derives from the fundamental limitations of distributed consensus operating under asynchronous communication conditions, rather than from any specific implementation decision.
The Condorcet Paradox and the Impossibility of Perfect Fairness
The most straightforward and robust conception of fairness is termed Receive-Order-Fairness (ROF). Its principle is elegantly simple: "first-come, first-served." Under ROF, when a majority of nodes observe transaction A arriving before transaction B, the protocol should execute A prior to B.
This appears both simple and equitable. The difficulty arises because nodes do not observe transactions arriving at precisely identical moments. Network messages propagate at varying velocities. Certain nodes might witness A's arrival first. Other nodes might witness B's arrival first. Given this reality, guaranteeing perfect "first-come, first-served" fairness becomes impossible unless all nodes possess the capability to communicate with zero latency and instantaneous propagation. In actual network environments, such conditions never materialize.
A more profound complication exists, known as the Condorcet paradox. This concept originates from voting theory. It demonstrates that even when individual participants (or nodes in this context) maintain clear and internally consistent orderings according to their own observations, the collective group can arrive at a circular relationship that defies logical resolution.
For example:
- Most nodes see A before B
- Most nodes see B before C
- Most nodes see C before A
This configuration produces a majority preference cycle (A→B→C→A), indicating that no singular ordering can satisfy the majority perspective across every pairwise comparison. The network cannot construct a single sequence that accurately represents what the majority of nodes witnessed first.
Given that perfect ROF cannot be achieved under these circumstances, practical implementations adopt weaker fairness assurances as detailed in the following sections.
Hashgraph's Fairness Model: Graph of Hashes, Median Timestamps, and aBFT Consensus
Hedera, utilizing the hashgraph algorithm, addresses the fairness challenge through a directed acyclic graph (DAG) composed of cryptographically linked events. It represents a leaderless consensus mechanism that functions within a fully asynchronous environment and delivers Asynchronous Byzantine Fault Tolerance (aBFT). Within this framework, honest nodes ultimately converge on an identical transaction log even when message delays are unbounded. Consensus ordering emerges through network-wide observation via a virtual voting mechanism: the sequence is determined collectively by participating nodes rather than dictated by a designated block producer.
Upon receiving a transaction, a node encapsulates it within a message structure called an event and propagates it to neighboring peers through gossip. When a subsequent node generates a new event, it incorporates the cryptographic hash of previously observed events and applies its digital signature to the newly created event. This mechanism provides cryptographic evidence that the node had witnessed prior events before creating and signing the new one. The hashgraph structure therefore enforces causal ordering: after a node publishes an event, the ancestry information embedded within that event proves which transactions temporally preceded it.
This connection can be conceptualized as an edge within the DAG. When one event serves as a direct or indirect ancestor of another event, a descending path exists connecting them in the graph structure, and the protocol delivers a cryptographic assurance that the ancestor event was generated first. Transactions linked by such pathways are sequenced according to their causal dependencies within the graph. When two events lack any ancestor relationship, they are considered concurrent, and the protocol determines their relative sequence through the round-received mechanism. Each event receives a round assignment based on the point at which a supermajority of nodes, defined as exceeding two-thirds, can be demonstrated to have strongly seen it through the DAG's structure. Events assigned to numerically earlier rounds receive prioritization in the final ordering.
For events sharing an identical round-received value, the protocol employs median timestamps to establish ordering. Every node records a local timestamp upon first receiving an event. The consensus timestamp attributed to an event represents the median value of timestamps reported across the entire node set. This timestamp is not derived from arbitrary local clock readings in isolation. It is constrained by the gossip ancestry preserved within the hashgraph: a node cannot claim to have received an event prior to its causal predecessors without creating a detectable inconsistency within the DAG structure.
Under the standard aBFT security assumption that fewer than one-third of nodes exhibit Byzantine behavior, the median value falls upon an honest timestamp or between two honest timestamps, thereby preventing adversarial nodes from shifting the median value beyond a bounded range.
The Condorcet paradox remains applicable to concurrent events, specifically those lacking any ancestor relationship within the DAG, where different nodes may perceive them in contradictory orders. The DAG structure eliminates this ambiguity for causally connected events: contradictory causal pathways cannot exist because each event's ancestry is cryptographically established at the moment of creation. Since gossip propagation characteristically causes newly created events to become descendants of previously existing events within fractions of a second, the majority of transactions fall into unambiguous causal chains. The remaining concurrent events are resolved through round-received assignment and median timestamp computation as previously described.
Nevertheless, the hashgraph's fairness guarantees possess a bounded adversarial attack surface. Individual nodes still control when to gossip an event, which events to relay with priority, and the duration of delays before relaying. These decisions reshape the first-seen observation patterns that serve as inputs to median timestamp calculation. The DAG structure cannot misrepresent the causal ordering it has recorded, but it can be strategically influenced by gossip behavior prior to that ordering being permanently recorded.
BOF Protocols: Fairness Through Batch Aggregation
BOF protocols conceptualize a "block" as the collection of transactions constituting a single Condorcet cycle, then order these blocks fairly while disregarding the internal ordering within each block. The BOF criterion was initially introduced by Mahimna Kelkar et al. (2020) in "Order-Fairness for Byzantine Consensus," which formalized the Aequitas family of protocols. Within Aequitas, BOF mandates that if a γ-fraction of nodes observe block (b) prior to block (b′), then no honest node may produce (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 mechanism.
Under BOF, when the fairness predicate indicates that transaction tx should precede tx′, then tx cannot appear within a later block than tx′. When the fairness relation forms a cycle, the protocol consolidates 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 sole prohibited outcome is positioning tx′ in a strictly earlier block than tx when a directed constraint tx→tx′ exists. The protocol permits both transactions to appear within the same block and imposes no restrictions on their internal ordering within that block.
As an illustration, Figure 2 below depicts a Condorcet cycle involving 30 transactions, which would therefore be consolidated into a single block. Sorting by hash might position transaction 30 before transaction 1 in the final ordering. However, a γ-fraction of nodes observed transaction 1 before transaction 30, yet positioning 30 before 1 is still deemed "fair" under γ-BOF. Since transactions 1 and 30 exist within the same block, and this fairness notion only considers the ordering of blocks, not the ordering of transactions within individual blocks.
In scenarios where no cycles exist, BOF coincides exactly with the strong formulation of ROF. When Condorcet cycles emerge, all transactions participating within the cycle are consolidated into a single block, and a deterministic method, such as a hash-based ordering rule, sequences events within that batch.
The protocol advances through three coordinated phases to ensure consistent transaction ordering across the network: the Gossip stage, the Agreement stage, and the Finalization stage.
During the gossip stage, nodes employ FIFO broadcast to propagate transactions in the sequence they were locally received per sender, maintaining per-sender sequence so that each peer preserves a comparable transaction view. After gossiping stabilizes, the agreement stage commences, where nodes execute a Set Byzantine Agreement (Set-BA) protocol to achieve consensus on a unified set of local orderings that will form the foundation for the global ordering. During the finalization stage, nodes construct a dependency graph capturing transaction ordering relationships. Any transactions forming a cycle within this graph are grouped into the same strongly connected component and finalized collectively within a block.
However, Aequitas experiences weak liveness, as its substantial communication overhead and stringent fairness constraints require the protocol to wait for the complete Condorcet cycle before finalizing the collapsed SCC. Since Condorcet cycles can chain together indefinitely, this waiting duration can expand without limit. Consequently, transaction delivery can be postponed for an arbitrarily extended period, creating the "freeze" risk that characterizes Aequitas' weak-liveness guarantee.
Themis was developed to resolve this limitation. It maintains the identical γ-BOF property while addressing these liveness and communication challenges. Like Aequitas, Themis also constructs a dependency graph and collapses SCCs during its "FairFinalize" phase. The SCCs represent the identical non-transitive Condorcet cycles underlying the γ-BOF relaxation, and Themis uses the condensation graph to derive the batch structure of the final output. The critical distinction is that Themis does not wait for a complete cycle to finish. Instead, it employs deferred ordering and batch unspooling to output SCCs incrementally while permitting new transactions to continue flowing. This preserves γ-BOF but upgrades Aequitas' weak liveness to standard liveness, guaranteeing delivery within a bounded delay.
In its standard configuration, Themis requires each participant to exchange messages with the majority of other nodes in the network. As participant count increases, the communication volume grows rapidly, roughly proportional to the square of the network size. However, in its optimized version, SNARK-Themis, nodes employ succinct cryptographic proofs to verify fairness without requiring direct communication with every other participant. This reduces the communication burden so that it grows only in direct proportion to the number of nodes, thereby enabling Themis to scale efficiently even in large network environments.
If a malicious proposer attempts to exploit the system by proposing an empty block, Themis utilizes deferred ordering, where the partially ordered batch (B₁) is still accepted, and the final, precise ordering of its transactions is determined subsequently by the next honest proposer. That proposer finalizes the ordering based on verifiable transaction relationships, not personal discretion. This design ensures finalization depends exclusively on bounded network delay, not on the arbitrary behavior of the current proposer, thereby closing a critical liveness gap that Aequitas could not guarantee.
This architecture guarantees that every transaction is both included and executed deterministically, even when conflicting arrival orders exist. Because Themis leverages the internal dependency graph and SCC condensation to extract a final ordering, it is resilient against adversarial manipulation. Attackers cannot simply reorder or front-run other users' transactions after they are included in the batch. Any attempt to alter dependencies would violate the verified graph consistency.
In an empirical analysis conducted by Mahimna Kelkar et al., γ-BOF demonstrates stronger resistance to adversarial reordering compared to timestamp-based approaches within geo-distributed networks. However, it demands significantly greater computational resources and protocol complexity, which can also be viewed as a disadvantage.
Conclusion
Perfect fairness in transaction ordering remains structurally impossible within distributed systems lacking synchronized clocks and instantaneous communication. The Condorcet paradox guarantees that majority preferences can conflict in ways that no single linear sequence can satisfy. The genuine question becomes how to identify the most realistic and beneficial trade-offs.
Hashgraph and BOF represent two coherent solutions. Neither methodology is inherently superior. Both embed fairness directly into the consensus mechanism rather than depending on trust or centralized authority. Both approaches demonstrate that fairness is not a binary characteristic but a spectrum of compromises defined by formal impossibility results. Where synchrony is unavailable, and clocks remain untrusted, the choice between median-timestamp aggregation and batch-order collapsing reflects different but equally principled responses to the identical underlying constraint.