Cowrie Research

nullifier-derivation-nondeterminism

14 min read

Nullifier-Derivation Nondeterminism / One Spend Right, Many Valid Nullifiers

  • Name: nullifier-derivation nondeterminism / one spend right, many valid nullifiers
  • Category: exploit pattern / zk-proof integration failure / replay-protection boundary failure / witness-side canonicalization gap / nullifier uniqueness drift
  • Summary: This pattern appears when a protocol relies on nullifiers for one-time semantics, but the nullifier is not derived from one canonical witness object. Instead, the same logical spend right, claim right, or anonymous-action right can generate multiple verifier-acceptable nullifiers because the derivation path is nondeterministic or because one witness component is only partially constrained before it feeds the nullifier. The result is replay without needing a second entitlement: the prover keeps the real underlying right constant while varying high bits, signature randomness, or another under-constrained derivation input so each proof produces a fresh nullifier. The StealthDrop lesson is especially sharp here: noticing one obvious malleability branch such as (r, s) versus (r, N-s) is not the same thing as proving that a signer-produced authorization envelope is a canonical replay-prevention object.
  • What it is:
    • A protocol uses a zk proof to authorize a one-time action such as a claim, spend, or anonymous airdrop redemption.
    • Replay prevention depends on a nullifier that is supposed to be a deterministic function of one underlying right.
    • The design assumes that one right maps to one nullifier.
    • In the vulnerable case, the mapping is not injective or not canonical: the same right can generate multiple valid nullifiers.
    • The multiplicity can come from signature malleability, signer-chosen randomness, truncated-bit assumptions, or witness variables that are only partially constrained before nullifier derivation.
    • Because the verifier accepts each derivation as valid and the contract only stores spent nullifiers, every fresh nullifier reopens the same logical right.
  • Typical preconditions:
    • The protocol uses nullifiers as its primary or only double-spend defense.
    • The nullifier is derived inside the proof from a witness object rather than supplied as one pre-canonicalized protocol object.
    • That witness object has multiple valid encodings or multiple valid generation paths for the same semantic right.
    • The circuit checks validity of the object but not uniqueness of its derivation.
    • The downstream contract or application assumes new nullifier means new right.
  • Common vulnerable surfaces:
    • anonymous claim systems that use hash(signature) or another proof-internal witness artifact as the nullifier
    • spend systems where note position, note identifier, or path index is truncated for membership logic but not equally constrained for nullifier logic
    • circuits that verify ECDSA or Schnorr signatures and then treat the signature bytes themselves as replay-prevention material
    • privacy systems where nullifiers are derived from a witness that has both a semantic form and multiple wire-level representations
    • protocols that try to avoid private-key-in-circuit derivation by accepting a broader proof of possession object and then overloading it into uniqueness state
  • Exploit sequence:
    1. The attacker starts from one genuine spend right, claim right, or eligible address.
    2. They identify a nullifier derivation input that can vary without changing the underlying right: a malleable signature, a signer-controlled nonce, or an under-constrained bit-width-expanded witness.
    3. They generate one valid proof and consume the right under nullifier n1.
    4. They regenerate the proof from the same underlying right while varying that derivation input, producing a second verifier-acceptable nullifier n2.
    5. The contract sees n2 as fresh because replay protection only tracks prior nullifiers, not prior underlying rights.
    6. The same right is redeemed again, and the cycle can continue as long as the nullifier derivation remains many-to-one.
  • Variants:
    • Signature-malleability nullifier — the protocol hashes a valid signature and assumes the signature is unique, but (r, s) and (r, N-s) or more general valid signing randomness choices produce multiple nullifiers for the same authorization.
    • Witness bit-width drift — membership or correctness checks only constrain part of a witness (for example, low 32 bits of an index), while nullifier derivation consumes the whole field element, letting high bits vary.
    • Possession-proof overload — the system proves you know an authorization object and then incorrectly reuses that object itself as replay-prevention state even though many valid proofs-of-possession objects can represent the same right.
    • Canonicalization half-fix — the protocol patches one malleability form such as low-s enforcement but still leaves other signer-controlled nondeterminism or alternate encodings alive.

