Towards Encrypted Mempools from Threshold IBE without Batching

Cryptography
1

Towards Encrypted Mempools from Threshold IBE without Batching

Thanks to @b-wagn, @aelowsson and Jan Bormet for helpful feedback and discussions.

TL;DR

  • We sketch an encrypted mempool for Ethereum that requires threshold IBE without batch decryption. Dropping the batching requirement enlarges the space of threshold schemes we could build on.

  • The idea: a FOCIL-like ticket, inspired by LUCID, lands on-chain first and pins execution to a known future block. Only then does the sender encrypt, towards the identity id given by the blockhash of the ticket-carrying block B[n]. Since the identity is already known when we encrypt, plain threshold IBE suffices: nobody has to agree on a set of ciphertexts at decryption time. Using the blockhash rather than the slot number binds the encrypted transaction to one fork, so a reorg invalidates that encrypted transaction.

  • Three blocks: the ticket is included in B[n]; the ePBS payload timeliness committee (PTC) votes per ticket on whether it saw a valid encrypted transaction etx by the payload deadline; B[n+1] commits an etx_seen bitfield constrained by those votes, after which the threshold committee releases shares of the decryption key sk_id belonging to id; B[n+2] contains sk_id together with the decrypted transactions top-of-block, in the order of the tickets in B[n].

  • Why the extra round: binding etx_seen in consensus ensures that no builder ever makes an include-or-exclude decision that could depend on encrypted content. The price is one additional consensus round and a fixed two-block delay.

  • Failure cases: for honest users under normal conditions, an encrypted transaction that does not make it on-chain stays private, and we aim to prevent inclusion once the content has been revealed prematurely, so that the optionality returns to the user. Under exceptional conditions — deep reorgs, or a threshold committee that stops releasing keys — we accept and mitigate some failures rather than prevent them; to ensure dynamic availability survives even in exceptional conditions (such as a large fraction of attestors going offline), we include a circuit breaker that turns off the encrypted mempool.

  • Caveat: we know of no threshold IBE scheme that meets our requirements — post-quantum security in particular. This post is therefore a design sketch meant to inform future constructions, not a spec.

Encrypted Mempools

The problem of encrypted mempools has garnered some attention lately, in particular with the proposal of LUCID. See, e.g. this post explaining why the underlying problem is of significant importance. Unfortunately, the dream solutions to this problem seem to require cryptographic tools, namely some form of good enough threshold encryption that we do not know how to construct (yet?), at least not within our constraints for efficiency, bandwidth, security (including security against quantum computers), etc.

For that reason, LUCID basically forgoes aiming for such a solution in-protocol and instead proposes an encrypted mempool design that tries to be the best we can do with the cryptography of today, the price being having to deal with certain optionality issues and countermeasures to those issues that may or may not be acceptable.

Part of the reason why we cannot go for the dream solution is that the list of requirements and desiderata on the threshold encryption schemes is quite extensive.

So, in this post, we try to make some progress from a different angle: we aim to construct an encrypted mempool from a threshold encryption scheme with reduced requirements. Namely, we try to do without batch decryption. Unfortunately, even without the batch decryption requirement, we still do not have a perfect solution, mostly due to the requirement of being post-quantum secure. However, we hope that this will inspire further research in that direction; lowering the requirements enlarges the solution space.

Our construction combines the properties of IBE with pending transaction privacy. I.e., we can decrypt all transactions encrypted for a given block at once, with the additional guarantee that, for honest users, transactions that do not (yet) make it from the mempool on-chain remain private.

Structure of this post

Due to the fact that we do not have a suitable threshold encryption scheme ready for our construction here, we shall make no attempt at providing a full spec, as that would likely require adjustments to the concrete threshold encryption scheme and its limitations. The construction is already quite complicated. Instead, we hope that this construction may be used as a starting point if we ever have a sufficiently good threshold scheme. Since the goal of this post is to inspire future solutions and research, we will spend considerable time explaining and exploring the background and the "why"s of our various design choices, to preserve those learnings for the future at the expense of being intentionally vague elsewhere.

The rest of this post is structured as follows.

Goals of Encrypted Mempools

Roughly speaking, the goal of an encrypted mempool is to provide a way for users to submit a transaction tx and eventually have tx included on-chain and finalized, where the content (and possibly sender) of tx remains hidden until it is included.

In particular, other parties should not be able to submit other transactions tx' (e.g. a frontrunning transaction) that get executed before tx and that depend on the content of tx. Such a dependency might be either that the validity of tx' depends on the content of tx or that the actions taken (including whether any action is taken at all) by tx' depend on the content of tx. We shall make no security proofs or a formal model in this post and mostly stick to this rough intuition.

However, there is some subtlety about what happens with transactions that don’t make it on-chain and it is helpful to look at the relevant failure/success modes:

  • A: The content of tx gets revealed prematurely and then makes it on-chain

  • B: The content of tx gets revealed prematurely, but does not make it on-chain

  • C: The content of tx does not get revealed prematurely and does not make it on-chain

  • D: The content of tx does not get revealed prematurely and tx makes it on-chain

