L1 Nullifier Sets: Consensus-Layer Double-Spend Prevention in a UTXO-Based Privacy Chain

1. Introduction

A shielded UTXO chain reveals neither sender, recipient, nor amount on chain. To prevent double spends without revealing the spent note, every shielded protocol since Zerocash (Ben-Sasson et al., 2014) has used a nullifier: a deterministic single-use identifier $\mathsf{nf}$ derived from a secret known only to the spender and the public commitment of the consumed note. The chain treats the global set of disclosed nullifiers as state; a duplicate nullifier indicates a double spend.

The structural question every such chain must answer is where the nullifier set lives. The historical answers — wallet-side index, smart-contract sidechain, consensus-layer state — span a spectrum of soundness, operator-trust, and engineering complexity. The Zcash protocol (Hopwood et al., 2022) places the set in node chainstate; the Tornado-style Ethereum deployments place it in a contract; some lighter-weight UTXO experiments leave it to the wallet.

We focus on a specific point in this design space: a Bitcoin-fork chain that carries the nullifier set in consensus state. We refer to such a chain as an L1-nullifier chain. The contribution of this paper is:

1. A chain model that extends the Garay–Kiayias–Leonardos backbone protocol (Garay et al., 2015) with a shielded UTXO type and a chainstate-resident nullifier set.
2. A soundness theorem establishing that in this model the probability of an accepted double spend is bounded above by the probability of a hash collision in the underlying nullifier construction.
3. A proof sketch reducing soundness to the collision resistance of the hash used to derive nullifiers — in our instantiation, Poseidon-2 (Grassi et al., 2023) over the BN254 scalar field.
4. A treatment of two extensions: compressed-account chains where notes are batched into a Merkle commitment per block, and the operator cost of maintaining a sparse Merkle tree (Buterin et al., 2016) over the nullifier set under adversarial insert orderings.

The paper is theorem-statement in shape and engineering-aware in spirit. Where empirical claims appear, they are flagged.

2. Chain model

We adopt the backbone abstraction of Garay et al. (Garay et al., 2015) with three additions.

Definition 2.1 (Shielded UTXO chain). A shielded UTXO chain $\mathcal{C}$ is a sequence of blocks $B_0, B_1, \dots$ where each $B_i$ contains:

1. A set of transparent transactions $\mathsf{Tx}^t_i$ in the standard Bitcoin sense.
2. A set of shielded transactions $\mathsf{Tx}^s_i$. Each $\tau \in \mathsf{Tx}^s_i$ contains:
   • A vector of new commitments $\{C_j\}$ — Pedersen commitments (Pedersen, 1992) to values not visible on chain.
   • A vector of spent nullifiers $\{\mathsf{nf}_k\}$ — the nullifier outputs of consumed notes.
   • A zero-knowledge proof $\pi$ asserting that the spent notes were valid and unspent at some prior block.
3. A coinbase commitment to the root of the global nullifier set $\mathsf{NS}_i$ as of block $i$.

A node maintains $\mathsf{NS}_i = \bigcup_{j \le i} \bigcup_{\tau \in \mathsf{Tx}^s_j} \{\mathsf{nf}_k : \mathsf{nf}_k \in \tau\}$ as part of its chainstate, together with the standard UTXO set.

Definition 2.2 (Validity). Block $B_i$ is valid with respect to $\mathcal{C}|_{<i}$ if:

1. Every transparent transaction in $\mathsf{Tx}^t_i$ is valid by Bitcoin script rules.
2. For every shielded transaction $\tau \in \mathsf{Tx}^s_i$, the proof $\pi$ verifies under the canonical shielded-spend relation.
3. No-collision rule: For every spent nullifier $\mathsf{nf}_k$ in $B_i$, $\mathsf{nf}_k \notin \mathsf{NS}_{i-1} \cup \bigcup_{\tau' \in \mathsf{Tx}^s_i \setminus \{\tau\}} \{\mathsf{nf} : \mathsf{nf} \in \tau'\}$.
4. The coinbase’s $\mathsf{NS}$-root commitment matches the recomputed root after applying $B_i$‘s nullifiers.

The no-collision rule is the central addition. Under the standard backbone semantics, an honest node observing a block whose shielded transactions reuse a nullifier rejects the block. The block is not “valid until someone notices”; it is invalid at the consensus boundary, in the same way a transparent transaction spending an absent UTXO is invalid.

