On Auctions, Privacy, and Blockchains

This article provides a gentle introduction to why auctions are useful, why bid privacy matters in cases like token auctions, and what bid privacy means. It then describes the design space of private auctions on blockchains. Follow-on articles will dive into the design tradeoffs of specific implementations in more detail. At Axis, we're developing new auction systems that leverage these concepts.

Why auctions?

Humans are always buying and selling things. In modern society, most people do more buying than selling. However, most assets have some useful lifespan to each person, and they end up on the selling side every once in a while. When selling an item, the biggest challenge is deciding how much you should sell it for. If there is a market where other people constantly buy and sell that item in large volumes, i.e. a liquid market, then it's fairly easy. The most sensical thing would be to sell it for the going price on that market. However, most things don't have liquid markets. So what do you do?

Imagine you're selling a couch you bought three years ago for $300. If the same couch can be bought new for $300, that is probably the ceiling. However, it likely has some wear and tear on it. So, you list it on a second hand site for $200 since it still has, in your opinion, a lot of good years ahead. No one bites for 10 days. It turns out your smelly old couch might be not worth $200. Now, wanting to sell it, you lower the price by $10 every day until someone buys it for $100. You underestimated the demand for the item initially and only sold it by lowering the price until someone finally bought it. Without realizing it, you just conducted an auction (specifically a Dutch Auction).

It turns out that people have trouble valuing things at any given moment. We often need auctions to find a clearing price between a buyer and a seller of an item.

Going once, going twice...Sold!

When most people think of an auction, they envision someone standing on a stage soliciting bids from the crowd by hypnotizing them with an inhuman, vocal drumroll. Bidders shout out their prices until the auctioneer slams a hammer down to declare the winner. They're exciting! You're competing! The person who wants it bad enough and has enough money will take the item home.

While this sounds like something scripted for TV, different versions of it play out daily around the world in certain industries. Car auctions function as a secondary market for dealers to move in and out of inventory. Ebay popularized selling used consumer products online with auctions. Famous auction houses like Sotheby's sell fine art, luxury goods, and rare historical items. The U.S. Treasury holds regular auctions to sell newly minted bonds to raise money for the government. Auctions are everywhere.

The popular auction format that I described above is called an English Auction, or more technically an "Open Outcry Ascending Price Dynamic" auction. With all of those adjectives stacked next to each other, the obvious conclusion is that there must be other a bunch of other auction types, and there are. As an example, you may be familiar with a Silent auction where bidders walk around an auction exhibit and write their bids down for an item. A Silent auction may use "open" bids, like the English auction, where each bidder has to bid higher than the last person to place a bid. However, it may also use "sealed" bids where the bidder folds up their bid and puts it in a hat and not knowing the current high price. After the auction ends, an auctioneer opens up each bid and announces the winner. These two formats may lead to very different outcomes, and it's not immediately obvious which will fetch a higher price for the item.

Auction theory is a part of the field of Economics that analyzes and proposes new auction types that achieve optimal behavior from sellers and bidders for specific situations. In the last ~75 years, many auctions have been formalized with academic rigor, but their history goes back to ancient times. I'm not going to get too bogged down in formalities here, but there are a couple key concepts we will consider from the research that's been done.

Getting Bidders to Behave: No Peeking!

Between 2014 and 2015, the U.S. Marshals Service auctioned off about 179,000 bitcoin that were seized following the shutdown of the Silk Road marketplace. That sentence seems innocuous at first, but it's strange to think that bitcoin needed to be auctioned in the first place. Why not just sell it on an exchange? More recent Government sales have used a combination of exchanges and auctions. At the time, there wasn't a very liquid market for bitcoin, and the value of that amount of bitcoin was too large for exchanges to handle (even at 100x less than it is now). This sets up an interesting dynamic. You have a commodity asset with a current market price, but a price at which the auctioned amount could not be liquidated at via existing liquidity. Therefore, the value of the auctioned amount cannot be realized until some point in the future when there is additional liquidity. Due to the volatile nature of bitcoin against a currency like the U.S. dollar, this creates uncertainty around the actual value of the auctioned amount. At any point in the future, the value will be the same for all participants. In auction theory, this is called a "common value" auction, since the item has a common value to all participants, but the exact value is unknown at the time of the auction.