Here, “tx makes it on-chain” means that the transaction is included and its content is executed; we assume that execution requires decryption, so the content of tx needs to be available at the point of on-chain inclusion.

Premature reveal means that the content of tx is revealed in a way that allows an attacker to submit a transaction tx' that depends on the content of tx and is executed before tx, as explained above.

We consider these cases to be in descending order of badness: A > B > C > D, with D being the success case. In particular, if a transaction somehow gets revealed prematurely, we want to prevent inclusion: this gives the option of whether to resubmit or not back to the user. Our protocol needs to make sure that others cannot resubmit, so we need to take care about replay protection. Our protocol is not able to fully prevent all failure cases, but rather restrict them to certain exceptional cases.

Notably, we need to care about cases where a deep re-org undoes inclusion of an encrypted transaction after its decryption, leading to case A or B, depending on whether the transaction can be replayed. We also have to think about what happens if a significant fraction of validators suddenly goes offline, possibly along with a finality crisis and inactivity leaks triggering. Threshold encryption (and its variants) require some threshold from a committee to cooperate in order to facilitate decryption. In our case, such a committee would consist of (possibly all) validators, so the required threshold to decrypt may no longer be reachable, hence this will lead to failure case C. Remember that one of Ethereum’s tenets is dynamic availability, i.e., we still want to produce blocks even if we (temporarily) lose finality and then hopefully recover. This means we need to seriously consider such situations and make sure that an encrypted mempool design does not stop dynamic availability.

We take the pragmatic approach of accepting some failures in such exceptional situations and mitigate instead of prevent them, provided we have a good understanding of the circumstances that could trigger them. We discuss the reorg cases in Reorgs and the case of a threshold committee that stops producing decryption keys in Circuit Breaker.

Threshold Encryption, IBE and Batching

Threshold Encryption

Let us give a brief (and heavily simplified) explanation of threshold (identity-based) encryption and what batching means in this context. See e.g. ePrint 2025/1665 or Stanford CT-RSA’06 for a more formal treatment, actual definitions and missing details.

We also refer to an upcoming interactive website by Jan Bormet, which explains various security notions and desirable properties of threshold encryption schemes and gives an overview of various constructions from the literature, together with which of those properties they have. That website is not online yet; we will post a link to it as a reply to this post as soon as it is available.

Consider a (non-threshold) public key encryption scheme at first: such a scheme allows to encrypt a message m wrt. a public key pk to obtain some ciphertext c. Whoever holds the corresponding secret key sk can decrypt c to get m.

In a threshold encryption scheme with threshold t, we replace the single secret key sk by a list sk_1,\ldots, sk_N of key shares held by different parties P_1,\ldots,P_N. Any coalition of parties holding at least t key shares can then jointly decrypt the ciphertext, but any coalition holding only t-1 should not be able to.

For our encrypted mempool applications, we can use such a scheme to encrypt a transaction tx while it is in the mempool. We then rely on a committee of decryptors, each holding a single key share, to decrypt. By using a committee rather than a single entity, we avoid a single point of failure (a single entity could refuse to decrypt) and we retain privacy prior to decryption as long as a sufficient fraction of the committee is honest.

Let us discuss several properties of such threshold encryption schemes and what they mean for encrypted mempools (again, see the upcoming website mentioned above for more details):

  • We need some way to securely generate the individual secret key shares sk_1,\ldots,sk_N and the public key pk. Depending on the scheme used, this may involve (a) some expensive one-time setup that does not depend on the actual parties or eventual keys and/or (b) some expensive interactive protocol among the N parties that will hold the keys. We want to particularly avoid the latter (i.e. we want a scheme with so-called silent setup). This setup cost may put severe limits on N and the ability to rotate the committee of decryptors in our application.

  • We need the scheme to have the appropriate notion (there are several) and level of security for our application. To avoid having to redesign the protocol, we want the scheme to be post-quantum secure, which greatly limits our options.

  • The amount of interaction in the decryption process should be limited: rather than allowing an arbitrary interactive protocol, we want each party P_i to produce a partial decryption m_i, given c,sk_i and public data, without interacting with the other P_j's. Then, the final decryption m should be efficiently and publicly computable from sufficiently many such partial decryptions m_i (and c and public data).

  • The scheme needs to be efficient enough for our applications, especially regarding bandwidth.

  • To compute the final decryption, we need to collect at least t partial decryptions. Assuming t=\Theta(N), this means that the bandwidth requirement for the party that computes m is linear in N (or worse, if the sizes of the individual m_i scale with N). Depending on the encrypted mempool design, we may need to actually broadcast each m_i to the whole network. Even worse, this cost has to be paid separately for each ciphertext, so the bandwidth requirement per slot is also linear in the number of encrypted transactions executed per slot.

Batching

To overcome the bandwidth issue from the last bullet above, some threshold encryption schemes support some form of so-called batching, which allows decryption of a set of ciphertexts S in a way that is more efficient than individual decryption[1].

Threshold Identity-Based Encryption