Three replay-protection promotions healthy systems should not collapse

  1. A witness-shaped object exists that can prove the right at all

    • A signature verifies, a note witness satisfies membership, a hidden index lands on the expected commitment, or a signer-produced envelope can prove control of the eligible account.
    • This is only the witness-validity question: some admissible proof input exists for this right.

  2. That witness-shaped object is the canonical replay-prevention identity for this exact right

    • This is the step vulnerable systems skip over. They quietly promote valid authorization witness into the one and only object that should be allowed to become nullifier material.
    • StealthDrop is the clean preserved case: a valid ECDSA authorization envelope existed, but the system had not proved that one claim right implied one admissible signature object.

  3. That accepted replay-prevention identity still deserves one-time economic authority here

    • Even once a witness-derived object looks canonical enough, the protocol still has to decide how much payout, claim, vote, or spend authority one fresh nullifier unlocks and whether any sibling right-tracking surface can catch mismatches.
    • Healthy systems do not let fresh nullifier observed stand in for fresh semantic right consumed unless those are already the same proved object.
  • Detection heuristics:
    • Ask whether the nullifier is derived from the underlying right itself or from a witness artifact that merely proves possession of that right.
    • For every nullifier input, ask could two distinct valid witnesses represent the same semantic right?
    • Fuzz witness-side bit widths, alternate encodings, and signature-generation choices while keeping the underlying spend right constant.
    • Compare the variables used in membership, ownership, or authorization checks against the variables hashed into the nullifier. If they are not constrained identically, the boundary is suspect.
    • Treat hash(signature) and similar constructions as red flags unless the signature scheme and the signing process are explicitly non-malleable and deterministic for the protocol’s purposes.
    • If privacy requirements are the reason the design chose hash(signature) or another hidden witness artifact, ask what hidden canonical right replaced the public claim slot, address, or note identity. If the answer is still the signature itself, the design has only hidden the right, not made it canonical.
    • If reviewers can point to one specific malleability branch but cannot name the full canonicalization argument for the witness object, assume the nullifier boundary is still under-specified.
  • Defenses:
    • Derive nullifiers from one canonical right object, not from a merely valid proof artifact that can have multiple representations.
    • If a witness component is assumed to be k bits, range-constrain it to k bits before any path that feeds nullifier derivation.
    • Use non-malleable, protocol-appropriate signature schemes or enforce canonicalization plus deterministic derivation strong enough to make one right map to one signature object.
    • If the protocol cannot constrain signature creation itself, do not promote the resulting signature envelope into nullifier state just because signature verification already fits in the circuit.
    • Prefer nullifier constructions that bind directly to note secrets, canonical indices, or other uniquely constrained protocol state rather than signer-produced envelopes.
    • Add regression tests that hold the underlying right fixed while varying every admissible witness degree of freedom; all such attempts should collide to the same nullifier or fail.

What sound design looks like

  • Healthy systems keep three facts separate on purpose: some witness can prove the right, this exact witness-side object is canonical replay-prevention identity for that right, and this accepted replay-prevention object is allowed to unlock one-time economic authority here.
  • A healthy design has one semantic right and one nullifier for that right. Reviewers should be able to point to one canonical object whose uniqueness is fully constrained before it ever touches replay-protection state.
  • Membership logic, ownership logic, and nullifier derivation should consume the same constrained representation. If low bits decide membership but full-width values decide nullifier derivation, the system already has two different rights.
  • Proof systems should distinguish object that proves ownership from object that is safe to store as replay-prevention state. Those are often not the same thing.
  • Signature-backed flows should assume signatures are authorization envelopes, not naturally unique identifiers, unless the scheme and workflow explicitly make them so.
  • Privacy pressure does not excuse witness nondeterminism. If a public address hash or claim-slot hash would be too easy to brute-force, the answer is to derive a hidden canonical right object, not to promote a signer-produced authorization envelope into replay-prevention identity.
  • We already fixed low-s is not a canonicality proof. The real question is whether any signer-controlled or representation-level degree of freedom still remains between one right and one nullifier.
  • The clean reviewer question is: if I keep the real spend right constant, what degrees of freedom remain that can still change the nullifier?
  • Nullifier right-object canonicalization discipline is the positive-design companion when the next question is how to define the underlying one-time right early enough that witness artifacts never become replay-prevention identity by accident.
  • High-signal incidents:
    • double-claim near miss (2022-02-15) — the clean signature-backed exemplar where the protocol treated a valid ECDSA signature as a unique nullifier source even though one claim right admitted multiple valid signatures; the public design README had already discussed (r, s) versus (r, N-s) and low-s canonicalization, which makes the surviving bug a stronger warning that noticing one malleability branch is still far short of proving one signer-produced envelope == one nullifier.
    • Useful contrast: Semaphore nullifier field-modulus aliasing and a16z ZkDrops show the sibling family where the same logical nullifier crosses the verifier / storage boundary under multiple raw encodings rather than being many-to-one already at derivation time.

