New Threshold Encryption Schemes for Mempool Privacy and Timelock Encryption

The focus of this blogpost is on protecting the privacy of transactions that have been submitted to a public mempool but are yet to be included on chain.

Based on work with Arka Rai Choudhuri, Sanjam Garg, Dimitris Kolonelos, Julien Piet, and Mingyuan Wang.

[09/2024] UPDATE: We improved batched-threshold encryption by removing the epoch setup and simplifying the initial setup. See new blogpost.

Why?

There are many situations in which one would want to hide a transaction until the very moment before it is executed. A popular example is the mitigation of “bad” MEV, where a block proposer can frontrun and/or backrun a user’s transactions, thereby exploiting to exploiting price movements to gain profits at the expense of users.

Another situation where privacy would be useful is during the recovery of funds which were sent to a wrong address as outlined this blog post. In this particular case, submitting the recovery transaction to the public mempool already leaks too much information. A frontrunner could simply copy the transaction and replace the recipient address with their own to steal the funds.

💡 At a fundamental level, users should be able to submit transactions to a blockchain with the guarantee that no party learns any information about their transaction until it is actually executed.

Note: For the moment, we are not concerned with the ordering of transactions. Fair ordering of transactions is an important and complementary problem to mempool privacy.

The Flashbots Research Talk by Justin Drake is good starting point to learn more about the state of the art.

Threshold Encryption

Amongst the various approaches to mempool privacy outlined (see blogpost for a summary), we focus on threshold encryption. At a high level, threshold encryption allows for a message to be encrypted to a committee of $n$ parties (say) such that it can be decrypted by any $t$ sized subset of $n$ parties, while remaining semantically secure against any coalition of up to $t-1$ parties.

It is highly desirable (in this setting I would argue necessary) to have non-interactive decryption where each committee member computes a “partial decryption”, locally, using just their secret key and the ciphertext. These partial decryptions, can later be publicly aggregated to recover the message.

---

It’s not too hard to see how this would be used for Mempool privacy:

1. Users encrypt transactions to a committee and submit ciphertexts to the mempool.
2. A block proposer creates a block containing ciphertexts, using any strategy of their choice.
3. Once a block has been confirmed i.e. received enough signatures from validators, the committee members decrypt the block.

Bottlenecks

We identify two main bottlenecks to deploying threshold encryption in practice.

Setup is Expensive

Most threshold encryption schemes (based on groups) have a setup phase, where parties run a distirbuted key generation protocol to establish shamir secret shares of a random value. This can be quite expensive in a massively distributed setting. If a party joins/leaves the committee, we require further interaction to re-share the key with the new committee. Or we are forced to rerun the setup entirely. Moreover, it requires parties to be aware of who else is in the committee.

Decryption is Expensive

Decryption in existing threshold encryption schemes requires a large amount of communication. Say there are $B$ transactions in each block. In the original setting without privacy, we required a broadcast of size $O(B)$ — the block needs to reach everyone. When using Threshold Encryption, we require a broadcast of size $O(nB)$ — the block needs to reach everyone, and the partial decryptions for each transaction need to reach everyone. In practice, this can mean $10-100\times$ blowup in the communication, which may be untenable. In more concrete terms, this paper, showed that each kilobyte over 20kB adds an 80~ms delay in the time taken to reach a majority of nodes in the Bitcoin network.

(Unsatisfactory) Fixes

We note that there are (albeit unsatisfactory) ways to get around the above issues. For instance, if committees once formed, stay together for a long time, this "amortizes" the setup cost. A new committee can be formed before the existing one decides to "disband" and users can begin encrypting to the new committee after a certain block number.

One can also get around the decryption issue by encrypting transactions to an epoch number, instead of a committee. The committee issues keys to decrypt transactions for the current epoch, using which all transactions that were encrypted to that epoch can be decrypted. This decryption material can be a few group elements per party, irrespective of how many transactions were encrypted to the epoch number. But this comes with the problem that a user's transaction is compromised if it is not included within time. In some situations such as decentralized auctions, this can be a great solution, but this may not be acceptable in settings where for example a user wants to place a large order for a token and does not want to be frontrun. Here, even revealing the intention to buy a large amount of a particular token may be unacceptable. Shutter Network and McFly use an adaptation of the Boneh-Franklin IBE scheme to achieve this.

Our Solution

We are excited to announce two papers that make progress on the above issues:

1. Silent Threshold Encryption [CRYPTO 2024, code] - A novel threshold encryption scheme that avoids any interaction during the setup procedure and provides other attractive features.

   • Anyone who wants to participate as a committee member simply publishes their public key. No interaction with any other party.
   • Users can create a committee of their choice at the time of encryption. In particular, this allows a user to remove committee members that they do not trust or even add new committee members.
   • Users can also choose the threshold required for decryption, at the time of encryption. Dynamic thresholds can be an attractive feature as it provides users with the ability to choose a tradeoff between liveness and privacy.
   • The CPA ciphertexts are $\approx 8\times$ the size of an ElGamal ciphertext.

2. Batched Threshold Encryption [USENIX Security 2024, code] - A novel threshold encryption scheme where a batch of ciphertexts can be decrypted using communication that is independent of the batch size. Our ciphertexts are 370 bytes long, which is $<3\times$ as large as the Cramer-Shoup CCA2 scheme. For a commitee with 128 parties, irrespective of block size, we only need $\approx 10$ KB of data to be broadcast for decryption. However, this only addresses the latter issue, while making the former worse. A more complicated setup is required, and each epoch needs a setup, but if these can be performed well in advance, and the committee is fixed (at least for extended periods of time), this can be a viable solution.

Bonus: Silent Timelock Encryption

Our silent threshold encryption scheme is actually a witness encryption scheme for the statement "If you know at least $t$ signatures on some special string, issued by any of the $n$ committee members, then you can decrypt my ciphertext". By setting this special string to be the current block number, we immediately get a silent setup version of tlock.