In a threshold identity-based encryption (TIBE) scheme, we can encrypt a message m wrt. a public key pk (associated to a decryption committee) and an identity id. We note that calling id an identity is due to the original usage scenarios of IBE; generally, id is an arbitrary identifier (a block hash, in our case) that does not need to be related to identities.

Similar to threshold encryption, we have a decryption committee, where each member P_i holds a (now called master) key share msk_i. A coalition of t committee members (but not t-1) can jointly compute a decryption key sk_id that allows to decrypt every message that was encrypted towards that identity id.

From the lens of threshold encryption, this can be viewed as a very restricted form of batching, where the sets S of ciphertexts to be decrypted in one go are those that were encrypted towards a given identity id. The key differences are:

  • The decision on which ciphertexts are to be decrypted simultaneously is made already at the time of encryption by the encryptors rather than by the committee at the time of decryption.

  • We require each committee member to output a share of a decryption key sk_id that can be publicly aggregated into sk_id, i.e. we impose the same limits on interaction as before. However, note that the committee members only require id as input, but not the encrypted messages.

  • The appropriate security notions need to take released keys sk_id into account: messages encrypted wrt. an identity id should remain private, even if secret keys for other (adaptively chosen) identities are revealed.

Why is Constructing an Encrypted Mempool from Threshold IBE Difficult?

Before we present our concrete protocol draft, it is instructive to look at a simple solution and why it fails: assume that we have a threshold IBE scheme and committee set up. To send an encrypted transaction tx, the sender selects a future slot number n and threshold IBE-encrypts tx wrt id=n. During each slot n, once the list of transactions executed in the block is fixed, the threshold IBE committee publishes sk_n. Then everyone can decrypt tx and we can include it top-of-block of slot n+1.

There are several issues with this naive approach:

  • We need to take care of the ordering of execution of encrypted transactions. Notably, the builder must not be able to order the transaction depending on the transaction content. So we need to somehow determine and agree on the order of execution before decryption, which requires some information about the set of encrypted transactions to be on-chain even before decryption.

  • We need to take into consideration that transactions may not get included at all (e.g. due to gas limits we might just not be able to). In particular, the builder must not be able to decide whether to include an (encrypted) transaction or not depending on the content of (possibly other) encrypted transactions executed in the same block. Even if the builder opts to not include a transaction, the released sk_n still allows to decrypt the transaction, so we are in failure case B (or A, if the transaction can get included later).

Rough Idea

In order to solve the above issues, we take the following design idea, inspired by LUCID: we use a FOCIL-like mechanism that guarantees inclusion of the transaction at a specific point in time, provided the transaction sender adheres to the protocol. Importantly, we only publish the ciphertext once we have obtained such an inclusion guarantee. This way, we avoid the failure case B issue that the naive solution has. Fixing the ordering of executions of encrypted transactions ahead of time comes essentially for free. Other than that, we very roughly follow the basic idea of the naive scheme.

More specifically, to send an encrypted transaction, the sender starts by buying a transaction ticket: this is a specific transaction type that, once it lands on chain, reserves some gas in one of the following blocks (more precisely, 2 blocks later) and guarantees inclusion there. The ticket is bound via hiding commitments to the actual transaction content.

Only once the ticket lands on chain do we actually encrypt and broadcast the transaction as an encrypted transaction etx. This is because only then do we know id. To avoid issues with reorgs, we use as id not the slot number, but rather the blockhash of the block that includes the ticket: this serves to invalidate the transaction should the ticket-carrying block get reorged.

To make this work, we now need to somehow guarantee that etx gets decrypted and included on chain. An issue that arises now is that we only can make this guarantee if etx actually is broadcast: so we need some way to detect whether etx was made sufficiently widely available. Fortunately, Ethereum already has some infrastructure in place (as part of ePBS) for precisely this type of task: the PTC (Payload Timeliness Committee). This committee shall vote on whether etx was made available: if yes, then the transaction should be decrypted and included and we shall force a future builder to do so. If no, we must not force a future builder to do so (because they might not be able to and we do not want to halt the chain).

A subtle issue that arises here is that we must not leave any include-or-not decision to the builder that eventually includes the decrypted transaction, particularly not after they learn the key. Furthermore, adherence to this forced inclusion (or not) is enforced via fork-choice rule. As a consequence, we need to have consensus about the PTC vote. For that reason, we actually need an extra round of the consensus protocol and the beacon block immediately following the block containing the ticket shall not yet include the decrypted transactions, but rather a bitfield of which etx shall actually be decrypted. This bitfield is bound to the PTC vote, but its construction needs to have some leeway (to account, e.g. for equivocations by the PTC or for PTC votes not reaching everyone on time). These rules serve the purpose that

  • An honest sender should be able to reach the quorum to enforce inclusion.

  • We do not enforce inclusion of a transaction that was being withheld.

There are multiple voting rules that seem to work. For instance, we could use a strategy similar to LUCID. Or we could use something like the following strawman rule:

If >80\% of the PTC vote to have seen etx, the bitfield needs to include it and if <40\% of the PTC vote for it, the bitfield must not include it.[2] In-between, it is at the builder’s discretion.

