Architecture & algorithms deep-dive

Trace the full construction end to end: how deposit/withdraw works over a Poseidon Merkle tree with a Groth16 membership proof and nullifier accounting, how Proposition 1 breaks it, how the one-note-one-spend invariant (Theorem 1) repairs it, and how the positive wallet-layer construction and relayer binding (Theorem 2) are assembled — with the model written out in schematic code and a worked walkthrough.

Track

Research

Module

5 · Research case studies

Prerequisites

Why in-protocol decoys break value safety (case study, part 2) · Merkle trees · What is a zero-knowledge proof

The construction composes three standard pieces. None is novel; the contribution is how value is accounted over them. Fix the vocabulary first, because the negative result turns on the difference between a cryptographic value and the contract state keyed on it.

Poseidon hash H

An arithmetic-friendly hash used for commitments and for every internal node of the Merkle tree, chosen for low in-circuit constraint cost. Treat it as a collision-resistant function evaluated cheaply inside the circuit.

Merkle accumulator

A fixed-depth tree whose leaves are note commitments. The root is public on-chain; a withdrawal proves a leaf is under the current root without revealing which leaf.

Groth16 verifier

A deployed contract that checks a succinct proof against a public-input vector in constant time. Soundness is conditional on the circuit's trusted setup (assumption H4 of Theorem 1).

Spend identifier (nullifierHash)

A value published on withdrawal and recorded in an on-chain spent set S. The double-spend test is keyed ONLY on this identifier — the fact the whole negative result exploits.

A deposit inserts a commitment leaf; a withdrawal proves membership and publishes a nullifierHash. Here is the model as schematic pseudocode — the shapes, not a reference implementation.

synthetic — deposit and single-nullifier withdrawal (schematic)
# ---- client: create and deposit a note ----
s        = random_secret()                 # note secret material
nf       = random_nullifier()              # nullifier preimage
C        = H(nf, s)                        # commitment (leaf)
tree.insert(C)                             # contract stores C, updates root R

# ---- client: withdraw ----
#   public inputs seen by the verifier:
#     R      current Merkle root
#     nh     nullifierHash  = H(nf, s)     # deterministic spend identifier
#     recip  payout recipient
#   private witness (never revealed):
#     s, nf, and the Merkle path from C to R
proof = Groth16.prove(
          public = (R, nh, recip),
          witness = (s, nf, merkle_path(C -> R)))

# ---- contract: verifyWithdraw ----
def verifyWithdraw(R, nh, recip, proof):
    assert R == tree.currentRoot()         # (A) membership is against the live root
    assert Groth16.verify((R, nh, recip), proof)   # (B) proof is valid
    assert nh not in S                     # (C) double-spend gate: THE only value gate
    S.add(nh)                              # (D) consume the identifier
    pay(recip)

Read gate (C) carefully. The contract never marks C consumed; it marks nh consumed. If the circuit lets one commitment produce two different valid nh values, gate (C) is satisfied twice and the contract pays twice. That is the entire attack surface, and it is a contract-accounting surface, not a cryptographic one.

The in-protocol decoy binds two nullifiers into one commitment and selects between them inside the witness, so one deposit can produce two distinct valid identifiers. Watch the contract state evolve; every line uses only gates (C)/(D) above.

synthetic — the dual-nullifier double-withdrawal (k = 2)
# decoy-enabled commitment binds TWO nullifiers
C = H(s, nf_real, nf_decoy)            # one economic note, two preimages
nh_decoy = H(nf_decoy, s)              # identifier #1
nh_real  = H(nf_real,  s)              # identifier #2   (nh_decoy != nh_real)

# both prove membership of the SAME leaf C under R, selecting their branch in-circuit
proof_d = Groth16.prove((R, nh_decoy, recip), witness picks decoy branch)
proof_r = Groth16.prove((R, nh_real,  recip), witness picks real  branch)

