Research Update: The Case for Candle Auctions

By Samuel Häfner, Web3 Foundation Research Scientist

Parachain auctions are a central feature of both Kusama and Polkadot. Their outcome determines who gets which parachain slots and the amount of tokens locked. For the health of the ecosystem, it is important that the scarce slots are allocated to those projects that can make most use of them. It is well known that auctions in general are an excellent means of achieving this goal, because — other than, e.g., bilateral negotiations — they force the teams to be upfront about their valuation for the slot on auction.[1]

Both Kusama and Polkadot employ a candle auction format to allocate parachain slots. There are many good resources that explain how this mechanism works in practice.[2] Nevertheless, the candle format is quite an unusual way to run an auction. Also, auctions of the size and scope of the parachain auctions do not happen on the blockchain every day. This post will explore the following fundamental questions:

1. Why are auctions better run on-chain than off-chain?
2. What is the particular reason for using a candle auction?

To answer these questions, we will first delve into the rather tragic story of Gian Vincenzo Pinelli (1535 - 1601), a Paduan scholar, avid collector, and mentor to Galileo Galilei. The sale of his legacy was done in a candle auction, which ended in disaster. Second, we argue that the reasons for this failure are exactly the reasons why running auctions on the blockchain in general is a good idea. Third, we turn to the question of why a candle auction is the most suitable form for blockchain auctions. Here, we briefly look into recent research done at Web3 Foundation.

Pinelli’s legacy

Pinelli, who was of noble Neapolitan descent, collected pretty much everything of scholarly interest, ranging from fossils to coins, from minerals to historical portraits, and from astronomical instruments to maps.[3] The most famous part of his legacy, though, was his immense library. Besides numerous books, it consisted of over 700 manuscripts, among which were many rarities, such as illustrated fragments of Homer from the fourth century and a Dante with miniatures from 1355.

After his death, Pinelli’s library was packed and shipped to his heir in Naples. The library consisted of some 130 boxes and required three ships to transport. One of the ships was lost to pirates and soon after the remaining parts of the library reached its destination, Pinelli’s heir died. After years of back and forth, during which more of the books were lost due to negligence, the library was auctioned off on behalf of the widow of Pinelli’s heir in 1608.

As was customary at the time, the format of the auction was that of a candle auction: the auctioneer lit a candle in sight of the interested bidders, who then called out their bids until the candle went out. The highest bidder at the moment the candle went out won the object and paid his bid. The Pinelli auction was one of the first candle auctions on which a detailed historical account exists. Candle auctions were used as early as in Medieval France (records date back at least to 1368), mostly to solve inheritance disputes. Other records include ship and fur auctions in England.

Candle auctions were in regular use only for a relatively short period of time. (They were eventually replaced by auctions whose end was announced by the auctioneer with three knocks from a baton, much as we know them today.) The reason for their disappearance was that they were quite problematic to run. Specifically, most of the candle auctions at the time faced the following three problems.

First, people soon started to engage in what is known today as sniping; i.e., they:

“maliciously [drew] out the bidding until the candle [was] much burned down, with result that inheritances [were] hardly ever sold at their real value.”[4]

Second, there were repeated attempts to manipulate the ending time, mainly by coughing so hard that the candle went out.

And third, it was often very difficult to accurately determine the winner once the candle went out, which could lead to heated disputes. For example, Samuel Pepys wrote in his famous diaries upon observing a candle auction in England that he was appalled to see:

“when the candle is going out, how they bawl and dispute afterwards who bid the most first.”[5]

The sale of Pinelli’s library did not quite go as planned for an additional, fourth reason: because the widow was unhappy with the price the auction achieved, she refused to hand over some of the books after the auction. The buyer — a lawyer acting on behalf of Cardinal Federico Boromeo, who founded the famous Biblioteca Ambrosiana in Milan — was on the lookout for the Pinelli library for years. For fear of further delay due to a prolonged legal battle, he accepted a new, less favorable deal and eventually shipped the books to Milan.

The advantages of blockchain technology

So, early candle auctions in general and the sale of Pinelli’s library, in particular, were a disaster. In what sense could blockchain technology have helped?

First, the behavior of the widow after the sale points to a major problem of any auction that is held off-chain: a lack of commitment power by the auctioneer. Even with the best legal system in place, the seller can at least delay the transaction of the goods on sale when having a sudden change of mind after the auction. Of course, if the bidders in the auction anticipate such behavior, then they will not bid as seriously as they would otherwise, which in turn yields even lower revenues. In contrast, if both the auction and the object on sale are on the blockchain, a smart contract can easily solve this problem, triggering the transfer of both the bid and the object once the winning bidder is determined.