Only after this bitfield has been committed to, the key for the threshold encryption is revealed and the next builder will include the (decrypted) transaction in the next block payload. A consequence of the extra round is that if a ticket appears in a beacon block, then the actual transaction will appear in the payload of the block 2 blocks later.

Lifecycle of an Encrypted Transaction

We now sketch how the lifecycle of an encrypted transaction is supposed to look like in more detail, with a focus on the happy path and with some simplifications:

Throughout, B[n], B[n+1] and B[n+2] denote consecutive (non-empty) beacon blocks rather than slots: empty/missed slots are simply skipped, so B[n+1] is the next beacon block that actually exists after B[n] and need not be the beacon block for slot n+1. Of course, on the happy path, it is. We come back to this in Failures Due to Missed Slots.

In our design, special care needs to be applied when handling various nonces. To remain future-compatible, our treatment here assumes that we have EIP-8250: keyed nonces active, so transactions can have multiple (keyed) nonces.

The figure below gives an overview of the whole lifecycle; we refer back to it throughout this section.

Lifecycle of an encrypted transaction
Lifecycle of an encrypted transaction1315×554 84.3 KB

Lifecycle of an encrypted transaction.

Let us assume that we have somehow performed the necessary setup for a threshold IBE scheme with a decryption committee with N members. Canonically, those members are sampled from the set of validators, but our design does not really require that. To what extent and how frequently we can rotate the committee and how large N can be depends on the (efficiency of the) scheme; for simplicity, we assume that the committee is fixed and N is moderately sized, say N\in\{128,256\}. In particular, we shall not assume that the committee is the full validator set (this would considerably open up the design space and simplify things).

Assume that some party P wants to send a (raw) transaction raw_tx from sender. Here, raw_tx denotes the raw plaintext transaction, excluding nonce(s) and signature. In order to get anything on chain (and pay gas fees), we need to assume that the party also has some way to pay gas fees prior to decryption. If we want to hide sender, this gas payment should not be linkable to sender; for simplicity, assume that P has an address ticket_address (which may or may not be the same as sender) from which P pays gas. Note that this implicitly means that sender and ticket_address trust each other fully.

To start, P sends (via the standard, non-encrypted mempool) a special type of transaction, called a ticket, containing the following data:

ticket:

  • a hiding commitment com_raw to the triple (raw_tx, sender, tx_nonces)

  • data about (maximum) gas usage data / how much the sender is willing to pay

  • some variant of priority_fee, i.e. some information about how much the sender is willing to pay for their transaction to be executed earlier (required for deterministic transaction ordering)

  • ticket_spending_key a fresh public key of a one-time signature scheme, used to spend the ticket.

  • Optional excess_gas_refund_address (if not given, will default to sender later)

  • All the above is authenticated by ticket_address.

Such a ticket constitutes a regular (nonce-consuming) transaction of its own type and is treated and broadcast accordingly. Note that it is a relatively small object and as such is (in a post-ePBS world) treated and broadcast as part of the beacon block.

Let us assume that ticket eventually gets included in beacon block B[n] at slot n. The ordering of tickets determines the eventual ordering of the transaction execution and may be bound to how much the sender has specified they are willing to pay.

Then, during that slot, after receiving the beacon block, P encrypts and broadcasts the encrypted transaction etx. Such an encrypted transaction contains the following data:

etx:

  • an encryption ct of tx_env under the public key of the threshold committee responsible for slot n, with identity id given by the blockhash of B[n]. Here tx_env is some kind of transaction envelope defined below.

  • A reference to the ticket within B[n], say the index in the list of tickets and the blockhash of B[n].

  • All of the above is signed by ticket_spending_key of the corresponding ticket.

The transaction envelope contains the following data:

tx_env:

  • an opening of com_raw to (raw_tx, sender, tx_nonces).

  • a reference ticket_nonce_reference to the nonce(s) used in the ticket transaction.

  • some domain separator

  • All of the above is signed by sender.

Each member of the PTC for slot n votes for each ticket in beacon block B[n] whether it received some valid etx for this ticket by the payload deadline or not. In this context, validity of etx means that the signature verifies against ticket_spending_key and that the gas paid by the ticket is at least sufficient for the calldata + decryption (this only depends on the length of etx). We only expect one valid etx per ticket and only forward at most 2 different valid etx per ticket (2 different valid etx serve as proof of equivocation). PTC members vote for not having seen etx if they have proof of equivocation. For efficiency reasons, PTC members cast a single vote on a bitfield to vote for each ticket in B[n] at once.

As described here, this means that propagation of etx, which may be large, is on the critical path. This is purely for simplicity of exposition. See the discussion on key encapsulation below on how to avoid that.

In the next beacon block B[n+1], the proposer then includes an etx_seen bitfield that selects the subset of the tickets from the parent block B[n] for which a valid etx has been broadcast.

The proposer must include any ticket in the etx_seen bitfield that a large fraction of the PTC voted for and must not include any ticket that a large fraction did not vote for. This is enforced by fork choice / consensus rules.

Notably, a validator V must not attest to a block if its etx_seen bitfield

  • includes a ticket for which V has not seen a valid etx.

  • includes a ticket, but V has seen less than some fixed fraction (say 40%) of the PTC vote for “seen”.

  • does not include a ticket, but V has seen more than some fixed fraction (say 80%) of the PTC vote for “seen”.

