Nullifier Tree for O1js
Upgrade from sparse merkle trees, build private applications at scale
Created on 12th November 2023
•
Nullifier Tree for O1js
Upgrade from sparse merkle trees, build private applications at scale
The problem Nullifier Tree for O1js 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.
Challenges I ran into
proof generation is slow
Tracks Applied (1)
O(1)Labs - ZK Data Structure
O(1)Labs
Technologies used