Since the participants do not know the exact value of the item, they have to develop a private estimate of what they think it will be worth in order to decide what they will bid. Each auction was for a large amount of bitcoin that was divided into multiple lots of ~3,000 bitcoin each. Multiple bidders can therefore win a subset of the auction. They have the current market price as a reference, but they need to consider what they believe the price will be in the future. Additionally, bitcoin was hard to buy in large quantities in the U.S. at the time, so investors may have viewed the auction as a way to acquire a large amount without pushing the market price up too much (and therefore paying more).

Now, consider two auction formats:

All bidders go in a room. They have 30 minutes. They each get a whiteboard and must write their bid as a combination of price per lot and number of lots to acquire on the whiteboard where everyone else can see it. They can change their bid as many times as they want until the time runs out. They also do not have to write anything on their board until they see fit.
Bidders submit a sealed envelope of their price per lot and number of lots they are bidding for to an auctioneer. They have 30 minutes. They can submit their bids at any time during this period.

In both cases, the winner is determined at the end of the auction period by selecting the X highest lot bids where X is the number of lots offered. How would these two formats change the behavior of the bidders?

For starters, the formats are identical except for the visibility of the bids. Both are Multiunit First Price Batch auctions.

Multiunit - There are multiple items (or groups of items) being auctioned at the same time. This doesn't affect the analysis here, but it's important later on.
First Price - The bidder with the highest price wins and pays the price they bid. The winning bidder in these cases often suffers from "Winner's curse". Winner's curse is when the winner lowers their value estimate after realizing they bid more than everyone else and believe they paid too much. A Second Price (or Vickrey) auction can alleviate this and motivate participants to bid their true value, but it's not important for this example.
Batch - Bids are accepted over a period of time and then all settled at the conclusion of the auction. Most auctions are this format. A counterexample is a Dutch auction since the first bidder (which will be the highest bid) wins the offered lot instantly.

The first format is Open Bid, where all bids are open and visible to all other participants. Let's consider the potential behavior of two participants (a low and a high bidder) in an Open Bid format based on their private valuations of the items. At the beginning, none of the participants know which group they're in because they don't know anything about the private values of other participants. Consider these scenarios with only 2 bidders:

The low bidder places their bid first. The high bidder sees it and bids a value slightly higher than that instead of their original value. High bidder wins at a value lower than they were willing to bid.
High bidder places their bid first. Low bidder thinks the bid is too high and abstains. High bidder wins and pays the amount they were willing to bid.

Expanding to more bidders would yield similar results, the original high bidder winning at a price slightly higher than the next marginal bidder some of the time, reducing the value received by the seller.

The second format is Sealed Bid, where bids are concealed from other participants. Depending on the situation, bids may be revealed at the end or not. It is common for only the winning bid to be revealed. Regardless, the high bidder would win the auction every time if they bid at or close to their estimated value without seeing the other participants lower bids, increasing the average proceeds received by the seller.

Therefore, in common value auction situations, sealed bid auctions prevent bidders from changing their behavior (i.e. bidding less) since they cannot see the bids from the other participants.

The USMS got this right and used a sealed bid auction to sell their seized bitcoin. They also did not reveal the winning bids after the fact so as to not influence future auctions.

Cross your heart and hope to die

The difference between a sealed bid and an open bid auction sounds straightforward. In one case, you keep the bids a secret. In the other, you don't. The devil is in the details though.

When someone tells you a secret, what questions do you ask to establish your ground rules for keeping it a secret?

