For many years, analysis in distributed programs, particularly in Byzantine consensus and state machine replication (SMR), has centered on two primary objectives: consistency and liveness. Consistency means all nodes agree on the identical sequence of transactions, whereas liveness ensures the system continues so as to add new ones. Nonetheless, these properties don’t cease dangerous actors from altering the order of transactions after they’re obtained.

In public blockchains, that hole in conventional consensus ensures has change into a major problem. Validators, block builders or sequencers can exploit their privileged position in block ordering for monetary acquire, a follow often known as maximal extractable worth (MEV). This manipulation consists of worthwhile frontrunning, backrunning and sandwiching of transactions. As a result of transaction execution order determines validity or profitability in DeFi functions, the integrity of transaction ordering is important for sustaining equity and belief.

To handle this vital safety hole, transaction order-fairness has been proposed as a 3rd important consensus property. Honest-ordering protocols make sure that the ultimate order of transactions is determined by exterior, goal components, equivalent to arrival instances (or receiving order) and is proof against adversarial reordering. By limiting how a lot energy a block proposer has to reorder transactions, these protocols transfer blockchains nearer to being clear, predictable, and MEV-resistant.

The Condorcet paradox and impossibility of ultimate equity

Essentially the most intuitive and strongest notion of equity is Obtain-Order-Equity (ROF). Informally outlined as “first obtained, first output,” ROF dictates that if a adequate variety of transactions (tx) arrive at a majority of nodes sooner than one other transaction (tx′), then the system is required to order tx earlier than tx′  for execution.

Nevertheless, attaining this universally accepted “order equity” is essentially inconceivable except it’s assumed that every one nodes can talk instantaneously (i.e., working right away synchronous exterior community). This impossibility outcome stems from a stunning connection to social selection concept, particularly the Condorcet paradox.

The Condorcet paradox illustrates how, even when each particular person node maintains a transitive inner ordering of transactions, the collective choice throughout the system can lead to what are often known as non-transitive cycles. For instance,  it’s doable {that a} majority of nodes obtain transaction A earlier than B, a majority obtain B earlier than C, and a majority obtain C earlier than A. Therefore, the three majority preferences type a loop (A→B→C→A). Which means that no single, constant ordering of the transactions A, B and C can ever fulfill all majority preferences concurrently. 

This paradox demonstrates why the objective of completely attaining Obtain-Order-Equity is inconceivable in asynchronous networks, and even in synchronous networks that share a typical clock if exterior community delays are too lengthy. This impossibility necessitates the adoption of weaker equity definitions, equivalent to batch order equity.

Hedera Hashgraph and flaw of median timestamping

Hedera, which employs the Hashgraph consensus algorithm, seeks to approximate a powerful notion of receive-order equity (ROF). It does this by assigning every transaction a ultimate timestamp computed because the median of all nodes’ native timestamps for that transaction. 

Nevertheless, that is inherently liable to manipulation. A single adversarial node can intentionally distort its native timestamps and invert the ultimate ordering of two transactions, even when all sincere contributors obtained them within the right order.

Think about a easy instance with 5 consensus nodes (A, B, C, D and E) the place Node E acts maliciously. Two transactions, tx₁ and tx₂, are broadcast to the community. All sincere nodes obtain tx₁ earlier than tx₂, so the anticipated ultimate order ought to be tx₁ → tx₂.

On this instance, the adversary assigns tx₁ a later timestamp (3) and tx₂ an earlier one (2) to skew the median. 

When the protocol computes the medians:

• For tx₁, the timestamps (1, 1, 4, 4, 3) yield a median of three.

• For tx₂, the timestamps (2, 2, 5, 5, 2) yield a median of two.

As a result of the ultimate timestamp of tx₁ (3) is bigger than that of tx₂ (2), the protocol outputs tx₂ → tx₁, thus reversing the true order noticed by all sincere nodes.

This toy instance demonstrates a vital flaw: The median perform, whereas showing impartial, is paradoxically the precise explanation for unfairness as a result of it may be exploited by even a single dishonest participant to bias the ultimate transaction order.

In consequence, Hashgraph’s often-touted “truthful timestamping” is a surprisingly weak notion of equity. The Hashgraph consensus fails to ensure receive-order equity and as an alternative is determined by a permissioned validator set slightly than on cryptographic ensures. 

Attaining sensible ensures

Nevertheless, to avoid the theoretical impossibility demonstrated by Condorcet, sensible fair-ordering schemes should calm down the definition of equity in a roundabout way. 

The Aequitas protocols launched the criterion of Block-Order-Equity (BOF), or batch-order-fairness. BOF dictates that if sufficiently many nodes obtain a transaction tx earlier than one other transaction tx′, then tx should be delivered in a block earlier than or similtaneously tx′, which means no sincere node can ship tx′  in a block after tx. This relaxes the rule from “should be delivered earlier than” (the requirement of ROF) to “should be delivered no later than”.

