The impossibility of perfect fairness in transaction ordering

For decades, research has been done on distributed systems, especially in… Byzantine consensus and State Machine Replication (SMR)focus on two main goals: consistency and vitality. Consistency means that all nodes agree on the same sequence of transactions, while liveness ensures that the system continues to add new transactions. However, these properties do not prevent bad actors from changing the order of transactions after they are received.

In public blockchains, this gap in traditional consensus guarantees has become a serious problem. Validators, block creators or Sequencers They can exploit their privileged role in block ordering for financial gain, a practice known as maximum extractable value (MEV). This manipulation includes profitable primary and back-end liquidations and transaction counting. Since the order to execute a transaction determines validity or profitability in DeFi applications, the integrity of the transaction order is vital to maintaining fairness and trust.

To address this critical security gap, the fairness of transaction orders has been proposed as a third fundamental consensus property. Fair system protocols Ensure that the final ordering of transactions is based on external and objective factors, such as arrival times (or order receipt) and is resistant to adversarial reordering. By limiting the amount of power a block provider has to reorder transactions, these protocols move blockchains closer to being transparent, predictable, and MEV-resistant.

Condorcet’s paradox and the impossibility of perfect justice

The most intuitive and powerful concept of justice is… Receiving Order Fairness (ROF). ROF is informally defined as “first in, first out”, which dictates that if there are enough transactions (Texas) Access to the majority of nodes before another transaction (texas’)then the system is required for the system tx before Texas ′ To implement.

However, achieving universally accepted “system fairness” is essentially impossible unless it is assumed that all nodes can communicate instantaneously (i.e. operate in an instantaneous synchronous external network). This impossibility result stems from a surprising connection to social choice theory, specifically the Condorcet paradox.

Condorcet’s paradox explains how even when each node maintains an internal transitive order of transactions, collective favoring across the system can lead to what are known as nontransitive cycles. For example, it is possible that the majority of nodes receive the transaction A before forThe majority receive for before CAnd the majority receive C before A. Hence, the three majority preferences form a loop (A→for→C→A). This means that there is no single, consistent arrangement of transactions A, B, and C that can satisfy all majority preferences simultaneously.

This paradox explains why the goal of perfect receiving justice is impossible to achieve Asynchronous networkingor even in Synchronous networks That share a common clock if external network delays are too long. This impossibility requires adopting weaker definitions of fairness, such as fairness of batch orders.

Hedera Hashgraph and Intermediate Timestamp Defect

Hedera, which uses the Hashgraph consensus algorithm, seeks to approximate a robust idea of ​​Request Receipt Fairness (ROF). This is done by assigning a final timestamp to each transaction that is calculated as an average of the local timestamps of all nodes for that transaction.

However, this is inherently vulnerable to manipulation. A single competitive node can intentionally distort its local timestamps and reflect the final order of two transactions, even when all honest participants receive them in the correct order.

Consider a simple example with five consensus nodes (A, B, C, D, and E) where node E acts maliciously. Two transactions, tx₁ and tx₂, are broadcast to the network. All honest nodes receive tx₁ before tx₂, so the expected final order should be tx₁ → tx₂.

In this example, the adversary assigns tx₁ a later timestamp (3) and tx₂ an earlier timestamp (2) to skew the medium.

When the protocol calculates the arguments:

• For tx₁, the timestamps (1, 1, 4, 4, 3) give an average of 3.

• For tx₂, the timestamps (2, 2, 5, 5, 2) give an average of 2.

Since the final timestamp of tx₁(3) is larger than that of tx₂(2), the protocol outputs tx₂ → tx₁, thus reversing the true order observed by all honest nodes.

This game example illustrates a serious flaw: the middle job, although seemingly neutral, is paradoxically the actual cause of injustice because it can be exploited by a single dishonest participant to bias the order of the final transaction.

As a result, the “fair timestamp” that Hashgraph often promotes is a surprisingly weak idea of ​​justice. Hashgraph consensus fails to guarantee the fairness of receiving requests and instead relies on a set of permissioned validators rather than cryptographic guarantees.

Achieving practical guarantees

However, to circumvent the theoretical impossibility demonstrated by Condorcet, practical just order schemes must somehow relax the definition of justice.

