Bloom Filters And Keyed Nonces

Privacy
1

Bloom Filters and Keyed Nonces

by @GottfriedHerold ; thanks to @soispoke, @Nero_eth @b-wagn and @vbuterin for valuable feedback.

TL;DR

EIP-8250 should distinguish binary (i.e., one-shot) from non-binary (i.e., counter) nonces via the nonce key by using the first byte as a nonce-type tag, in order to be compatible with future upgrades such as using a Bloom filter to reduce the amount of VOPS storage that stateless nodes need to hold.

Keyed Nonces

Keyed nonces (EIP-8250) are proposed for inclusion in H*. Prior to it, every transaction must include the current value of the sender’s nonce. A successful transaction increments the value of this nonce to prevent replay attacks. The nonce is tied to the sender and stored in the state trie as part of the sender’s account.

With EIP-8250, this changes for frame transactions to allow arbitrary keyed nonces, i.e. every sender may have multiple nonces that each count upwards independently. Those new nonces are still tied to a sender and stored in a single system contract NONCE_MANAGER. The keys are 32 bytes long and each transaction can use up to 16 different nonce keys.

Envisioned Usage Scenarios

One application of keyed nonces is to greatly simplify privacy pools, for two reasons. First, all user transactions go through a single sender, so a single nonce would require coordination or limiting throughput. Second, those transactions essentially follow a UTXO model, where each transaction writes a nullifier to the state to indicate that coins have been spent. The idea is to use a nonce key as the nullifier, where a nonce value of 1 indicates that the nullifier is set (i.e. the coin has been spent). This means that with EIP-8250, all nonce values included in such a transaction will be 0. Setting nullifiers this way via nonces (together with appropriate checks in the approval frame) gives the atomicity guarantees that privacy protocols need; see EIP-8250 for a discussion.

We note that keyed nonces can also be used for other (non-privacy) applications that use a similar UTXO model.

Furthermore (h/t Vitalik Buterin), another application is enabling accounts with multiple independent authenticated senders, e.g. multiple persons/wallets using the same account to send coins from. With the single legacy nonce per account, they would need to coordinate to avoid reusing the same nonce; this issue is avoided by each person/wallet using their own nonce key. Note that in this application, the nonce values used may be arbitrary counters, not just 0 as in the UTXO application above.

VOPS

A future goal of Ethereum is that only block builders need to retain the full state trie, while other nodes validate state accesses via proofs provided by the block proposer (weak statelessness). To protect the public mempool and FOCIL includers, non-builders may still need to store a fraction of the state, called VOPS-state. Reading the nonce value stored in NONCE_MANAGER needs to happen as part of transaction authentication before any payment has been guaranteed. A consequence is that the NONCE_MANAGER state would need to be VOPS state in order to protect the public mempool and to ensure seamless integration with FOCIL. Hence, each nonce key used as a nullifier grows the VOPS state, which is quite expensive.

Bloom Filters

One idea to curb the growth of VOPS state from the usage of such nullifiers is to let stateless nodes use a Bloom filter. Each such node locally stores an (independent) Bloom filter that records which nullifiers have been set. When ascertaining that a certain nonce value is 0, Bloom filters have a one-sided error: a false positive makes a node believe that a nullifier has been set when it has not, so the node wrongly rejects a valid transaction. Crucially, the error never goes the other way, i.e. a node can never be fooled into accepting a transaction whose nullifier has in fact already been set. This means that some nodes may wrongly reject a small fraction of valid transactions; but since every node uses a different Bloom filter (with independently salted hash functions and hence different errors), each node rejects a different set of valid transactions and a rejected transaction still gets propagated and included by other nodes. For the public mempool and FOCIL, such a small one-sided error is not a problem. Using a Bloom filter, the amount of storage per keyed nonce is only 1 to 2 bytes, compared to storing a 32-byte key and an (up to) 32-byte value, in addition to trie overhead.[1] Note that, with EIP-8037 writing new nullifiers to NONCE_MANAGER costs 97,920 (state creation) gas per nullifier. If we assume that non-VOPS state creation will be priced significantly cheaper than VOPS state creation in the future, a ballpark estimation of the saved cost might be around 10x.[2]