Think about three consensus nodes (A, B and C) and three transactions: tx₁, tx₂, and tx₃. A transaction is taken into account “obtained earlier” if a minimum of two of the three nodes (a majority) observe it first.

If we apply majority voting to find out a worldwide order:

• tx₁ → tx₂ (agreed by A and C)

• tx₂ → tx₃ (agreed by A and B)

• tx₃ → tx₁ (agreed by B and C)

These preferences create a loop: tx₁ → tx₂ → tx₃ → tx₁. On this state of affairs, there’s no single order that may fulfill everybody’s view directly, which implies strict ROF is inconceivable to attain.

BOF solves this by grouping all of the conflicting transactions into the identical batch or block as an alternative of forcing one to return earlier than one other. The protocol merely outputs:

Block B₁ = {tx₁, tx₂, tx₃}

Which means that, from the protocol’s perspective, all three transactions are handled as in the event that they occurred on the identical time. Contained in the block, a deterministic tie-breaker (equivalent to a hash worth) decides the precise order during which they’ll be executed. By doing this, BOF ensures equity for each pair of transactions and retains the ultimate transaction log constant for everybody. Each is processed no later than the one which precedes it.

This small however necessary adjustment lets the protocol deal with conditions the place transaction orderings battle, by grouping these conflicting transactions into the identical block or batch. Importantly, this doesn’t lead to a partial ordering, as each node should nonetheless agree on one single, linear sequence of transactions. The transactions inside every block are nonetheless organized in a hard and fast order for execution. In circumstances when no such conflicts happen, the protocol nonetheless achieves the stronger ROF property.

Whereas Aequitas efficiently achieved BOF, it confronted important limitations, significantly that it had very excessive communication complexity and will solely assure weak liveness. Weak liveness implies {that a} transaction’s supply is simply assured after your entire Condorcet cycle it is part of is accomplished. This might take an arbitrarily very long time if cycles “chain collectively.”

The Themis protocol was launched to implement the identical robust BOF property, however with improved communication complexity. Themis achieves this utilizing three methods: Batch Unspooling, Deferred Ordering, and Stronger Intra-Batch Ensures.

In its normal type, Themis requires every participant to trade messages with most different nodes within the community. The quantity of communication required will increase with the sq. of the variety of community contributors. Nevertheless, in its optimized model, SNARK-Themis, nodes use succinct cryptographic proofs to confirm equity while not having to speak immediately with each different participant. This reduces the communication load in order that it grows solely linearly, which permits Themis to scale effectively even in giant networks.

Assume 5 nodes (A–E) collaborating in consensus obtain three transactions: tx₁, tx₂, and tx₃. Attributable to community latency, their native orders differ:

As in Aequitas, these preferences create a Condorcet cycle. However as an alternative of ready for your entire cycle to be resolved, Themis retains the system shifting utilizing a technique known as batch unspooling. It identifies all transactions which can be a part of the cycle and teams them into one set, known as a strongly linked element (SCC). On this case, all three transactions belong to the identical SCC, which Themis outputs as a batch-in-progress, labeled Batch B₁ = {tx₁, tx₂, tx₃}.

By doing this, Themis permits the community to maintain processing new transactions even whereas the inner order of Batch B₁ continues to be being finalized. This ensures the system stays stay and avoids stalling.

Overview: 

The idea of excellent equity in transaction ordering could seem simple. Whoever’s transaction reaches the community first ought to be processed first. Nevertheless, because the Condorcet paradox demonstrates, this ultimate can’t maintain in actual, distributed programs. Completely different nodes see transactions in numerous orders, and when these views battle, no protocol can construct a single, universally “right” sequence with out compromise.

Hedera’s Hashgraph tried to approximate this ultimate with median timestamps, however that strategy depends extra on belief than on proof. A single dishonest participant can distort the median and flip transaction order, revealing that “truthful timestamping” is just not actually truthful.

Protocols like Aequitas and Themis transfer the dialogue ahead by acknowledging what can and can’t be achieved. As a substitute of chasing the inconceivable, they redefine equity in a approach that also preserves order integrity beneath actual community circumstances. What emerges is just not a rejection of equity, however its evolution. This evolution attracts a transparent line between perceived equity and provable equity. It reveals that true transaction-order integrity in decentralized programs can’t depend upon fame, validator belief or permissioned management. It should come from cryptographic verification embedded within the protocol itself.

This text doesn’t comprise funding recommendation or suggestions. Each funding and buying and selling transfer entails threat, and readers ought to conduct their very own analysis when making a call.

This text is for common data functions and isn’t meant to be and shouldn’t be taken as authorized or funding recommendation. The views, ideas, and opinions expressed listed here are the writer’s alone and don’t essentially replicate or signify the views and opinions of Cointelegraph.

Cointelegraph doesn’t endorse the content material of this text nor any product talked about herein. Readers ought to do their very own analysis earlier than taking any motion associated to any product or firm talked about and carry full accountability for his or her choices.