Once the beacon block B[n+1] has been committed to, during payload dissemination of slot n+1, each member of the threshold committee responsible for slot n either releases its key share for id given by the blockhash of B[n] or an explicit (signed) message indicating that this committee member won’t release a key. Note that honest committee members C only release keys for B[n] if

  • B[n] is contained in C's preferred fork by the fork-choice rules.

  • B[n+1] has sufficiently many attestation votes (essentially looking at some form of fast confirmation rule). Otherwise C votes for “no key release”. Note that these attestations also vouch for validity of etx_seen.

  • C deems the etx_seen bitfield in B[n+1] valid. Otherwise, C votes for “no key release”.

Next, in beacon block B[n+2], if the parent block’s etx_seen bitfield has any bits set, the proposer must include either the reconstructed key sk_id allowing decryption of threshold encrypted ciphertexts encrypted against id given by the blockhash of B[n] or signed messages from sufficiently many threshold committee members indicating that those did not wish to release a key (see Refusal to Reveal a Key).

In the latter case, we do not include any decrypted transactions. If we have a (valid) decryption key sk_id, then the encrypted transactions selected via the parent block’s etx_seen bitfield must be included top-of-block in the payload of slot n+2 in the order determined by the order of the tickets in B[n]. Tickets from B[n] which were not selected by etx_seen must not be included.

While the decrypted tx_env is included in the payload of slot n+2 unconditionally, actual execution of the transaction is conditional on further validity checks: we check that the decryption was done correctly, opening of com_raw is valid, the ticket_nonce_reference matches the nonce(s) used in the ticket and we check the signature and tx_nonces. Here, tx_nonces are the EIP-8250 style keyed nonces that are checked and incremented for execution of raw_tx. As opposed to the usual behaviour, we allow and default to an empty tx_nonces here: we do not default to the legacy account nonce of sender and, by default, no nonce is consumed at all. In particular, pre-EIP-8250, we do not need tx_nonces at all.

The gas used for executing raw_tx (including cost for calldata and decryption) was already paid for by the ticket. Any excess gas is returned to excess_gas_refund_address specified by the ticket. If we run out of gas, the transaction reverts. Note that we are guaranteed that we have enough gas for calldata.

We recommend including information about failure cases (e.g. if a tx_env is invalid and why) in the beacon block.

Rationale and Further Details

We now give some more details of this construction and explain why certain choices were made.

Pending Transaction Privacy

The idea to use a transaction ticket essentially follows LUCID and is needed to pin the actual transaction execution to a predictable target block (2 blocks from inclusion of the ticket in our design). As long as the ticket is not included on-chain, we do not send the encrypted transaction and only a hiding commitment is public. The ticket transaction itself is (as far as mempool considerations are concerned) essentially just a normal transaction of a special type.

Gas Accounting

When including the ticket, we also charge up-front the gas for the eventual execution + calldata cost + decryption cost, an amount that we dub reserved_gas, but this should not count against the gas limit of slot n itself. We also separately charge calldata for the ticket in B[n], which does count against the gas limit of slot n. The total amount of gas that is reserved for delayed execution via this mechanism must be limited and we also need to ensure that regular transactions can still get through. So we need to impose a limit on the amount of reserved_gas that is a fraction of the total gas limit (similar to LUCID).

Note that there is the question of whether this reserved_gas should be ETH-denominated or gas-denominated at this point, i.e. whether we take the gas price at the slot where the ticket is included or when the eventual execution takes place. Both choices are possible (essentially, since we can bound the gas price fluctuation) and we leave this open, but using the gas price at the ticket inclusion time is much simpler: the reason is that it becomes much easier to guarantee that the gas is sufficient for at least the cost of decryption + calldata.

The reason that excess_gas_refund_address defaults to sender (rather than ticket_address) is that it is always possible to just set excess_gas_refund_address=ticket_address manually. However, sender is hidden, so we want a way for P to get refunds into sender later without revealing sender at this point in time.

Privacy Pools and Frame Support

While the ticket_address may be the same as the sender, users who want to keep sender hidden until execution will need to pay gas in a way that can not be linked to sender. There are various ways to do that such as paying via an external party (which adds trust assumptions) or using a one-time unlinkable address. The most elegant way would be to pay directly from a privacy pool. To this end, note that the design actually allows using custom validation logic: basically, the ticket could be bought by a frame of a frame transaction in the sense of EIP-8141, i.e. a transaction that is decomposed into a sequence of frames — contract calls that validate the transaction, approve gas payment and execute the actual user operations — so that validity and gas payment can be defined abstractly. Since frames execute as part of payload processing, the authentication and gas-payment logic would in this case sit in its own frame in the payload of slot n, while another frame of the same frame transaction is the one that buys the ticket and references the ticket in the beacon block. Only the ticket itself is in the beacon block. Also, we want compatibility with EIP-8250-style keyed nonces, precisely to support paying directly from a privacy pool: there, the paying address is shared between many users, so a single sequential account nonce would make concurrent spenders race for the next nonce value. Keyed nonces let each user pick an essentially independent nonce key, which in particular keeps the ticket_nonce_reference that sender has to sign in tx_env predictable before the ticket is on-chain.

