Building private verifiable auctions with FHE

At Sunscreen, we're working to enable a new class of applications operating on private shared state via fully homomorphic encryption (FHE). These applications tend to have two requirements—input privacy (keeping inputs hidden even after the program is complete) as well as verifiability (how can we know for a fact the program was run correctly?). One such application is auctions, with one of the more interesting use cases aimed at determining blockspace ordering.

In this article, we'll walk through how blockspace auctions work at a high level and how threshold FHE can improve the auction process. We'll then look at where threshold FHE is as a field and how Sunscreen is working to make private verifiable (d)apps available to all.

So far we've focused on developers but we're excited to showcase our first demo where end users can see what such an FHE-enabled application might look like! Our demo implements a first-price sealed-bid auction using our own variant of the torus fully homomorphic encryption scheme (TFHE) and is inspired by top-of-block blockspace auctions. With a 64-core machine, determining the winner over all 93 encrypted bids should take <2 seconds but, depending on the number of people using the demo, you may experience a slowdown.

For the full experience, connect via Metamask and make sure to have some Sepolia ETH available!

First-price sealed bid auctions are just the start for us and we're excited to explore bringing privacy and verifiability to all kinds of auctions.

Crash course on blockspace auctions

If you're new to blockspace auctions, keep reading! We'll take a look at why they were created, how some of them operate at a high level, and limitations with existing constructions. Please note that the following provides a simplified overview; blockspace auctions are just one example of an auction where privacy and verifiability are crucial so don't get too hung up on the details.

Let’s say there’s an arbitrage opportunity across two decentralized exchanges (DEXs) on the same chain—specifically, we notice that token τ is quoted at price α on exchange A and price β on exchange B where α < β. This seems like a good opportunity to potentially purchase token τ on exchange A and then sell it at a higher price on exchange B, pocketing the profit.^[1]

Unfortunately, it turns out that many people are thinking exactly the same thing! We'll broadly refer to the individuals competing to take advantage of arbitrage opportunities as "searchers."^[2] Once one person takes advantage of this arbitrage opportunity, token τ’s price on both exchange A and B are likely to change (potentially such that the price difference between the two is smaller or so that the prices converge across the two exchanges).

How do we decide who gets to the opportunity first? In blockchain, this boils down to transaction ordering within a block but how transaction ordering occurs is chain-dependent. If we're looking at Ethereum, transaction ordering is generally tied to gas price. Thus, searchers could submit transactions directly to the public mempool and compete by offering a higher gas price to try to get their transaction processed faster. If we're looking at Cosmos, transaction ordering generally obeys a first in, first out (FIFO) rule so a searcher may attempt to spam the network to get their transaction in first. The space becomes even more complex when looking at L2s, which lack public mempools and often operate on a FIFO basis. Irregardless of which chain we're on, both of these strategies lead to a number of issues for both searchers and ordinary users.

Professional searchers may also be looking to take advantage of many arbitrage opportunities within a single day, meaning they submit a large number of transactions in a fairly small time period. By revealing both the transaction details and gas price, competitors might be able learn that searcher’s trading strategy. Ideally, there should be way for searchers to submit transactions such that the transaction details either aren't revealed to competitors or so that whatever they’re willing to pay for the transaction remains private to other searchers/users (especially in the case of unsuccessful transactions).^[3]

How might we determine transaction ordering within a block in a way that optimizes the experience for both ordinary users and searchers? Blockspace auctions are one such solution (offered by the likes of Flashbots and Skip); these auctions segment searchers from ordinary users, allowing searchers to compete against one another for priority ordering while preventing a degradation of experience for ordinary users.

Let's dive into how blockspace auctions work at a high level, as the process is often not that transparent and differs based on the particular protocol/chain.

We'll look at the most straightforward of these auctions where we're bidding for the top of a block using a first-price sealed-bid auction (e.g. Skip Select). Flashbots also employs a first-price sealed-bid auction but allows searchers to express more granular ordering preferences but with no guarantee of top of block execution.^[4]

Roughly speaking, the following happens:

• Searchers submit a "sealed bid" directly to a third party. The sealed bid consists of how much the searcher is willing to pay for their transaction (potentially a bundle of transactions) to be placed at the top of the block. If the searcher wins, they'll have to pay this bid amount (potentially to the block builder/validator but in theory this bid amount could be distributed across several parties).
• The third party looks through all submitted bids and determines who placed the highest bid.
• The third party gossips the result of the auction to the validators/block builders who will then ensure the winner's transaction (bundle) will be placed at the top of the block.

