Leaderless auctions
Leaderless auctions are decentralized auctions with no auctioneers. They address the "last look" problem that can arise when one participant is allowed to act after all the other participants.
In a leaderless auction, all participants must commit to their bids at the same time. Any breach of this commitment will result in attributable fault. Bids are threshold-encrypted to avoid information leakage.
Auctions can be done by submitting the results to the blockchain, where they can be effectively verified through signature aggregation. For the purposes of this article, we will be using Ethereum.
This protocol is similar to the Byzantine fault-tolerant consensus protocol in that it assumes a predetermined set of participants in which more than two-thirds of the participants are honest. It also requires participants to be able to reliably deliver messages to each other for a fixed period of time (say, two seconds). Some honest parties may receive an error if the latter assumption is violated, such as network partitioning, however, assuming that such breaches are rare, we can design failure penalties so that the impact of this issue is minimized.
This design does not solve several problems. In particular, participants can still submit their bids later than others because of their lower latency. In addition, in this version of the protocol, bids from the public are unencrypted for the sake of simplicity. This means that dishonest auction participants have the last touch to the public that trusts them.
motivation
Auctions are ubiquitous in cryptocurrency. Time trial games, final checks, and short-term reviews are starting to emerge, and this protocol is at least meant to resist some of them.
We are exploring how to integrate this into Angstrom's top block and batch auction, which uses a separate consensus mechanism to secure MEV by executing orders at a common price.
Variations of this auction may work with other settings, such as:
• Include PBS auctions in L1s like Ethereum, as proposed by Mike Neuder and Justin Drake
• Enforce the fairness of order stream auctions such as UniswapX or MEV-share
• Enhanced on-chain bulk auctions, as discussed by dYdX
• Decentralized sequencers into L2 like Optimism
Previous work
There's been a lot of great work on crypto auctions lately. For example, see:
• 链上拍卖中的审查阻力(2023)，作者：Elijah Fox, Mallesh M. Pai和Max Resnick
• 通过区块链进行可信、最优的拍卖(2023)，作者：Tarun Chitra, Matheus V. X. Ferreira和Kshitij Kulkarni
• A New Architecture for Mitigating MEV (2023) by dYdX
• Multiplicity (2023) by Duality
• 蝉 (2024) 作者:Noemi Glaeser、István András Seres、Loránd Eötvös、Michael Zhu 和 Joseph Bonneau
While much of this work addresses the issue of censorship – the ability of a leader to exclude trades or bids from others – we have yet to find any work that directly addresses the issue of the last censorship – the ability of proposers to insert or cancel their own bids long after other participants.
issue
background
Zed wants to auction one ETH every 12 seconds. He formed a committee of his friends Alice, Bob, Charlie, and Dan to manage the auction. These participants will collect bids from the public, and together, they will decide on the highest bid they have ever seen. Zed trusts the whole team, but he thinks at most one of them may be dishonest.
First attempt
One possibility is to use single-block auctions in a decentralized consensus protocol like Tendermint. Each participant will collect bids from the public and submit the highest bid for inclusion in the block. However, Tendermint features a block proposer who has full control over the content of a block. This means that a dishonest bidder can simply review other people's bids and win the auction with a bid of 0.
To solve this problem, we can change the duration of each auction from one block to two. Then, two different proposers would come up with a block one after the other that contained the highest bid they had ever seen. The final winner of the auction will be the highest bidder of the two blocks. Because at most one proposer is dishonest, at least one of these blocks contains honest bids. That's a big step forward!
Last Look question
However, imagine supposing that a dishonest proposer, like Bob, is the proposer of the second block.
The first proposer, Alice, submitted a $10,000 ETH bid in her first block. Bob now has a few seconds to decide what he wants to do. He looked at the price of Ether and saw that it had just soared to $11,000. He bid $10,001 himself and won the auction, netting $999.
As a dishonest participant, Bob will do so whenever it is profitable – that is, as long as the price of Ether is greater than the current winning bid price in the Alice block. This means that anyone who sends a bid to Alice will only get a deal if the current price of Ether is less than or equal to their bid – in other words, if the trade is unprofitable for them. Even if Bob can't see the bids of other bidders, he still has an information advantage because he is able to submit his own bids a few seconds later than others.
If they are rational and know what is happening, when Bob is the second proposer, other bidders other than Bob will stop bidding. At the margin, this will depress the overall bid, resulting in less money for Zed.
This is known as the "last look" problem, and it is a form of MEV. Because it's so similar to other currently tolerable forms of MEV, even "honest" players like Alice, Charlie, and Dan may be tempted enough to get involved, putting Zed and any honest bidders at a disadvantage.
We want to stop that from happening.
solution
Summary of the problem
The protocol is specifically designed to solve the "last look" problem in decentralized auctions – where one participant can meaningfully bid later than others or cancel their bids at no cost to them, giving them an unfair advantage.
In particular, we want to make sure that all bids are submitted at a given wall clock time (e.g., 12:00 PM), regardless of who submits them.
Most blockchain consensus protocols have a leader or proposer proposing a block for other participants to agree on. Because all the other participants have to send their offers to the leader in a timely manner so that the leader can include them, the leader has more time to decide on their own offer, giving them one last free chance.
Protocol Overview
The leaderless auction comes up with the auction results in three rounds, and in the fourth round, an easy-to-verifyable aggregate signature is created to verify them. Anyone can submit these signature results to Ethereum to complete the auction.
The protocol also specifies a set of failure conditions that are easy to demonstrate. Anyone can submit a false proof at any time, and penalties will be imposed on the responsible participant.
performance
As we'll demonstrate below, this protocol solves the last look problem by satisfying the following two attributes:
1. No latecomers: No participants can place bids after the wall clock time at the end of the first round.
2. There is no free option: Any participant who retains an option that cancels after the first round must pay for the option in advance. Effective penalties should make the practice economically unviable.
It is important to note that some participants may have a lower delay than others and are therefore able to act later than others in the first round.
hypothesis
We assume that out of 3f+1 participants, 2f+1 is "honest" (the same threshold as required by the Byzantine fault-tolerant consensus protocol).
Our synchronization assumption is that all honest participants are able to send messages to each other, and these messages are guaranteed to arrive at a certain fixed amount of time, say 1 second. This assumption doesn't need to be held for the sake of overall security or liveness (to ensure that we don't produce conflicting auction results, and that the auction will eventually happen), as we rely on Ethereum for these properties. We will discuss below what happens when this assumption is violated.
We also assume that participants have synchronized clocks, just like in Ethereum.
auction
Round 1 - Send bids
Each participant sends a signature bid to the other participants.
These bids are threshold encrypted, meaning they are encrypted with a public key that can be decrypted by a collection of any F+1 or more participants (this will happen in Round 3). This means that no participant will be able to see the value of any other participant's bid before submitting their own bid, and therefore cannot leverage the knowledge of that offer. There are several ways to achieve this encryption, but the details are beyond the scope of this article - see example vetKeys.
Honest participants must submit the highest bid they have received from the public. However, since bids from the public are not encrypted in this design, a dishonest participant can choose to bid a fraction higher than the one they received from the public. The public can solve this problem by sending their bids to only one participant they trust. Cryptographic solutions are feasible but add complexity.
Round 2 - Send the bid set
Each participant passes on a signed set of all crypto bids they received in the first round (a "bid set"), including their own, to all other participants. All participants now have a "bid view", or a set of bid sets received from other participants.
Honest participants will only include another participant's bid in their bid set when they arrive before the end of the first round of bids, determined by the participant's synchronous clock. Therefore, if a bid is included in the bid set of honest participants, it must be sent at the end of the first round. Since there are a maximum of f dishonest participants, if a bid appears in an F+1 or more bid set, at least one of them comes from an honest participant, and the bid must be issued at the end of the first round.
Any honest participant can use this information to solve the auction problem. However, the protocol has no way of knowing which participants are honest. So, we need another round.
Round 3 - Send bid view and threshold decryption information
Each participant will tell all other participants about all the bid sets they received in the second round (their "bid view"), including their own bid set.
In addition to their bid views, they also send the decryption information they use in the threshold encryption scheme discussed above. Any set of F+1 where it is enough to decrypt all encrypted bids.
This is the most expensive step in terms of bandwidth: each participant must send O(n) bid sets containing O(n) bids to O(n) participants, for a total bandwidth of O(n^3) in the worst-case scenario. However, everyone should get the same actual bid from the other participants (in the absence of costly ambiguous errors, which will be discussed below), and the presence or absence in a given set or the bid is just a single bit. Also, if everyone is honest, and the network is functioning properly, then all participants should own each bid in their bid set, and each participant should own the bid set of other participants. So, if a participant only sends a message indicating which bids or sets of bids they are missing, then ideally they only need to send one ("everything is here") or a few bits ("set 3 lost bid 13, everything else is fine").
At this point, each participant should have a 2f+1 bid view from an honest participant and be able to decrypt it. If there are F+1 of these people, they can prove that they have at least one bid view of an honest participant, which is enough to solve the auction problem.
Theoretically, the protocol could end here, and any participant could submit an F+1 bid view to the blockchain for finalization. However, due to spatial complexity and the cost of validation, it is impractical to submit a 2f+1 bid view to Ethereum and validate it (perhaps more feasible on a custom chain).
Therefore, we need to conduct another round so that participants can verify the auction results in a way that is easy to verify on-chain.
Round 4 - Verify the bid view
To guarantee the performance we want, we want to easily verify that the winning bid for the auction is the winning bid for at least one valid bid view, and that it is greater than or equal to the winning bid for at least one honest participant view. Round 4 is designed to do just that.
Each participant checks all of their decrypted bid views. A bid is _valid _in valid in the bid view if it exists in at least F+1 bid sets that make up the bid set. The winning bid for a view is the highest valid bid in that view.
If the bid in a given bid view is greater than or equal to the bid in the participant's own bid view, the participant nomins the bid.
Each participant builds a threshold signature for each bid they nominate and passes a collection of all those bids and signatures to other participants. Note that this is only O(n^2) in spatial complexity (up to one signature per view) and bandwidth complexity. In fact, if all participants are honest and there are no network difficulties, the same bid will win every bid view, so each participant will only nominate a single bid.
settlement
Any bid with at least F+1 participants signed in this way is confirmed. Note that in some cases, two or more different bids may be confirmed (although this means that at least one participant loses in the first round and therefore does not receive the free option).
Any confirmed bid can be submitted to the Ethereum blockchain, where it can be verified with a simple signature verification. Submitters may receive a small payment from the protocol to reimburse them for their gas fees. Only one confirmed bid is accepted on Ethereum, and if there are multiple confirmed bids, all participants are allowed to reach consensus on the winning bid.
Ethereum block proposers may review auctions without including them in the block. This may even happen several blocks in a row. In this case, the participant who submitted the auction results for the current block must also submit the auction results for all missing blocks. We'll discuss below how this changes the error penalty.
mistake
foundation
Anyone can submit a false proof asynchronously as long as there is evidence, which is likely to result in all or part of the offending participant's stake being cut. Participants who report false proofs may receive a portion of the staked that was cut as a reward for reporting.
Ambiguity errors occur when participants have conflicting bids in different bid sets or different bid sets in different bid views. Because this ambiguity is either deliberate, or at least due to client issues rather than network issues, the penalties for it can be quite severe, including across-the-board cuts.
An absence error occurs when a participant's bid is not present in some of the F+1 bid set sets. This could mean that the participant was dishonest, trying to withdraw from the bid they made in the first round, or, hopefully, that the participant was honest and that the network was partitioned.
The penalty for an absent error should be set higher than the option to be able to cancel the bid. This needs to be balanced against the true frequency of network failures and is ultimately a quantitative problem. In the worst-case scenario, there is an escalating punishment system that limits the frequency of repeat offenses and keeps this behavior to a minimum. Any system using this protocol can monitor the frequency of these types of failures relative to verified network failures and adjust penalties accordingly.
Review the auction for deficiencies
As we'll discuss further below, auction participants can retain the option to cancel their bids in the next round by making a mistake in the first round.
Any participant who does so can create more optionality for themselves by bribing the Ethereum block proposer to review the auction results of the Ethereum block auction, possibly several times in a row, and then finally submit a "settlement" as described above. In order to maintain the "no free choice" nature, we increase the error penalty linearly each time a given auction is reviewed, so that the original wrongdoer has to pay for the option value of each missed block.
If an honest participant inadvertently makes a mistake due to network issues, someone can use these ever-increasing penalties to sabotage them, but the saboteur must pay to review the block.
Mitigate unexpected breakdowns
If any participant is missing f+1 or more bids in the bid set, we know by assumption that they are missing at least one honest participant's bid, because at most f participants are dishonest. Therefore, in order to calculate the absence error, we can ignore the bid set of this participant, because they are either dishonest or network partitioning has occurred. This should reduce the number of failures caused by the primary network partition.
prove
i. No Latecomers: Any participant must send their bid to at least one honest participant in Round 1 so that it is valid in any bid view for a chance to win
Let's say that in the first round, some participants did not send their bids to any honest participants. Because there are 2f+1 honest participants, this bid appears at most in the second round in (3f+1)-(2f+1)=f bid sets, which is not enough to make it valid in any bid view.
If it is invalid in any bid view, it cannot be the winning bidder in any bid view, and no honest participant will nominate it. Since an F+1 participant must nominate a bid for it to win the auction, at least one of these participants must be honest and this bid cannot be won.
ii. In the absence of network partitions, participants who send bids to all participants in the first round do not incur errors
Let's say the honest participant is Alice.
She sends her bid to all 3f+1 participants in the first round. Because 2f+1 of them are honest, each honest participant will send their own bids to other honest participants. This means that every honest participant will see her bid in the set of bids they receive, including their own.
Since there are up to 3f+1 bid sets, her bids will be absent in the maximum (3f+1)-(2f+1)=f bid sets, so no errors will be generated.
iii. In the absence of network partitioning, if a participant sends a bid to an honest participant on F+1 or more in Round 1, that participant will win the auction, provided that this is the highest bid submitted to any honest participant in Round 1
Let's say Alice sends her bid to an honest f+1 participant in round 1. These honest participants will then include her bid in their bid set and send it to other participants. This means that each of the 2f+1 honest participants sees Alice's bid in the f+1 bid set and therefore considers her bid to be valid in their bid view.
According to the assumptions, Alice's bid is the highest among all honest participants in Round 1. So her bid is a winner in the eyes of every honest participant, and every honest participant will nominate her. In addition, according to proof (i) above, no higher bid is valid in any bid view, so no honest participant will nominate it. This means that Alice's bid is the only one to receive at least an F+1 nomination and must win the auction.
Note that if two such bidders are tied with the highest bid, there is a marginal case. We can judge based on the randomness of the threshold decryption.
iv. Any participant must send their bids to at least F+1 honest participants in Round 1 to avoid errors
Let's say a participant sends his bid to a k among the honest participants in Round 1
This bid will then appear in the set of k bids sent by honest participants.
Each honest participant will receive 2f+1 bid sets from other honest participants (including themselves), of which only k contain the bids in question, so the 2f+1-k>=2f+1-f=f+1 bid set will not contain the bids in question, which is enough to produce a failure.
Note that even if the network is split, if an honest participant ensures that all other participants have received their bid set, and resends the bid set until an acknowledgment is received, a failure will occur once the network is restored.
v. There is no free option
Through (iii), any participant who places a bid to an F+1 or more honest participant in Round 1 will win the auction if it is the highest bid made to any honest participant in Round 1, regardless of what they later did. In clause (iv), any participant who sends a bid to less than F+1 participants in Round 1 will be judged in error (and therefore penalized). Therefore, anyone who wishes to retain the right to cancel will have to pay for it.
conclusion
Decentralized auctions have only recently begun to gain widespread use, creating a number of new problems. This article is aimed at a problem that we haven't seen solved elsewhere. We hope and expect that more and better solutions will emerge – ideally those that are simpler, have fewer rounds, or have fewer assumptions about issues like synchronization or the number of honest participants.
While this design doesn't solve all the problems, it does solve some of the common "last look" problems inherent in decentralized auctions. We hope that it can be of some use in itself, to help others solve similar problems, or even improve or remix into something better.