Accountability for Encrypted Mempools

Cryptography
,
1

Accountability for Encrypted Mempools

Authors: Aditi Partap, Arantxa Zapico

Introduction

The prevalence of sandwich attacks on Ethereum highlights a fundamental vulnerability in public mempools: because pending transactions are visible to all participants before inclusion, block proposers and searchers can strategically reorder them to extract value.

Encrypted mempools aim to reduce this leakage by hiding transaction contents until a protocol-defined reveal point. But once transactions are encrypted, the protocol has to decide who is responsible for revealing them. One direction is to let users participate directly in decryption, which raises the reveal/non-reveal option problem: users may choose not to reveal transactions once doing so is no longer favorable. Another direction is to enshrine decryption through a committee.

One leading approach to implementing committee-based encrypted mempools uses a distributed committee. In this model, a group of parties holds individual shares of a secret decryption key, ensuring that no single entity can reveal transaction data prematurely. This configuration, however, remains vulnerable to committee members compromising the protocol through the unauthorized distribution or sale of their decryption shares.

Encrypted mempools raise several broader research challenges, including batch decryption (CGPP25), context-dependent decryption (BBNRS25), and traitor tracing (BPR24). This post focuses on traitor tracing for committee-based encrypted mempools: how can we identify committee members who leak or sell partial decryption capability before transactions are meant to be revealed?

We give a candidate traceable threshold encryption construction for this setting, adapting tracing techniques from BPR25, where they are applied to Paillier-based VRFs and traceable secret sharing, to Paillier encryption. The goal is to identify committee members who contribute to a leaked partial decoder, without falsely accusing honest ones. This is a first step toward mitigating share leakage, not a deployment-ready solution: significant challenges remain, especially around setup and the tracing authority.

The post has three parts. Part I gives a self-contained overview of the accountability problem, the threat model, and the tracing construction we propose. Part II sketches the cryptographic construction in more detail. Part III discusses the open problems that must be solved before traitor tracing can be applied to encrypted mempools in practice. Readers mainly interested in the encrypted mempool design problem can skip Part II.

Part I: Overview

How committee-based encrypted mempools work

We first spell out the committee model more concretely. Committee members hold individual shares of a secret decryption key. No single committee member can reveal transaction data on their own, but any threshold-size set of committee members can jointly decrypt once the protocol reaches the reveal point.

We briefly describe this flow using a threshold encryption scheme with five algorithms: \mathsf{KeyGen}, \mathsf{Enc}, \mathsf{ShareDec}, \mathsf{ShareVerify}, and \mathsf{Combine}. We set a t-out-of-n threshold.

  1. A setup procedure runs \mathsf{KeyGen} and outputs one public key pk and secret keys sk_1,\ldots, sk_n for the committee members.
  2. When user \mathsf{user}_j wants to publish a transaction \mathsf{tx}_j, they encrypt it using \mathsf{Enc} under the committee public key pk and publish the ciphertext \mathsf{ct}_j to the mempool.
  3. Eventually, \mathsf{ct}_j gets included in a block.
  4. The committee members run \mathsf{ShareDec} on input \mathsf{ct}_j and publish their decryption shares, each with a proof of validity.
  5. Any party can verify the decryption shares using \mathsf{ShareVerify} and run \mathsf{Combine} on any t valid shares to recover the transaction \mathsf{tx}_j.
  6. \mathsf{tx}_j is executed in the next block.

This committee approach prevents any single member from decrypting early. The remaining question is what happens when several members collude.

Threat model: leaked partial decryption capability

The main risk we consider is early access to transaction contents through leaked committee shares. A group of committee members may sell or jointly use their decryption shares before the protocol intends transactions to be opened. Their goal is to combine forces, learn transaction contents early, and then extract MEV using this extra information.

If at least t committee members collude, then they already have enough shares to decrypt directly. In this post, we focus on the more subtle case where fewer than t committee members collude and the early decryption capability is still being assembled. These parties are collecting decryption shares before the intended reveal time, but the capability is still missing some of the shares needed to complete decryption.