Definition 2.3 (Double spend). A double spend against $\mathcal{C}$ is a pair of accepted shielded transactions $\tau, \tau'$ in the same chain history such that $\tau \neq \tau'$ and $\exists\, \mathsf{nf} : \mathsf{nf} \in \tau \cap \tau'$.

3. Soundness

Theorem 3.1 (Soundness of L1-nullifier-set enforcement). Let $\mathcal{C}$ be a shielded UTXO chain as in Definition 2.1, with nullifier function $\mathsf{nf} = H(sk, C)$ where $H$ is a $(\lambda)$-collision-resistant hash and $sk$ is uniformly distributed in the note’s secret-key space. Then, conditioned on the underlying backbone protocol’s common-prefix and chain-quality properties (Garay et al., 2015) holding with parameter $\epsilon$, the probability that an accepted block contains a double spend is at most $\mathrm{negl}(\lambda) + \epsilon$.

Proof sketch. Let $\tau$ and $\tau'$ be two shielded transactions sharing a nullifier $\mathsf{nf}$. Two cases.

Case A. $\tau$ and $\tau'$ consume the same underlying note. By construction of the proof system, the existence of a valid $\pi$ for both transactions implies both knew the witness $(sk, C)$ for the consumed note. The chain accepts at most one such transaction by the no-collision rule (Definition 2.2, clause 3). Acceptance of both therefore violates the no-collision rule and constitutes a consensus violation, not a soundness violation: such an acceptance can occur only if the backbone’s common-prefix property fails, which happens with probability $\le \epsilon$.

Case B. $\tau$ and $\tau'$ consume distinct notes that produce the same nullifier. This requires $H(sk_1, C_1) = H(sk_2, C_2)$ with $(sk_1, C_1) \neq (sk_2, C_2)$, i.e., a collision in $H$. By assumption $H$ is $(\lambda)$-collision-resistant, so the probability of this case is $\mathrm{negl}(\lambda)$.

A union bound over the two cases yields the theorem.

The structure of the argument deserves comment. The interesting work is done by the no-collision rule, which lifts double-spend prevention from a wallet-side liveness property (where one trusts every wallet to refuse to construct a colliding spend) to a chain-wide safety property (where a colliding block is rejected by every honest node regardless of who produced it). The proof is then almost trivial; this is the point. A clean primitive admits a clean theorem.

3.1 Concrete instantiation: Poseidon-2 over BN254

In our reference implementation, $H(sk, C) = \text{Poseidon2}_t(sk, C)$ with $t = 3$ and the BN254 (Barreto & Naehrig, 2006) scalar field. Poseidon-2 (Grassi et al., 2023) inherits the cryptanalytic argument of the original Poseidon design (Grassi et al., 2021) with simplified round structure, and is currently the subject of active analysis (Bariant et al., 2023). Under the standard sponge indifferentiability argument (Bertoni et al., 2008), Poseidon-2 is collision-resistant against generic adversaries up to the output bound, which for the BN254 field with a 256-bit output gives $\lambda = 128$ bits of collision resistance — sufficient for practical deployment.\note{TODO: empirical validation — confirm cryptanalytic state-of-the-art for Poseidon-2 at submission time. Bariant et al. 2023 introduces a degree-of-freedom argument worth surveying.}

Theorem 3.1 then specialises to the statement that, conditioned on the backbone holding, the probability of an accepted double spend on this chain is $2^{-128}+\epsilon$ — for any plausible $\epsilon$, the cryptographic term dominates the operational term, which is the desired regime.

4. Storage and synchronisation costs

The headline cost of consensus-resident nullifier sets is monotonically increasing storage. Each accepted shielded spend permanently extends $\mathsf{NS}$ by $|H|$ bytes. We give a back-of-envelope analysis.

For Poseidon-2 over BN254, $|H| = 32$ bytes. If the chain achieves a long-term steady state of $k$ shielded spends per block at a block interval of $T$ seconds, the annual nullifier-set growth is

For a one-minute-block chain ($T = 60$) with five shielded spends per block, $\Delta_{\text{year}} \approx 84$ MB.\note{TODO: empirical validation — confirm against measured Vanta block telemetry once a steady-state shielded-spend rate is established.} Over a decade this yields $\approx 840$ MB of nullifier state, well below the current Bitcoin UTXO set (Bonneau et al., 2015).