Why Use a One-Time Signature to Spend the Ticket?

The actual encrypted transaction etx is signed by a one-time signature with public key ticket_spending_key that is tied to the ticket. While we could in principle use the ticket_address again to authenticate, we use a fresh one-time signature instead. This has the following three reasons:

  • As we mentioned above, we envision use cases where we have custom validation logic to authenticate the gas payment (such as frame transactions). This would not work very well for authenticating etx in the same fashion, since there is nothing that is actually being executed in the context of the etx.

  • Even if we had a way to execute arbitrary validation logic, the validation of etx needs to be fast, since propagation is latency critical. We also want the cost of this validation to be predictable for gas accounting purposes.

  • Producing authentication via ticket_address might have a large latency from the user’s side: for example, imagine that ticket_address is a regular EOA and the user stores the signing keys for ticket_address on a hardware wallet. Producing etx is only possible once B[n] is known; signing and broadcasting it is latency-critical and there is no time to use a hardware wallet here. With our design with a ticket_spending_key, we only have to touch (the signing keys of) both ticket_address and sender once each, both in a non-latency-critical way. We can then store the secret key to the ephemeral ticket_spending_key in the browser / whatever is used to monitor the chain for inclusion of the ticket. Observe that, as opposed to the ticket_address or sender keying material, the secret key for ticket_spending_key is actually very low-value: all an adversary can do with it is to equivocate etx and thereby prevent the transaction from being executed (and wasting the user’s gas). In particular, the adversary cannot sign an arbitrary transaction and have it executed, since the ticket contains a commitment to raw_tx.

Tying the TIBE-Identity to a Blockhash

Note that we encrypt etx with respect to id given by the blockhash of B[n] rather than the slot number. This has the advantage that we can tie the decryption key release to the block: an honest threshold decryption committee member will only release keys for a block that its own fork-choice prefers. In particular, the block B[n] must be valid. This behaves better in case of reorgs, since etx is bound to a particular fork. We note that the party P using the encrypted mempool has the option not to broadcast etx. However, this does not constitute the same kind of optionality that designs such as LUCID suffer from: the point is that this decision can not be made dependent on the content of other’s encrypted transactions. Also, P can simply send an (unencrypted) transaction to be included in slot n+1, which may write data that the encrypted transaction reads. In particular, the raw transaction raw_tx that was sent via the encrypted mempool and executes in slot n+2 could read data y from some predefined address, decrypt y with a key hardcoded in raw_tx (which is hidden until execution) into x and make its execution dependent on x.

Key Encapsulation to Avoid Sending the Full Transaction on the Critical Path

In the above presentation, we assumed that P encrypts tx_env as soon as P learns that the ticket has been included. We assume that an honest P is actually able to disseminate etx in a way that will make most PTC members vote for having seen it and thereby enforce execution of the (decrypted) raw_tx. Note that this happens before P can be sure whether the block containing the ticket is valid, but this does not matter, since we will never release keys that could decrypt etx for such an invalid block. The dissemination of etx itself is latency critical. We note here that, similar to LUCID, there is an important optimization here: we can disseminate an encryption c of tx_env wrt. a fresh key k of an appropriate symmetric encryption scheme alongside the ticket ahead of time. Then we only have to encrypt/encapsulate k using the threshold scheme instead of encrypting the large tx_env. This means that the ticket needs an additional field that commits to c, which is disseminated as a sidecar. etx then contains an encryption of k instead of an encryption of tx_env. The PTC vote is for having seen both c and ct.

Leeway in the PTC Votes

We note that we cannot guarantee that every validator sees the same votes from the PTC members due to latency and because PTC members might equivocate. This is the reason why the rules of when to include a ticket in the etx_seen bitfield have some leeway where the proposer of block B[n+1] may have a choice of whether to include a ticket or not: this is to make sure that the proposer can construct an etx_seen bitfield that all (honest) validators consider valid, even if different honest validators have (slightly!) different views on the PTC votes. We stress that if P acts honestly and a high fraction of the PTC is honest, there is actually no choice whether to include P's transactions. In our design, we essentially assume that if a high fraction (such as 80%) of the PTC vote for having seen etx by the PTC deadline of slot n, then etx will be available to everyone by the time B[n+1] and the etx_seen bitfield is disseminated. Conversely, we need to make sure that the proposer of block B[n+1] is not able to include a transaction into etx_seen which has not been made widely available, since this would prevent the construction of a valid block in slot n+2.

The reason why availability matters this much is that the actual transactions only live in the mempool until the point where they are included in the payload of slot n+2. All validators need to decrypt and check that the result matches what was included on-chain. In particular, validators need etx to make those checks, which is why we need to ensure availability.

Nonces and Domain Separator