The goal is to make this partial collusion accountable. At a high level, an honest tracer participates in the under-construction decryption capability using trapdoor-generated decryption shares. These interactions let the tracer recover information about the committee members whose shares were embedded in the capability.

Accountability for partial decoder boxes

To reason about this kind of leak, we take inspiration from BPR25 and model the leaked capability as a partial decoder box. Suppose some f<t parties collude, pool their decryption key shares, and make a “partial decoder box” D. These parties can then sell D to an external party.

The decoder box D is an algorithm that takes as input a ciphertext \mathsf{ct} and t-f additional decryption shares. It combines those additional shares with the decryption key shares contributed by the corrupted parties, and outputs the decryption msg of \mathsf{ct}. A good decoder box is one that outputs the correct decryption with high probability on well-formed inputs. Anyone who obtains such a box can decrypt a ciphertext after collecting only t-f additional shares, rather than waiting for the full threshold of t public shares.

Although this model may sound abstract, it captures a broad range of concrete attacks. If the corrupted parties simply sell their secret key shares sk_i, this can be modeled as a decoder box. If they write a script with their shares hard-coded, that is also a decoder box. The same abstraction also captures obfuscated programs or other packaged decryption capabilities.

We say that a threshold encryption scheme achieves accountability against partial decoders if any good decoder box D can be traced back to the corrupted parties who contributed to it. Formally, this means there is an efficient tracing algorithm \mathsf{Trace} that gets a tracing key tk, interacts with D via oracle access, and outputs the subset of corrupted parties. The tracing guarantee should catch all corrupted parties who contributed shares, without implicating honest parties.

Why naive tracing fails

Before describing the construction, it is useful to see why a simpler tracing strategy is not enough. A first idea is to give the tracer decryption shares for all n parties on some challenge ciphertext \mathsf{ct}. In the case f=t-1, the tracer could run the decoder box once per party, each time giving it \mathsf{ct} and one party’s decryption share. If the box outputs the correct message, the party whose share was used must have been honest: the box could not have decrypted unless that share completed the threshold. The tracer could then exonerate honest parties one at a time and blame the rest.

Although this approach works for perfect decoder boxes that always decrypt when given enough shares, it fails miserably for imperfect boxes. For example, corrupted parties could build a box that decrypts only when the provided share satisfies some predicate, such as H(\sigma_i) starting with five zeros. Then the box may fail even on an honest party’s share, causing the tracing algorithm to falsely blame that honest party.

This is why the tracing problem is not just “try shares and see what works.” The tracing algorithm needs to extract information about the corrupted parties even when the decoder box is noisy, selective, or intentionally designed to confuse simple tests. Our construction uses the algebraic structure of the underlying secret sharing scheme to be able to trace even such imperfect boxes.

Construction overview

Our construction starts from traceable secret sharing based on Shamir secret sharing, as in BPR24. In their scheme, each party’s share is an evaluation (x_i, y_i=h(x_i)) of a polynomial h at a hidden point x_i, and reconstruction interpolates the polynomial at 0. The key tracing insight is that if a reconstruction box contains some parties’ shares, then carefully perturbing an additional input share lets the tracer recover information about the Lagrange coefficient associated with that input. That coefficient depends on the hidden x_i values of the corrupted parties. By repeating this process, the tracer can recover a polynomial whose roots identify the corrupted parties.

We adapt this idea to threshold Paillier encryption. In Paillier, the secret decryption key can be shared with a Shamir-style polynomial h such that h(0) is the Paillier secret. A committee member’s decryption share for a ciphertext \mathsf{ct} has the form \mathsf{ct}^{y_i} (up to constant factors in the exponent that we ignore in this overview; see Part II), where y_i=h(x_i). Combining threshold-many shares amounts to doing interpolation in the exponent, which recovers the Paillier decryption value.

Tracing intuition

The tracer uses the same perturbation idea as in BPR24, but now against a decoder box for threshold Paillier. For simplicity, consider the case f=t-1, where the box needs one additional decryption share. The tracer queries the box on an arbitrary ciphertext \mathsf{ct} with a random-looking share (x,\mathsf{ct}^y), and then queries it again with a related share (x,\mathsf{ct}^y\cdot(1+N)). The difference between the two outputs reveals a value proportional to the Lagrange coefficient for x. Repeating this process at enough points lets the tracer recover the polynomial whose roots correspond to the corrupted parties’ hidden share points.

