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.]
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.
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 ). Inside the proof circuit, three conditions are checked:
- nfiold is correctly calculated from ask,iold and ρiold;
- ask,iold is the (unique ) 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
 Enforcement of ρiold being unique is done when the note is created, by the condition “Uniqueness of ρnew” in section 4.9.
 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.)