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

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 https://github.com/zcash/zips/blob/master/protocol/protocol.pdf or https://eprint.iacr.org/2012/215.pdf.

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 ninew from a transaction are private inputs to the proof, and additionally the commitments cminew to those notes are public inputs listed in the transaction. Inside the proof circuit, the following condition is checked:

  • cminew is correctly calculated from ninew.

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 niold to a transaction and the input spending key ask,iold 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 nfiold. The input note niold includes the fields apk,iold (the paying key to which the note was paid) and ρiold (which is unique to this note [1]). Inside the proof circuit, three conditions are checked:

  • nfiold is correctly calculated from ask,iold and ρiold;
  • ask,iold is the (unique [2]) spending key corresponding to the paying key apk,iold;
  • There is a valid Merkle tree path (provided as a private input) from the commitment of niold 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 ninew from transaction 1 as niold 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 :smiley:

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

[2] ask,iold is the unique feasibly obtainable spending key corresponding to apk,iold because PRFaddr 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.)

4 Likes

@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.

1 Like

Thank you very much, this is really helpful.

1 Like