Synchronisation cost is dominated by the $O(\log n)$ sparse-Merkle insertion path per nullifier, where $n$ is the size of $\mathsf{NS}$. Provided that nodes maintain $\mathsf{NS}$ as an SMT (Buterin et al., 2016) with hash-array-mapped-trie compression, the per-insert cost is on the order of microseconds, and the per-block insert batch is dominated by the proof-verification time of the shielded transactions, not the SMT maintenance.

4.1 Initial-block-download cost

The initial-block-download (IBD) cost dominates the operator experience for a new node joining the network. Concretely: how long does it take for a freshly synced node to reach tip, given that it must validate every shielded transaction in the chain’s history?

The validation cost per shielded transaction breaks down into three components:

1. The script-validation cost (transparent path), unchanged from upstream Bitcoin.
2. The proof-verification cost. For Groth16 (Groth, 2016) verification on BN254 with three pairing operations, this is approximately 30 ms per proof on a modern CPU.
3. The nullifier-set membership check and SMT update, approximately 100 µs per nullifier on a SSD-backed implementation.

Component (2) dominates by two orders of magnitude. A back-of-envelope calculation: assuming 5 shielded spends per block at 30 ms verification each, the per-block proof cost is 150 ms. For a one-minute-block chain over ten years, this is $5 \cdot 525{,}600 \cdot 10 \cdot 0.030 \approx 22$ hours of pure CPU time, which scales linearly with the number of cores available for parallel proof verification. On a 16-core machine, IBD completes in under 90 minutes — comparable to Bitcoin’s transparent IBD.\note{TODO: empirical validation — measure on production hardware once the chain has substantial history.}

The takeaway is that IBD is feasible but not trivial. Operators running on resource-constrained hardware (single-core SBCs, embedded systems) should be advised that IBD is the primary bottleneck and that the chain’s hardware floor is set by proof-verification performance.

4.2 Pruning the proof, not the nullifier

A natural follow-on question to §6.2’s discussion of nullifier pruning: can we instead prune the proofs that established the validity of historical shielded spends, while retaining the nullifiers themselves?

The answer is yes, and our reference implementation does so: a node that has reached the network’s checkpointed tip discards proof bytes for transactions older than a configurable horizon, retaining only the nullifier and the commitment-tree root. The savings are substantial — proofs are 256 bytes in our Groth16 instantiation, so over a decade with 5 spends per block one saves roughly $5 \cdot 525{,}600 \cdot 10 \cdot 256 \approx 6.5$ GB of proof data.

The soundness of pruning rests on the same assumption that justifies pruning the witness data of confirmed transparent transactions: a sufficiently-confirmed shielded spend will not be reorganised, and a node that joins after the prune horizon has elapsed must trust the network’s checkpoints to validate history rather than re-verifying every proof. This is a standard SPV-style assumption and is conventionally accepted.

5. Extension: compressed-account chains

A compressed-account chain batches notes into a single Merkle commitment per block to reduce on-chain storage; the chainstate stores roots, not individual notes. The natural extension of L1 nullifier sets to compressed-account chains stores not individual nullifiers but a Merkle tree of nullifiers per block, with the per-block root committed in the coinbase.

The soundness statement (Theorem 3.1) carries over with minor modifications. The no-collision rule generalises to: for every spent nullifier in the block, no preceding block’s nullifier-tree contains it, and no other transaction in this block discloses it. Membership proofs replace direct lookup. The asymptotic cost of a membership proof is again $O(\log n)$ but now with a larger constant due to the per-block tree maintenance overhead.

We do not pursue a full proof of the compressed-account variant in this paper; we register only that the soundness argument transfers, conditioned on the membership-proof verifier being itself sound — a property the underlying SNARK already provides.\note{TODO: empirical validation — formalise once a reference compressed-account UTXO chain ships in production.}

6. Two open questions

We close with two questions our own engineering experience has not yet resolved.

6.1 Adversarial insert ordering

A sparse Merkle tree’s per-insert cost depends, in the worst case, on the depth of the longest currently-occupied path. An adversary that influences the order of nullifier insertions — by, e.g., populating insertion blocks with adversarially-chosen shielded transactions — could in principle drive insertion paths toward a worst-case profile, increasing per-block validation time. We do not have a tight bound on the adversary’s leverage here. Existing analyses of Merkle-tree insertion costs assume uniformly random keys, which is an unrealistic assumption when the keys are hash outputs the adversary partly chooses.