state: S = {}
  verifyWithdraw(R, nh_decoy, recip, proof_d)
     (C) nh_decoy not in {}        -> pass    (D) S = {nh_decoy}   -> PAYOUT #1
  verifyWithdraw(R, nh_real,  recip, proof_r)
     (C) nh_real  not in {nh_decoy} -> pass   (D) S = {nh_decoy, nh_real} -> PAYOUT #2

# one deposited denomination -> two payouts -> value safety violated

This is Proposition 1 at k = 2. The general statement: under (C1) a monotone spent set with reject-if-present, (C2) one commitment admitting k ≥ 2 distinct valid identifiers, and (C3) no shared consumed-state across those identifiers, an adversary withdraws k denominations against one deposit. The proof is an induction over the spent set: before the i-th withdrawal S holds at most i−1 identifiers, all distinct from the i-th by (C2), so gate (C) passes and the withdrawal is accepted. Nothing in gates (A)–(D) references C or relates the identifiers — that is (C3).

The repair is to make a note yield exactly one identifier, negating condition (C2). The circuit is constrained so the witness determines a unique public nullifierHash per commitment; no accepted proof for C can publish a second value.

synthetic — the corrected single-nullifier circuit (schematic)
# circuit constraints enforced for every accepted proof of commitment C:
#   1.  C == H(nf, s)                 # the note is this exact commitment
#   2.  merkle_path(C -> R) is valid  # membership under the public root
#   3.  nh == H(nf, s)                # nullifierHash is a DETERMINISTIC function
#                                     #   of the same (nf, s) bound to C
# => for the single (nf, s) that opens C, constraint 3 fixes exactly one nh.
#    There is no second branch and no selector input to choose another nh.

# contract unchanged: gate (C) nh not in S, gate (D) S.add(nh)
# first presentation of C: nh new -> accepted, appended
# any later presentation of C: reproduces the SAME nh -> gate (C) fails -> revert

Theorem 1 states the guarantee under four assumptions: (H1) a valid withdrawal proves Merkle membership of the spent commitment under the verified root; (H2) the circuit constrains nullifierHash = H(nullifier, s) so the witness determines a unique public nullifierHash — no accepted proof for C publishes a second value; (H3) the contract records every accepted nullifierHash and rejects repeats; (H4) the deployed Groth16 verifier is sound under its trusted setup. Then for every commitment accepted under the verified root, at most one value-consuming withdrawal is accepted. A single deterministic nullifier negates (C2), so the k ≥ 2 double-withdrawal cannot arise.

With the spend path locked to one note, one spend, deniability cannot live there — any second spendable identifier would reintroduce (C2). So the construction places deniability at the wallet: two economically independent single-nullifier notes, each an ordinary deposit, linked only by a local label the protocol never sees.

synthetic — wallet-layer derivation of two independent notes
# role in { real, decoy }; independent passphrases AND independent salts
def derive(passphrase_role, salt_role):
    stretched = scrypt(passphrase_role, salt_role)   # memory-hard: device alone is not enough
    s_role    = HKDF(stretched)                      # key-derivation function
    nf_role   = KDF_nf(s_role)                        # note preimages from s_role
    C_role    = H(nf_role, s_role)                    # independent commitment
    return (s_role, nf_role, C_role)

real  = derive(passphrase_real,  salt_real)    # funded with the target amount
decoy = derive(passphrase_decoy, salt_decoy)   # funded with a smaller REAL amount

deposit(real.C)     # two separate, ordinary single-nullifier deposits
deposit(decoy.C)    # on-chain: unrelated; disjoint salts, no shared seed

# under coercion:
#   surrender passphrase_decoy -> wallet derives s_decoy -> withdraw decoy note
#   adversary receives a real, non-trivial amount via an ordinary valid tx
#   real note is untouched; protocol emitted no datum relating the two notes

Because the salts are independent, knowing one passphrase yields neither the other passphrase nor the other note — a stronger separation than a BIP-39 hidden wallet, where decoy and hidden accounts share a single root seed. Each note stays single-nullifier, so Theorem 1 still holds and no double-withdrawal is introduced. The decoy holds real funds, so the coerced withdrawal is a genuine, credible transaction — it has to be, or the surrender would look anomalous.