Let's say you're throwing a surprise birthday party for a friend. Obviously, you don't want to tell the friend about the party, but who else is allowed to know? It's likely that their parents and your other mutual friends will be involved too. When is the party? The friend will find out when it happens so the secret only has to be kept until then.

On the other end of the spectrum, imagine you're the commander of a nuclear submarine on a deterrence patrol. It's important that your location at any time remains a secret to ensure the safety of the crew and success of the mission. Due to the security implications, only very trusted individuals with a "need to know" should have this information (e.g. the admiral commanding yours and other subs). What if there is an inadvertent leak of your location from a week ago? It's not as bad as if the current position is leaked, but it still provides some information about your whereabouts since observers can make assumptions based on the distance you can travel in that time period. What if your patrol route is leaked months after you have returned to shore? You aren't in the water anymore and are out of danger. However, it's likely that observers make assumptions about current or future patrols based on this information. Therefore, it's important the secret is kept even after the patrol is over to not provide information that can be used in the future.

Auctions probably aren't that big of a deal, but they're somewhere between these two extremes. In a sealed bid auction, it's important that each bidder's submission is kept secret from other existing and potential bidders. Potential bidders is a broad group. If we assume that rules are in place to prevent insider dealing, then this is everyone except the seller and auction runner. If not, then it literally means everyone. How long does the secret need to be kept? We know that it must be secret until the auction ends, but what about afterwards? In an ideal world, no bid information would ever be leaked and the winners would pay for the lots they are awarded privately. However, as I'll explain in the next section, if you want to do auctions on a blockchain, we have to bend a little bit.

Hiding in plain sight

Programmable blockchains are a modern marvel. They provide a decentralized, neutral settlement platform for financial transactions with built-in payment rails. This makes them a great platform for building auctions since the most challenging parts of the infrastructure are provided out of the box. However, they are still in active development and certain features aren't yet available.

Current public blockchains enable anonymity, but not privacy. All on-chain data and, to an extent, all data sent to the network is public. You don't necessarily care who you're bidding against so being anonymous is fine. However, as we saw before, you should care about your auction bids being private. This is a problem if you want to do sealed bid auctions. If all data on the chain is public, how can you hide bid data from other participants?

Goals

The key juxtaposition of this article so far is that sealed bid auctions are good, but blockchains make them hard. However, there are a few more things that must be considered to build a suitable, blockchain-based auction system. Many of these goals are at odds with each other.

Bid Privacy

Ideally, we would keep all bids secret during and after the auction. However, we may need to bend here depending on the other design goals. At a minimum, all bids must be kept secret until the auction concludes. There are tradeoffs we'll consider between privacy and trust assumptions on the platform.

Auction Fairness

An auction system must assure users of inclusion and fair treatment of their bids to gain credibility. Specifically, it needs to provide guarantees around:

Completeness - All bids that are submitted are evaluated
Accuracy - The evaluation of bids is performed correctly

Depending on the design of the system, these properties may be inherent or difficult to achieve. There is typically a tradeoff between user experience and these guarantees.

Decentralization

A key improvement of public blockchains over traditional financial systems is that they are decentralized and reduce the trust required in third-parties. In building an auction system on a blockchain, it is desirable to maintain this property so that the system is credibly neutral and resilient.

User Experience (UX)

It's possible to gain early adopters with a sub-par user experience, but it's hard to scale that way. In the context of blockchains, user experience typically comes down to the number of required actions for the user and the cost of those actions in transaction fees. Potential designs may have different UX for buyers and sellers, which is important to keep in mind.

Design Space

Now that we've establish the goals. Let's consider the different ways a system could be designed to achieve them. Most of the design variations are based on whether the

There are three main steps to any batch auction:

Bid submission - Users submit bids over an alloted time period
Evaluation - The submitted bids are evaluated using the auction logic and winners are determined
Settlement - The proceeds of the auction are distributed to the winners and the auction is closed

