Breaking Fair Ordering with a Minority

Jun 1, 2023 · 6 min · paper

• transaction ordering
• mev
• voting theory

Fair-ordering protocols try to take sequencing power away from any single operator by putting it to a vote. If most nodes saw tx₁ before tx₂, tx₁ goes first. The result in this paper is that aggregating those local orderings inherits a problem Condorcet described in 1785: pairwise majorities can cycle, and where they cycle, the protocol stops promising anything.

Every protocol in this family knows about the cycles. All of them treat the cycles as accidents of timing, a handful of transactions that arrived at roughly the same moment, swept into a batch, ordered inside the batch by whatever is cheap. This paper builds them on purpose.

The claim

Two valid transactions from an ordinary client are enough to pull unrelated transactions into a Condorcet cycle, where fair ordering guarantees nothing. Every node in the committee can be honest and it still works.

Themis, the strongest of these protocols, tolerates up to f < (2γ − 1) n / 4 faulty nodes. The attack needs none of them. It needs one client, two transactions that look like anyone else’s, and control of nothing but its own send order.

A majority can fail to have an opinion

Three nodes, three transactions, each node reporting a rotation of the same list. Take any pair and there is a clear two-to-one winner. Take all three and the winners point in a circle.

No ordering satisfies all three majorities, and no protocol can invent one; the impossibility is older than the systems it now blocks. So every fair-ordering protocol carves out the same exception. Transactions caught in a cycle go into a batch, and unfairness inside a batch is not counted against the protocol. Aequitas orders a batch alphabetically. Quick-Fairness says nothing about it at all.

That exception is the whole target. A cycle is not an accident to be waited out. It is a hole in the guarantee, and it can be dug where you want it.

Forging the cycle on purpose

Split the committee into three parts. Send A then B to the first part, B alone to the second, nothing to the third. Then wait. Ordinary traffic arrives during the wait, and every node sees it in the same order, because the transactions are seconds apart. Finish by sending A to the second part and A then B to the third.

Read the three reports at the bottom of the figure. Each is an honest account of what that part saw. Together they put A, B and every transaction from the pause into one cycle. The honest transactions did not arrive close together and their senders had no relationship to each other. They were bracketed.

The pause length sets the haul, bounded only by the length of one consensus round.

Two details from the simulations are worth keeping. The runs sit below an external network ratio of one, meaning transactions arrive further apart than the network’s own latency, the regime where cycles do not form on their own, so every cycle measured is one the attack built. And an adversary that instead controls a quarter of the committee including the leader, and simply reverses its reported orderings, achieves close to nothing in that same regime. Sending from outside is what gives the attack its reach.

The one fragile part is the network. The injected transactions have to arrive in the order they were sent, and packet reordering breaks individual attempts. The fix is cloning: interleave several copies of the attack. Four transactions across four parts with a single clone is close to immune.

What the batch costs

A batch is a cycle and a cycle has no first element, so it cannot be a schedule. Themis turns one into a schedule by building a Hamiltonian cycle through the batch and cutting the lightest edge.

In this five-transaction version the rule holds: the light edges are the adversary’s own, so cutting one leaves tx₁, tx₂, tx₃ in the order they were sent. That is luck, not protection. The paper gives a five-node construction where every edge in the cycle carries identical weight, and then the choice of cut is arbitrary. Scale the batch from three honest transactions to twenty and arbitrary is what it looks like in practice.

What actually helps

Three mitigations, none complete, none in conflict:

• Ranked pairs inside the batch. Tideman’s 1987 rule: sort the edges by weight, accept them strongest first, skip any edge that would close a cycle. Where the honest ordering has full support it is accepted before anything else can interfere, and it survives, that is the proposition in the paper. Where support is split, the guarantee goes with it.
• Order encrypted, resolve after. Keep the batch encrypted through consensus, then decrypt and split it into groups of transactions that actually touch each other. The adversary’s transactions cannot move honest ones they have nothing to do with. Unless the adversary picks its dependencies deliberately: during an NFT drop, everything is in the same group.
• Broadcast on receipt. Nodes gossip transactions the moment they arrive, which destroys the pause, the second injection lands on nodes that already ordered the first. This is the most effective of the three in simulation, and the easiest to defeat if the adversary controls the internal network and can hold the gossip until the attack is done.

The honest summary is that all three together raise the cost, and an adversary with both an outside client and a foothold inside the committee still gets somewhere.

Open threads

• Why cycles built from inside stay short while injected ones stretch across the whole pause. The paper leaves the analysis open, and it is the question I would most like answered.
• Whether a better injection pattern exists. The one here was constructed by hand and already traps nearly everything, which suggests the ceiling is close, not that it has been found.
• What ranked pairs actually guarantees against an adversary holding both ends: the injection and a share of the votes.

The full construction, the proofs and the simulation details are in the paper.

← all research