The crucial point is that Paillier decryption lets us see the effect of the perturbation even though interpolation happens in the exponent, because it computes a discrete log before decryption. In the Shamir setting, perturbing an input share by adding 1 reveals a Lagrange coefficient. In the Paillier setting, multiplying the decryption share by (1+N) plays the analogous role, and the difference between the two decoded messages reveals the corresponding coefficient up to the denominator-clearing factor used by threshold Paillier.

Share verification and trapdoor proofs

The construction also needs share verification. In a threshold encryption scheme, a committee member should not be able to publish an arbitrary value and call it a decryption share. Each decryption share should come with a proof that it was computed correctly from the committee member’s secret share.

For threshold Paillier, this can be done using a proof of discrete-log equality. The public verification key contains commitments to the coefficients of the secret-sharing polynomial, for example values of the form v^{h_0},\ldots,v^{h_{t-1}}. Given a claimed decryption share (x_i,\sigma_i=\mathsf{ct}^{y_i}), anyone can derive the corresponding public value v^{h(x_i)} and verify that the same exponent was used in both v^{h(x_i)} and \sigma_i. This gives public verification of decryption shares.

Tracing complicates this picture. The tracer needs to query the decoder box with values such as (x,\mathsf{ct}^y) and (x,\mathsf{ct}^y\cdot(1+N)). One of these is not a valid decryption share under the public verification key. If the decoder box requires a valid proof before it runs, then tracing would fail unless the tracer can attach proofs to these malformed or perturbed shares. To handle this, the share-verification proof system includes a trapdoor that lets the tracer produce valid-looking proofs even for invalid shares during tracing.

Remaining obstacles

There are two important cryptographic obstacles. First, Paillier works over \mathbb{Z}_N, which is not a field, so the finite-field list-decoding tools for Reed-Solomon codes that were needed for tracing in Traceable Shamir do not apply directly. The construction therefore needs a tracing method that avoids relying on full-fledged list decoding over a field. Second, the trapdoor for share-verification proofs makes the tracing authority powerful, so the setup and governance of the tracing key become central open questions. We refer the reader to BPR25 for how to get around both these obstacles.

The rest of the post gives the cryptographic definitions and construction details behind this overview, then discusses limitations and open problems for using this approach in encrypted mempools.

Part II: Cryptographic construction

This section gives the more formal cryptographic version of the construction sketched above. We first define the threshold encryption and traceability notions we need. We then recall the threshold Paillier structure used as the base scheme and describe how the tracing algorithm interacts with a partial decoder box. The limitations that remain unresolved are discussed in Part III.

Definitions

Threshold Encryption Scheme

A threshold encryption scheme is a tuple of five algorithms:

  • (\mathsf{pk}, \mathsf{vk}, \mathsf{sk}_1, \ldots, \mathsf{sk}_n)\gets\mathsf{KeyGen}(1^λ,t,n) generates the public key and a secret key component for all n parties, along with a verification key \mathsf{vk} that will be used to verify decryption shares.
  • \mathsf{ct}\gets\mathsf{Enc}(\mathsf{pk},msg) outputs an encryption of the message msg.
  • (\sigma_i, \pi_i)\gets\mathsf{ShareDec}(\mathsf{pk},i,\mathsf{sk}_i,\mathsf{ct}) outputs the decryption share of party i for ciphertext \mathsf{ct}, along with a proof.
  • 1/0\gets\mathsf{ShareVerify}(\mathsf{pk},\mathsf{vk},\mathsf{ct},\sigma_i,\pi_i) outputs a bit denoting whether the decryption share \sigma_i is indeed valid.
  • msg \gets \mathsf{Combine}(\mathsf{pk}, \mathsf{vk}, \mathsf{ct}, \{\sigma_i, \pi_i\}_{i\in S}) combines the decryption shares of any t parties to output the decryption.

Traceable Threshold Encryption Scheme

