Consensus ensures right now, deal with two properties: Consistency and Liveness. Consistency requires that every one nodes ultimately agree on the identical set and sequence of transactions, whereas liveness ensures the system continues to course of new transactions. What they don’t tackle is whether or not the agreed-upon transaction order completely displays equity.
In public blockchains, transaction ordering has direct financial penalties. The order during which transactions execute determines who captures worth and who pays the fee, notably as validators, block builders, or sequencers can exploit their privileged position in block development for monetary achieve. This follow is named maximal extractable worth (MEV) and contains the worthwhile frontrunning, backrunning, and sandwiching of transactions. Prima facie, there isn’t any apparent solution to stop MEV extracting practices as a result of block proposers maintain unilateral energy over transaction ordering, and no protocol rule inherently constrains how they train that energy.
To handle this, transaction order-fairness has been proposed as a 3rd important consensus property. A protocol is transaction order-fair if no participant can systematically bias transaction ordering past what goal community circumstances and protocol guidelines suggest. By limiting how a lot energy a block proposer has to reorder transactions, fair-ordering protocols transfer blockchains nearer to being clear, predictable, and MEV-resistant.
Nonetheless, even this intuitive thought of equity encounters a structural restrict. In an asynchronous distributed system, there isn’t any globally outlined reception order as a result of every node observes messages at completely different occasions, and no shared clock exists. Due to this fact, no protocol can assure execution strictly in line with a single common arrival sequence. This limitation follows from the fundamental constraints of distributed consensus underneath asynchronous communication, not from any explicit design selection.
The Condorcet Paradox and the Impossibility of Good Equity
Probably the most intuitive and strongest notion of equity is named Obtain-Order-Equity (ROF). It merely means “first-come, first-served.” ROF dictates that if most nodes obtain transaction A earlier than transaction B, then A must be processed earlier than B.
That sounds easy and honest. Nonetheless, the issue is that nodes don’t all see transactions at the very same time. Messages journey at completely different speeds. Some computer systems may obtain A primary. Others may obtain B first. Due to this, it’s inconceivable to ensure good “first-come, first-served” equity except each node can talk immediately with no delays. In actual networks, that by no means occurs.
There may be additionally a deeper drawback referred to as the Condorcet paradox. This concept comes from voting idea. It exhibits that even when every particular person (or node on this case) has a transparent and constant order in their very own thoughts, the group as a complete can find yourself with a loop that is senseless.
For instance:
- Most nodes see A earlier than B
- Most nodes see B earlier than C
- Most nodes see C earlier than A
This produces a majority choice cycle (A→B→C→A), that means no single ordering satisfies the bulk view throughout all pairs. The community can not assemble one sequence that matches what most nodes noticed first.
As a result of good ROF is unachievable underneath these circumstances, sensible techniques undertake some weaker equity ensures as outlined within the sections beneath.
Hashgraph’s Equity Mannequin: Graph of Hashes, Median Timestamps, and aBFT Consensus
Hedera, which employs the hashgraph algorithm, approaches the equity drawback by means of a directed acyclic graph (DAG) of cryptographically linked occasions. It’s a leaderless consensus algorithm that operates in a completely asynchronous setting and achieves Asynchronous Byzantine Fault Tolerant (aBFT). Beneath this mannequin, trustworthy nodes ultimately attain settlement on the identical transaction log even underneath unbounded message delays. Consensus ordering emerges from network-wide commentary by means of a digital voting course of: the order is calculated collectively by nodes reasonably than assigned by a delegated block producer.
When a node receives a transaction, it packages it right into a message referred to as an occasion and gossips it to friends. When one other node creates a subsequent occasion, it information the hash of the occasions it has already seen and digitally indicators the brand new occasion. This offers cryptographic proof that the node had seen prior occasions earlier than signing the brand new one. The hashgraph, subsequently, enforces causal order: as soon as a node publishes an occasion, the ancestry embedded in that occasion proves which transactions preceded it.
This linkage will be represented as an edge within the DAG. If one occasion is a direct or oblique ancestor of one other, a downward path exists between them within the graph, and the protocol offers a cryptographic assure that the ancestor occasion was created first. Transactions related by such paths are ordered in line with their causal relationships within the graph. When two occasions haven’t any ancestor relationship, they’re concurrent, and the protocol resolves their relative order by means of the round-received mechanism. Every occasion is assigned a spherical primarily based on when a supermajority of nodes, outlined as greater than two-thirds, will be proven to have strongly seen it by means of the DAG construction. Occasions assigned to earlier rounds are ordered first.
For occasions that share the identical round-received, the protocol makes use of median timestamps to find out ordering. Every node information a neighborhood timestamp when it first receives an occasion. The consensus timestamp assigned to an occasion is the median of the timestamps reported throughout the node set. This timestamp isn’t derived from arbitrary native clocks in isolation. It’s constrained by the gossip ancestry preserved within the hashgraph: a node can not declare to have obtained an occasion earlier than its causal predecessors with out producing a detectable inconsistency within the DAG.
Beneath the usual aBFT assumption that fewer than one-third of nodes are Byzantine, the median falls on an trustworthy timestamp or between two trustworthy timestamps, which prevents adversarial nodes from shifting the median past a bounded vary.
The Condorcet paradox can nonetheless apply to concurrent occasions, particularly these with no ancestor relationship within the DAG, the place completely different nodes could observe them in several orders. The DAG construction eliminates this ambiguity for causally linked occasions: no contradictory causal paths can exist as a result of every occasion’s ancestry is cryptographically fastened at creation. As a result of gossip propagation usually causes new occasions to change into descendants of prior occasions inside fractions of a second, most transactions fall into clear causal chains. The remaining concurrent occasions are resolved by means of round-received task and median timestamps as described above.
Nonetheless, the hashgraph’s equity ensures have a bounded adversarial floor. A node nonetheless determines when to gossip an occasion, which occasions to relay first, and the way lengthy to delay relaying. These decisions reshape the first-seen patterns that feed into median timestamp computation. The DAG can not misrepresent the causal order it information, however it may be strategically formed by gossip habits earlier than that order is recorded.
BOF Protocols: Equity Via Batch Aggregation
BOF protocols outline a “block” because the set of transactions forming a single Condorcet cycle, after which order these blocks pretty whereas ignoring the ordering contained in the block. The BOF criterion was first launched by Mahimna Kelkar et al. (2020) in “Order-Equity for Byzantine Consensus,” which formalized the Aequitas household of protocols. In Aequitas, BOF requires that if a γ-fraction of nodes observe block (b) earlier than block (b′), then no trustworthy node could output (b) after (b′). The γ-fraction is the proportion of nodes that should agree on a block ordering for that ordering to be thought-about “honest” and enforced by the consensus protocol.
For BOF, if the equity predicate signifies {that a} transaction tx ought to precede tx′, then tx can not seem in a later block than tx′. When the equity relation turns into cyclic, the protocol collapses all the strongly related part right into a single block, as a result of BOF treats that block, not the person transaction, because the atomic equity unit. Beneath γ-BOF, the one forbidden end result is putting tx′ in a strictly earlier block than tx when a directed constraint tx→tx′ exists. The protocol permits each transactions to seem in the identical block and locations no restrictions on their ordering inside that block.
For instance, Determine 2 beneath, is a Condorcet cycle of 30 transactions, so they might be in a single block. Sorting by hash may place 30 earlier than 1 within the last ordering. Nonetheless, a γ-fraction of nodes noticed transaction 1 earlier than transaction 30, but putting 30 earlier than 1 continues to be thought-about “honest” underneath γ-BOF. As a result of 1 and 30 are in the identical block, and this notion of equity solely considers the order of the blocks, not the order of the transactions inside a block.
When no cycles exist, BOF coincides with the robust type of ROF. When Condorcet cycles emerge, all transactions collaborating within the cycle are positioned right into a single block, and a deterministic methodology, reminiscent of a hash-based rule, orders occasions inside that batch.
The protocol proceeds by means of three coordinated phases to make sure constant transaction ordering throughout the community: the Gossip stage, the Settlement stage, and the Finalization stage.
Within the gossip stage, nodes use FIFO broadcast to disseminate transactions within the order they have been domestically obtained per sender, preserving per-sender sequence so that every peer maintains a comparable transaction view. As soon as gossiping stabilizes, the settlement stage begins, the place nodes execute a Set Byzantine Settlement (Set-BA) protocol to achieve consensus on a unified set of native orderings that may function the muse for the worldwide order. Within the finalization stage, nodes assemble a dependency graph that captures transaction ordering relationships. Any transactions forming a cycle inside this graph are grouped into the identical strongly related part and finalized collectively inside a block.
Nonetheless, Aequitas suffers from weak liveness, as its excessive communication value and strict equity constraints require the protocol to attend for all the Condorcet cycle earlier than finalizing the collapsed SCC. As a result of Condorcet cycles can chain indefinitely, this ready interval can develop with out certain. Thus, transaction supply will be delayed for an arbitrarily very long time, and creates the “freeze” danger that defines Aequitas’ weak-liveness assure.
Themis was launched to resolve this. It preserves the identical γ-BOF property whereas resolving these liveness and communication points. Like Aequitas, Themis additionally constructs a dependency graph and collapses SCCs throughout its “FairFinalize” stage. The SCCs characterize the identical non-transitive Condorcet cycles underlying the γ-BOF rest, and Themis makes use of the condensation graph to derive the batch construction of the ultimate output. The important thing distinction is that Themis doesn’t look ahead to a full cycle to finish. As an alternative, it makes use of deferred ordering and batch unspooling to output SCCs incrementally whereas permitting new transactions to proceed flowing. This preserves γ-BOF however upgrades Aequitas’ weak liveness to plain liveness, and ensures supply inside a delay certain.
In its commonplace kind, Themis requires every participant to change messages with most different nodes within the community. Because the variety of members will increase, the quantity of communication grows quickly, roughly proportional to the sq. of the community measurement. Nonetheless, in its optimized model, SNARK-Themis, nodes use succinct cryptographic proofs to confirm equity while not having to speak straight with each different participant. This reduces the communication load in order that it grows solely in direct proportion to the variety of nodes, thus permitting Themis to scale effectively even in giant networks.
If a malicious proposer makes an attempt to take advantage of the state of affairs by proposing an empty block, Themis employs deferred ordering, the place the partially ordered batch (B₁) continues to be accepted, and the ultimate, exact order of its transactions is decided later by the following trustworthy proposer. That proposer finalizes the order primarily based on verifiable transaction relationships, not private discretion. This design ensures finalization relies upon solely on bounded community delay, not on the arbitrary habits of the present proposer, thus closing a key liveness hole that Aequitas couldn’t assure.
This construction ensures that each transaction is each included and executed deterministically, even within the presence of conflicting arrival orders. As a result of Themis leverages the inner dependency graph and SCC condensation to extract a last ordering, it’s resilient to adversarial manipulation. Attackers can not merely reorder or front-run different customers’ transactions as soon as they’re included within the batch. Any try to change dependencies would break the verified graph consistency.
In an empirical evaluation by Mahimna Kelkar et al., γ-BOF resists adversarial reordering extra strongly than timestamp-based approaches in geo-distributed networks. Nonetheless, it requires considerably extra computational and protocol complexity, which will also be seen as a draw back.
Conclusion:
Good equity in transaction ordering is structurally unattainable in distributed techniques that lack synchronized clocks and instantaneous communication. The Condorcet paradox ensures that majority preferences can battle in methods no single linear order can fulfill. The actual query is discover essentially the most life like and helpful trade-offs.
Hashgraph and BOF characterize two coherent solutions. Neither method is inherently superior. Each embed equity straight into the consensus mechanism reasonably than counting on belief or authority. Each approaches exhibit that equity isn’t a binary property however a spectrum of trade-offs outlined by formal impossibility outcomes. The place synchrony is unavailable, and clocks are untrusted, the selection between median-timestamp aggregation and batch-order collapsing displays completely different however equally principled responses to the identical underlying constraint.
