resource: https://github.com/0xPolygonMiden/miden-vm/discussions/356

This protocol thus provides a robust way to handle nullifiers without indefinite growth of the database, ensures privacy via epoch indexing, and offers performance optimizations through hash chains and sequential lookups. The discussion also highlights potential future research areas, such as the use of mutator sets or alternative approaches.

Nullifier Generation and Note Creation:

• Note fields: A note consists of several fields:
  • vault: A map from asset IDs to balances.
  • program: A Miden program MAST.
  • block_number: The block number of the note creation.
  • serial_num: A user-provided identifier.
• Nullifier Generation: The nullifier for a note is created by hashing the serial_num, i.e., nullifier = hash([serial_num]).
• Note Hashing: The note hash is generated as hash([vault.root], [program.root], [block_number], [serial_num]).

Nullifier Database Storage (Epoch-based):

• Nullifiers of consumed notes are stored in an ordered set of sparse Merkle trees (SMT). Each SMT corresponds to an epoch.
• The current nullifier trie (s_n) is the one actively updated as nullifiers are consumed during an epoch.
• Epoch Freezing: At regular intervals of N blocks, the current nullifier tree (s_n) is frozen (no further updates) and a new empty tree (s_(n+1)) is created for the next epoch.

Frozen Epoch Roots:

• The roots of frozen SMTs are stored in a separate SMT (e). Each key in this tree is the root of a frozen epoch's nullifier tree, and the corresponding value is the block number at which that epoch was frozen (i*N).
• The historical nullifier trees are stored as immutable, allowing for more straightforward verification processes without needing updates.

Note Consumption and Non-Membership Proofs:

To consume a note, the following checks need to be performed:

• Current Epoch Check: The nullifier for the note is not present in the current epoch’s trie (s_n).
• Historical Epoch Check: If the note's block_number is greater than N, non-membership proofs must be provided for each previous epoch’s nullifier trie. This involves proving that the nullifier does not exist in any trie from epoch ⌊r/N⌋ to s_(n-1) (where r is the note's block number).

This is done using:

• A Merkle proof for the current epoch (s_n) to show non-membership.
• Non-membership proofs for frozen epochs (s_i), if applicable.