Notes on scaling nullifier sets

tl;dr: Trying to organize some thoughts on how to scale nullifier sets.

Approach 1: Sharded Herkle trees

High-level:

• Build depth-256 (or compressed, if possible) homomorphic Merkle prefix tree over global nullifier sets (e.g., via SADS¹)
• Shard the tree into “triangles” (e.g., a top triangle with $k$ leaves and $k$ other bottom triangles, but can have multiple levels of triangles; in fact can add them dynamically, as the tree “extends downwards”)
• Each triangle is managed by its own proof-serving node (PSN)
• Importantly, when a leaf $i$ changes by $\delta_i$ every PSN can locally update its portion of the path w/o waiting for other nodes or communicating with them $\Rightarrow$ extremely simple sharding
• Proof serving nodes can be incentivized to serve proofs (see Hyperproofs²)

Approach 2: Tachyon

Just some loose notes for now (will go into more depth as I understand later) from a few resources:

• Sean Bowe’s blog in April 2025
• Sean Bowe’s original tweet announcement
• Replies between me and Wei Dai on Twitter regarding the interactive payment flow
• Sean Bowe’s notes on a possible SNARK-friendly accumulator scheme for this
• Sean Bowe’s notes on Tachyon
• Tweet about my understanding of Tachyon in Oct. 2025
• Mike O’Connor’s post
• Mike O’Connor’s clarification on how you precompute some nullifiers and then send one to whomever is trying to pay you.
  • This makes the recursive proof more efficient because, I suppose, you can prove in batch that all of your precomputed nullifiers have not yet been spent:

Some disadvantages:

1. it requires out of band communication during payments.
2. cannot recover funds from seedphrase only; need other dynamic state as well that is not on-chain
3. no more viewing keys (?)
4. cannot just give out your address to get paid: you have to give a place for the sender to include the extra info

Quotes from Sean Bowe:

as the wallet state updates to reflect new blocks it will continually maintain a proof of its own correctness. Then, when it’s time to spend our funds we will extend our transaction with this proof-carrying data. This effectively attaches evidence that the transaction is valid up until a certain recent point in the history of the blockchain — the position of the anchor. The result is that validators are now only responsible for ensuring that the transaction is correct in the presence of the additional transactions that appeared in the intervening time, which just involves checking that the most recent block(s) do not contain the revealed nullifier. [15] As a result, almost everything in a block can be permanently pruned by validators and ultimately all users of the system as well. Despite transactions sharing a common state by being indistinguishable from each other, nearly all state contention problems vanish in this new approach.

[15] Together with the proof of the wallet’s validity, this demonstrates that the nullifier did not appear in another transaction that followed the block that created the note commitment being spent. Notably, this loosens the condition that the nullifier has never been seen before in the history of the blockchain but still manages to prevent double-spending.

Is the key observation that the TXN proves that the note’s nullifier did not appear in the nullifier set accumulated so far? But how do you construct that proof without the full set? Ah! You dont. You just need the nullifiers created between the note’s creation and the note being spent. And that’s what the wallet can prove recursively!

Other approaches

• Stateless validation: removes the validation state but introduces PSNs and needs the right approach
• Epoch-based nullifiers: freezes old nullifier sets
• Mutator sets 1 and 2: need to investigate

References

For cited works, see below 👇👇