reviewers: 🟡@David Rusu

Process Flow

Start: Nullifier Tree State

• The current state of the nullifier tree is represented by its root, organized as an MMR of nullifiers.

Step 1: Interval Identification

• Search for an interval $[low\_nf, next\_value]$ that bounds the new nullifier. This ensures the nullifier can be inserted without duplication.

Step 2: Non-Membership Verification

• Verify that the nullifier falls strictly between low_nf and next_value.
• If not, the process fails as the nullifier already exists.

Step 3: Construct New Leaf Node

• Create a new leaf for the nullifier:
  • value: New nullifier to insert.
  • next_value: Previous upper bound (next_value) of the interval.

Step 4: Verify Merkle Path

• Compute and verify the Merkle path of low_nf to prove its existence.
• The path consists of hashes from the leaf to the root to validate consistency.

Step 5: Update MMR with New Leaf

• Add the new leaf to the MMR.
• Combine the MMR roots and recompute the full tree root.

Step 6: Compute and Verify Updated Root

• The updated root of the nullifier tree is computed.
• Ensure that the updated root matches the expected value after the insertion.

End: Proof Completion

• Verification succeeds when the new root matches the expected tree root.

Explanation of the MMR Structure

MMR Purpose

• MMR enables efficient appending of new values (nullifiers) while maintaining cryptographic integrity.
• MMR roots represent different levels of the tree, combining them incrementally when required.

MMR Components

• Leaves: Nullifiers stored as Leaf structs with a value and next_value (next nullifier in the range).
• Frontier: A list of partial tree roots representing the structure before merging.
• Empty Roots: Precomputed hash values for subtrees filled with zeroes, used when extending the tree.

Non-Membership Proof Protocol Steps

Inputs: