sonobe/folding-schemes/src/folding/nova/zk.rs
folding-schemes/src/folding/nova/zk.rsRaw
1/// Implements Nova's zero-knowledge layer, as described in https://eprint.iacr.org/2023/573.pdf.
2///
3/// Remark: this zk layer implementation only covers a subset of the use cases:
4///
5/// We identify 3 interesting places to use the nova zk-layer: one before all the folding pipeline
6/// (Use-case-1), one at the end of the folding pipeline right before the final Decider SNARK
7/// proof (Use-case-2), and a third one for cases where compressed SNARK proofs are not needed, and
8/// just IVC proofs (bigger than SNARK proofs) suffice (Use-case-3):
9///
10/// * Use-case-1: at the beginning of the folding pipeline, right when the user has their original
11/// instance prior to be folded into the running instance, the user can fold it with the
12/// random-satisfying-instance to then have a blinded instance that can be sent to a server that
13/// will fold it with the running instance.
14/// --> In this one, the user could externalize all the IVC folding and also the Decider
15/// final proof generation to a server.
16/// * Use-case-2: at the end of all the IVC folding steps (after n iterations of nova.prove_step),
17/// to 'blind' the IVC proof so then it can be sent to a server that will generate the final
18/// decider snark proof.
19/// --> In this one, the user could externalize the Decider final proof generation to a
20/// server.
21/// * Use-case-3: the user does not care about the Decider (final compressed SNARK proof), and
22/// wants to generate a zk-proof of the IVC state to an IVC verifier (without any SNARK proof
23/// involved). Note that this proof will be much bigger and expensive to verify than a Decider
24/// SNARK proof.
25///
26/// The current implementation covers the Use-case-3.
27/// Use-case-1 can be achieved directly by a simpler version of the zk IVC scheme skipping steps
28/// and implemented directly at the app level by folding the original instance with a randomized
29/// instance (steps 2,3,4 from section D.4 of the [HyperNova](https://eprint.iacr.org/2023/573.pdf)
30/// paper).
31/// And the Use-case-2 would require a modified version of the Decider circuits.
32///
33use crate::folding::nova::traits::NovaR1CS;
34use ark_crypto_primitives::sponge::CryptographicSponge;
35use ark_ff::{BigInteger, PrimeField};
36use ark_std::{One, Zero};
37
38use crate::{
39 arith::r1cs::{RelaxedR1CS, R1CS},
40 RngCore,
41};
42use ark_crypto_primitives::sponge::{
43 poseidon::{PoseidonConfig, PoseidonSponge},
44 Absorb,
45};
46use ark_ec::{CurveGroup, Group};
47use ark_r1cs_std::{
48 groups::{CurveVar, GroupOpsBounds},
49 ToConstraintFieldGadget,
50};
51
52use crate::{commitment::CommitmentScheme, folding::circuits::CF2, frontend::FCircuit, Error};
53
54use super::{circuits::ChallengeGadget, nifs::NIFS, CommittedInstance, Nova, Witness};
55
56// We use the same definition of a folding proof as in https://eprint.iacr.org/2023/969.pdf
57// It consists in the commitment to the T term
58pub struct FoldingProof<C: CurveGroup> {
59 cmT: C,
60}
61
62pub struct RandomizedIVCProof<C1: CurveGroup, C2: CurveGroup> {
63 pub U_i: CommittedInstance<C1>,
64 pub u_i: CommittedInstance<C1>,
65 pub U_r: CommittedInstance<C1>,
66 pub pi: FoldingProof<C1>,
67 pub pi_prime: FoldingProof<C1>,
68 pub W_i_prime: Witness<C1>,
69 pub cf_U_i: CommittedInstance<C2>,
70 pub cf_W_i: Witness<C2>,
71}
72
73impl<C1: CurveGroup, C2: CurveGroup> RandomizedIVCProof<C1, C2>
74where
75 <C1 as Group>::ScalarField: Absorb,
76 <C1 as CurveGroup>::BaseField: PrimeField,
77{
78 /// Computes challenge required before folding instances
79 fn get_folding_challenge(
80 sponge: &mut PoseidonSponge<C1::ScalarField>,
81 pp_hash: C1::ScalarField,
82 U_i: CommittedInstance<C1>,
83 u_i: CommittedInstance<C1>,
84 cmT: C1,
85 ) -> Result<C1::ScalarField, Error> {
86 let r_bits = ChallengeGadget::<C1>::get_challenge_native(sponge, pp_hash, U_i, u_i, cmT);
87 C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits)).ok_or(Error::OutOfBounds)
88 }
89
90 /// Compute a zero-knowledge proof of a Nova IVC proof
91 /// It implements the prover of appendix D.4.in https://eprint.iacr.org/2023/573.pdf
92 /// For further details on why folding is hiding, see lemma 9
93 pub fn new<
94 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
95 GC2: CurveVar<C2, CF2<C2>>,
96 FC: FCircuit<C1::ScalarField>,
97 CS1: CommitmentScheme<C1, true>,
98 CS2: CommitmentScheme<C2, true>,
99 >(
100 nova: &Nova<C1, GC1, C2, GC2, FC, CS1, CS2, true>,
101 mut rng: impl RngCore,
102 ) -> Result<RandomizedIVCProof<C1, C2>, Error>
103 where
104 <C1 as Group>::ScalarField: Absorb,
105 <C2 as Group>::ScalarField: Absorb,
106 <C2 as Group>::ScalarField: PrimeField,
107 <C2 as CurveGroup>::BaseField: PrimeField,
108 <C2 as CurveGroup>::BaseField: Absorb,
109 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
110 GC2: ToConstraintFieldGadget<<C2 as CurveGroup>::BaseField>,
111 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
112 {
113 let mut challenges_sponge = PoseidonSponge::<C1::ScalarField>::new(&nova.poseidon_config);
114
115 // I. Compute proof for 'regular' instances
116 // 1. Fold the instance-witness pairs (U_i, W_i) with (u_i, w_i)
117 // a. Compute T
118 let (T, cmT) = NIFS::<C1, CS1, true>::compute_cmT(
119 &nova.cs_pp,
120 &nova.r1cs,
121 &nova.w_i,
122 &nova.u_i,
123 &nova.W_i,
124 &nova.U_i,
125 )?;
126
127 // b. Compute folding challenge
128 let r = RandomizedIVCProof::<C1, C2>::get_folding_challenge(
129 &mut challenges_sponge,
130 nova.pp_hash,
131 nova.U_i.clone(),
132 nova.u_i.clone(),
133 cmT,
134 )?;
135
136 // c. Compute fold
137 let (W_f, U_f) = NIFS::<C1, CS1, true>::fold_instances(
138 r, &nova.w_i, &nova.u_i, &nova.W_i, &nova.U_i, &T, cmT,
139 )?;
140
141 // d. Store folding proof
142 let pi = FoldingProof { cmT };
143
144 // 2. Sample a satisfying relaxed R1CS instance-witness pair (U_r, W_r)
145 let relaxed_instance = nova.r1cs.clone().relax();
146 let (U_r, W_r) = relaxed_instance.sample::<C1, CS1>(&nova.cs_pp, &mut rng)?;
147
148 // 3. Fold the instance-witness pair (U_f, W_f) with (U_r, W_r)
149 // a. Compute T
150 let (T_i_prime, cmT_i_prime) =
151 NIFS::<C1, CS1, true>::compute_cmT(&nova.cs_pp, &nova.r1cs, &W_f, &U_f, &W_r, &U_r)?;
152
153 // b. Compute folding challenge
154 let r_2 = RandomizedIVCProof::<C1, C2>::get_folding_challenge(
155 &mut challenges_sponge,
156 nova.pp_hash,
157 U_f.clone(),
158 U_r.clone(),
159 cmT_i_prime,
160 )?;
161
162 // c. Compute fold
163 let (W_i_prime, _) = NIFS::<C1, CS1, true>::fold_instances(
164 r_2,
165 &W_f,
166 &U_f,
167 &W_r,
168 &U_r,
169 &T_i_prime,
170 cmT_i_prime,
171 )?;
172
173 // d. Store folding proof
174 let pi_prime = FoldingProof { cmT: cmT_i_prime };
175
176 Ok(RandomizedIVCProof {
177 U_i: nova.U_i.clone(),
178 u_i: nova.u_i.clone(),
179 U_r,
180 pi,
181 pi_prime,
182 W_i_prime,
183 cf_U_i: nova.cf_U_i.clone(),
184 cf_W_i: nova.cf_W_i.clone(),
185 })
186 }
187
188 /// Verify a zero-knowledge proof of a Nova IVC proof
189 /// It implements the verifier of appendix D.4. in https://eprint.iacr.org/2023/573.pdf
190 #[allow(clippy::too_many_arguments)]
191 pub fn verify<
192 CS1: CommitmentScheme<C1, true>,
193 GC2: CurveVar<C2, CF2<C2>>,
194 CS2: CommitmentScheme<C2, true>,
195 >(
196 r1cs: &R1CS<C1::ScalarField>,
197 cf_r1cs: &R1CS<C2::ScalarField>,
198 pp_hash: C1::ScalarField,
199 poseidon_config: &PoseidonConfig<C1::ScalarField>,
200 i: C1::ScalarField,
201 z_0: Vec<C1::ScalarField>,
202 z_i: Vec<C1::ScalarField>,
203 proof: &RandomizedIVCProof<C1, C2>,
204 ) -> Result<(), Error>
205 where
206 <C1 as Group>::ScalarField: Absorb,
207 <C2 as Group>::ScalarField: Absorb,
208 <C2 as CurveGroup>::BaseField: PrimeField,
209 <C2 as CurveGroup>::BaseField: Absorb,
210 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
211 GC2: ToConstraintFieldGadget<<C2 as CurveGroup>::BaseField>,
212 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
213 {
214 // Handles case where i=0
215 if i == C1::ScalarField::zero() {
216 if z_0 == z_i {
217 return Ok(());
218 } else {
219 return Err(Error::zkIVCVerificationFail);
220 }
221 }
222
223 // 1. Check that u_i.x is correct - including the cyclefold running instance
224 // a. Check length
225 if proof.u_i.x.len() != 2 {
226 return Err(Error::IVCVerificationFail);
227 }
228
229 // b. Check computed hashes are correct
230 let mut sponge = PoseidonSponge::<C1::ScalarField>::new(poseidon_config);
231 let expected_u_i_x = proof.U_i.hash(&sponge, pp_hash, i, z_0, z_i);
232 if expected_u_i_x != proof.u_i.x[0] {
233 return Err(Error::zkIVCVerificationFail);
234 }
235
236 let expected_cf_u_i_x = proof.cf_U_i.hash_cyclefold(&sponge, pp_hash);
237 if expected_cf_u_i_x != proof.u_i.x[1] {
238 return Err(Error::IVCVerificationFail);
239 }
240
241 // 2. Check that u_i values are correct
242 if !proof.u_i.cmE.is_zero() || proof.u_i.u != C1::ScalarField::one() {
243 return Err(Error::zkIVCVerificationFail);
244 }
245
246 // 3. Obtain the U_f folded instance
247 // a. Compute folding challenge
248 let r = RandomizedIVCProof::<C1, C2>::get_folding_challenge(
249 &mut sponge,
250 pp_hash,
251 proof.U_i.clone(),
252 proof.u_i.clone(),
253 proof.pi.cmT,
254 )?;
255
256 // b. Get the U_f instance
257 let U_f = NIFS::<C1, CS1, true>::fold_committed_instance(
258 r,
259 &proof.u_i,
260 &proof.U_i,
261 &proof.pi.cmT,
262 );
263
264 // 4. Obtain the U^{\prime}_i folded instance
265 // a. Compute folding challenge
266 let r_2 = RandomizedIVCProof::<C1, C2>::get_folding_challenge(
267 &mut sponge,
268 pp_hash,
269 U_f.clone(),
270 proof.U_r.clone(),
271 proof.pi_prime.cmT,
272 )?;
273
274 // b. Compute fold
275 let U_i_prime = NIFS::<C1, CS1, true>::fold_committed_instance(
276 r_2,
277 &U_f,
278 &proof.U_r,
279 &proof.pi_prime.cmT,
280 );
281
282 // 5. Check that W^{\prime}_i is a satisfying witness
283 let mut z = vec![U_i_prime.u];
284 z.extend(&U_i_prime.x);
285 z.extend(&proof.W_i_prime.W);
286 let relaxed_r1cs = RelaxedR1CS {
287 l: r1cs.l,
288 A: r1cs.A.clone(),
289 B: r1cs.B.clone(),
290 C: r1cs.C.clone(),
291 u: U_i_prime.u,
292 E: proof.W_i_prime.E.clone(),
293 };
294 relaxed_r1cs.check_relation(&z)?;
295
296 // 6. Check that the cyclefold instance-witness pair satisfies the cyclefold relaxed r1cs
297 cf_r1cs.check_relaxed_instance_relation(&proof.cf_W_i, &proof.cf_U_i)?;
298
299 Ok(())
300 }
301}
302
303#[cfg(test)]
304pub mod tests {
305 use super::*;
306 use crate::commitment::pedersen::Pedersen;
307 use crate::folding::nova::tests::test_ivc_opt;
308 use crate::frontend::tests::CubicFCircuit;
309 use crate::transcript::poseidon::poseidon_canonical_config;
310 use ark_bn254::{Fr, G1Projective as Projective};
311 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
312 use rand::rngs::OsRng;
313
314 // Tests zk proof generation and verification for a valid nova IVC proof
315 #[test]
316 fn test_zk_nova_ivc() {
317 let mut rng = OsRng;
318 let poseidon_config = poseidon_canonical_config::<Fr>();
319 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
320 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
321 poseidon_config.clone(),
322 F_circuit,
323 3,
324 );
325
326 let proof = RandomizedIVCProof::new(&nova, &mut rng).unwrap();
327 let verify = RandomizedIVCProof::verify::<
328 Pedersen<Projective, true>,
329 GVar2,
330 Pedersen<Projective2, true>,
331 >(
332 &nova.r1cs,
333 &nova.cf_r1cs,
334 nova.pp_hash,
335 &nova.poseidon_config,
336 nova.i,
337 nova.z_0,
338 nova.z_i,
339 &proof,
340 );
341 assert!(verify.is_ok());
342 }
343
344 #[test]
345 fn test_zk_nova_when_i_is_zero() {
346 let mut rng = OsRng;
347 let poseidon_config = poseidon_canonical_config::<Fr>();
348 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
349 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
350 poseidon_config.clone(),
351 F_circuit,
352 0,
353 );
354
355 let proof = RandomizedIVCProof::new(&nova, &mut rng).unwrap();
356 let verify = RandomizedIVCProof::verify::<
357 Pedersen<Projective, true>,
358 GVar2,
359 Pedersen<Projective2, true>,
360 >(
361 &nova.r1cs,
362 &nova.cf_r1cs,
363 nova.pp_hash,
364 &nova.poseidon_config,
365 nova.i,
366 nova.z_0,
367 nova.z_i,
368 &proof,
369 );
370 assert!(verify.is_ok());
371 }
372
373 #[test]
374 fn test_zk_nova_verification_fails_with_wrong_running_instance() {
375 let mut rng = OsRng;
376 let poseidon_config = poseidon_canonical_config::<Fr>();
377 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
378 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
379 poseidon_config.clone(),
380 F_circuit,
381 3,
382 );
383 let (sampled_committed_instance, _) = nova
384 .r1cs
385 .clone()
386 .relax()
387 .sample::<Projective, Pedersen<Projective, true>>(&nova.cs_pp, rng)
388 .unwrap();
389
390 // proof verification fails with incorrect running instance
391 let mut nova_with_incorrect_running_instance = nova.clone();
392 nova_with_incorrect_running_instance.U_i = sampled_committed_instance;
393 let incorrect_proof =
394 RandomizedIVCProof::new(&nova_with_incorrect_running_instance, &mut rng).unwrap();
395 let verify = RandomizedIVCProof::verify::<
396 Pedersen<Projective, true>,
397 GVar2,
398 Pedersen<Projective2, true>,
399 >(
400 &nova_with_incorrect_running_instance.r1cs,
401 &nova_with_incorrect_running_instance.cf_r1cs,
402 nova_with_incorrect_running_instance.pp_hash,
403 &nova_with_incorrect_running_instance.poseidon_config,
404 nova_with_incorrect_running_instance.i,
405 nova_with_incorrect_running_instance.z_0,
406 nova_with_incorrect_running_instance.z_i,
407 &incorrect_proof,
408 );
409 assert!(verify.is_err());
410 }
411
412 #[test]
413 fn test_zk_nova_verification_fails_with_wrong_running_witness() {
414 let mut rng = OsRng;
415 let poseidon_config = poseidon_canonical_config::<Fr>();
416 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
417 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
418 poseidon_config.clone(),
419 F_circuit,
420 3,
421 );
422 let (_, sampled_committed_witness) = nova
423 .r1cs
424 .clone()
425 .relax()
426 .sample::<Projective, Pedersen<Projective, true>>(&nova.cs_pp, rng)
427 .unwrap();
428
429 // proof generation fails with incorrect running witness
430 let mut nova_with_incorrect_running_witness = nova.clone();
431 nova_with_incorrect_running_witness.W_i = sampled_committed_witness;
432 let incorrect_proof =
433 RandomizedIVCProof::new(&nova_with_incorrect_running_witness, &mut rng).unwrap();
434 let verify = RandomizedIVCProof::verify::<
435 Pedersen<Projective, true>,
436 GVar2,
437 Pedersen<Projective2, true>,
438 >(
439 &nova_with_incorrect_running_witness.r1cs,
440 &nova_with_incorrect_running_witness.cf_r1cs,
441 nova_with_incorrect_running_witness.pp_hash,
442 &nova_with_incorrect_running_witness.poseidon_config,
443 nova_with_incorrect_running_witness.i,
444 nova_with_incorrect_running_witness.z_0,
445 nova_with_incorrect_running_witness.z_i,
446 &incorrect_proof,
447 );
448 assert!(verify.is_err());
449 }
450}