A traceable threshold encryption scheme is a threshold encryption scheme equipped with a tracing algorithm that allows tracing leaked key information. More formally we have algorithms (\mathsf{Setup, Enc, ShareDec, ShareVerify, Combine, Trace}), where the first five algorithms are the same as above with the following changes:

  • (\mathsf{pk}, \mathsf{vk}, \mathsf{tk}, \mathsf{sk}_1, \ldots, \mathsf{sk}_n)\gets\mathsf{Setup}(1^λ,t,n) additionally outputs a tracing key \mathsf{tk}.
  • \mathcal{I} \gets \mathsf{Trace}^D(\mathsf{tk}) is the tracing algorithm that takes as input the tracing key, and gets black-box access to a decoder box D. It then outputs a set \mathcal{I} \subseteq [n] of corrupt parties.

Security Definitions

Correctness

A traceable threshold encryption scheme should satisfy the standard notion of correctness for threshold encryption, which means that any set of t parties should be able to decrypt any ciphertext.

Security

For security, we consider semantic security and robustness, as standard for threshold encryption. We also define three new security notions for a traceable threshold encryption scheme, called tracer semantic security, tracer robustness and traceability. We now give a brief overview of each of these notions:

Semantic Security: Informally, a set of less-than-threshold number of parties should not be able to learn anything about the message from its encryption.

Robustness: Robustness means that a decryption share \sigma_i can be publicly verified, to make sure that it is indeed a valid decryption share of a ciphertext \mathsf{ct}, originating from party i. In a bit more detail, it means that an adversary cannot produce two different shares \sigma_i, \hat{\sigma}_i with valid proofs for any party i, and any ciphertext \mathsf{ct}, even if it is given the secret keys for all parties.

Tracer Semantic Security: We require that the tracer should not be able to break semantic security, even if it can collude with up to t-1 parties. This allows us to restrict the power of the tracer. For instance, if the tracer was just given the decryption key as part of the tracing key, then the tracer would be a single point of failure in the system, defeating the purpose of using a threshold decryption scheme in the first place.

Tracer Robustness: We require that the tracer should not be able to break robustness either.

Traceability: This is the key security property that enables tracing. Suppose a coalition \mathcal{I} \subseteq [n] of parties, of size f < t, gets together and constructs a decoder box D using their shares. This D is an algorithm that takes in a ciphertext \mathsf{ct} along with t-f decryption shares and outputs the decryption of \mathsf{ct}. Intuitively, if this D is a “good” decoder box, then it should be possible to trace it back to the parties who “contributed” their shares to it. “Good” here means that, given any t-f additional decryption shares for \mathsf{ct}, the box outputs the correct decryption with high probability, for many of the ciphertexts. For now, we will focus on “perfect” decoder boxes, which always output the correct decryption, for all ciphertexts, though the techniques we discuss here can be used to trace any good box by using ideas from BPR25.

Constructing Traceable Threshold Encryption

The definitions above specify what the primitive should achieve. We now instantiate the base threshold encryption layer with threshold Paillier. The traceability mechanism will later modify this base scheme by choosing secret-sharing points in a way that supports tracing, and by giving the tracer enough auxiliary information to simulate valid-looking decryption shares during the tracing interaction.