Regarding the transaction envelope tx_env format, we note that there is a ticket_nonce_reference and a domain separator, and that the execution of raw_tx itself consumes no nonces. Let us explain why.

  • The domain separator serves to ensure that a (decrypted and) signed tx_env cannot be replayed as a regular transaction, but is only valid as (decrypted) transaction sent via the encrypted mempool. This is quite important, since it may happen that the tx_env get decrypted without execution in case dissemination of etx fails due to network issues; also, remember that execution of raw_tx itself consumes (by default) no nonces.

  • Not consuming a nonce simplifies usecases where we send a (regular, unencrypted) transaction between the ticket inclusion and execution of raw_tx. Such a transaction should not (by default) invalidate raw_tx. Also, we do not really need the same type of replay protection: the tx_env is tied to a particular ticket, which already does have replay protection.

  • As ticket_nonce_reference, we can take (a collision-resistant hash of) the list of nonce keys and values that the ticket-carrying transaction used. Note that, with frame transactions, if tickets are a type of frame, multiple tickets could use the same transaction, so have the same ticket_nonce_reference. By including and signing ticket_nonce_reference, we tie the tx_env to the state of the ticket_address when the latter sent the ticket. This essentially means that sender authorizes ticket_address to initiate a particular transaction as an encrypted transaction, where the authorization is bound to ticket_address’s nonce state.

  • We note that we need to make sure that tx_env can be produced before the hash of block B[n] is known and before the ticket makes it on-chain: encrypting tx_env is latency critical and producing tx_env involves secret keys of the sender, which might reside on a hardware-wallet.

Failures Due to Missed Slots

In the description we gave, a missed slot (including an invalid beacon block) is just skipped, i.e. the counting of blocks n, n+1, n+2 just ignores missed blocks and skips over them. Note that we do not send any new tickets, etx or release a new sk_id for a missed block, so there is no pileup of encrypted transactions here. The next non-missed block can in principle just contain new tickets. This non-missed slot will also contain the etx_seen bitfield, sk_id and decrypted transactions top-of-block of what should have been in the missed slot.

What is more interesting is the case of rejected payload, i.e. we reject a block/treat it as empty after a valid beacon block B was released, due to some issue with the actual payload: in this case, we publish some encryptions etx as a response to the tickets in the beacon block and we might publish decryption shares once the etx_seen bitfield was fixed.

Regarding new tickets, the inclusion of tickets in B becomes void[3], we don’t charge for those and we ignore any etx that reference those tickets by blockhash; note that we shall never decrypt those.

If the etx_seen bitfield of the block with rejected payload was valid, then the next (hopefully non-empty) block B' must contain the exact same etx_seen bitfield. Otherwise, it behaves like a missed slot, i.e., B' must decrypt and execute those transactions ToB, whose tickets are in B's grandparent and whose etx_seen bitfield is in B's parent block.

Observe that the key that is to be released in B' is actually the same as the one that may have been released in B. If it was already released in B, then the etx_seen bitfield in B must have been valid, so the etx_seen bitfield in B' must be the same and the builder of B' cannot choose it depending on sk_id and the transactions that can be decrypted with it.

Refusal to Reveal a Key

Recall that the threshold decryption committee can explicitly refuse to reveal a key. If enough members do that (the threshold for this case should be set such that we may assume that the key actually was not released, even tolerating a small fraction of malicious committee members), then the builder of the next block B is not obliged to include a decryption key and decrypted transactions.

If that happens, then we do not allow any new tickets in block B and do not include an etx_seen bitfield. Essentially, we treat it as a missed block as far as encrypted mempool transactions are concerned. Note that frame transactions that contain both transaction tickets and regular transactions become unincludable in B as a whole.

The next valid block B' that contains a decryption key will then again contain new tickets, an etx_seen bitfield and a key. This etx_seen bitfield references the parent of B and the key is for tickets from the grandparent of B.

Circuit Breaker

We note that there is an issue with our design if a large fraction of the threshold committee suddenly goes offline: we can no longer decrypt in that case and, due to the need to include decrypted transactions, this prevents us from building blocks. To avoid breaking liveness of the chain, we propose a circuit breaker:

  • If there were too many missed/rejected/key-refused slots in recent blocks, we must not include any new tickets. Key-refused means that the beacon block contains no key because the decryption commitee explicitly refused to release it.

  • If there were too many missed/rejected/key-refused in a row, we invalidate all pending encrypted transactions and refund their reserved gas.

The precise criteria of what is too many may weigh missed, rejected and key-refused slots differently. Note that, after triggering the second circuit breaker, the next block will treat its parent etx_seen bitfield as empty, so it does not need to include a decryption key.

Invalidating all pending encrypted transactions this way leads to failure case C and/or B. The latter happens if the decryption key that was supposed to be included in the next good slot was already released. While such failure cases are not ideal, they are tied to bad (overall) conditions of the blockchain and might be acceptable.

Gas is refunded to the address specified in excess_gas_refund_address. If it was unset (which normally defaults to sender), we default to ticket_address since the protocol does not know sender.

Note that a sequence of censoring proposers (not builders!) that refuse to release the block with the pending decrypted top-of-block transaction can intentionally trigger that circuit breaker. We deem that acceptable, provided the number of bad slots in a row that is required to trigger the circuit breaker is large enough.

