Hidden in Plain Sight: A Sneaky Solidity Implementation of a Sealed-Bid Auction

Editor’s note: This piece is part of our ongoing series on all things auctions for web3. Part 1 was an overview of auction designs, and technical challenges (and opportunities) specific to mechanism design in a permissionless blockchains context. Part 2 was a piece on clearing the market and avoiding gas wars. Part 3 shares an overview of canonical auction types, a look into how theory translates into practice, and our first implementation of a novel, sealed-bid Vickrey auction. 

On-chain auctions are one of the most interesting (and ubiquitous) design spaces in web3 — from NFT sales to collateral auctions — giving rise to a new landscape of implementations and research. While auction mechanism design has been around for centuries, and has evolved in recent decades with the advent of the web and ecommerce, we’re only now applying these approaches to smart contracts.

We’re also starting to see more auction designs that are native to blockchains, including our open source Solidity implementation of a Vickrey auction, and several interesting developments from the community (including suggestionsfor efficiency improvements, new theoretical results, and two hackathon-winning implementations of sealed-bid auctions). In our first design, we made a tradeoff between privacy and capital efficiency: We used overcollateralization (bidders lock up more collateral than is required by their bid) in order to enforce payment from the winning bidder, without revealing the precise bid values via the collateral amount. By locking up more capital you get more privacy at a potentially greater opportunity cost. But what if we could have bid privacy without overcollateralization?

This post introduces a new auction design that we call “SneakyAuction,” which combines the CREATE2 opcode and state proofs to guarantee bid privacy without requiring bidders to lock up more collateral than is required. We begin by breaking down how it works, and then compare it to our previous implementation (OverCollateralizedAuction) in terms of gas cost, user experience, and privacy. We’ve also added the implementation to our Auction Zoo repository on GitHub so that you can fork it, build on it, and follow along as we dive into more mechanics; in meantime, more on how it works and compares to our past design below.

There are two requirements we need to create an “eventually-public” sealed-bid auction on-chain. First, bids need to be private for the duration of the bidding period, and then revealed when it ends; commit-reveal schemes (where users publish hash-committed values, and then reveal their inputs later) can replicate this mechanism on-chain. The second requirement is collateralization: bids must be backed by collateral to ensure the winner has enough funds to fulfill their commitment.

In our overcollateralized Vickrey implementation, prospective buyers place bids by calling the commitBid function, supplying a hash commitment and the collateral to be escrowed. This approach satisfies the requirements, but has some drawbacks. Even though the bid itself is hidden by the hash, the commitBid transaction openly and immediately signals the intent of the user: “I would like to bid on this auction, and here is the collateral for my bid.” Without overcollateralization, the visibility (and linkability) of both intent and collateral would reveal bid values. But if we can obfuscate the intent of a transaction, we might be able to achieve bid privacy without relying on overcollateralization.

The CREATE2 opcode, introduced in EIP-1014 and included in the Constantinople hard fork, gives us a way to do just that. The CREATE and CREATE2 opcodes are both used to deploy smart contracts, but they differ in how the deployment addresses are computed. The CREATE deployment address is computed as a hash of the deployer’s address and nonce; the CREATE2 deployment address, on the other hand, is computed as a hash of the contract’s bytecode and constructor parameters, an arbitrary salt, and the deployer’s address (details).

CREATE2 is often used in the factory pattern to deploy contracts to predictable addresses — for example, the UniswapV3PoolDeployer contract uses CREATE2 to deploy each pool contract to an address which is a function of the token pair and fee tier. CREATE2 can also be used to (re)deploy upgradable smart contracts, most notably in the metamorphic contract pattern.

More importantly for us, the CREATE2 deployment address can function as a hash commitment to any behavior defined by the input bytecode and parameters. If the constructor parameters encode a bid, the CREATE2 address can serve as a bid commitment.

Moreover, the contract itself can serve as a vault — a bidder can send ETH to the CREATE2 vault address before the contract is deployed to collateralize and commit to their bid in one simple transfer! Since the bidder does not have the private key for the vault address, the collateral is locked until the bid is revealed, at which point the SneakyAuction contract deploys and unlocks the vault.

This approach makes the transaction indistinguishable from a transfer to an externally owned address (EOA). The bid transaction is hidden in plain sight, among other transfers on the blockchain. One important caveat, however: this seemingly tidy solution also makes it difficult to determine when the collateral was locked. It’s essential for auction security that the vault was funded before any bids are revealed. Otherwise, an opportunistic buyer could wait until the very end of the reveal period, at which point most bids have already been revealed, to decide whether or not to collateralize their vault. We need to ensure that vaults are collateralized during the bidding period, not during the reveal period, using another tool: state proofs.

One way to ensure that a vault was collateralized during the bidding period is by checking its balance at a past block. It’s relatively easy to do this off-chain by querying an archive node; but much more difficult to accomplish (trustlessly) on-chain. The EVM’s BALANCE opcode reads the current balance of an address, but no such opcode exists to retrieve a pastbalance. In fact, the only EVM opcode that provides any sort of historical state access is BLOCKHASH, which returns the hash of one of the last 256 blocks. Fortunately — with some off-chain help — blockhash works just well enough for our use case.

The blockhash is the hash of the block header, which includes (among other metadata) the state root of that block. The state root is the root node of a Merkle-Patricia trie, where each leaf node corresponds to a particular address and includes the address’ balance at that block. We can’t directly access these leaf nodes on-chain, but we can verify that the contents of a leaf node are correct. In fact, the eth_getProof RPC method supported by Alchemy (among other providers) returns the Merkle proofs needed to perform this verification (Leo Zhang provides an in-depth explanation of how this works in the context of Ethereum light clients). This means that with a little bit of off-chain help (a single RPC call), bidders can prove to the SneakyAuction contract that their vault was collateralized during the bidding period.

