Nullifiers

In a private system like Veil, we cannot just track "balance" for an address, because balances are hidden. Instead, we use a UTXO-like model (Unspent Transaction Output) with Nullifiers.

If I have a private note worth 100 USDC, what stops me from spending it twice?

• I generate a proof that I own "a valid note" (without revealing which one).
• I send the proof to the network.
• I do it again.

Since the note remains in the Merkle Tree (we can't remove it without revealing which one changed), the proof is still valid.

Veil uses a two-step circuit-safe nullifier derivation to prevent double-spending while protecting the user's master secret.

Two-Step Derivation

Step 1: Derive Spending Key $spending\_key = Poseidon(secret, \text{"NYX\_SPENDING\_KEY"})$

Step 2: Derive Nullifier $nullifier = Poseidon(spending\_key, Hash(leaf\_index \, || \, \text{"NYX\_NULLIFIER"}))$

This two-step approach is critical for circuit safety: the master secret is never directly used in the nullifier computation within the zkSNARK circuit. Instead, we first derive an intermediate spending_key, which is then used to compute the nullifier. This prevents potential secret exposure through constraint system analysis.

How it Works

1. Note Creation:

   • You create a note with a secret (32 bytes).
   • The commitment is computed: $C = amount \cdot G + blinding \cdot H$
   • The commitment is added to the on-chain Merkle tree at position leaf_index.

2. Spending:

   • Off-chain: You generate a zkSNARK proof that includes:
     • Deriving spending_key from your secret
     • Deriving nullifier from spending_key and leaf_index
     • Proving the commitment exists in the Merkle tree
     • Proving you know the correct secret
   • On-chain submission: You publish the nullifier (32 bytes) along with the proof.

3. On-Chain Verification:

   • The Solana program verifies the zkSNARK proof
   • It checks: "Has this nullifier been recorded before?"
   • No: Transaction accepted. A Nullifier PDA is created to mark it as spent.
   • Yes: Transaction rejected (double-spend attempt detected).

PDA-Based Nullifier Storage

Veil uses Solana's Program Derived Addresses (PDAs) to track spent nullifiers:

PDA Seeds:

[NULLIFIER_SEED, pool_id, nullifier_bytes]

The Anchor framework's init constraint ensures that each nullifier can only be initialized once. Attempting to spend the same note twice will fail because the PDA already exists, making double-spend prevention automatic and efficient.

The nullifier provides strong privacy guarantees:

Mathematical Unlinkability: Given:

• Commitment: $C = amount \cdot G + blinding \cdot H$
• Nullifier: $nullifier = Poseidon(Poseidon(secret, \text{domain}), leaf\_index)$

These two values appear completely uncorrelated to any observer. Without knowing the secret, it is computationally infeasible to link a nullifier to its corresponding commitment.

What This Means:

• Watching the blockchain, you see commitments being added (new notes) and nullifiers being published (notes being spent).
• You cannot determine which commitment corresponds to which nullifier.
• This breaks the transaction graph and provides strong privacy for users.

The domain separators ("NYX_SPENDING_KEY" and "NYX_NULLIFIER") ensure that:

• Nullifiers cannot be accidentally reused across different contexts
• The spending key derivation is isolated from other cryptographic operations
• Collision resistance across different protocol operations

Double-Spend Prevention:

• Each note can only be spent once (enforced by PDA uniqueness)
• The zkSNARK proof ensures honest derivation of the nullifier
• No trusted third party needed for enforcement

Spending Key Safety:

• The master secret never appears directly in nullifier constraints
• Even if circuit constraints are analyzed, the secret remains protected
• The two-step derivation adds an additional layer of cryptographic separation

Size & Representation:

• Nullifier: 32 bytes (BN254 scalar field element)
• Stored on-chain as PDA account (minimal storage overhead)
• Efficiently checkable during transaction verification

See also: Commitments for how notes are created, and zkSNARKs for how nullifier correctness is proven in zero knowledge.