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