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