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