Next, turn to the candle auction more specifically and consider the problem of sniping. The reason for using a candle is to make the ending time of the auction stochastic (random): no one should be able to tell when the auction is over, which in turn should encourage early bidding. This sounds like a nice idea, but the probability distribution that the candle provided had the most mass around the time when the candle was almost burnt down. In other words, the probability of the auction ending early was practically zero. No wonder, then, that everyone waited until the candle was almost out (which you could tell when the flame started to flicker).

By contrast, modern computers allow for ending time distributions (possible ending times) that are more spread out, increasing the probability of an auction ending early. The potential for early ending times implies that sniping is indeed not an issue anymore, as the bidders are under pressure to bid seriously from the start.

Nevertheless, modern computers alone cannot solve the second problem of the candle auction: the manipulability of the ending time. In particular, the auctioneer acting on behalf of the seller still has to convince the bidders that the announced ending is indeed the one picked by the random number generator. After all, because the bids are increasing over time, the seller always prefers a later rather than an earlier ending time. Luckily, recent advances in cryptography allow for randomness that is immutable and that can be verified by everyone in the network.[6] So in a blockchain candle auction, the bidders cannot just cough out the candle nor can the auctioneer lie about the ending time.

The third issue with candle auctions was that their execution was often quite hectic, leading to quarrels around who bid when and what amount. In modern auctions (both on- and offline), the exact order of bids is recorded, which should reduce these kinds of disputes. Nevertheless, there is still an issue with the secret manipulation of such records. Especially in complex online auctions, accusations of fraud are made frequently.[7] So, participation in such auctions is always based on a fair amount of trust in the auctioneer. Of course, this contrasts with blockchain auctions: if bids are recorded on chain, then everyone can verify the amount and timing of all the bids and no trust is required at all.

The case for the candle auction

Now that we have an idea how blockchain implementations of candle auctions are an improvement over earlier implementations, the question remains: why use a candle auction in the first place?

Recent research at Web3 Foundation [cf. Häfner and Stewart, 2021] suggests that the candle auction helps with two major issues typically faced by blockchain-based auctions: front-running and the presence of smart contracts among bidders.

Front-running opportunities (acting before others based on privileged information or insider knowledge) naturally emerge on blockchains because upcoming transactions become known among the network participants before they are included in new blocks.[8] For blockchain implementations of auctions, this means that some bidders can see and react to other bidders’ bids before they come into effect; i.e., before they are recorded on the chain and are thus taken into account by the auction mechanism.

For example, in first-price auctions (auctions where the winning bidder pays the highest bid) this gives tech-savvy bidders the possibility to outbid other bidders as they please. But then, the worry is that the presence of front-running makes participation very unattractive for some bidders, depresses overall bids, and thus reduces revenue in the auctions. Also, efficiency could be negatively affected because the good on sale goes to the most technically advanced bidder rather than to the bidder with the highest valuation.

As discussed in Web3 Foundation research by Jeff Burdges and Luca de Feo, cryptographic solutions to the front-running problem exist. Yet, they are either very computing intensive or require multiple actions by the bidders. Most importantly, though, cryptographic solutions do not work if bidding itself is executed by smart contracts. The reason is that smart contracts correspond to publicly visible code. Hence, their valuation for the good on sale and their strategy is publicly known before the auction. Given their widespread use, the presence of smart contracts among potential bidders is highly likely in any auction that is implemented on a blockchain.

Smart-contract bidders face a problem of transparency more generally. If a smart contract’s valuation is known in advance, then the auctioneer has an incentive to register his own (pseudonymous) bidder and to place so-called shill bids (i.e., bids that are intended to raise the price paid by the winner). This is particularly problematic in second-price auctions (i.e., auctions where the winning bidder pays the second-highest bid). In such auctions, it is optimal for everyone to bid truthfully and, hence, the auctioneer may go as far as to essentially defraud the smart contract of any positive utility from the auction (by submitting a bid just below the valuation of the smart contract). But smart contracts anticipating such behavior are likely to be hesitant to participate in the first place. This again leads to issues with efficiency, because the smart contracts deciding not to participate might very well have been the ones with the highest valuation.

In conclusion, front-running essentially precludes static auctions auctions (where the bidders simultaneously submit just one bid) and the transparency of smart contracts precludes auctions with a second-price payment rule (be it static or dynamic; i.e., with multiple rounds of bidding).