In our implementation, the first bid revealed for an auction stores the blockhash of the previous block. This transaction effectively transitions the auction from the bidding phase to the reveal phase — all subsequent bids revealed must provide a Merkle proof that their vault was sufficiently collateralized before that block (i.e. before the first bid was revealed). Note that the first revealBid transaction would ideally be submitted via a private transaction pool (e.g. Flashbots); otherwise, a bidder watching the mempool (seeing the value of the revealed bid) could front-run the transaction and place a last-second bid.

LibBalanceProof

To minimize costs for bidders, we wrote a gas-optimized library to verify balance proofs on-chain that builds on contractswritten by the Aragon team (who pioneered on-chain storage proofs in 2018), and Hamdi Allam’s contracts for on-chain RLP decoding. Our library uses a number of low-level tricks and optimizations that rely on the particular structure of the state trie, so it cannot be used for generic Merkle-Patricia trie proofs. In return, it allows the SneakyAuction contract to verify the past balance of a vault in less than 30,000 gas.

We also wrote a lightweight JavaScript wrapper for the eth_getProof RPC method. Given an address and block number, it returns the balance proof and RLP-serialized block header, which can be used to reveal a bid.

Let’s compare our new SneakyAuction approach against the OverCollateralizedAuction design we last released, along several key dimensions that technical designers or users care about: gas costs, user experience, and privacy.

Gas costs

SneakyAuction’s revealBid, endAuction, and withdrawCollateral functions require deploying a SneakyVault, so they are more expensive than their OverCollateralizedAuction counterparts. revealBid is particularly expensive because it also verifies a balance proof, which costs about 25,000 gas.

User experience

Although the two implementations follow a similar overall flow (bidding phase, reveal phase, auction ends), there are some differences in user experience. SneakyAuction has a few minor disadvantages:

• The experience of sending ETH to an undeployed vault, though it could be abstracted away by the front-end, is potentially confusing for users who examine their bid transaction on a block explorer.
• With OverCollateralizedAuction, it’s possible to end the auction early if all bids have been revealed. This is not possible in SneakyAuction because the contract has no way of knowing how many bids have been committed.
• Bidders can update their bid and top up their collateral with OverCollateralizedAuction by calling commitBid again. In SneakyAuction, bidders can’t make updates once the bid’s vault has been collateralized.

Privacy

The bid privacy of OverCollateralizedAuction relies on bidders choosing to lock up extra collateral (so onlookers know an upper bound of a bid but not the exact amount). SneakyAuction, on the other hand, derives privacy from on-chain activity that’s completely unrelated to the auction itself: ETH transfers that happen during the auction’s bidding period.

For simplicity, let’s assume that each bid is collateralized using a single ETH transfer. We observe that:

1. The collateralization transaction should be the first time anyone has interacted with the vault address on-chain.
2. We don’t expect any other transactions to touch the vault address for the rest of the bidding period.
3. No transactions can originate from the vault address (because no one has the private key).

ETH transfers during the bidding period to otherwise “untouched” addresses are plausibly bids — in other words, they are the “noise” that hides bid transactions. To help quantify the privacy of SneakyAuction, we can look at the shape of this noise distribution.

This histogram shows the year-to-date distribution of daily ETH transfers (on Ethereum mainnet) to untouched addresses, illustrating the noise distribution for a 24-hour bidding period. We can see that most transactions fall into the [0.001, 1] ETH range, implying that auctions with an expected bid value in that range would have the strongest privacy. On the other hand, the typical noise may not provide sufficient privacy for auctions where the expected bid is greater than 10 ETH — there are rarely more than 100 transfers in that range, so an auction attracting many bids would create a conspicuous spike in the distribution.

For another perspective on this data, these scatter plots depict the transfers on October 15, 2022, overlaid with bids from two hypothetical auctions:

Intuitively, it would be much easier for an observer to identify bids from the second auction. In practice, you could use a clustering algorithm such as the expectation-maximization (EM) algorithm to predict which transactions are bids.

However, there are a few other factors that can make SneakyAuction more private (and therefore more compelling) in practice:

1. Longer bidding periods: Privacy scales with the length of the bidding period –– the longer the bidding period, the more transfers there are to hide bids.
2. Concurrent auctions: Privacy scales with the number of concurrent auctions –– if two auctions are in their bidding phases at the same time, one auction’s bids serve as noise for the other.

SneakyAuction can also benefit from overcollateralization — since SneakyVault returns any excess ETH to the bidder, bidders can opt to overcollateralize for further privacy. So in a sense, SneakyAuction provides strictly stronger privacy than our previous implementation.

A simple corollary of SneakyAuction’s privacy mechanism is that it hides the number of bids during the bidding period. This is an advantage over OverCollateralizedAuction, which only hides the bid values — the number of bid commitments that have been made for a given auction is fully public (and may give away how competitive the auction is).

***

While our first implementation of a sealed-bid auction translated real-world features into on-chain design decisions, our second design relies on a novel and practical mechanism to use the public nature of blockchains to its advantage: sealed bids “hide” among unrelated blockchain activity.

Though this new approach is a convenient way to achieve bid privacy without overcollateralization, it’s not necessarily suitable for all auctions (for instance auctions with many high-value bids). Privacy improves for auctions that expect smaller bids (and especially over a longer period of time).

***
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.

This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.

Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information