search

docknetwork / crypto

Rust crypto library for data privacy tools
Apache License 2.0
94 stars 30 forks source link

Question: Composite Proofs #8

Closed uvdsl closed 1 year ago

uvdsl commented 1 year ago

Hi! :wave: Thank you for your great work! (Especially all the comments in the code!)

I was looking at how the composite proof system works, especially focusing on BBS+ with LegoGroth16. From [1] I gather that everything is kinda glued together via Schnorr. Is there a formal description on how this works? I am really curious about this...

I recently looked into combining BBS+ and Bulletproofs (with Hyperledger Ursa) but got stuck at exactly that point... Could not think of how to prove the usage of the witness from the BBS+ in the range proof (...still learning...). As a side question: Would there be anything blocking the combination of the two from the get-go or could one "plug in" Bulletproofs (to avoid the trusted setup) using the same approach to composite proofs (i.e. adding to this repo)?

Cheers Christoph

[1] https://github.com/docknetwork/crypto/blob/main/proof_system/src/sub_protocols/bound_check_legogroth16.rs

lovesh commented 1 year ago

Hi :wave: Thanks for reaching out.

From [1] I gather that everything is kinda glued together via Schnorr.

Correct.

Is there a formal description on how this works? I am really curious about this...

If you mean proofs, then no, don't have it for the exact combination (BBS+ & LegoGroth16) but the idea is that the snark proof contains a Pedersen commitment to the witness(s) . This witness (which is a BBS+ message) is also used in proof of knowledge of BBS+ signature, notice commitment d in the section 4.5 of paper, so we prove that the witness used in both the Pedersen commitment from snark and d is indeed the same.

Could not think of how to prove the usage of the witness from the BBS+ in the range proof

Yes, its possible. I did that in my own fork while I was contributing to ursa. See these 2 tests. The idea is the same with Bulletproofs as here also you have a commitment to the witness and you can prove equality of the witness with the message in d in the BBS+ proof.

Would there be anything blocking the combination of the two from the get-go or could one "plug in" Bulletproofs

No blocker as evident from above.

uvdsl commented 1 year ago

Thank you for the quick reply!

If you mean proofs, then no, don't have it for the exact combination (BBS+ & LegoGroth16) but the idea is that the snark proof contains a Pedersen commitment to the witness(s) .

Yes, I was thinking about this - thanks for the hints! I will have a look at the math...

Yes, its possible. I did that in my own fork while I was contributing to ursa. See these 2 tests.

Cool! Was there a specific reason you went with LegoGroth16 instead of Bulletproofs then? I am not yet sure what the implications of the trusted setup are if the verifier is dishonest... (e.g. trying to figure out the witness ) I will have to double check that.

lovesh commented 1 year ago

Was there a specific reason you went with LegoGroth16 instead of Bulletproofs then?

Faster verification.

I am not yet sure what the implications of the trusted setup are if the verifier is dishonest

A verifier who did the trusted setup cannot learn the witness but can only forge proofs, i.e. create a proof for a witness that does not satisfy the relation. In our case, the verifier has no incentive to do that.

uvdsl commented 1 year ago

Thanks alot!