Reorgs

Finally, let us consider what happens in case of reorgs. Such a reorg might affect the slot with the ticket and/or the slot with etx_seen. Note that the slot with the actual decryption does not really matter here (what happens there is determined by the previous slot and the key). We also assume that the encrypted target transaction tx that we want to protect broadcasts etx sufficiently well that etx_seen will always be forced to include it.

Before going through the individual cases, note that one mitigation applies to all of them: honest members of the threshold committee only release their key share if the block carrying etx_seen has sufficiently many attestation votes. In a reorg situation, the number of attestations that a committee member has seen for that block is typically low — although this is by no means guaranteed — so in most reorg scenarios no key is released at all and we end up in the milder failure case C. This gives a second line of defence that makes the attacks below considerably harder to pull off, without preventing them outright. Note, however, that once sk_id has been released, it is not tied to the fork that carried etx_seen: for reorgs that happen after B[n], the key can be used on both sides of the fork, even if the whole threshold decryption committee is on one side of the fork and believes that everything is fine.

Let us look at the relevant cases:

  • If a reorg invalidates the whole lifecycle of an encrypted transaction, i.e. reorgs out the ticket carrying transaction after we have released keys, we land in failure case B. There is not very much we can do against whole-lifecyle-reorgs; our design aims to at least prevent that the reorged encrypted transaction can be replayed on another fork after the contents are known (which would yield failure case A). This is why etx signs the blockhash of the ticket-carrying transaction.

  • If a reorg invalidates the ticket carrying transaction, but the key has not yet been released (and never will), then we end up in failure case C.

  • In case of a reorg between two forks with differing etx_seen and no missed slots, the two forks might differ in what (encrypted) transactions are executed before tx in the slot where decryption+execution happens. If an attacker can select which fork eventually finalizes after the decryption key is released, this leads to failure case A. Note that this attack involves equivocating etx_seen in the beacon block, which is attributable to the proposer and constitutes a slashable offence.

  • In case of a reorg between two forks with the same ticket-carrying block B, but a different number n_1 < n_2 of missed/rejected/keyless slots between B and the slot with etx_seen, the key is released in the fork with n_1 while in the fork with n_2 there is still a sequence of missing/rejected/keyless slots going on. An attacker can then select etx_seen (if they control the proposer) in the n_2 fork while having knowledge of the decrypted transactions. Even worse, they can just get an (unencrypted) transaction in the slot that contains etx_seen in the n_2 fork. If the n_2 fork eventually finalizes, we are in failure case A.

For the last case, one mitigation is that a user can optionally check inside their transaction whether the previous block was empty. However, this also reverts their transaction (and wastes gas) in benign cases.

Another mitigation is that we can tie the key release to the fork by essentially requiring the members of the threshold committee to attest in each slot (rather than once per epoch) and only considering a block that contains a released key valid if, in addition to the usual rules, it has attestations from a supermajority of the threshold committee. By doing so, we prevent block building in case of a split until the circuit breaker triggers.

Final Remarks

We want to stress again that the purpose of this design is to further research and showcase that batching might not be needed. It is not a proposal for such an encrypted mempool scheme to be implemented.

  1. Note that for batch decryption we also want stronger security notions: if, say, we use only t-1 key shares to partially decrypt a set S of ciphertexts and t-1 other key shares to decrypt a different set S' of ciphertexts, then the union of resulting partial decryptions should not allow to decrypt something in the intersection S ∩ S'. For the mempool design, this essentially means that the decryption committee needs to reach consensus on the set of to-be-decrypted ciphertexts rather than agree on each ciphertext individually. In fact, if we view providing a partial decryption for a particular set as a vote on that set, then voting (with the aim of reaching consensus) and broadcasting partial decryptions can be done simultaneously. This contrasts with the mempool design described in this post, where we vote (albeit with a different interpretation of what the vote means) on each individual ciphertext and separate the consensus from the decryption step. ↩︎

  2. As such a rule is to be enforced via fork choice (either via attestors or the next PTC), this really means that an attestor A will not attest / a member A of the next PTC will reject the block if the builder does not adhere to the rule. What matters for the rule is the (valid, non-equivocated) votes of PTC members that A has (locally) seen by some deadline. Note that as opposed to LUCID, our strawman rule only considers “seen” votes and looks at the fraction of “seen” votes relative to the committee size rather than “seen” votes minus “not seen” votes. This means that abstaining counts as “not seen”. ↩︎

  3. We note here that in case a transaction ticket is a special type of frame of a frame transaction, we might have custom authentication / payment logic. This custom logic is actually part of the payload rather than the beacon block. The beacon block header only contains the list of (valid) tickets that the payload will reference. In particular, without a valid non-empty payload, we may not even be able to check whether the tickets are valid in the first place. For this reason, we just invalidate all tickets in case of a rejected payload / empty block for simplicity. This differs from LUCID; the reason is that in our design, the release of decryption keys for tickets from a block B is scheduled for after we know whether B's payload is rejected. This allows us to invalidate the tickets without running into failure case B. There is no need to deal with a pileup of queued tickets in our case here. ↩︎