Nullifier tree about anon HOT 9 CLOSED

Hmm I kinda understand what you're getting at. Though I'm not sure this will work in practice. Our field is quite larger than 2^32, and nullifiers are expected to be random elements there. So this would require some decent amount of preprocessing to select nullifiers, likely more than simply generating a random value in the field to use as one.

You do bring up a good point about storage, though if we reach that storage limit it's definitely a double-edged sword. It will be a hugely populated tree! This is good to think about though.

from anon.

Since we initialize all the leaves as 0, the preprocessing is basically like the one you did previously: https://github.com/edgeware-builders/anon/blob/1f2a7f589b43d1cc58ecc3f9a486f16bdc9b36f4/pallets/merkle/src/lib.rs#L155-L173 just for 256 height (our field is 2 ** 256?). This can be done off-chain and stored into a constant and reused when a new tree is created

EDIT: I guess what I'm explaining is a sparse tree

from anon.

I guess what I'm trying to say is that nullifier corresponds to an index of a leaf node in some sparse tree. We initialize all leaves as 0, and when a nullifier gets used, we update the leaf node at that index (we set it to 1).

from anon.

The downside is that users would need to sync their clients before verifying ZK proof, which could become a problem if a lot of people wants to do it at once

from anon.

This is also the case for the group tree, which can be solved by periodically saving the tree state users will prove against. The period should be long enough so all the nodes can sync before trying to submit the proof

EDIT: I guess this is happening by default, given how blockchain works this is not true after all

from anon.

Closing until we find a solution to this:

The downside is that users would need to sync their clients before verifying ZK proof, which could become a problem if a lot of people wants to do it at once

from anon.

We introduce a queue of nullifiers + their paths. Every time user submits a nullified, we check if it isn't in the tree using the method above, and we also check if it isn't in the queue. Then we insert the nullified and the path into the queue.

Every t block we take all nullifiers from the queue and insert it in the tree using the provided path. At each insert, we have to keep track of changed nodes on each level (this doesn't need to be in the storage) to be able to insert the next nullifier.
This computation can be done inside on_finalize or using an off-chain worker.
In the end, we delete nullifiers from the queue and their paths

from anon.

@drewstone Let me know your solution

from anon.

The solution is to add nullifiers into yet another incrementally built merkle tree and then require users to provide non-membership proofs to this merkle tree. It would require the user to still get all the nullifiers in order to generate this proof. I think given the complexity of this I will still hold off from implementation and resort to storing nullifiers on chain. We can continue to spec this part out as an update/optimisation.

from anon.