Nullifier freshness circuit

The nullifier-freshness proof shows that none of a transaction's three nullifiers is in the pool's nullifier tree. It is a separate Groth16 proof, made by whoever submits the transaction, and it is the half of double-spend prevention that covers nullifiers the forester has already inserted.

What it provesCopy Anchor Link

A nullifier is the public tag a spend publishes for each input note; see nullifiers. Spending the same note twice would publish the same nullifier twice, so a nullifier that is already recorded means the note is spent.

The nullifier tree records them as an indexed Merkle tree. Each leaf holds a value, the index of the leaf with the next-larger value, and that next value, so the leaves form a sorted linked list threaded through the tree. A value is absent exactly when it falls strictly between some leaf's value and that leaf's next value. The chart below shows a small example.

flowchart LR
A["Leaf 0, next 17"] --> B["Leaf 17, next 42"]
B --> C["Leaf 42, next 0"]
Q["Nullifier 30"] -.->|falls in the gap| B

The leaf holding 17 points to 42 as its next value, so nothing between 17 and 42 is in the tree. Proving that 30 is absent needs only that one leaf and its Merkle path, however large the tree is. The last leaf's next value is zero, which marks the end of the list.

For each of the three nullifiers, the circuit proves:

• The gap leaf is in the tree. A leaf with value v, next index and next value w is in the tree at the given root. The leaf is rebuilt as the Poseidon hash of the indexed-leaf domain, v, the next index and w, so the prover cannot invent a gap the tree does not contain.
• The nullifier is above the leaf. v is less than the nullifier.
• The nullifier is below the next leaf. The nullifier is less than w, or w is zero, which marks the largest leaf.

The comparisons are the delicate part. The circuit's values are elements of a field modulo a 254-bit prime, and a comparison that splits a value into bits without pinning a unique decomposition can be fooled: the same element can be presented in a second, larger encoding that slips past the check. The circuit therefore decomposes each value into its canonical 254 bits, with the decomposition forced below the field modulus, and compares the two 127-bit halves.

The public input is the Poseidon hash of the three nullifiers and the root. The circuit is NullifierNonMembership(3, 11, 8, 1, 8), over a tree of 11 levels of 8 children and one level of 8 (2³⁶ leaves), and has 22,209 non-linear constraints.

Entry	circuits/zk/nullifier_non_membership.circom
Instantiation	NullifierNonMembership(3, 11, 8, 1, 8)

Who makes itCopy Anchor Link

The proof needs no private data: the nullifiers are public in the transaction, and the tree's leaves can be rebuilt from chain data. So the submitter makes it, not the owner of the notes.

A relayed transaction. The relayer asks an indexer's mirror of the nullifier tree for the three gap witnesses, checks them against the root it chose, proves, and attaches the proof before sending. This is the relayer's prove stage. If the mirror reports that a nullifier is already in the tree, the relayer rejects the transaction instead of proving.

A deposit you submit yourself. Your device makes it alongside the transaction proof.

The sequence below shows the relayed case.

sequenceDiagram
participant R as Relayer
participant I as Indexer mirror
participant P as Shielded pool
R->>I: gap witnesses for three nullifiers
I-->>R: leaves and Merkle paths
R->>R: check witnesses, prove
R->>P: transaction with both proofs
P->>P: resolve root, verify

The proof sits in the payload after the combined attester signature, together with the sequence number of the root it was made against. The attesters sign only the payload before their signature, so the submitter can make this proof at submission time, against the newest root, without asking anyone to sign again. The relayer chooses the root as late as possible and proves against it. The freshness proof binds its own root, and the transaction proof binds the nullifiers, so neither can be swapped for another transaction's.

Where it is verifiedCopy Anchor Link

process_3x3x2x2 resolves the named root from the staging buffer, which the code calls the turnstile. The nullifier staging buffer keeps a ring of the nullifier tree's last 512 roots and a watermark; a root older than the ring, or below the watermark, is refused with the staging buffer's StaleRoot error. The program then folds the three nullifiers and the root, and verifies the proof under the three-nullifier key compiled into the program, in one pairing with the transaction proof and the combined attester signature.

A freshness proof whose points do not decode, or are the point at infinity, fails with its own error code, NullifierProofInvalid, separate from the transaction proof's codes (ProofDecompressionFailed for a point that does not decode, InvalidProof for one at infinity), so a client can tell which of the two proofs to rebuild. Once all three are well formed, the single pairing cannot say which of them is wrong: a failure there is TransactionBatchRejected, and the client checks each proof and the signature against its own copy of the keys to find the one at fault. The codes are listed in the reference section below.

What it does not proveCopy Anchor Link

The proof says nothing about nullifiers that were staged but not yet inserted into the tree. The forester inserts staged nullifiers only in batches, so the tree always lags the staging buffer. That gap is covered by the program, not the proof. When the transaction stages its nullifiers, the staging buffer refuses any key already held in either of its two buffers. A buffer is emptied only after all its keys are in the tree, and emptying it raises the watermark to the root that contains them, so no proof can be made against a tree that lacks keys the buffer has forgotten. The Lean model of the staging buffer proves that, under its invariants, no key is staged twice. See preventing double spends.

It also says nothing about who owns the notes or whether the nullifiers are correctly derived. The transaction circuit proves that.

Other places non-membership is provenCopy Anchor Link

The escape hatch and fee collection do not use this proof. Their circuits prove non-membership of their own nullifiers inside the main proof, against the nullifier tree or the fee-nullifier tree, because those operations have no attester signature to sit outside of.

An eight-nullifier variant, nullifier_non_membership_8, exists for the merge circuit. It has no Solana handler, no key compiled into the program and no test key; see the merge circuit.

ReferenceCopy Anchor Link

RelatedCopy Anchor Link