creating more than one tree to contain uxto.

[yanyanho]

hi, I think about one solution to short the time to generate proof. I want to decrease the depth (for example set depth 5 rather than 32 )of merkeltree to shorten the time of generating proof. Meanwhile, I need to create more trees(depth is 5) to contain the utxo . Do you have the solution?

[dtebbs]

@yanyanho if we create multiple trees, a few possible problems may arise:

• either the primary inputs to the circuit will reveal which of the trees the commitment belongs to (leaking information to an observer), OR
• if you want to hide which tree the commitment belongs to, the proof must contain a proof that the depth 5 merkle proof you create results in the root of one of the N trees - effectively meaning the proof will need to build a merkle tree from the roots of the N trees. This will have an equivalent cost to creating the full tree in the first place.

As far as I can tell, we would need some way to address the above to avoid compromising the privacy of the system.

[AntoineRondelet]

Rather than "tweaking" the size of the anonymity set (on which we really shouldn't do any compromise IMO), the best way to diminish the proof generation time is to optimize the circuit by using more performant primitives: things like an algebraic PRF (that has a more succint R1CS representation that blake2s/sha256) and switch to a more efficient hash function in the Merkle tree. However, the right tradeoffs need to be made for the protocol to remain sound. It's often tempting to optimize for performances, but one needs to make sure that the protocol remains secure..!

While Ped Hash is provably collision resistant under DLOG (for fixed input length), some algebraic hash functions like Poseidon etc (which have very simple algebraic structures - and thus very efficient R1CS representations) still are pretty new and not universally deemed secure. Choosing MiMC here as we did, already is quite exotic, and requires some care (we only use it for collision resistance in the tree. In the rest we use more universally-agreed-to-be-secure hash functions/PRFs like blake2s), so I wouldn't advise to switch to things like Poseidon right away. Switching to Ped. Hash is a good alternative however, and this is something that we are considering already (the recent support of BLS12-381 on Geth is certainly a good news, as we can hash on Jubjub like the Zcash guys did (instead of hashing over baby-jubjub)). However, the Prover performances is not the only parameter to take into consideration here, as we also want to make it "cheap" to hash on-chain, and EC operations certainly are cheaper since the last Hardfork of Ethereum, but remain costly, so this is another parameter to take into consideration in your design decisions.

[yanyanho]

Rather than "tweaking" the size of the anonymity set (on which we really shouldn't do any compromise IMO), the best way to diminish the proof generation time is to optimize the circuit by using more performant primitives: things like an algebraic PRF (that has a more succint R1CS representation that blake2s/sha256) and switch to a more efficient hash function in the Merkle tree. However, the right tradeoffs need to be made for the protocol to remain sound. It's often tempting to optimize for performances, but one needs to make sure that the protocol remains secure..!

While Ped Hash is provably collision resistant under DLOG (for fixed input length), some algebraic hash functions like Poseidon etc (which have very simple algebraic structures - and thus very efficient R1CS representations) still are pretty new and not universally deemed secure. Choosing MiMC here as we did, already is quite exotic, and requires some care (we only use it for collision resistance in the tree. In the rest we use more universally-agreed-to-be-secure hash functions/PRFs like blake2s), so I wouldn't advise to switch to things like Poseidon right away. Switching to Ped. Hash is a good alternative however, and this is something that we are considering already (the recent support of BLS12-381 on Geth is certainly a good news, as we can hash on Jubjub like the Zcash guys did (instead of hashing over baby-jubjub)). However, the Prover performances is not the only parameter to take into consideration here, as we also want to make it "cheap" to hash on-chain, and EC operations certainly are cheaper since the last Hardfork of Ethereum, but remain costly, so this is another parameter to take into consideration in your design decisions.

I want to know if the observer know what commitment I used , how the observer get the useful imformation ? Is the case that the new tree has only one commitment, it will reveals the the commit's owner? Do you have the plan to support the Ped hash and is python lib available? Thanks for your suggection, I was going to use Poseidon hash to replace the blake2s and mimc. I will take the pederson hash into consideration. Thanks to your great work again.

[AntoineRondelet]

We are interested in supporting Pedersen hashes at some point indeed (always keeping an eye on the space of "algebraic hash functions" in case something offering better trade-offs shows up), however, I can't promise when this will be implemented. Always happy to receive contributions though :)

[youwenbusi]

The base field and the scalar field of altbn are 254bits, but the value of FieldT::capacity() is 253. When I replaced the MiMC hash in merkletree with poseidon hash(the result is FieldT type), I found that the result of poseidon hash could be 254bits, which means that the FieldT type variable can be 254bits, not only 253bits.

[AntoineRondelet]

The bit-length of an element is given to you by the log_2, i.e. by doing ⌊(log_2(x))⌋+1. Yes, if your prime p is 254 bit long, say > 2^{254} + 1, elements of the field are encoded on 254 bits, but if I give you a number in Z encoded on 254 bits, you don't know - without further processing - if the element in in Fp, so if you take 1 to the binary representation length (253 here), you know that all elements of this binary length (i.e. 253) are elements of the field.

Anyway, the FieldT "interface" is not part of Zeth. This is implemented in libsnark, so any issue related to that needs to be raised there if necessary. Likewise we do not implement Poseidon as we wait for more cryptanalysis on this hash function before considering adding it to the protocol.