There are five main designs of auctions that could be built based on where the bids are submitted, where the bid evaluation logic is performed, and where the settlement occurs. I will refer to these as "local", for on-chain, and "external", for off-chain, to avoid using similar hyphenated words. As you'll see, each has tradeoffs between decentralization, user experience, level of privacy, and efficiency (i.e. gas costs).

On-chain Maxi: Local bid submission, evaluation, and settlement

Fully on-chain auction, similar to Gnosis auction, but with encryption. Since you cannot pre-sort the bids, it requires an intermediate step to decrypt and sort all submitted bids before settlement to avoid issues with the gas limit. Gas concerns are eased if you requiring bidders to claim their payout and/or refund instead of trying to distribute it all at once. The risk of DoS attacks is decreased by requiring bid deposits, but this leaks some information. This solution natively guarantees both "completeness" and "accuracy" of the bids. Since bids are evaluated and settled on-chain, all bid data is leaked after the auction concludes. Fully homomorphic encryption (FHE) may allow sorting bids on submission and possibly evaluating them without revealing the data, but practical usage on major chains isn't yet supported.

On-chain with Web3 Function: Local submission, external evaluation, and local settlement

Bids are submitted on-chain (encrypted). Once the auction ends, an external party can decrypt the bid data, perform bid evaluation off-chain, and submit the winning bids with a validity proof of the evaluation. This version natively adheres to the "completness" property, but requires trusting the "accuracy" of the submitted evaluation. A validity proof can provide this in a decentralized way. This may be a workable solution if a ZK proof could be constructed correctly to verify the off-chain evaluation. However, proving times and the sizes are the required circuits limit practical usage currently. In this case, only winning bids are guaranteed to leak following the auction, but all bids may be leaked depending on how the bids are decrypted externally.

Gasless Bids V1: External bid submission, local evaluation and settlement

Bids are collected off-chain, filtered for bids that aren't valid (e.g. below min price or too small), and sorted. Then, they are submitted on-chain, where the auction price logic is performed to determine the winners. This version natively adheres to the "accuracy" guarantee through on-chain evaluation of bids, but requires trusting the "completeness" property of the bids that are submitted for evaluation. This is difficult to do in a decentralized way. Since bids are evaluated and settled on-chain, all bid data is leaked after the auction concludes. This version is not practical to implement due to the need to submit all raw bid data on-chain and compute against it.

Gasless Bids V2: External bid submission and evaluation, local settlement

Bids are collected off-chain and the settlement algorithm is performed to determine the winning bids. The winning bids are submitted on-chain for settlement of payments. This would have the best UX and is most gas efficient of the locally settled versions, but is the least decentralized. It requires trusting both the "completeness" and "accuracy" of the submitted evaluation. Only winning bids are leaked since they are provided on-chain for settlement. Similar to the Web3 Function version, a ZK validity proofs may be able to verify the completeness and accuracy of the submitted winning bids, but has the same issues. This version is more feasible than Gasless Bids V1 because a Merkle Tree can be used to provide the winning bids, similar to the Web3 Function version.

Validium: External bid submission, evaluation, and settlement

In order to perform all of these actions off-chain without a complete trust assumption on the operator, we can use a Validium. Validiums are a scaling solution similar to ZK rollups that verify transactions on base layer with validity proofs, but doesn't store transaction data onto the base layer. This makes them more efficient, but more trusted. Users would bridge funds to the Validium service from the main blockchain. All auction logic would happen off-chain and validity proofs are generated to update user balances. Users submit these validity proofs to withdraw their assets from the validium. This solution requires trusting the secrecy of the external services and data availability of the provider to generate validity proofs.

Conclusion

The intersection of auctions and blockchains shows great promise for selling illiquid assets. However, bid privacy is an important and challenging problem to solve. I'm actively working on this and other auction-related problems at Axis where we're building a modular auction platform. Stay tuned!