In Häfner and Stewart (2021), we show that the candle auction format is a good alternative. To make our point, we analyze a stylized candle auction between two bidders. In every round, the two bidders move sequentially in a fixed order. That is, one bidder (think of it as the less tech-savvy or the smart contract bidder) is systematically front-run by the other bidder. The bids must be increasing over time. The bidder holding the highest bid in the decisive round wins and pays her bid.

It turns out that with a suitably chosen ending time distribution it is optimal for the first bidder to place increasing bids over time and for the second bidder to just match these bids whenever her valuation for the good on sale is higher. So, the candle auction format provides some security against shill-bidding attacks: in order to raise the price above the equilibrium price, a shill-bidding auctioneer would have to submit a higher winning bid in an earlier round. But this comes at the cost of foregoing a payment by one of the bidders in case the auction happens to end in that exact period.

Also, a random ending time makes participation for the bidder being front-run more attractive than a fixed ending time. Under a fixed ending time it is optimal for both bidders to wait with bidding until the very last period. The random ending time, on the other hand, puts pressure on the bidders to bid earlier. In particular, because it is optimal for the front-running bidder to match the current highest bid whenever her valuation is higher, the bidder being front-run can explore the valuation of the front-running bidder by submitting increasing bids over time. This allows him to fine-tune his bids to his new information and thus obtain a higher expected utility.

Further, we show that a random ending time leads to higher winning bids than a fixed ending time, and thus higher revenue. This is by no means a foregone conclusion. Because the bidders submit increasing bids over time, having a random-closing rule means that sometimes the auctioneer also has to accept lower bids from earlier rounds. Nevertheless, the magic of the random ending time works to make the bidders bid higher overall, so that the winning bid is higher on average.

Last, we show that under a uniform ending time distribution and a large number of rounds, the outcome approaches that of a second-price auction. This means that the expected payment of the bidders and, hence, the expected revenue of the auctioneer are equal to those in the second-price auction. This is an important result, because the second-price auction is among the most optimal auctions — that is, among those auctions that yield the highest revenue. It also means — and this is probably the most important consequence for Polkadot — that the bidder with the highest valuation obtains the good. In other words, the outcome is efficient.

To sum up, the candle auction format is able to mitigate all three problems caused by front-running: (1) low utility for the disadvantaged bidder; (2) low revenue; (3) low efficiency. Also, as long as the number of rounds is finite, there is a cost to shill bidding (because, as said above, the auctioneer runs the risk of submitting a winning bid himself, in which case his revenue would be zero). Given these properties, we should expect the candle auction to become a standard mechanism for any auction run on the blockchain.
Postscript

In a final, last tragic twist of the Pinelli book sale, the transport of the books to Milan turned out to be more expensive than expected and, as a consequence, a large part of the books were disposed of on the way. Finally, only 35 boxes (out of the initial 130) made it to the Biblioteca Ambrosiana in Milan, where they are still today.

Learn More

Learn more about how Polkadot candle auctions work on the Polkadot Wiki, and visit the Web3 Foundation Research Portal for the latest publications from Web3 Foundation researchers.

References

Bulow, Jeremy, and Paul Klemperer. 1996. “Auctions Versus Negotiations.” The American Economic Review, 86(1), 180-194.

Burdges, Jeffrey, and Luca De Feo. 2020. “Delay Encryption.” Working Paper.

Daian, Philip, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2019. Flash Boys 2.0: Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges.

Häfner, Samuel, and Alistair Stewart. 2021.Blockchains, Front-Running, and Candle Auctions.” Working Paper.

Hobson, Anthony. 1971. “A Sale by Candle in 1608.” The Library 5 (3): 215-233.

Micali, Silvio, Michael Rabin, and Salil Vadhan. 1999. “Verifiable Random Functions.” 40th annual symposium on foundations of computer science (cat. No. 99CB37039), 120-130.

Pepys, Samuel. The Diary of Samuel Pepys.

1. See the seminal work by Bulow and Klemperer (1996). ↩︎

1. For a general overview, cf. the Polkadot wiki article. The Polkadot decoded talk by Shawn Tabrizi is also very informative. ↩︎

1. The accounts given in this and the next section largely follow Hobson (1971). ↩︎

1. Hobson (1971, 223). ↩︎

1. Pepys (1662, Wed. 3 September). ↩︎

1. See, e.g., Micali, Rabin, and Vadhan (1999). ↩︎