Paillier Threshold Encryption Scheme

  1. (\mathsf{pk}, \mathsf{vk}, \mathsf{sk}_1, \ldots, \mathsf{sk}_n)\gets\mathsf{PE.}\mathsf{Setup}(1^λ,t,n):
    • Choose N=pq, for p,q primes such that p=2p'+1 and q=2q'+1 and \gcd(N, \varphi(N))=1. Define m=p'q' and \Delta=n!
    • Sample \beta\gets\mathbb{Z}_N^* and (a,b)\gets \mathbb{Z}_N^*\times \mathbb{Z}_N^*. Set g=(1+N)^a\times b^N mod N^2
    • Define \mathsf{sk}=\beta m and share it using Shamir through the polynomial h(X)=\sum_{i=0}^{t-1} h_iX^i where h_0=\beta m. i.e., \mathsf{sk}_i=h(i) mod Nm.
    • Set d=am\beta mod N
    • \mathsf{vk}=v, a square that generates the cyclic group of squares in \mathbb{Z}_{N^2}^*. \mathsf{vk}_i=v^{\Delta \mathsf{sk}_i} mod N^2
    • \mathsf{pk}=(N,g, d)
    • Output (\mathsf{pk}, \mathsf{vk}, (\mathsf{sk}_i, \mathsf{vk}_i)_{i=1}^n)
  2. \mathsf{PE.}\mathsf{Enc}(\mathsf{pk},msg)
    • r\gets\mathbb{Z}_N^*
    • \mathsf{ct}=g^{msg}⋅r^N mod N^2
    • Output \mathsf{ct}
  3. \mathsf{PE.}\mathsf{ShareDec}(\mathsf{pk},i,\mathsf{sk}_i,\mathsf{ct})
    • \sigma_i=\mathsf{ct}^{2\Delta\mathsf{sk}_i} mod N^2
    • \pi_i=\mathsf{NIZK.Prove}(\mathsf{DLEq}(v,\mathsf{vk}_i,\mathsf{ct}^2, \sigma_i))
    • Output (\sigma_i, \pi_i)
  4. 1/0\gets\mathsf{PE.}\mathsf{ShareVerify}(\mathsf{pk},\mathsf{vk},\mathsf{ct},\sigma_i,\pi_i):
    • \mathsf{NIZK.Verify}(v,\mathsf{vk}_i,\mathsf{ct}^2, \sigma_i, \pi_i)
  5. msg/\bot\gets\mathsf{PE.}\mathsf{Combine}(\mathsf{pk}, \mathsf{vk}, \mathsf{ct}, \{\sigma_i, \pi_i\}_{i\in S}):
    • If |S|\leq t-1, output \bot
    • Else:
      • V=\prod_{i\in S} \sigma_i^{2 \Delta \lambda_i} mod N^2, where \lambda_i=\prod_{j\in S\setminus\{i\}}\frac{j}{j-i} are the Lagrange interpolation coefficients at 0 for the set S, i.e. h(0)=\sum_{i\in S}\lambda_i h(i)
      • msg=\frac{V-1}{N}⋅\frac{1}{4\Delta^2d} mod N

Adding Traceability

To support traceability, we first modify the above Paillier threshold scheme with random evaluation points, i.e. party i now gets (x_i , h(x_i)) as its key share, where x_i is randomly sampled, instead of (i, h(i)) as in \mathsf{PE.Setup}. Accordingly, \Delta becomes the product of all pairwise differences i.e. \Pi_{i \neq j} (x_i - x_j), \mathsf{sk}_i=h(x_i), \mathsf{vk}_i=v^{\Delta h(x_i)}, and the Lagrange coefficients in \mathsf{Combine} are computed over the points x_i instead of i.

Next, we describe the tracing algorithm that turns the threshold Paillier scheme into an accountable one. Informally, it treats the leaked partial decoder as a stateless oracle, queries it on carefully related decryption shares, and uses the difference between the outputs to recover algebraic information about the shares embedded in the decoder.

