search

privacy-scaling-explorations / sonobe

Experimental folding schemes library
https://privacy-scaling-explorations.github.io/sonobe-docs/
MIT License
191 stars 47 forks source link

feat: implement nova's zk layer #127

Closed dmpierre closed 1 month ago

dmpierre commented 2 months ago

This PR implements nova's zero-knowledge layer, as specified in Appendix D.4 of Kothapalli, Setty (2023).

Edit: we initially were blinding the cyclefold instance. However, after discussing, it appears that blinding the cyclefold instance should not be necessary, while keeping zk for the IVC proof.

CPerezz commented 1 month ago

Currently discussing why is it required to add ZK to CycleFold instance.

DIscussed in Zulip with @dmpierre and Srinath.

Hey Srinath I was reviewing the PR from Pierre where ZK is included for Nova. And I saw that the CycleFold instance was also getting folded with a randomized sample to produce ZK on that side too. I'm curious on why is needed to add ZK to the CycleFold instance. AFAIK, it doesn't leak any info of the operations in the Primary Curve. And that means no relevant data is leaked at all.

In short, the main important operations related to circuit logic and ZK happen in the PrimaryCurve. CycleFold works on the secondary proving correct folding only. Therefore, I wonder why does it need to be ZK if in reality is not giving any sensitive info.

Thanks. And sorry if the answer is trivial. I just did not see why while reviewing the PR.

dmpierre commented 1 month ago

Currently discussing why is it required to add ZK to CycleFold instance.

DIscussed in Zulip with @dmpierre and Srinath.

Hey Srinath I was reviewing the PR from Pierre where ZK is included for Nova. And I saw that the CycleFold instance was also getting folded with a randomized sample to produce ZK on that side too. I'm curious on why is needed to add ZK to the CycleFold instance. AFAIK, it doesn't leak any info of the operations in the Primary Curve. And that means no relevant data is leaked at all. In short, the main important operations related to circuit logic and ZK happen in the PrimaryCurve. CycleFold works on the secondary proving correct folding only. Therefore, I wonder why does it need to be ZK if in reality is not giving any sensitive info. Thanks. And sorry if the answer is trivial. I just did not see why while reviewing the PR.

Answer from Srinath:

Hi! Good question, we are writing up a more general ZK compiler with proofs, which will clarify more details. Yes, you are right that we could avoid blinding U_EC instance. Btw, if you are using Groth16 for wrapping IVC proofs, then there is no need to do this blinding step as long as Groth16 provides zk (which is easier than this blinding approach, for Groth16).

Nice, this should simplify this PR, will take this into account and remove the blinding of the cyclefold instances!

CPerezz commented 1 month ago

Hi! Good question, we are writing up a more general ZK compiler with proofs, which will clarify more details. Yes, you are right that we could avoid blinding U_EC instance. Btw, if you are using Groth16 for wrapping IVC proofs, then there is no need to do this blinding step as long as Groth16 provides zk (which is easier than this blinding approach, for Groth16).

Thanks for the quick reply @Srinath Setty !!

In regards of your reply, I think there is a need no? Mainly because if we want to have a distributed folding setting then the intermediate blinding is required such that future folders don't get witness nor commitment info from previous ones.

I agree, that otherwise, ZK is not needed at all as G16 can provide us with it, thus saving us 1 extra blinding at the very least (so 1 fold with a randomized instance) for each previous fold verification.

So to sum-up. Does it make sense @Srinath Setty to just keep the folding with randomized instances in the primary curve? (For the distributed prover setting I mean ofc) and simply don't do any ZK at all if we own all the provers and allow G16 to take care of it?

Thanks, Carlos.

Last transcription. After we get an answer for this, I think we are good to go.

dmpierre commented 1 month ago

cc @arnaucube (quote replying breaks latex code)

Thanks for the thoughtful comment and questions!

Yes, this PR is only focused on implementing the zk layer for nova. In fact, there is a third use case, where the user computes folds and sends the zk IVC proof to any IVC verifier, without any decider circuit involved anywhere.

Regarding use case 1: this is correct. Using the nova zk layer, a user can blind his running and incoming instances and send a zk IVC proof that can be groth16'ed by an untrusted server. This PR is not modifying sonobe's decider circuit to make this possible. In fact, I think the decider circuit would be a tad different? Notably to accommodate for the random instances. Hence, this might require its own PR.

Regarding use case 2: this is correct. This PR does not aim to cover this use case, but you can do what you are describing with what this PR introduces, since you only need sampling relaxed r1cs instances. I see the connection with doing tree-like folding, nice! This is tangential, but here as well, I guess that obtaining a final compressed snark would require another modified final decider.

CPerezz commented 1 month ago

As per discussion with @srinathtv I think we can simply remove the Cyclefold blinding for now and merge this. Once he releases a more formal version of it, we can stick to it much better.

But was clearly stated in the Folding implementers call that the Cyclefold Instance blinders indeed aren't useful as "a priori" CycleFold shouldn't leak anything relevant from the IVC. ie. doesn't break ZK.