An auction where nobody sees the bids

A share of a tokenised receivable goes to auction. There is only one, and several people want it. Before any theory, pick a number: the most you would pay for it without regretting it.

Hold on to that number. It is the only piece of information that really matters in this article, and it is exactly the information an ordinary auction forces you to hand over to your competitors.

In an ordinary auction, whoever bids highest pays their own bid. You learn quickly not to write down what the thing is worth to you: you write less, hoping to win anyway. Everyone does the same, and the auction ends up decided by whoever guessed best, not by whoever values the share most.

In 1961, William Vickrey proposed a one-line change: whoever bids highest wins, but pays the second-highest bid. Drag your bid below and follow your profit under the two rules.

Under second price, the profit curve goes flat as soon as you pass the highest rival. Raising your bid does not increase what you earn, because the price is not your bid. Lowering it only makes you lose an auction that was worth winning. And lying upwards, above your value, can make you win an auction that loses money.

One strategy is left: telling the truth. That is what theory calls a dominant strategy, and it is why the Vickrey mechanism is treated as manipulation-proof.

Switch to first price and the curve becomes a ramp. There is an optimal bid, but it depends on everyone else's bids, which you do not know. First price rewards whoever guesses. Second price rewards whoever is honest.

In the paper: the formal Vickrey rules and the proof of truthfulness (§2.5.4 and §2.5.5)

That whole guarantee rests on one premise: that the auction really is sealed. You decide your bid without knowing anyone else's, and they decide without knowing yours.

On a public blockchain, the premise does not survive the transaction's journey. Before being confirmed, it passes through the mempool, the waiting room for pending transactions, and any node on the network can read what is there. That is not a flaw: for the network to agree on the next block, everyone must know the candidate transactions first. Transparency is the price of decentralisation.

What the bot did has a name, frontrunning, and under Vickrey it is especially perverse: the second-price rule works in favour of whoever copies. Offering a little more than you is enough to win while paying exactly your number, without ever having appraised the share.

There is a whole industry inside that window between sending and confirming, studied under the name MEV. Bots watch the mempool, and whoever assembles the block chooses the order of the transactions inside it. Each stage leaks something different: how much, when, from whom and in what order. And the record stays forever, which turns every auction into study material for competitors in the next ones.

If the bid appears in plaintext at any instant, the auction stopped being sealed at that instant. Hiding it afterwards recovers nothing.

In the paper: leakage in native auctions and the variants of MEV (§1.2.1 and §1.2.2)

The classic answer from contract engineering is commit-reveal. First you send only the hash of your bid, a fingerprint that binds you to the number without revealing it. Once the deadline closes, you come back and reveal the amount; the contract recomputes the hash and checks that it matches.

That solves the mempool: while the auction runs, nobody sees anything. Play with the participants below to see what it does not solve.

There are two holes, and the second is deeper than the first.

• Whoever disappears stalls the settlement. A participant who realises they have lost has no reason at all to come back and reveal. The usual escapes, a mandatory bond, a deadline or a re-auction, charge everyone in order to punish one.
• Whoever reveals hands over the number. It is by construction: to know which are the two highest, everyone must show their hand. In the end, each participant knows everyone else's valuation, and carries that into the auctions that follow.

Add to that two transactions per person instead of one, with the cost and the chance of forgetting that come with it.

Commit-reveal hides the bids during the auction and publishes them at the end. Vickrey needs exactly the opposite: reveal the price and never reveal the bids.

In the paper: the four structural limitations of commit-reveal (§1.2.3)

The two previous attempts failed for the same reason: at some moment the number had to exist in plaintext so that someone could compare it. The question that opens the way out is whether that moment really has to exist.

Fully homomorphic encryption, FHE, answers no. In a homomorphic scheme, operations performed on the ciphertexts correspond to operations on the plaintexts. You hand encrypted numbers to a machine you do not trust, it returns the result encrypted, and only whoever holds the key decrypts it. The machine computed without seeing.

The two columns below do the same computation, that of finding out which of two bids is higher. Change the values and compare.

Two things there deserve attention. The first is that even the result of the comparison comes out encrypted: the contract can use that result, but cannot read it. The second is that the decryption key belongs to nobody in particular. It is split into shares among the members of a threshold network, and nothing is decrypted unless a minimum number of them cooperate.

