Archiving historic nullifiers with mutator sets

[narodnik]

With #100, then Monero now has an infinitely growing nullifier set.

However it's possible to put a bound on this using merkle trees. Basically all coins belong to a large batch, call this index k. When spending the coin, we create an unlinkable nullifier and also reveal the batch index k.

All nullifiers for previous windows except the current active one are put in a merkle tree (a merkle mountain range to be precise). When spending, we have to show our nullifier isn't in the batch. An efficient way of doing this is using bloom filters instead of just storing the ordered nullifiers in the tree.

Then anyone else with coins in that batch, will update their set of nullifiers (the bloom filter) with the newly added nullifier. Users without coins in that batch don't need to keep track of those nullifiers.

This decreases privacy since the batch k that a nullifier belongs to is public, but the batch can be sufficiently large enough that it still provides practical strong anonymity while ensuring the nullifier set isn't unbounded. For example a batch could be for 2 years worth of coins.

Mutator Sets and their Application to Scalable Privacy by Alan Szepieniec .et al