Problem: Bloom Filters Only Work for Binary Nonces

The issue at hand is that this approach only really works for binary nonces and for asking whether they are 0, which is appropriate in the usage for nullifiers. If we generalize this to arbitrary values, we lose simplicity and efficiency and, more importantly, we get a two-sided error[3]. A noticeable two-sided error enables an attacker to trick mempool nodes and, much worse, FOCIL nodes into wrongly accepting invalid transactions and thereby flooding inclusion lists. Hence, we deem a two-sided error unacceptable.

Potential Solutions

Let us discuss several options to tackle the above issue and what the consequences are. We assume here that we activate keyed nonces in H* and Bloom filters at some unspecified time later (after statelessness).

An important criterion in this discussion is whether a solution gives us retroactive benefits, i.e. whether nonce keys that are already in use by the time we activate Bloom filters can profit as well. This matters because keyed nonces are never cleaned up: once set, a key keeps its value in NONCE_MANAGER indefinitely, and it is exactly this unbounded accumulation that drives the VOPS growth we want to curb. Any key that we cannot recognize as binary hence remains VOPS state forever. Note that we cannot simply classify the keys that already exist by their value at the time of activation: a key whose value is currently 1 may be a binary nonce, but it may just as well be a non-binary nonce that is incremented to 2 at some later point.

  1. Do nothing now, just use Bloom filters later for all nonce keys and do not make the NONCE_MANAGER state VOPS: Note that the Bloom filter would still only be used to ascertain that a nonce value is 0, so we keep the one-sided error; nonces that have a non-zero value simply cannot be validated by stateless nodes at all. This gives us the full benefit of Bloom filters, but means that users of non-zero keyed nonces can no longer use the public mempool easily. FOCIL nodes might reject transactions with keyed nonces that have a non-zero nonce value. While this may be acceptable for certain applications, the impact on the aforementioned use case of having multiple senders/wallets for a single account makes this an unacceptable solution.
  2. As above, but use proofs for non-zero nonces: We could ask users to provide a proof for the nonce value relative to a recent state[4] of the NONCE_MANAGER contract. The problem here is that this proof needs to be supplied by the sender of the transaction rather than by the builder. We would need some way to enable senders to construct such proofs, or to incentivize nodes that have the full state to provide such a service in privacy-preserving way. This is essentially the general problem that VOPS aims to solve.
  3. Only use Bloom filters for binary nonces and store non-binary nonces as VOPS state: This is the most promising approach and the one suggested by the Bloom filter proposal.

Determining Whether a Nonce Key Is Binary

The difficulty with this third option is knowing whether a nonce key is binary or not, and there are multiple ways to determine that:

  • Elevate a nonce key to VOPS once its value reaches at least 2: The problem here is that this approach fails when increasing the nonce value from 1 to 2, unless the key is already VOPS when the value is 1. To avoid that special case, we would want to have a way to increment the nonce value from 0 to 2 in a single transaction (to mark a key as non-binary and avoid it ever being 1). This requires adding a way to actually do that in EIP-8250, which essentially means marking a nonce key as non-binary when first using it. We could in principle add the increment-from-0-to-2 feature only later, but then we need a transition period, before statelessness activates, in which users bump their pre-existing non-binary nonces to a value of at least 2. We would rather not deal with that, since such a transition period adds complexity, requires user interaction and users might fail to act.
  • Add a way to mark a nonce key as binary upon first use (i.e., when incrementing the value to 1) and store that information in the state somehow: This can be achieved in multiple ways, for example by adding a separate nonce_list for binary nonces to the transaction header, essentially treating binary nonces as separate objects. We may or may not store them in the same NONCE_MANAGER. Note that this option and the previous one differ mainly in where they put the onus: in the previous option, the optimization applies by default and users whose use case it breaks have to opt out of it by bumping their nonce values, whereas this option asks users to opt into the optimization. Not defaulting to the optimization is also why this feature does not need to be included from the onset: Keys that predate it are simply unmarked and hence classified as non-binary irrespective of their value. Those keys, however, never get the benefits, so adding the feature late forgoes them retroactively.
  • Make the information whether a nonce is binary a part of the nonce key: That is, reserve the first byte[5] to indicate the type of nonce (e.g., binary / non-binary, with the other values of the first byte reserved). This reduces the space of possible nonce keys to 31 bytes, which should still be enough. Only make non-binary nonces (eventually) VOPS and eventually use a Bloom filter for binary nonces. This seems by far the easiest and cleanest way to tackle the issue: like the two options above, it requires a change to EIP-8250 already now to reserve the first byte, but that change is a much smaller one, as it needs neither additional transaction fields nor extra state. While we could in principle just reserve the first byte and only have non-binary nonces for now, this would not give benefits retroactively, so we suggest already distinguishing binary from non-binary nonces from the outset. To avoid any future behaviour changes, transactions that use binary nonces shall only use them with a value of 0. Consequently, a binary nonce key can be used successfully exactly once: afterwards its value is 1 and any further transaction using that key is invalid. Since we get the benefits retroactively, we may want to incentivize using binary nonces even before we have Bloom filters.