This is sharper than the corresponding question for transparent UTXO sets, where insertion order is largely unconstrained, because nullifier values are deterministically derived from the spending witness. An adversary controlling a fraction of block-production capacity has bounded but non-zero influence over the nullifier stream. Open question. Bound the worst-case per-insert cost as a function of the adversary’s mining-power fraction.

6.2 Pruning under monotonic growth

The nullifier set is, by construction, monotone: nothing is ever removed. After ten years of operation a chain with substantial shielded-spend volume will accrete several gigabytes of nullifier state. We do not have a satisfying answer to when, if ever, it is safe to prune. Pruning under the canonical model breaks soundness: a pruned nullifier could be re-spent.

A speculative direction: pruning conditioned on a soundness-preserving accumulator structure that retains a constant-size membership proof for any past nullifier. We do not pursue this here.

6.3 Witness-availability in light-client settings

A third question the engineering literature touches but has not, to our knowledge, formalised: under what conditions can a light client verify that an alleged nullifier set is faithful? A light client does not store the full $\mathsf{NS}$; it stores commitment-tree roots and verifies SPV-style. The coinbase commitment to the SMT root of $\mathsf{NS}_i$ allows a light client to verify, given a membership proof, that a particular nullifier is included or excluded as of block $i$.

The verification cost is logarithmic in $|\mathsf{NS}_i|$, but the proof construction is performed by full nodes, which have an incentive to truthfully serve membership proofs to light clients only insofar as the underlying chain is honest by hypothesis. A light client receiving a fabricated exclusion proof from a malicious full node has no recourse if the underlying merkle root does not commit to enough information to detect the fabrication. We rely on the SMT’s structural property that exclusion proofs in a sparse Merkle tree are unique and verifiable — given a leaf path, either the leaf is empty (and the path’s hashes match the root) or the leaf is occupied (and the path includes the occupant). An adversary cannot forge an exclusion proof for a present element, conditioned on the SMT hash function being collision-resistant.

This reduces the light-client safety argument to the same Theorem 3.1 — collision resistance of the underlying hash — without introducing a new trust assumption.

6.4 Re-org tolerance and finality

A separate question concerns how nullifier-set state behaves under chain reorganisations. Bitcoin’s UTXO set is reorg-tolerant by construction: a UTXO that is spent in a block, and then the block is reorganised away, is restored as unspent. The same property must hold for the nullifier set: a nullifier consumed in a block that is subsequently orphaned must be removed from $\mathsf{NS}$, returning the corresponding note to the unspent state.

In our reference implementation this is straightforward — the nullifier set is maintained as part of the chainstate snapshot, and chainstate rollbacks happen atomically with block-level rollbacks. The implementation cost is confined to the SMT update logic: deletions during reorg are operationally identical to insertions during apply, with the input ordering reversed.

The interesting subtlety is that selfish-mining attacks (Eyal & Sirer, 2014) (Sapirshtein et al., 2016) interact with the nullifier set in the same way they interact with the transparent UTXO set: an attacker who withholds a block can construct a competing chain with a different nullifier history, and the network may converge on either. A spender whose transaction is reorganised away should be informed by their wallet, exactly as a transparent-transaction spender is informed by their wallet. The nullifier set inherits the reorg semantics of the underlying chain; it does not introduce a new finality caveat.

7. Conclusion

We have shown that a Bitcoin-fork shielded UTXO chain that places the nullifier set in consensus state admits a clean soundness statement (Theorem 3.1) reducing double-spend prevention to the collision resistance of the underlying nullifier hash. The cost is monotonic chainstate growth, manageable in practice for plausible shielded-spend rates (Bonneau et al., 2015) and below current Bitcoin UTXO-set sizes for a decade-scale operating window.

The architectural argument is that consensus is the right place for safety properties. Wallet-side enforcement is a liveness property that the network depends on every wallet implementer to honour. Consensus-side enforcement makes the rule binding for every honest node regardless of wallet provenance. For privacy chains aiming at the same finality semantics as transparent Bitcoin, the consensus-side answer is the structurally honest one.

References