I built a FROST-based wallet for the ZecHub hackathon and noticed one problem that I was having in testing it out and then trying to get the coordination part between parties to line and all and it came down to syncing the wallet in a timely fashion so that the party can do their thing (ie sing transactions, coordinate, etc…) and not have to wait a long time for their wallets on their computers to sync up for a long time. Spent some time working with my clanker to try and optimize different options and what other open source projects did and came upon Accumulators (like utreexo for Bitcoin) that seemed interesting and started to try and play around with it to see if there was anything there. An accumulator allows you to gain the validation of transactions or membership using specialized merkle trees, but if we look at the nullifier set we are wanting to prove non-membership.
Bitcoin’s answer to the analogous problem is Utreexo. The obvious question is whether it transfers. It mostly doesn’t, and the interesting part is why:
- Transparent UTXOs → Utreexo transfers directly. Same operations.
- Nullifiers → Utreexo is the wrong primitive. It proves membership; nullifier checking needs to prove non-membership, and you cannot prove absence from an unordered accumulator without holding the whole set. The right structure is an indexed Merkle tree: leaves hold
(value, next_value, next_index), keeping the set sorted via a linked list, so absence ofxis proven by exhibiting the leafLwithL.value < x < L.next_valueplus an ordinary Merkle path. - Note commitment trees → leave alone. Already an append-only frontier, membership proven inside the circuit.
I built all three, with per-pool parameterisation from day one (Sprout, Sapling, Orchard, Ironwood, both Orchard and Ironwood nullifier sets are live indefinitely, since Orchard drains rather than empties post Ironwood activation).
Then I measured it, expecting to confirm the pitch. The measurements substantially disagreed with the pitch, which is why I’m posting.
The measurements
Baseline = zebrad 6.3.0, mainnet, synced to height 3,444,700, on a 12th-gen i5 laptop:
| Total node state on disk | 298 GB |
| Initial block download, genesis → tip | 19.4 h |
| Peak RSS during IBD | 5.07 GiB |
| Shielded nullifiers per block | 9.264 (Orchard 6.192, Ironwood 2.934, Sapling 0.138) |
| Transparent inputs / outputs per block | 7.118 / 5.716 |
Accumulator primitives — indexed Merkle tree at depth 32:
| Operation | 10⁴ nullifiers | 10⁶ nullifiers |
|---|---|---|
verify_non_membership |
4.14 µs | 4.13 µs |
prove_non_membership |
1.27 µs | 2.68 µs |
insert |
18.1 µs | 21.1 µs |
Verification is flat across a 100× increase in set size ~127 ns per tree level, i.e. exactly one BLAKE2b compression per level and nothing else. The asymptotic claim holds.
Proof sizes: 1,106 bytes non-membership, 2,139 bytes insertion.
Result 1: the validating-node case doesn’t survive contact with the numbers
The pitch is “hold a few kilobytes instead of the full nullifier set.” That’s true. What nobody had measured is how big the nullifier set actually is relative to everything else a node stores.
Of 298 GB of node state, the nullifier set is on the order of 0.3–0.9 GB just under one percent. The rest is block and transaction history, which an accumulator does not touch. The structure we’re compressing to nothing was never what made a node expensive.
(That range is the one estimated figure in this post, and I’d welcome a correction. Zebra doesn’t expose a nullifier count, so it’s derived from the measured flow, 9.264/block over ~3M post-Sapling blocks at 32 bytes, rather than counted. Getting the exact number means a full-history scan or reading RocksDB directly. It would have to be off by two orders of magnitude to change the conclusion.)
And you pay for the privilege. A node holding only roots must be sent a proof per spend:
| Per year | |
|---|---|
| Storage avoided (nullifier set growth) | ~125 MB |
| Proof data downloaded instead | ~8.3 GB |
That’s ~66× more bandwidth than the storage saved. Per block it’s 19.4 KB of proofs against a median block of 13.6 KB, the proofs are larger than the blocks they describe.
Batching helps: proofs for spends in the same block share internal nodes, and consecutive appends share nearly their whole path. My rough estimate is that this gets ~19.4 KB down to ~11 KB. That improves the trade. It does not reverse it.
If you are a full validating node, this is not worth doing. So that means a validating node is not worth doing.
Result 2: the transparent half is doubly dead
Two independent findings:
- Zcash’s transparent UTXO set is not growing. 7.118 inputs against 5.716 outputs per block; netting out coinbase, roughly flat. Utreexo’s saving is proportional to the set it replaces, so a flat set means the saving never compounds while the proof cost is paid forever.
NOTE: This is proof of the more shielding happening onchain as people have been migrating funds from transparent addresses to shielded address, which should make many here happy.
Given the trends, building a utreexo-like MMR for the transparent pool may or may not be worth it, but still open to feedback or thoughts on it.
Result 3: Wallets might be the place best suited for this
The one case that looks genuinely good is a wallet resuming after a long absence. Today it learns whether its notes were spent by scanning every nullifier revealed since it last synced, linear in the gap. With an indexed Merkle tree it’s one proof per note, independent of chain length:
| Wallet offline for | Nullifiers revealed | Scan cost today | Proofs (10 notes) |
|---|---|---|---|
| 1 month | 0.32 M | 10 MB | 11 KB |
| 1 year | 3.90 M | 125 MB | 11 KB |
| 3 years | 11.7 M | 374 MB | 11 KB |
The right-hand column doesn’t grow. That’s a real asymptotic improvement.
But there’s a catch, a wallet still has to find its notes, and today the only way is trial decryption over every shielded output. While it streams those blocks it receives the nullifiers anyway. So against today’s light-wallet protocol, the nullifiers are only about 21% of what the wallet downloads regardless ztreexo saves that 21%, which is real but ordinary.
The 1,000×–30,000× version only materialises in a world where trial decryption has already been solved by something else. I’m curious to see if this is something that Tachyon is planning to solve, which would negate investing time into it.
My understanding, because I’m working from public summaries rather than the current design is that Tachyon’s core move is to make a wallet’s sync work proportional to its own activity rather than to chain length, with senders handing recipients the state they need out-of-band, and that private information retrieval has been under discussion for the pieces that remain server-mediated.
If that’s right, then Tachyon plausibly already covers the only use case my measurements say is worth pursuing. Specifically:
-
Under Tachyon, how does a wallet learn that a note it holds has been spent particularly on restore-from-seed, where it doesn’t know its own history? Is that cost proportional to the wallet’s note count, or to elapsed chain length?
-
Is there still a global nullifier set that full nodes must retain for double-spend prevention, and if so, does its size/growth remain an unbounded liability under Tachyon, or does the design bound it?
-
If PIR ends up serving nullifier queries, does it give a better privacy story than bridge-served non-membership proofs? Asking a server for a specific nullifier’s proof is a metadata leak my own design notes flag it as a gating review item, and PIR looks like a strictly better answer to it if the performance works out.
-
Is there anything in an authenticated, sublinear non-membership structure that composes usefully with Tachyon ie letting a light client verify a server’s “not spent” answer rather than trusting it — or does Tachyon already have an authenticated path there?
I’m not looking for anyone to adopt anything. I’m trying to establish whether this is duplicated effort.