Gasless withdrawals are submitted by a relayer for a fee. If a proof were transferable, a different relayer could front-run it and steal the fee or redirect the payout. The fix is to bind the relayer address R and fee f as public inputs to the verifier.

synthetic — relayer/fee binding
# public-input vector includes (relayer, fee):
public = (root, nh, recip, relayer, fee)
proof  = Groth16.prove(public, witness)

# Groth16 verification is a function of the FULL public-input vector.
# Changing any public input changes the pairing check:
verify((root, nh, recip, relayer', fee'), proof) == false   if relayer' != relayer or fee' != fee

Theorem 2 (relayer binding): a proof accepted for the public-input vector (relayer, fee, …) does not verify for any (relayer', fee') with relayer' ≠ relayer or fee' ≠ fee. The argument relies on the binding of public inputs to the verification equation — not on proof non-malleability. The paper is careful here: Groth16 proofs are re-randomizable, but only for the same public-input vector, which does not affect relayer/fee binding. So a proof is non-transferable to another relayer: front-running resistance follows from public-input binding alone.

Putting the pieces together on one synthetic timeline makes the separation of concerns visible.

1. 1Shielding: the wallet derives a real note (target amount) and a smaller decoy note from independent passphrases/salts, and submits two ordinary deposits. On-chain: two unrelated single-nullifier commitments; the link is a local label only.
2. 2Normal withdrawal: later, to spend the real note, the wallet proves membership of C_real under the current root with a deterministic nh_real, binds the chosen relayer/fee as public inputs, and the relayer submits it. Gate (C) sees nh_real for the first time and pays out.
3. 3Replay attempt: any second presentation of C_real reproduces the same nh_real (Theorem 1), gate (C) finds it in S, and the withdrawal reverts — no double-spend.
4. 4Front-running attempt: a competing relayer tries to resubmit the proof with its own address/fee; the public-input vector changes, Groth16 verification returns false (Theorem 2), and the steal fails.
5. 5Coercion: the user surrenders passphrase_decoy; the wallet derives s_decoy and withdraws the decoy note — a real, valid, unremarkable transaction. The real note is untouched and no protocol-introduced datum links the two.

Expected direction: Gate (C) — "assert nh not in S" — is keyed on the spend identifier nh, not on the commitment C, and the contract never marks C consumed (no shared consumed-state). A dual-nullifier commitment yields two distinct valid nh values, so gate (C) passes twice and the contract pays twice. Strengthening Groth16 or Poseidon does not help because the double-spend check never references their outputs as a value-binding on C; both proofs are perfectly valid. The fix is the circuit constraint nh == H(nullifier, s) tying the nullifierHash deterministically to the single (nf, s) that opens C, so one commitment can produce only one nh (negating condition C2 / Theorem 1).

Which value does the double-spend gate deduplicate on, and why does that matter?

On the spend identifier nullifierHash, not on the commitment C. If one commitment can produce two distinct valid nullifierHashes, the gate passes twice and value safety breaks — the defect is in contract accounting, not cryptography.

What exactly does the corrected circuit constrain to negate condition C2?

It constrains nh = H(nullifier, s) so the witness that opens C determines a unique nullifierHash; there is no selector input and no second branch, so a commitment yields exactly one spendable identifier.

Why is Theorem 2 (relayer binding) NOT a claim that Groth16 proofs are non-malleable?

Groth16 proofs are re-randomizable, but only for the same public-input vector. Theorem 2 binds the relayer address and fee as public inputs, so a proof fails verification under a different relayer/fee — front-running resistance from public-input binding, not from non-malleability.

What keeps the two-note construction consistent with Theorem 1?

Each note is an independent single-nullifier deposit, so every note still maps to exactly one spendable identifier. Deniability is added at the wallet, off the spend path, without reintroducing a second identifier.