As we can see, each of the options that provide a seamless transition to statelessness with retroactive benefits actually requires changes to EIP-8250 before it goes live in order to make it future-proof. Using the first byte of the nonce key seems by far the simplest option.

Open Questions

It would be great if we could get some efficiency benefit from designating keyed nonces as binary even without (weak) statelessness and Bloom filters. This way, we might be able to lower the gas cost already now and provide an incentive to use binary nonces instead of non-binary nonces where applicable. Such benefits seem possible, since clients might store them much more efficiently. In principle, storing only the 32-byte key instead of 64 bytes for key and value could potentially reduce the gas cost from about 100k to about 50k. Some of the relevant questions here are:

  • How difficult would it be for clients to optimize their data layout for binary nonces?
  • How much would we actually gain from doing so?
  • In theory, we could store binary and non-binary nonces in different system contracts. What is the complexity / benefits tradeoff of doing so?

  1. To get the one-sided error probability down to approximately 5 percent for a single transaction, we need about 12 bits per nonce and 8 hash functions in the Bloom filter. This takes into account that we can have up to 16 nonces per transaction, which is why the number differs from the analysis given here. Also, there are variants of Bloom filters that have a worse space-efficiency-to-error-rate tradeoff but that offer other advantages, such as better locality for data access. We may want a bit of leeway to allow implementations to utilize such variants. ↩︎

  2. In a post-stateless world, writing a nonce entails growing state by one slot for full nodes. The builder/prover has to prove the corresponding state accesses and state trie updates; those proofs need to be aggregated and verified by all nodes. To index into 8 bits of the bloom filter, stateless nodes need to evaluate a hash function with a per-node fixed salt and an ouput size of 8L bits, where L is the logarithm of the size M (in bits) of the bloom filter. This size M needs to be provisioned from the onset at about 12–16 bits per nonce written over the lifetime of the Bloom filter (if we exceed that size by too much, we would fully replace the filter by a filter with a larger M and regenerate it from scratch). Each stateless node needs to (asynchronously) read and write at 8 unpredictable locations of its Bloom filter. Consequently, by how much a Bloom filter can reduce gas cost depends on the (relative) cost and throughput limits of these constituents. Without Bloom filters, we expect the bottleneck to be the memory provisioning cost of the stateless nodes and that gets cut by approx. 32x, so it will likely no longer dominate the cost. ↩︎

  3. In general, a Bloom filter (or generalizations such as a counting Bloom filter or a count-min sketche) would allow us to ask questions of the form “Is the value of the nonce for key K at most X?” for some X and K. We can thereby also ask whether a nonce has value exactly X by asking whether it is at most X+1 and whether it is at most X. However, this gives a two-sided error rate. Fundamentally, the issue is that the answer to a question of the form “Is the value of the nonce exactly X?” for X ≠ 0 can change from no to yes and then change a second time from yes to no. Bloom filters are only appropriate if the answer changes at most once. ↩︎

  4. This requires all nodes to store a sequence of recent NONCE_MANAGER states and to buffer any recent changes to keyed nonces before writing them into the Bloom filter. In practice, implementations likely need to do that anyway to account for reorgs. ↩︎

  5. Note that EIP-8250 mandates that the nonce list of a transaction is sorted by key. Due to that, using the first byte seems natural. ↩︎

1 Like