Failure-prevention checklist

  • Identify the exact semantic object that grants one-time rights, then prove the nullifier is a deterministic and canonical function of that object rather than of a looser witness artifact.
  • Range-constrain every witness component before any branch that feeds nullifier derivation. Do not rely on one downstream gadget to effectively use only some bits while another gadget consumes the full field element.
  • Treat signature verification, replay-prevention identity, and one-time payout authority as separate design problems. A signature scheme being valid for authorization does not make it safe as a unique identifier, and a fresh nullifier does not by itself prove a fresh semantic right was consumed.
  • If signatures are involved, document all malleability and signer-choice degrees of freedom: low-/high-s, nonce selection, alternate encodings, recovery id handling, and any wallet-specific normalization behavior.
  • Separate we ruled out one known alternate signature form from we proved the signing workflow yields exactly one admissible nullifier witness. Those are different review conclusions.
  • Prefer replay-protection designs that track one canonical note secret, canonical note index, or other protocol-native unique object instead of signer-produced envelopes.
  • Add regression tests that replay the same right with altered signature randomness, alternate signature encodings, widened witness values, and any high-bit variations that preserve the checked low-bit semantics.
  • Keep the nullifier derivation logic adjacent to the constraints that make its inputs unique. Separation between this proves ownership and this hashes into the nullifier is where multiplicity leaks in.
  • During upgrades or library swaps, re-prove that the new verifier, wallet integration, or signature adapter still gives one semantic right exactly one admissible nullifier.
  • Monitor for impossible economics such as repeated claims from one eligibility slot or repeated spends whose note-membership evidence traces back to the same committed object.
  • Treat nullifier uniqueness as an invariant worthy of property testing, not just example-based happy-path tests.

Audit prompts

  • What exact object is the nullifier derived from, and is that object itself uniquely constrained for one semantic right?
  • Can two different valid signatures, proofs, or widened witness values correspond to the same authorization while hashing to different nullifiers?
  • Do membership checks, ownership checks, and nullifier derivation consume the same bit width and same representation of every shared input?
  • If a wallet or signer can choose randomness, low-/high-s, or other formatting details, does any of that survive into replay-protection state?
  • Is the protocol using proof of ownership material as if it were a canonical identifier when it is really just one admissible witness among many?
  • What property test demonstrates that holding the underlying right constant leaves zero remaining degrees of freedom that can change the nullifier?
  • If canonicalization is enforced, where exactly is it enforced, and does every caller path share that same enforcement?
  • If a design doc already identifies one malleability branch, what proves that the remaining signer workflow still cannot produce multiple verifier-acceptable nullifier witnesses for the same right?
  • Could a future migration to a different wallet API, signature library, or circuit backend silently widen the space of verifier-acceptable nullifier inputs?
  • If the protocol patched one malleability vector, what proves there are no remaining alternate valid derivations for the same right?
  • What onchain or offchain evidence would reveal that the same eligibility slot or note is being redeemed under multiple nullifiers?

Lessons that should already be standard

  • Nullifiers only give one-time semantics if the derivation path is canonical. We hash something hard to invert is not enough.
  • A valid witness exists is weaker than this witness is the canonical replay-prevention object, which is weaker than this fresh nullifier deserves one-time economic authority right now.
  • Authorization artifacts are not automatically identity artifacts. A valid signature or valid witness can prove control of a right without being a unique encoding of that right.
  • Witness-side multiplicity is just as dangerous as contract-side aliasing. The replay can already be baked into the proof before calldata ever reaches Solidity.
  • Bit-width assumptions are security boundaries. If one circuit gadget sees last 32 bits and another sees full field element, the protocol has already defined two different realities.
  • Signature malleability and signer-controlled randomness are replay surfaces when signatures feed uniqueness state, not just when they feed transaction acceptance.
  • Hiding the right is not the same as canonically defining the right. Privacy-driven systems still need one protocol-owned hidden claim object rather than whatever valid signature the wallet happened to produce.
  • Catching one obvious alternate encoding is not enough. Replay protection needs a positive canonical object, not just a blacklist of a few bad representations.
  • The healthiest nullifier designs are boring: one canonical secret or index, one constrained representation, one derived nullifier, everywhere.
  • Replay-protection reviews should always ask both questions: can the same nullifier appear under many encodings? and can the same right generate many nullifiers?

Where this pattern stops

  • Use nullifier-canonicalization-failure when the same logical nullifier already exists but crosses the verifier / storage boundary under multiple raw encodings such as n versus n + q.
  • Use public-input-domain-mismatch when the broader issue is that some proof-facing value crosses from unrestricted contract integers into finite-field semantics, but replayable nullifier multiplicity is not the sharpest expression of the bug.
  • Use witness-public-input-binding-failure when the proof statement itself becomes underbound and proves the wrong relation rather than preserving one right but allowing many nullifier derivations from it.
  • Use duplicate-claim-idempotency-failure when duplicate redemption does not depend on zk witness multiplicity at all and instead comes from ordinary application-level bookkeeping.
  • In short: this pattern begins once one semantic right can produce multiple verifier-acceptable nullifiers at derivation time, and it stops once the sharper story is instead raw-encoding aliasing, general field-domain mismatch, or a non-zk idempotency bug.

Internal linkages

Control surface

Graph View

Backlinks