Delegating the computation without handing over the data: that is what FHE does. The rest of this article is what happens when you try to use it to run Vickrey for real.

In the paper: homomorphism, TFHE and the threshold decryption network (§2.2.3 and §2.3)

With encrypted comparison in hand, it looks finished: just find the highest and the second highest. But Vickrey hides a trap exactly there.

To find the second, you must take the first out of the way. And to take the first out, you would need to know who the first is. Under encryption you do not know, and asking would break all the secrecy just built. That is the exclusion problem, and it is the knot this work unties.

The way out adopted here is not to store the bids. The contract keeps only two encrypted numbers, the highest and the second highest, plus the encrypted identity of whoever is leading, and updates all three with every bid that arrives. Step through the bids below, and switch on the X-ray to see what sits behind each padlock.

Three things happen there, and none of them is obvious.

• The cost does not grow. It is always two comparisons and four selections, whether the auction has three participants or three hundred, because no old bid needs to be revisited.
• The storage does not grow. It is always three encrypted values kept, not one per participant.
• There is no if. The six operations always run, including when the bid changes nothing. A conditional branch would require someone to have read the result of the comparison, and nobody read it.

Ties still come for free. Because the comparison is strictly greater, a bid equal to the leader's does not replace it: whoever arrived first wins, which is the classic tie-breaking rule in auctions. The simulator's three tie scenarios are the same ones the contract's test suite verifies.

The alternative known in the literature is to store every bid and, at closing, zero out the winner with an encrypted mask in order to look for the new maximum. It works, but it charges per participant: it stores N bids, spends N comparisons at closing and still needs extra logic so as not to zero out two tied bids at once.

In the paper: the exclusion problem, the incremental top-2 pattern and the handling of ties (§4.2.2 to §4.2.4)

When the auction closes, two things become public out of necessity: who won, because somebody has to receive the share, and the second-highest bid, because that is the price to pay. Everything else stays encrypted forever.

“Stays encrypted” is easy to say. It can also be measured. Since the bid cap is public and the second price was revealed, an observer can narrow each bid down to a range: the winner's lies between the price paid and the cap, and each loser's lies between zero and the price paid. The size of those ranges is the size of the doubt that is left.

At the values of the demonstration auction, around 95% of the original uncertainty survives the closing. In a public auction it would be zero: every bid would be written down, with a name and an amount, forever. In the commit-reveal of scene 03, likewise: every revealed number is public.

The Vickrey rule requires revealing exactly one number. The measurement shows that it charges exactly that, and not a cent of information more.

The calculation is generous to the observer on purpose. It assumes they have no clue beyond what is on the blockchain, which produces the largest possible value of uncertainty. Whoever arrives knowing more ends up knowing more.

In the paper: the derivation of the residual entropy and the adversary model (§5.4)

Privacy is not free. Every encrypted comparison is a heavy operation, and somebody pays the bill. The numbers below come from complete auctions run on a public test network, with three, five and ten participants and five repetitions each.

Switch the number of participants on the mock and notice that the bars barely move. That is the promise of the top-2 pattern showing up in the measurement: the cost per operation does not depend on how many people have already bid. On the test network there is some variation, but it comes from the network's data fee, not from the algorithm.

In money, an encrypted bid costs cents of a dollar and a whole auction does not exceed a few dimes. For assets of high unit value, which is the case of tokenised receivables and real estate, the cost of confidentiality is noise.

Whoever places a bid waits around nine seconds, and most of that is not the network: it is your own browser encrypting the value and generating the proof that it is well formed. The blockchain confirmations all sit near two and a half seconds, and the query to the decryption network near three.

The bottleneck is not where you would expect. It is neither the blockchain nor the decryption network: it is your device encrypting the bid.

In the paper: computational cost and latency, with the full tables (§5.2 and §5.3)

The whole path in one sentence: Vickrey rewards honesty, but demands secrecy; the public blockchain keeps no secrets; commit-reveal postpones secrecy instead of guaranteeing it; FHE computes without seeing; the top-2 pattern delivers the second price without having to exclude anyone explicitly; and at the end almost all the uncertainty about the bids is left, for cents of a dollar per participant.

None of this is hypothetical. The contract is deployed on a public network, with verified code, and you can run an auction from start to finish.