Owner: @David Rusu
Reviewers: š”@Mehmet š“@Thomas Lavaur š”@Ćlvaro Castro-Castilla
The goal is to compact the commitment and nullifier sets to resolve the problem of unbounded state growth in private transaction systems.
The paper first describes an uncompacted version, and then compacts it using āMerkle Mountain Rangesā.
Proofs of non-membership (which are needed for proving that a nullifier has not been spent) are done by representing the nullifier set as a bloom filter.
To prove non-membership with a bloom filter, you can show that at least 1 of the $k$ bloom filter probes is inactive. On the other hand, bloom filter have false positives, and the rate of false positives increase with the number of elements in the set.
To resolve this overcrowding problem, the authors substitute the bloom filter for a Sliding Window Bloom Filter (SWBF) which as the name suggests, moves the window that set elements probe into as the nullifier set grows.
In the un-compacted version, the protocol state holds to ever-growing lists:
A sliding window bloom filter projects the commitmentās nullifiers from the commitments list onto the bitmap through $k$ probes. ($k=3$ in the following example)

The top list represents the growing list of commitments, the bottom bitfield represents the state of the bloom filter. The rainbow shows the mapping of commitments onto the bitfield
Nullifiers for commitments can only touch the bloom filter window corresponding to their location in the commitment list. This does imply a temporal link between when a commitment was created and when it was spent, but in practice we make the bloom filter so large that anonymity set is sufficiently large.
In this example, every 3 commitments added to the commitment list shifts the sliding bloom filter window by 4 bits.
Their key insight here is that in order to avoid over-crowding a bloom filter, we can simply slide forward in the infinite bloom fieldās bitfield to make space for new commitments. This is of-course untenable long term, hence the need for compaction:
To compact the above design, weāll make use of two āMerkle Mountain Rangeā
A Merkle Mountain Range (MMR) is a list of Merkle Trees sorted descending by height, If any two Merkle trees in the range have the same height $h$, they are merged to form a single Merkle tree of height $h+1$. This folding process happens iteratively until all trees in the MRR are of different height.