arkworks-rs / ivls Goto Github PK

During the process to replace rand, we encounter an issue where the HelpCircuit's constraint system is not satisfactory.

This error is not triggered yesterday and based on the current attempts, it is likely due to other repos. We have not yet unveiled what the cause is.

Since ivls depends on a large number of repos, it is hard to conduct the debugging. I will start to take a look later this week after my other obligations are met. Likely I will start from PCD. We may have to go all the way back to algebra if FFT is indeed the reason.

This is the same as arkworks-rs/pcd#1.

IVLS has two instantiations of Merkle trees, one via Poseidon, one via Bowe-Hopwood variant of Pedersen. The problem with Poseidon, as the post above mentions, is that the parameter is hardcoded regardless of the curve and field. Sometimes, and in some situations, such parameters could be completely insecure.

This, therefore, means that the current repo is benchmark-purpose, and will wait for an upstream end-to-end implementation of a nice Poseidon sponge.

In some applications, we need non-membership proofs, which would be based on Merkle prefix tree (e.g., in CONIKS and Google Key Transparency) or self-balancing search tree (e.g., AVL tree).

Preliminarily, it seems that a search tree is better than a prefix tree because its height no longer depends on the security parameters.

But, note that for a self-balancing search tree to work, it requires a few changes to the tree:

• Middle nodes need to store data, instead of just the left nodes.
• Some self-balancing data needs to be stored, too.

This would mean that the overhead of CRH for each layer is higher, roughly 1.5x for Pedersen and 2x for Poseidon.

This means that, if the number of elements is large enough (e.g., supposedly 2^32), then the prefix tree (assuming the height is 2^80), which is much easier to implement, may not be too bad compared with the search tree.