For now, let us assume a trusted party acts as the tracer and is given access to the tracing key and we assume a perfect decoder box as defined above. We also assume f=t-1 for simplicity, and let \mathcal{I}\subseteq[n], with |\mathcal{I}|=t-1, denote the set of corrupt parties whose shares (x_i, y_i = h(x_i)), for i\in\mathcal{I}, are embedded in the box.

  • \mathsf{TS.}\mathsf{Setup}(1^λ,t,n) additionally outputs a tracing key \mathsf{tk}. This key contains the x_i values for all n parties, a trapdoor for the \mathsf{DLEq} NIZK proof, along with valid decryption shares at random points for t random ciphertexts z_1,\ldots,z_t. Let us denote these as \{x'_s, z_s^{2 \Delta h(x'_s)}\}_{s \in [t]}.
  • \mathcal{I}' \gets \mathsf{TS.}\mathsf{Trace}^D(\mathsf{tk}):
    • For s=1,\ldots, t:
      1. Input (z_s, (x'_{s}, z_s^{2 \Delta h(x'_s)})) to the box D, along with a NIZK proof of it being a valid decryption share generated using the trapdoor. Let the output of D be w. Since D is perfect, we have $$w = \frac{L_N (z_s^{4\Delta^2 \cdot \beta \cdot m}) }{4 \Delta^2 d } \text{ mod } N$$ where L_N(x) = ((x \bmod N^2) - 1)/N.
      2. Input (z_s, (x'_{s}, z_s^{2 \Delta h(x'_s)}) \cdot (1+N)^{2\Delta} ) to the box, along with a NIZK proof of validity, again generated using the trapdoor. Let w' denote the output of D. Since the box is perfect, we have $$w’ = \frac{L_N \left( z_s^{4\Delta^2 \cdot \beta \cdot m } \cdot (1+N)^{4 \Delta^2 \lambda’_s} \right) }{4\Delta^2d } \text{ mod } N = w + \frac{\lambda’_s}{d}$$ where \lambda'_s=\prod_{i\in\mathcal{I}}\frac{x_i}{x_i-x'_s} is the Lagrange interpolation coefficient at 0 of the point x'_s with respect to the set \{x_i\}_{i\in\mathcal{I}}\cup\{x'_s\}.
      3. Observe that (w' - w)^{-1} = d \cdot \prod_{i\in\mathcal{I}}\frac{x_i-x'_s}{x_i} \mod N. Let us denote this as y'_s.
    • Define a polynomial R(X) = d \cdot \prod_{i \in \mathcal{I}} \frac{x_i - X}{x_i} \in \mathbb{Z}_N[X]. Hence, the tuples (x'_s,y'_s) computed in the last step are evaluations of this polynomial at points x'_s. Moreover, the x_i values of the corrupt parties are roots of this polynomial.
    • Interpolate R(X) from the t points (x'_s, y'_s)_{s\in[t]}; since R has degree t-1, these points determine it uniquely.
    • For all i \in [n], if x_i is a root of R(X), then add it to \mathcal{I}'. Formally, output \mathcal{I}'=\{i\in[n]: R(x_i)=0\}.

The full construction can be found in BPR25 along with details on how to generalize the above to trace imperfect boxes and the formal security proofs.

Part III: Limitations and Open Problems

The construction above should be seen as a first step toward accountable encrypted mempools, rather than a complete deployment-ready solution. Several parts of the setting still need to be understood better.

Trusted Setup

The scheme relies on a trusted setup that generates both the committee keys and the tracing key. This makes the party very powerful. Since it generates the committee keys, it could decrypt transactions early and perform the same MEV attacks that the scheme is meant to deter. It could also decrypt on behalf of any committee member and falsely accuse them by placing them in the set of dishonest parties. Finally, using the tracing trapdoor, it may be able to produce invalid decryption shares that still verify. A natural question is whether this role can be distributed, made publicly verifiable, or replaced by a weaker trust assumption.

Can the tracer be a committee member?

One possible direction is to let a randomly chosen committee member act as the tracer. This party could sample the tracing trapdoor and publish the corresponding public information. However, the tracing procedure also needs suitable challenge ciphertexts and corresponding decryption-share information. It is not yet clear who should generate these values.

Can users trace their own ciphertexts?

Another appealing goal is user-side tracing: a user whose transaction was encrypted may want to trace a misbehaving committee for that specific ciphertext. This would make accountability more direct, since the affected user could initiate tracing for their own transaction, though it is unclear how the users can trace without access to the trapdoor.

Tracing boxes that output partial decryption

The approach outlined above only works if the decoder box outputs the fully decrypted message. It would be interesting to extend these ideas to also trace boxes that only output one bit about the message.

Tracing stateful boxes

Our approach requires the tracer to make multiple queries to the decoder box. In particular, this means that we cannot trace stateful boxes, e.g. if the colluding parties offer an anonymous decryption service using their decryption shares, wherein they keep a record of all prior queries, then our technique would break down. We leave the question of tracing such stateful boxes as a future direction.

Post-quantum security

Our scheme relies on factoring-based assumptions, which can be broken by a quantum computer. Another interesting direction would be to construct accountable threshold encryption from post-quantum secure assumptions.