How does a node verify a nullifier without reveal its relation to its correspond commitment in Zcash?

[Senlody]

I know that each note commitment has exactly one correspond nullifier, and every node will check the existence of a nullifier in the nullifier set to prevent double spent. But it confused me that, when a node receives a new nullifier, how does it check whether there exists a commitment (in the commitment tree) whose correspond nullifier is the given one?

I didn’t find any details about this question in zips/protocol.pdf at main · zcash/zips · GitHub or https://eprint.iacr.org/2012/215.pdf.

[str4d]

tl;dr

This happens inside two zero-knowledge proofs (the one that created the note and the one that spends it), across four conditions that are listed in section 4.9:

• Merkle path validity
• Nullifier integrity
• Commitment integrity
• Spend authority

[Edit by @daira: added Spend authority, with a corresponding change to the explanation below.]

Explanation

Receiving notes

The output notes n_i^new from a transaction are private inputs to the proof, and additionally the commitments cm_i^new to those notes are public inputs listed in the transaction. Inside the proof circuit, the following condition is checked:

• cm_i^new is correctly calculated from n_i^new.

Thus if the transaction is included in the block chain, the correct commitments for the new notes will have been added to the global commitment tree.

Sending notes

The input notes n_i^old to a transaction and the input spending key a_sk,i^old are private inputs to the proof, and additionally there are two relevant public inputs listed in the transaction: the anchor (or commitment tree root) rt, and the nullifiers nf_i^old. The input note n_i^old includes the fields a_pk,i^old (the paying key to which the note was paid) and ρ_i^old (which is unique to this note [1]). Inside the proof circuit, three conditions are checked:

• nf_i^old is correctly calculated from a_sk,i^old and ρ_i^old;
• a_sk,i^old is the (unique [2]) spending key corresponding to the paying key a_pk,i^old;
• There is a valid Merkle tree path (provided as a private input) from the commitment of n_i^old to the current commitment tree root rt.

Because these conditions are being checked in the same proof (and therefore calculated from the same input notes), the nullifiers are cryptographically linked to the existence of a Merkle tree path. Because nullifiers are uniquely derived from notes, and commitments are unique in the Merkle tree, each Merkle tree path corresponds to a single nullifier.

Linking the two

Use n_i^new from transaction 1 as n_i^old in transaction 2 (ie. spending notes you received), and pick an rt from after the block that transaction 1 was included in (so that a Merkle path exists). Then you can create a valid proof for transaction 2, and when network nodes validate it they will inherently be checking that commitments for the given nullifiers previously exist

[1] Enforcement of ρ_i^old being unique is done when the note is created, by the condition “Uniqueness of ρ^new” in section 4.9.

[2] a_sk,i^old is the unique feasibly obtainable spending key corresponding to a_pk,i^old because PRF^addr is collision-resistant.
(This condition was actually missing from the original Zerocash security proof. It’s important because if you could find two spending keys matching the paying key of a note, you could calculate different nullifiers from them, so you could double-spend that note.)

[daira]

@str4d’s explanation is excellent but was missing detail about the Spend authority condition which is also necessary, so I edited it to include that.

[Senlody]

Thank you very much, this is really helpful.