Original title: "Research Update: The Case of Candle Auctions"
Written by: Web3 Foundation
Translation: Polkadot Chinese platform
Parachain auctions are a core feature of Kusama and Polkadot. The results of the auction determine which projects can get parachain slots and how many tokens need to be locked. For the health of the ecosystem, it is important to allocate scarce slots to projects that can best utilize them. Auctions, as we all know, are often an excellent way to achieve this, because—in addition to bilateral negotiations—teams therefore need to pre-valuate the auction. [1]
Both Kusama and Polkadot use the Candle Auction to allocate parachain slots. There are many good examples of how this mechanism works in practice. [2] Nonetheless, the candle format "Candle Auction" is a very unusual auction format. Additionally, parachain auctions of the size and scope do not happen every day on a blockchain. This article will address the following fundamental questions:
Why do auctions work better on-chain than off-chain?
What is the particular reason for using Candle Auction?
pinelli's legacy
Then let's discuss why "Candle Auction" is the most suitable form of blockchain auction.
Before doing so, let's briefly review recent research done by the Web3 Foundation.
pinelli's legacy
Pinelli, of Neapolitan aristocratic blood, assembled almost every academically relevant collection, from fossils to coins, from minerals to historical portraits, from astronomical instruments to maps. [3] However, the most famous part of his legacy is his vast library. In addition to a large number of books, it contains more than 700 manuscripts, including many rarities such as a 4th-century illustrated fragment of Homer and a 1355 miniature of Dante.
Candle auctions are only used for a relatively short period of time. (They were eventually superseded by auctions, which ended with three taps of the auctioneer's baton, as we know them today.) The reason they disappeared was that they were problematic to run. Specifically, most of the candle auctions at that time faced the following three problems.
As was customary at the time, the auction was formatted as a candle auction: the auctioneer lights a candle in front of interested bidders, who then bid until the candle goes out. The highest bidder when the candle goes out wins the item and pays his bid. The Pinelli auction was one of the first candle auctions with a detailed history. Candle auctions have been used as far back as medieval France (records date back to at least 1368), mainly to resolve inheritance disputes. Other records include auctions of ships and furs in England.
Candle auctions are only used for a relatively short period of time. (They were eventually superseded by auctions, which ended with three taps of the auctioneer's baton, as we know them today.) The reason they disappeared was that they were problematic to run. Specifically, most of the candle auctions at that time faced the following three problems.
Second, repeated attempts to manipulate the end time, such as coughing to extinguish the candle.
Second, repeated attempts to manipulate the end time, such as coughing to extinguish the candle.
In contrast, modern computers allow for a more diffuse distribution of end times, increasing the likelihood that an auction will end early. The possibility of early closing times meant that sniping was indeed less of an issue, as bidders were under pressure to bid seriously from the outset.
Advantages of blockchain technology
So the early candle auctions, especially those of the Pinelli Library, were a disaster. At what level can blockchain technology help?
First, the behavior of the auctioneer after the sale points to the main problem with any off-chain auction: lack of commitment from the auctioneer. Even with the best legal system, in the event of a sudden change of mind after an auction, the seller can at least delay the sale of the item for sale. Of course, if bidders in an auction anticipate this behavior, they will not bid as seriously as others, resulting in lower bids. In contrast, if the auctioned and sold items are on the blockchain, smart contracts can easily solve this problem, triggering the transfer of the auctioned items once the winning bidder is determined.
Next, turn to candle auctions more specifically, and consider the sniping problem. The reason for using candles is to make the end time of the auction random: no one can know when the auction will end, which encourages early bidding. It sounds like a good idea, but the chances of the auction ending early are next to zero.
In contrast, modern computers allow for a more diffuse distribution of end times, increasing the likelihood that an auction will end early. The possibility of early closing times meant that sniping was indeed less of an issue, as bidders were under pressure to bid seriously from the outset.
However, modern computers alone cannot solve the second problem of candle auctions: the manipulability of the end time. In particular, the auctioneer acting on behalf of the seller still has to convince bidders that the announced ending was indeed randomly generated. After all, because bids increase over time, sellers always prefer to bid later rather than earlier. Fortunately, recent advances in cryptography allow for randomness that is immutable and verifiable by everyone in the network. [6] Therefore, in blockchain candle auctions, bidders cannot arbitrarily abort the auction, and the auctioneer cannot lie about the end time.
It is believed that candle auctions can help solve two major problems that blockchain-based auctions typically face: front-running and the existence of smart contracts between bidders.
Candle auction case
Now that we know that candle auctions are implemented on the blockchain, they can be an improvement over earlier offline implementations, but the question remains: why use candle auctions in the first place?
It is believed that candle auctions can help solve two major problems that blockchain-based auctions typically face: front-running and the existence of smart contracts between bidders.
Finally, we find that with a uniform distribution of end times and a large number of rounds, the outcome is close to that of second-price auctions. This means that the bidder's expected payment and the auctioneer's expected revenue are equal to the revenue in a second-price auction. This is an important result because second-price auctions are among the most desirable auctions—that is, those that generate the highest revenue. This also means - the most desired outcome for Polkadot - that the bidder with the highest estimate wins the auction!
For example, in first-price auctions (an auction in which the winning bidder pays the highest bid), this makes it possible for a tech-savvy bidder to bid more than other bidders at will. However, there is concern that the existence of front-running makes some bidders feel less engaged, which depresses overall bidding and, in turn, reduces auction revenues. In addition, auction efficiency may also suffer, as items sold go to the most technologically advanced bidders rather than those with the highest valuations.
As Jeff Burdges and Luca de Feo discuss in their Web 3 Foundation study, there are cryptographic solutions to the front-running problem. However, they are either very computationally intensive or require bidders to take multiple actions. But most importantly, cryptographic solutions will not work if the bids themselves are executed via smart contracts. The reason is that smart contracts correspond to publicly visible code. As a result, their valuations of the items for sale and their strategies are made public before the auction. Given the widespread use of smart contracts, there is a high probability that smart contracts between potential bidders will exist in any auction implemented on the blockchain.
Smart contract bidders also face transparency issues. If the smart contract's valuation is known in advance, it is possible for the auctioneer to register a trumpet and make so-called shill bids (i.e. bids designed to increase the price paid by the winner). This is especially problematic in second price auctions (ie, auctions where the winning bidder pays the second highest bid). In such an auction, everyone has to bid honestly, so it is possible for the auctioneer to cheat the smart contract in the auction (by submitting bids slightly below the smart contract's valuation). But smart contracts that foresee this kind of behavior are likely to be hesitant to participate in it in the first place. This again leads to efficiency issues, as the smart contract that decides not to participate is likely to be the one with the highest valuation.
In summary, front-running auctions essentially precludes static auctions where bidders simultaneously submit a single bid, and the transparency of smart contracts precludes auctions with second-price payment rules.
In Häfner and Stewart 2021, we show that candle auctions are a good alternative. To illustrate our point, we analyze a candle auction between two bidders. In each round, the two bidders move in a fixed order. That is, one bidder is always ahead of the other. Bid prices must increase over time. In the deciding round, the highest bidder wins and pays the bid.
The results show that, with an appropriate choice of closing time distribution, it is optimal for the first bidder to make more bids over time, while the second bidder When an item has a higher estimate, it only needs to match the current bid. Therefore, candle auctions provide some safety measures against insidious bidding attacks: in order to increase the price above the equilibrium price, the auctioneer must submit a higher winning bid in an earlier round. But this comes at the cost of an early payment by one of the bidders if the auction happens to end within that time frame.
In addition, a random end time attracts bidders more than a fixed end time. With a fixed end time, two bidders may wait to bid until the last period. On the other hand, random end times put pressure on bidders to bid early. In particular, since frontrunners match the current highest bid when their valuation is high, frontrunners can gain an advantage by submitting increasing bids over time. This allows him to fine-tune his bids based on new information, resulting in higher expected utility.
We found that a random end time has a higher winning rate than a fixed end time. As bidders submit higher and higher bids over time, the random ending rule means that sometimes the auctioneer also has to accept lower bids from previous rounds. However, the magic of the random end time makes bidders bid higher overall, resulting in a higher average winning price.
Finally, we find that with a uniform distribution of end times and a large number of rounds, the outcome is close to that of second-price auctions. This means that the bidder's expected payment and the auctioneer's expected revenue are equal to the revenue in a second-price auction. This is an important result because second-price auctions are among the most desirable auctions—that is, those that generate the highest revenue. This also means - the most desired outcome for Polkadot - that the bidder with the highest estimate wins the auction!
references
In a final, tragic turn for Pinelli's book sales, shipping the books to Milan was more expensive than expected, and as a result, most of the books were disposed of en route. In the end, only 35 boxes (out of the original 130) were sent to the Biblioteca Ambrosiana in Milan, where they are still today.
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).
[2] For a general overview, cf. the Polkadot wiki article. The Polkadot decoded talk by Shawn Tabrizi is also very informative.
[3] The accounts given in this and the next section largely follow Hobson (1971).
[4] Hobson (1971, 223).
[5] Pepys (1662, Wed. 3 September).
[6] See, e.g., Micali, Rabin, and Vadhan (1999).
[7] For example, see this story on MarketWatch about the manipulation accusations of Daily Mail against Google
[8] See, e.g., Daian et al. (2019).
