Nullifier Tree for O1js
Upgrade from sparse merkle trees, build private applications at scale
About
The problem it solves Sparse merkle trees are often used for nullifier trees in the two tiered approach to privacy where the first tree holds the data and the second tree contains nullifiers. Using an indexed merkle tree rather then a sparse merkle tree allows for less data to be stored. The index merkle tree has a unique construction for a leaf where a leaf contains the current value, the next value and a pointer to the next value. One can do a proof of inclusion of a leaf to prove that a 'transaction' value is within the range of a leaf. This implies that the output has not yet been 'spent'. If one can prove the transaction is not in the nullifier tree then one can spend the transaction, subsequently updating the nullifier tree prevents a double spend. It is a scalable model, interesting to explore other applications. Useful to model "consumption" of a information.
How it's made
Challenges we ran into proof generation is slow