the Stock protocols Provided standard Block System Fairness (BOF)or the fairness of the batch order. BOF enforces that if multiple nodes receive a transaction tx before another transaction tx′, then tx must be delivered in a block before or at the same time as tx′, which means that no honest node can deliver tx′ in a block after tx. This relaxes the rule from “must deliver by” (ROF requirement) to “must deliver no later than”.

Consider three consensus nodes (A, B, and C) and three transactions: tx₁, tx₂, and tx₃. A transaction is considered “pre-received” if at least two of the three (majority) nodes notice it first.

If we apply majority voting to determine the world 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₁. In this case, no single request can satisfy everyone’s point of view simultaneously, which means that it is impossible to achieve a strict ROF.

BOF solves this problem by grouping all conflicting transactions into the same batch or block instead of forcing one to come before the other. The protocol simply outputs:

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

This means that, from the protocol’s point of view, the three transactions are treated as if they occurred at the same time. Within a block, a deterministic separator (such as a hash value) decides the exact order in which it will be executed. By doing this, BOF ensures fairness for every pair of transactions and keeps the final transaction history consistent for everyone. Each one is processed no later than the one before it.

This small but important modification allows the protocol to handle situations where transaction orders conflict, by grouping those conflicting transactions into the same block or batch. Importantly, this does not lead to partial ordering, as each node must agree on a single linear sequence of transactions. Transactions within each block are still arranged in a fixed order of execution. In cases where such conflicts do not occur, the protocol still achieves the stronger ROF property.

Although Aequitas was successful in achieving BOF, it faced significant limitations, especially since it had a very high communication complexity and could only guarantee weak liveliness. Weak liveness means that delivery of a transaction is only guaranteed after the entire Condorcet cycle of which it is a part has been completed. This can take an arbitrarily long time if the cycles are “chained together”.

the Themis Protocol It was introduced to enforce the same powerful BOF property, but with improved communication complexity. Themis achieves this using three techniques: batch unbundling, deferred ordering, and stronger inter-batch guarantees.

In its standard form, Themis requires each participant to exchange messages with most other nodes in the network. The amount of communication required increases with the square of the number of network participants. However, in its improved version, SNARK-Themis, nodes use brief cryptographic proofs to verify fairness without having to communicate directly with every other participant. This reduces the communication overhead so that it grows only linearly, allowing Themis to scale efficiently even in large networks.

Assume that five nodes (A–E) participating in the consensus receive three transactions: tx₁, tx₂, and tx₃. Due to network latency, its local requests vary:

As in Equitas, these preferences create a Condorcet cycle. But instead of waiting for the entire cycle to resolve, Themis keeps the system moving using a method called Batch unspooling. It identifies all the parameters that are part of the cycle and combines them into a single group, called a strongly connected component (SCC). In this case, all three transactions belong to the same SCC, which Themis outputs as a batch in progress, called Batch B₁ = {tx₁, tx₂, tx₃}.

By doing this, Themis allows the network to continue processing new transactions even while the internal request for payment B₁ is finalized. This ensures that the system stays alive and avoids downtime.

summary:

The concept of perfect fairness in a transaction request may seem straightforward. Whoever reaches the network first, must be processed first. However, as the Condorcet Paradox demonstrates, this ideal cannot hold in real distributed systems. Different nodes see transactions in different orders, and when these views conflict, no protocol can build a single, universally “correct” sequence without compromise.

Hedera’s Hashgraph has tried to approximate this model using average timestamps, but this approach relies more on trust than proof. A single dishonest participant can distort the broker and reverse the order of the transaction, revealing that the “fair timestamp” is not really fair.

Protocols like Aequitas and Themis move the discussion forward by acknowledging what can and cannot be achieved. Instead of chasing the impossible, they redefine justice in a way that preserves the integrity of the system under real network conditions. What results from this is not a rejection of justice, but rather its development. This development draws a clear line between perceived justice and demonstrable justice. It demonstrates that the true integrity of transaction orders in decentralized systems cannot depend on reputation, auditor trust, or permitted control. It must come from cryptographic verification built into the protocol itself.

This article does not contain investment advice or recommendations. Every investment and trading move involves risks, and readers should conduct their own research when making a decision.

This article is for general information purposes and is not intended and should not be taken as legal or investment advice. The views, thoughts and opinions expressed herein are those of the author alone and do not necessarily reflect or represent the views and opinions of Cointelegraph.

Cointelegraph does not endorse the content of this article nor any product mentioned here. Readers should conduct their own research before taking any action regarding any product or company mentioned and take full responsibility for their decisions.