A major shortcoming in this process is the need for a trusted party. As presented, there is a third party who is trusted for both (a) correct execution of the program (they've correctly declared the winner) and (b) maintaining the privacy of searchers' bids (neither sharing these values nor using this information for their own benefit).

Alternative constructions involve searchers submitting their bids directly to block builders but this introduces other problems (since builders can front-run, sandwich, or censor searchers' transactions at will). We won't be diving into the tradeoffs of that construction here but, if the topic interests you, we recommend listening to Interview with a Searcher 2.0.

When folks think of privacy tools, like FHE, they imagine how privacy can prevent MEV. Perhaps surprisingly, FHE also has the potential to enhance MEV extraction.

Reimagining the auction process

Can we improve the existing auction process? Ideally, this would mean:

1. Anyone can verify that the auction ran correctly (we'll refer to this property as verifiability).
2. Unsuccessful bids remain private to all parties (we'll refer to this property as privacy).

Imagine that auction participants (in our case searchers) now encrypt their bids—not with just any old public key encryption scheme, but using threshold fully homomorphic encryption. Specifically, the auction might work in the following way:^[5]

• A set of parties jointly generate a public-private key pair such that each party (we'll refer to them as the threshold committee) holds a share of the private key (i.e. decryption key).
• Auction participants encrypt their bids using the public key and post their encrypted bids to a data availability layer or some sort of ledger (the choice of which is up to the system designers).^[6]
• Anyone can run the auction program (whether it's as simple as a first-price sealed-bid auction or something more complex) directly on the encrypted bids to determine who the winner should be (thanks to the homomorphic properties of the encryption scheme).
  • Depending on the application's needs, there may a set of specialized parties tasked with running the auction program at scale to guarantee certain performance requirements are met. For example, say we need to determine who placed the highest bid in sub-second time on ~100 bids with 32-bit precision; achieving this sort of performance may require fairly beefy hardware. There will need to be an appropriate mechanism for punishing these specialized computing parties if the program wasn't faithfully run (e.g. via slashing).
• Only the winning bid is decrypted by the threshold committee (who come together to reconstruct the private key) and the outcome is gossiped.

How does threshold FHE allow us to satisfy the conditions of verifiability and privacy? FHE allows anyone to run computations on encrypted data. Thus, anyone can run the auction program on the encrypted bids to determine the winning bid (without even knowing what any of the underlying values are!). The "threshold" aspect ensures that losing bids remain private to everyone (including those on the threshold!). Roughly speaking, to construct a threshold FHE scheme, we start with a single-key FHE scheme and then split the private key into shares which we'll distribute across a certain set of parties. Encryption and computation work the same as usual but decryption will require some (pre-determined number) t of the n total threshold committee members coming together to reconstruct the private key. For most blockchains, we assume that there is an honest majority of validators; we'll make a similar assumption for the threshold committee members when using threshold FHE.^[7]

There are some challenges when it comes to using threshold FHE to perform auctions. We'll dive into these further on, covering the basics of threshold FHE and the current status of the field (spoiler: it's a pretty active area of research with little consensus on how best to construct a threshold FHE scheme)!

Note that nothing about this private verifiable auction process is specific to blockspace auctions; we've just chosen to motivate the initial problem with this application.

Building private verifiable auctions

We just saw how to use threshold FHE to make the auction process more transparent while still ensuring losing bids remain private to all. We've neglected to discuss two important points though—how practical any of this is today and how we know that auction participants have "valid" bids.

For auctions, we'll likely want to use the TFHE scheme (or some variant of it) as it's best suited to performing comparisons over encrypted data. Don't confuse TFHE with threshold FHE; TFHE is a particular single-key FHE scheme that operates over a torus whereas threshold FHE refers to a broad group of FHE schemes where we've distributed the secret key across multiple parties. Recall that single-key FHE can be viewed as an extension of public key cryptography, where anyone can perform computations directly on encrypted data; however, the key pair belongs to a particular user. As TFHE is a single-key fully homomorphic encryption scheme, we'll need to figure out how to transform it into a threshold scheme.

In our experience, most folks are interested in knowing what the auction's runtime is (i.e. how long does it take to determine the winner of the auction given x number of encrypted bids with y-bit precision for the bids). In working with a threshold scheme, performance will depend on additional factors such as n, t, and the network connection between the threshold parties. Unfortunately, there are no optimized threshold TFHE implementations we're aware of to benchmark against (and we're not ready to share ours yet!).

Given the nuances with threshold FHE and that decryption time is what's most impacted in converting a single-key scheme to its threshold version, the following numbers for single-key TFHE should still serve as a good reference point in thinking about threshold TFHE's performance.^[8]

Performance, performance, and performance

Before getting into any numbers, we need to identify what variable tends to have the most impact on TFHE's performance—bit precision. As we increase the precision (say from 16 bits to 32 bits), you'll notice a drop off in performance. Of course, the number of encrypted inputs and the complexity of the program have a large impact on performance but we have less control over these factors (the former could be restricted if necessary).

To give a sense of the numbers one might expect, we benchmark the first-price sealed-bid auction program (to determine who the winner is along with the winning bid) on a c7g.16xlarge (64 cores) for TFHE with programmable bootstrapping via tfhe-rs 0.4. With 16-bit precision, the program runtime varies from ~4.1 s on 64 bids to ~11.4 s on 256 bids. With 32-bit precision, the same program runs in ~6.1 s on 64 bids and goes up to ~18.9 s on 256 bids. These times do not include key generation, encryption, or decryption time.^[9]

Please note that we have our own variant of the TFHE scheme which offers much better performance than quoted (we're using our own TFHE variant in the demo to run the auction as well). More will be shared in the coming months.

Bid validity

So far we've assumed bidders behave honestly but that's not a given in practice. Namely, what if bidders submit bids they can't actually afford to pay out?^[10]

In an ideal setting, we might use zero knowledge proofs to help us— namely bidders could submit zero knowledge proofs, along with their encrypted bids, proving they can afford to make the bid.

Unfortunately, creating and verifying proofs for FHE-encrypted inputs will be quite expensive. If we want to minimize proof generation time, this will come at the cost of proof verification time. On the other hand, if we want to minimize proof verification time, this will come at the cost of proof generation time. Either way, someone will get the short end of the stick. Even with high end hardware, generating a proof about your FHE-encrypted bid will likely take on the order of a few seconds. In certain use cases that are not too time constrained, zero knowledge proofs may be a good option. For scenarios that are more time sensitive and cannot tolerate the blowup, financial disincentives to the rescue!

Imagine that, in order to participate in the auction, bidders need to "stake" some amount of currency. If they're found to be misbehaving (say Bob wins the auction and then refuses to pay), their stake will be appropriately slashed.^[11] The concept is akin to staking with Ethereum; participants will have to deposit some amount of money (determined by the system designers) in order to bid in the auctions. This money will be refunded in its entirety if they no longer wish to participate in the auctions.

Crash course on threshold FHE

Feel free to skip this section if you've already had your daily dose of math and cryptography.

We assume you’re already familiar with public key cryptography and fully homomorphic encryption at a high level (if not, we suggest looking through this article first). So what exactly is threshold FHE and how does it differ from regular FHE?

Threshold cryptography allows us to distribute trust across a number of parties, so that the private key is split across these parties and a subset of them need to come together to reconstruct it.^[12] To make the idea a bit more concrete, imagine 5 parties come together to generate the public-private key pair but we only need 3 of them (doesn’t matter who) to decrypt ciphertexts. This would be referred to as a (3, 5)-threshold scheme where the first entry (we usually use the letter t) refers to the minimum number of parties needed to decrypt and the second entry (we usually use the letter n) refers to the total number of parties who hold pieces of the private key. A general challenge with all of threshold cryptography is deciding what t and n should be in practice. We believe these choices are best left to the system/protocol designers as each application has its own needs in terms of decentralization and performance.

In threshold FHE, the two main algorithms that change are key generation and decryption. Now, some set of parties jointly generate a public-private key pair in an interactive process. Encryption and homomorphic computation work the same as usual but, in order to decrypt a ciphertext, some “threshold” needs to come together to reconstruct the private key. There is relatively little overhead for encryption and homomorphic computation times when we go from single-key FHE to threshold FHE for smaller values of n. Of course there is quite a bit of overhead in key generation but, as this process doesn’t happen all that often, we’re not too concerned about it. The main efficiency concern lies with decryption.

How do we construct a threshold FHE scheme?

When it comes to going from a single-key FHE scheme to a threshold FHE scheme, there are different ways to do this transformation, each with its own tradeoffs. The most straightforward threshold FHE scheme to construct is one that is "full threshold," meaning we have an (n, n)-scheme where every party who holds a share of the key must come back to decrypt. The simplest construction of a full threshold scheme is via additive secret sharing where the new secret key will simply be a sum of each party's individual secret key.

When it comes to constructing a (t, n)-threshold scheme, where t < n, things get more complicated. Threshold FHE is an active area of research with no consensus yet on the "best" threshold FHE construction.^[13]

A key ingredient of threshold FHE is "noise flooding" (i.e. adding additional noise to the ciphertext when performing computation on it, sometimes called "smudging") so let's look at what it is and why you need it. In FHE, each time we perform a computation on a ciphertext, there is some "noise" that accumulates. Certain computations introduce more noise than others. If the noise gets too large, we won't be able to decrypt the ciphertext. Bootstrapping is one way around this issue, pulling off some of the accumulated noise so we can continue doing computations on our ciphertext. However, if we know the noise associated with a ciphertext we've received, we might be able to infer what computations had been performed on it. That's where noise flooding comes in; it allows us hide the computation being performed on the encrypted data.^[14]

In threshold FHE, we'll use noise flooding during the decryption process. Let's say threshold party p₁ performs his part of the (partial) decryption process and then passes on this information to threshold party p₂. Can p₂ learn something from p₁'s partial decryption? p₂ can learn something but what exactly that is and how useful the information will be is not immediately clear. To protect against p₂ learning useful information from p₁'s partial decryption, we'll introduce noise flooding.

How to choose the correct amount of noise for noise flooding is outside the scope of this post. It turns out that doing noise flooding in a way that's secure without blowing up the scheme parameters (causing performance issues) is non-trivial.

Can I use threshold FHE today?

The short answer is no.

The longer answer is "well, it depends." There are a few libraries (OpenFHE, Lattigo) offering a select set of full threshold FHE schemes (specifically the BFV/BGV and CKKS schemes). If you'd like to do auctions, the BFV/BGV and CKKS schemes are not particularly useful. These libraries also appear to be written by cryptographers for other cryptographers—making it difficult for developers to harness the power of threshold FHE.

Additionally, if you're interested in using threshold FHE in a decentralized/trustless setting, you may need to combine threshold FHE with zero knowledge proofs (ZKPs).

Sunscreen

All of this sounds great but how does Sunscreen fit into the picture?

At Sunscreen, we're working to change the status quo. We are building tools to make threshold FHE performant and easy for developers to use, along with an accompanying ZKP library + compiler to work in combination with (threshold) FHE. In the future, developers will be able to harness the power of threshold FHE to build exciting applications like private verifiable auctions and DAO voting.

Thus far, we've been primarily focused on developers, but we wanted to showcase what an application with FHE might look like for end users. You can check out our demo here.

Try our sealed-bid auction demo on the Sepolia testnet!

Our demo implements a first-price sealed-bid auction (inspired by blockspace auctions). Under the hood, we're using our own variant of TFHE. We were not satisfied with the performance of any of the existing TFHE implementations so we asked ourselves if we could do better (spoiler: the answer was yes).

You're free to choose your own adventure—if you'd like the full experience, you can connect via Metamask, stake 5,000,000 (Sepolia testnet) gwei, and participate! As suggested in Bid Validity, we implement staking and slashing to discourage participants from submitting bids they can't afford to pay. We also offer a version without any staking/slashing.

For demonstration purposes, you can view all bids once the auction has finished execution. However, in a real world deployment, losing bids would not be decrypted by the threshold (you would, at best, be able to view the plaintext value of the winning bid).

The auction program is currently being run on a c7g.16xlarge instance (64 ARM cores). We take in 92 other encrypted bids, supporting 21-bit computation (so that you can place a bid between 5,000,000 - 7,000,000 gwei). There's promising work indicating that FPGAs can improve performance by 100x.

What the future holds

We have a few things going on in parallel at Sunscreen. If you'd like to serve as an early design partner, please reach out to us directly.

Redefining best-in-class performance

In speaking with various protocols, we found that performance times of existing TFHE implementations made TFHE challenging to deploy in real world use cases. We asked ourselves if there might be a way to improve best-in-class performance, particularly if we do bootstrapping differently. The answer was yes, leading us to create our own variant of TFHE.

Implementing threshold FHE

Threshold FHE enables a new class of private applications in which we might want to operate on private shared state.

Consequently, we're working on threshold implementations of the BFV scheme (the single key BFV scheme is already integrated into our FHE compiler) as well as the TFHE scheme. These two FHE schemes allow us to address a broad range of applications depending on the type of computation being performed.

ZKP compiler

Earlier, we announced the launch of our ZKP compiler (which you can try out in our playground).

We've been working on connecting our FHE compiler with our ZKP compiler (which currently supports Bulletproofs but can be extended to support additional proof systems), as well as allowing developers to prove their FHE ciphertexts are well-formed via the DLS19 proof system. The first part of this work involves "linking" the two proof systems together; we've completed this for BFV and up next is TFHE.

To make the combined FHE and ZKP compiler experience truly developer-friendly, we'll need to clean up the API.

Wrapping it up

We're excited about what the future holds and see FHE as a key ingredient in enabling a more private and fair web.

If you want to keep up with our work, follow us on Twitter for updates. If you'd like to chat with us about anything we're working on, feel free to join our Discord.

Finally, thanks to Ghada, the Skip team, and Walt for providing valuable feedback.