Epoch-based nullifier database

[maxgillett]

In #222, a sparse Merkle tree database was proposed to store nullifiers of consumed notes. To prevent this database from growing indefinitely, it was suggested that notes could expire after a fixed period starting from their creation (e.g. one year). This would allow nullifiers in the database to also be safely pruned following such a period. In this discussion, an alternative proposal is described that would eliminate note expiry and pruning, but still bound the size of the nullifier database. This new proposal is based on suggestions from @bobbinth and borrowing ideas from this EthResearch post.

The high-level idea is that at regular block intervals (epochs), the current Merkle tree storing nullifiers will be frozen (preventing further updates) and a new, initially empty tree will take its place. A separate Merkle tree will also be maintained to store the roots of frozen trees and that of the current tree. Assuming that a note maintains a record of its block number at creation, then if this number falls within the current epoch, proving non-membership is relatively straightforward, and a Merkle proof only needs to be supplied referencing the current tree. If this number falls within an older epoch, then Merkle proofs will also need to be supplied for every frozen tree, dating back to that epoch.

To state more precisely how this would work, if we have notes with the following fields:

Field	Data Type	Description
vault	NoteVault	A map from asset IDs to balances
program	Program	The Miden program MAST
block_number	BlockNumber	Block reference number (used in nullifier lookup)
serial_num	SerialNumber	An arbitrary user-provided identifier

then we define the nullifier by hash([serial_num]), and the note hash by hash([vault.root], [program.root], [block_number] [serial_num]). The block reference number is used to restrict the set of nullifier Merkle trees needed for note consumption (see below), and should be less than or equal to the current block number. This must be enforced during note creation in the create_note kernel call. To review previous discussion, notes are stored in an append-only Merkle Mountain Range-based trie where the leaf value is set to the note hash.

Nullifier database

Nullifiers of consumed notes are stored in an ordered set of sparse Merkle tries $[s_1,s_2,...,s_n]$, where $s_1$ denotes the trie for epoch 1, and $s_n$ the trie for the current epoch. In each trie $s_i$ for $i \in {1,...,n}$ the key is the nullifier, and the leaf value is the boolean value $1$ (or other nonzero value). Nullifiers may only be added to the trie for the current epoch.

New epochs are established at regular intervals of $N$ blocks. To transition to the next epoch $n+1$, the current epoch's nullifier trie is frozen, and a new trie $s_{n+1}$ is created for the newest epoch.

The roots of the sparse Merkle tries for each frozen epoch i<n are stored in a separate sparse Merkle tree $e$, where each key is the root of $s_i$, and each value is the block $iN$ at which the trie was frozen.

Note consumption

To consume a note with block reference number $r$, we need to prove the following:

• The nullifier does not exist in the current nullifier trie $s_n$
• If the current block number is greater than $N$, then the nullifier does not exist in the set of previous nullifier tries ${s_i}$ where $n &gt; i \geq \lfloor r/N \rfloor$.

This is achieved by supplying three sets of Merkle proofs. The first set of proofs is used to construct a list of all frozen epoch roots within in the block range $[iN, (n-1)N]$ spanning the block reference number of the note (i.e. $r &gt; iN$). The second set are non-memberships proofs, and demonstrate that for each root in this list, no nullifier exists in its corresponding trie. Finally, a proof of non-membership is supplied for the current nullifier trie. Following these checks, the block proposer will add an entry into the current nullifier tree.

This approach still satisfies the properties outlined in the previous linked discussion:

1. We need to be able to check that a given nullifier is not in the database. This is needed to ensure that notes consumed in a transaction haven't been already consumed.
2. We need to be able to prove that a given nullifier is not in the database. This is needed for state transition proofs we want to submit to L1.
3. We need to be able to add new nullifiers to the database. This would be done by an operator at the time when they create a new block.

The major difference is that the user will need to supply Merkle proofs for any previous epochs (if needed), as we don't expect the block builder to necessarily maintain tree data for these epochs and be able to construct these proofs themselves (item 3). As these trees are frozen, we don't need to worry about the root changing in between the time of transaction construction and block inclusion.

[bobbinth]

Great write-up! I think this works. I have just a coupe of small comments.

In the below, I'll refer the the kernel which us used to execute transaction as tx kernel, and to the kernel which is used to build blocks as block kernel.

First, I think we can probably store historical nullifiers tree roots in a sequential hash (rather than a sparse Merkle tree). This hash can be "unhashed" into memory by the block kernel before it verifies transaction proofs, and then we just need to read these roots from memory. Even if we need to unhash the entire chain, this would probably be more efficient than doing Merkle tree lookups, but in most case we probably need to unhash just a few last items in the chain and provide the starting hash nondeterministically.

For example, assume we have 5 nullifier roots: $s_1, ..., s_5$. The hash chain would be computed as follows:

$$ h_1 = hash(0, s_1) $$

$$ h_2 = hash(h_1, s_2) $$

$$ h_3 = hash(h_2, s_3) $$

$$ h_4 = hash(h_3, s_4) $$

$$ h_5 = hash(h_4, s_5) $$

So, if we needed to unhash just the last two roots (i.e., $s_4$ and $s_5$), we'd provide $h_3$ nondeterministically, and then verify that hashing $s_4$ and $s_5$ into it results in $h_5$.

Second, assuming I understood everything correctly: when we generate a local proof, public inputs would include tuples ([block reference number], [nullifier]) for all consumed notes. Then, when a block producer builds a block, they would use these block reference numbers to compute an epoch index for each nullifier, and then perform the lookups as you described.

If the above is correct, I think we could make two minor modification to improve privacy properties. Specifically:

1. The tuples could be ([epoch index], [nullifier]), and the tx kernel would verify that mapping from block numbers to epochs is done correctly. This way, block producer would not know the exact block a note was created in.
2. We can also add some "fuzziness" to epoch index in these tuples. Specifically, the tx kernel could check only that epoch index is not greater than what is implied by the block number, but any number equal to or smaller than the correct epoch index will pass. This way, I could claim that a consumed note was created in any of the prior epochs. This would mean that the block producer would need to do more work but it would also help increase anonymity set at the start of each epoch.

More concretely, let's say epoch $s_n$ has just started. The anonymity set for this epoch would be very small, and thus, consuming notes which were created in this epoch would provide very little privacy. But if I could claim that a note was created either in $s_n$ or in $s_{n-1}$, the block producer would need to check that the nullifier I produced is not present in nullifier trees of both these epochs. But my anonymity set would now include all notes created in $s_{n-1}$ as well.

[iAmMichaelConnor]

I recently came across this idea called "Mutator Sets", which seeks to solve a similar problem:
https://neptune.cash/blog/mutator-sets/
https://www.youtube.com/watch?v=Fjh1PxrgwQo

I haven't got my head around the tradeoffs yet, though.

[bobbinth]

Thanks! I came across this as well - though, haven't seen the video before.

I haven't analyzed the tradeoffs in depth either, but one of the differences seems to be (assuming I understood it correctly):

• In mutator sets, when a UTXO is consumed, a historical section of SWBF needs to be updated, and thus, anyone who has UTXOs related to this section would need to update their witnesses.
• In the construction described in this discussion, when a note is consumed, the nullifier is recorded in the current epoch. Thus, historical epochs are never modified.