sonobe/folding-schemes/src/folding/nova/mod.rs
folding-schemes/src/folding/nova/mod.rsRaw
1/// Implements the scheme described in [Nova](https://eprint.iacr.org/2021/370.pdf) and
2/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf).
3use ark_crypto_primitives::{
4 crh::{poseidon::CRH, CRHScheme},
5 sponge::{poseidon::PoseidonConfig, Absorb},
6};
7use ark_ec::{AffineRepr, CurveGroup, Group};
8use ark_ff::{BigInteger, PrimeField};
9use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
10use ark_std::fmt::Debug;
11use ark_std::{One, Zero};
12use core::marker::PhantomData;
13
14use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
15
16use crate::ccs::r1cs::{extract_r1cs, extract_w_x, R1CS};
17use crate::commitment::CommitmentScheme;
18use crate::folding::circuits::nonnative::point_to_nonnative_limbs;
19use crate::frontend::FCircuit;
20use crate::utils::vec::is_zero_vec;
21use crate::Error;
22use crate::FoldingScheme;
23
24pub mod circuits;
25pub mod cyclefold;
26pub mod decider_eth;
27pub mod decider_eth_circuit;
28pub mod nifs;
29pub mod traits;
30
31use circuits::{AugmentedFCircuit, ChallengeGadget, CF2};
32use cyclefold::{CycleFoldChallengeGadget, CycleFoldCircuit};
33use nifs::NIFS;
34use traits::NovaR1CS;
35
36#[cfg(test)]
37use cyclefold::CF_IO_LEN;
38
39#[derive(Debug, Clone, Eq, PartialEq)]
40pub struct CommittedInstance<C: CurveGroup> {
41 pub cmE: C,
42 pub u: C::ScalarField,
43 pub cmW: C,
44 pub x: Vec<C::ScalarField>,
45}
46
47impl<C: CurveGroup> CommittedInstance<C> {
48 pub fn dummy(io_len: usize) -> Self {
49 Self {
50 cmE: C::zero(),
51 u: C::ScalarField::zero(),
52 cmW: C::zero(),
53 x: vec![C::ScalarField::zero(); io_len],
54 }
55 }
56}
57
58impl<C: CurveGroup> CommittedInstance<C>
59where
60 <C as Group>::ScalarField: Absorb,
61 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
62{
63 /// hash implements the committed instance hash compatible with the gadget implemented in
64 /// nova/circuits.rs::CommittedInstanceVar.hash.
65 /// Returns `H(i, z_0, z_i, U_i)`, where `i` can be `i` but also `i+1`, and `U_i` is the
66 /// `CommittedInstance`.
67 pub fn hash(
68 &self,
69 poseidon_config: &PoseidonConfig<C::ScalarField>,
70 i: C::ScalarField,
71 z_0: Vec<C::ScalarField>,
72 z_i: Vec<C::ScalarField>,
73 ) -> Result<C::ScalarField, Error> {
74 let (cmE_x, cmE_y) = point_to_nonnative_limbs::<C>(self.cmE)?;
75 let (cmW_x, cmW_y) = point_to_nonnative_limbs::<C>(self.cmW)?;
76
77 CRH::<C::ScalarField>::evaluate(
78 poseidon_config,
79 vec![
80 vec![i],
81 z_0,
82 z_i,
83 vec![self.u],
84 self.x.clone(),
85 cmE_x,
86 cmE_y,
87 cmW_x,
88 cmW_y,
89 ]
90 .concat(),
91 )
92 .map_err(|e| Error::Other(e.to_string()))
93 }
94}
95
96#[derive(Debug, Clone, Eq, PartialEq)]
97pub struct Witness<C: CurveGroup> {
98 pub E: Vec<C::ScalarField>,
99 pub rE: C::ScalarField,
100 pub W: Vec<C::ScalarField>,
101 pub rW: C::ScalarField,
102}
103
104impl<C: CurveGroup> Witness<C>
105where
106 <C as Group>::ScalarField: Absorb,
107{
108 pub fn new(w: Vec<C::ScalarField>, e_len: usize) -> Self {
109 // note: at the current version, we don't use the blinding factors and we set them to 0
110 // always.
111 Self {
112 E: vec![C::ScalarField::zero(); e_len],
113 rE: C::ScalarField::zero(),
114 W: w,
115 rW: C::ScalarField::zero(),
116 }
117 }
118 pub fn commit<CS: CommitmentScheme<C>>(
119 &self,
120 params: &CS::ProverParams,
121 x: Vec<C::ScalarField>,
122 ) -> Result<CommittedInstance<C>, Error> {
123 let mut cmE = C::zero();
124 if !is_zero_vec::<C::ScalarField>(&self.E) {
125 cmE = CS::commit(params, &self.E, &self.rE)?;
126 }
127 let cmW = CS::commit(params, &self.W, &self.rW)?;
128 Ok(CommittedInstance {
129 cmE,
130 u: C::ScalarField::one(),
131 cmW,
132 x,
133 })
134 }
135}
136
137#[derive(Debug, Clone)]
138pub struct ProverParams<C1, C2, CS1, CS2>
139where
140 C1: CurveGroup,
141 C2: CurveGroup,
142 CS1: CommitmentScheme<C1>,
143 CS2: CommitmentScheme<C2>,
144{
145 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
146 pub cs_params: CS1::ProverParams,
147 pub cf_cs_params: CS2::ProverParams,
148}
149
150#[derive(Debug, Clone)]
151pub struct VerifierParams<C1: CurveGroup, C2: CurveGroup> {
152 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
153 pub r1cs: R1CS<C1::ScalarField>,
154 pub cf_r1cs: R1CS<C2::ScalarField>,
155}
156
157/// Implements Nova+CycleFold's IVC, described in [Nova](https://eprint.iacr.org/2021/370.pdf) and
158/// [CycleFold](https://eprint.iacr.org/2023/1192.pdf), following the FoldingScheme trait
159#[derive(Clone, Debug)]
160pub struct Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
161where
162 C1: CurveGroup,
163 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
164 C2: CurveGroup,
165 GC2: CurveVar<C2, CF2<C2>>,
166 FC: FCircuit<C1::ScalarField>,
167 CS1: CommitmentScheme<C1>,
168 CS2: CommitmentScheme<C2>,
169{
170 _gc1: PhantomData<GC1>,
171 _c2: PhantomData<C2>,
172 _gc2: PhantomData<GC2>,
173 /// R1CS of the Augmented Function circuit
174 pub r1cs: R1CS<C1::ScalarField>,
175 /// R1CS of the CycleFold circuit
176 pub cf_r1cs: R1CS<C2::ScalarField>,
177 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
178 /// CommitmentScheme::ProverParams over C1
179 pub cs_params: CS1::ProverParams,
180 /// CycleFold CommitmentScheme::ProverParams, over C2
181 pub cf_cs_params: CS2::ProverParams,
182 /// F circuit, the circuit that is being folded
183 pub F: FC,
184 pub i: C1::ScalarField,
185 /// initial state
186 pub z_0: Vec<C1::ScalarField>,
187 /// current i-th state
188 pub z_i: Vec<C1::ScalarField>,
189 /// Nova instances
190 pub w_i: Witness<C1>,
191 pub u_i: CommittedInstance<C1>,
192 pub W_i: Witness<C1>,
193 pub U_i: CommittedInstance<C1>,
194
195 /// CycleFold running instance
196 pub cf_W_i: Witness<C2>,
197 pub cf_U_i: CommittedInstance<C2>,
198}
199
200impl<C1, GC1, C2, GC2, FC, CS1, CS2> FoldingScheme<C1, C2, FC>
201 for Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
202where
203 C1: CurveGroup,
204 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
205 C2: CurveGroup,
206 GC2: CurveVar<C2, CF2<C2>>,
207 FC: FCircuit<C1::ScalarField>,
208 CS1: CommitmentScheme<C1>,
209 CS2: CommitmentScheme<C2>,
210 <C1 as CurveGroup>::BaseField: PrimeField,
211 <C2 as CurveGroup>::BaseField: PrimeField,
212 <C1 as Group>::ScalarField: Absorb,
213 <C2 as Group>::ScalarField: Absorb,
214 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
215 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
216 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
217{
218 type PreprocessorParam = (Self::ProverParam, FC);
219 type ProverParam = ProverParams<C1, C2, CS1, CS2>;
220 type VerifierParam = VerifierParams<C1, C2>;
221 type CommittedInstanceWithWitness = (CommittedInstance<C1>, Witness<C1>);
222 type CFCommittedInstanceWithWitness = (CommittedInstance<C2>, Witness<C2>);
223
224 fn preprocess(
225 prep_param: &Self::PreprocessorParam,
226 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
227 let (prover_params, F_circuit) = prep_param;
228
229 let (r1cs, cf_r1cs) =
230 get_r1cs::<C1, GC1, C2, GC2, FC>(&prover_params.poseidon_config, F_circuit.clone())?;
231
232 let verifier_params = VerifierParams::<C1, C2> {
233 poseidon_config: prover_params.poseidon_config.clone(),
234 r1cs,
235 cf_r1cs,
236 };
237 Ok((prover_params.clone(), verifier_params))
238 }
239
240 /// Initializes the Nova+CycleFold's IVC for the given parameters and initial state `z_0`.
241 fn init(pp: &Self::ProverParam, F: FC, z_0: Vec<C1::ScalarField>) -> Result<Self, Error> {
242 // prepare the circuit to obtain its R1CS
243 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
244 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
245
246 let augmented_F_circuit =
247 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&pp.poseidon_config, F.clone());
248 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
249
250 augmented_F_circuit.generate_constraints(cs.clone())?;
251 cs.finalize();
252 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
253 let r1cs = extract_r1cs::<C1::ScalarField>(&cs);
254
255 cf_circuit.generate_constraints(cs2.clone())?;
256 cs2.finalize();
257 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
258 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2);
259
260 // setup the dummy instances
261 let (w_dummy, u_dummy) = r1cs.dummy_instance();
262 let (cf_w_dummy, cf_u_dummy) = cf_r1cs.dummy_instance();
263
264 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
265 // R1CS that we're working with.
266 Ok(Self {
267 _gc1: PhantomData,
268 _c2: PhantomData,
269 _gc2: PhantomData,
270 r1cs,
271 cf_r1cs,
272 poseidon_config: pp.poseidon_config.clone(),
273 cs_params: pp.cs_params.clone(),
274 cf_cs_params: pp.cf_cs_params.clone(),
275 F,
276 i: C1::ScalarField::zero(),
277 z_0: z_0.clone(),
278 z_i: z_0,
279 w_i: w_dummy.clone(),
280 u_i: u_dummy.clone(),
281 W_i: w_dummy,
282 U_i: u_dummy,
283 // cyclefold running instance
284 cf_W_i: cf_w_dummy.clone(),
285 cf_U_i: cf_u_dummy.clone(),
286 })
287 }
288
289 /// Implements IVC.P of Nova+CycleFold
290 fn prove_step(&mut self) -> Result<(), Error> {
291 let augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
292
293 if self.i > C1::ScalarField::from_le_bytes_mod_order(&std::usize::MAX.to_le_bytes()) {
294 return Err(Error::MaxStep);
295 }
296 let mut i_bytes: [u8; 8] = [0; 8];
297 i_bytes.copy_from_slice(&self.i.into_bigint().to_bytes_le()[..8]);
298 let i_usize: usize = usize::from_le_bytes(i_bytes);
299
300 let z_i1 = self.F.step_native(i_usize, self.z_i.clone())?;
301
302 // compute T and cmT for AugmentedFCircuit
303 let (T, cmT) = self.compute_cmT()?;
304
305 // r_bits is the r used to the RLC of the F' instances
306 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
307 &self.poseidon_config,
308 self.U_i.clone(),
309 self.u_i.clone(),
310 cmT,
311 )?;
312 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
313 .ok_or(Error::OutOfBounds)?;
314 let r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&r_bits))
315 .ok_or(Error::OutOfBounds)?;
316
317 // fold Nova instances
318 let (W_i1, U_i1): (Witness<C1>, CommittedInstance<C1>) = NIFS::<C1, CS1>::fold_instances(
319 r_Fr, &self.W_i, &self.U_i, &self.w_i, &self.u_i, &T, cmT,
320 )?;
321
322 // folded instance output (public input, x)
323 // u_{i+1}.x = H(i+1, z_0, z_{i+1}, U_{i+1})
324 let u_i1_x = U_i1.hash(
325 &self.poseidon_config,
326 self.i + C1::ScalarField::one(),
327 self.z_0.clone(),
328 z_i1.clone(),
329 )?;
330
331 if self.i == C1::ScalarField::zero() {
332 // base case
333 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
334 _gc2: PhantomData,
335 poseidon_config: self.poseidon_config.clone(),
336 i: Some(C1::ScalarField::zero()), // = i=0
337 i_usize: Some(0),
338 z_0: Some(self.z_0.clone()), // = z_i
339 z_i: Some(self.z_i.clone()),
340 u_i: Some(self.u_i.clone()), // = dummy
341 U_i: Some(self.U_i.clone()), // = dummy
342 U_i1: Some(U_i1.clone()),
343 r_nonnat: Some(r_Fq),
344 cmT: Some(cmT),
345 F: self.F.clone(),
346 x: Some(u_i1_x),
347 cf1_u_i: None,
348 cf2_u_i: None,
349 cf_U_i: None,
350 cf1_U_i1: None,
351 cf_U_i1: None,
352 cf1_cmT: None,
353 cf2_cmT: None,
354 cf1_r_nonnat: None,
355 cf2_r_nonnat: None,
356 };
357
358 #[cfg(test)]
359 NIFS::<C1, CS1>::verify_folded_instance(r_Fr, &self.U_i, &self.u_i, &U_i1, &cmT)?;
360 } else {
361 // CycleFold part:
362 // get the vector used as public inputs 'x' in the CycleFold circuit
363 // cyclefold circuit for cmW
364 let cfW_u_i_x = [
365 vec![r_Fq],
366 get_cm_coordinates(&self.U_i.cmW),
367 get_cm_coordinates(&self.u_i.cmW),
368 get_cm_coordinates(&U_i1.cmW),
369 ]
370 .concat();
371 // cyclefold circuit for cmE
372 let cfE_u_i_x = [
373 vec![r_Fq],
374 get_cm_coordinates(&self.U_i.cmE),
375 get_cm_coordinates(&cmT),
376 get_cm_coordinates(&U_i1.cmE),
377 ]
378 .concat();
379
380 let cfW_circuit = CycleFoldCircuit::<C1, GC1> {
381 _gc: PhantomData,
382 r_bits: Some(r_bits.clone()),
383 p1: Some(self.U_i.clone().cmW),
384 p2: Some(self.u_i.clone().cmW),
385 p3: Some(U_i1.clone().cmW),
386 x: Some(cfW_u_i_x.clone()),
387 };
388 let cfE_circuit = CycleFoldCircuit::<C1, GC1> {
389 _gc: PhantomData,
390 r_bits: Some(r_bits.clone()),
391 p1: Some(self.U_i.clone().cmE),
392 p2: Some(cmT),
393 p3: Some(U_i1.clone().cmE),
394 x: Some(cfE_u_i_x.clone()),
395 };
396
397 // fold self.cf_U_i + cfW_U -> folded running with cfW
398 let (_cfW_w_i, cfW_u_i, cfW_W_i1, cfW_U_i1, cfW_cmT, cfW_r1_Fq) = self
399 .fold_cyclefold_circuit(
400 self.cf_W_i.clone(), // CycleFold running instance witness
401 self.cf_U_i.clone(), // CycleFold running instance
402 cfW_u_i_x,
403 cfW_circuit,
404 )?;
405 // fold [the output from folding self.cf_U_i + cfW_U] + cfE_U = folded_running_with_cfW + cfE
406 let (_cfE_w_i, cfE_u_i, cf_W_i1, cf_U_i1, cf_cmT, cf_r2_Fq) =
407 self.fold_cyclefold_circuit(cfW_W_i1, cfW_U_i1.clone(), cfE_u_i_x, cfE_circuit)?;
408
409 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
410 _gc2: PhantomData,
411 poseidon_config: self.poseidon_config.clone(),
412 i: Some(self.i),
413 i_usize: Some(i_usize),
414 z_0: Some(self.z_0.clone()),
415 z_i: Some(self.z_i.clone()),
416 u_i: Some(self.u_i.clone()),
417 U_i: Some(self.U_i.clone()),
418 U_i1: Some(U_i1.clone()),
419 r_nonnat: Some(r_Fq),
420 cmT: Some(cmT),
421 F: self.F.clone(),
422 x: Some(u_i1_x),
423 // cyclefold values
424 cf1_u_i: Some(cfW_u_i.clone()),
425 cf2_u_i: Some(cfE_u_i.clone()),
426 cf_U_i: Some(self.cf_U_i.clone()),
427 cf1_U_i1: Some(cfW_U_i1.clone()),
428 cf_U_i1: Some(cf_U_i1.clone()),
429 cf1_cmT: Some(cfW_cmT),
430 cf2_cmT: Some(cf_cmT),
431 cf1_r_nonnat: Some(cfW_r1_Fq),
432 cf2_r_nonnat: Some(cf_r2_Fq),
433 };
434
435 self.cf_W_i = cf_W_i1.clone();
436 self.cf_U_i = cf_U_i1.clone();
437
438 #[cfg(test)]
439 {
440 self.cf_r1cs.check_instance_relation(&_cfW_w_i, &cfW_u_i)?;
441 self.cf_r1cs.check_instance_relation(&_cfE_w_i, &cfE_u_i)?;
442 self.cf_r1cs
443 .check_relaxed_instance_relation(&self.cf_W_i, &self.cf_U_i)?;
444 }
445 }
446
447 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
448
449 augmented_F_circuit.generate_constraints(cs.clone())?;
450
451 #[cfg(test)]
452 assert!(cs.is_satisfied().unwrap());
453
454 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
455 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
456 if x_i1[0] != u_i1_x {
457 return Err(Error::NotEqual);
458 }
459
460 #[cfg(test)]
461 if x_i1.len() != 1 {
462 return Err(Error::NotExpectedLength(x_i1.len(), 1));
463 }
464
465 // set values for next iteration
466 self.i += C1::ScalarField::one();
467 self.z_i = z_i1.clone();
468 self.w_i = Witness::<C1>::new(w_i1, self.r1cs.A.n_rows);
469 self.u_i = self.w_i.commit::<CS1>(&self.cs_params, vec![u_i1_x])?;
470 self.W_i = W_i1.clone();
471 self.U_i = U_i1.clone();
472
473 #[cfg(test)]
474 {
475 self.r1cs.check_instance_relation(&self.w_i, &self.u_i)?;
476 self.r1cs
477 .check_relaxed_instance_relation(&self.W_i, &self.U_i)?;
478 }
479
480 Ok(())
481 }
482
483 fn state(&self) -> Vec<C1::ScalarField> {
484 self.z_i.clone()
485 }
486 fn instances(
487 &self,
488 ) -> (
489 Self::CommittedInstanceWithWitness,
490 Self::CommittedInstanceWithWitness,
491 Self::CFCommittedInstanceWithWitness,
492 ) {
493 (
494 (self.U_i.clone(), self.W_i.clone()),
495 (self.u_i.clone(), self.w_i.clone()),
496 (self.cf_U_i.clone(), self.cf_W_i.clone()),
497 )
498 }
499
500 /// Implements IVC.V of Nova+CycleFold
501 fn verify(
502 vp: Self::VerifierParam,
503 z_0: Vec<C1::ScalarField>, // initial state
504 z_i: Vec<C1::ScalarField>, // last state
505 num_steps: C1::ScalarField,
506 running_instance: Self::CommittedInstanceWithWitness,
507 incoming_instance: Self::CommittedInstanceWithWitness,
508 cyclefold_instance: Self::CFCommittedInstanceWithWitness,
509 ) -> Result<(), Error> {
510 let (U_i, W_i) = running_instance;
511 let (u_i, w_i) = incoming_instance;
512 let (cf_U_i, cf_W_i) = cyclefold_instance;
513
514 if u_i.x.len() != 1 || U_i.x.len() != 1 {
515 return Err(Error::IVCVerificationFail);
516 }
517
518 // check that u_i's output points to the running instance
519 // u_i.X == H(i, z_0, z_i, U_i)
520 let expected_u_i_x = U_i.hash(&vp.poseidon_config, num_steps, z_0, z_i.clone())?;
521 if expected_u_i_x != u_i.x[0] {
522 return Err(Error::IVCVerificationFail);
523 }
524
525 // check u_i.cmE==0, u_i.u==1 (=u_i is a un-relaxed instance)
526 if !u_i.cmE.is_zero() || !u_i.u.is_one() {
527 return Err(Error::IVCVerificationFail);
528 }
529
530 // check R1CS satisfiability
531 vp.r1cs.check_instance_relation(&w_i, &u_i)?;
532 // check RelaxedR1CS satisfiability
533 vp.r1cs.check_relaxed_instance_relation(&W_i, &U_i)?;
534
535 // check CycleFold RelaxedR1CS satisfiability
536 vp.cf_r1cs
537 .check_relaxed_instance_relation(&cf_W_i, &cf_U_i)?;
538
539 Ok(())
540 }
541}
542
543impl<C1, GC1, C2, GC2, FC, CS1, CS2> Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
544where
545 C1: CurveGroup,
546 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
547 C2: CurveGroup,
548 GC2: CurveVar<C2, CF2<C2>>,
549 FC: FCircuit<C1::ScalarField>,
550 CS1: CommitmentScheme<C1>,
551 CS2: CommitmentScheme<C2>,
552 <C2 as CurveGroup>::BaseField: PrimeField,
553 <C1 as Group>::ScalarField: Absorb,
554 <C2 as Group>::ScalarField: Absorb,
555 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
556{
557 // computes T and cmT for the AugmentedFCircuit
558 fn compute_cmT(&self) -> Result<(Vec<C1::ScalarField>, C1), Error> {
559 NIFS::<C1, CS1>::compute_cmT(
560 &self.cs_params,
561 &self.r1cs,
562 &self.w_i,
563 &self.u_i,
564 &self.W_i,
565 &self.U_i,
566 )
567 }
568 // computes T* and cmT* for the CycleFoldCircuit
569 fn compute_cf_cmT(
570 &self,
571 cf_w_i: &Witness<C2>,
572 cf_u_i: &CommittedInstance<C2>,
573 cf_W_i: &Witness<C2>,
574 cf_U_i: &CommittedInstance<C2>,
575 ) -> Result<(Vec<C2::ScalarField>, C2), Error> {
576 NIFS::<C2, CS2>::compute_cyclefold_cmT(
577 &self.cf_cs_params,
578 &self.cf_r1cs,
579 cf_w_i,
580 cf_u_i,
581 cf_W_i,
582 cf_U_i,
583 )
584 }
585}
586
587impl<C1, GC1, C2, GC2, FC, CS1, CS2> Nova<C1, GC1, C2, GC2, FC, CS1, CS2>
588where
589 C1: CurveGroup,
590 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
591 C2: CurveGroup,
592 GC2: CurveVar<C2, CF2<C2>>,
593 FC: FCircuit<C1::ScalarField>,
594 CS1: CommitmentScheme<C1>,
595 CS2: CommitmentScheme<C2>,
596 <C1 as CurveGroup>::BaseField: PrimeField,
597 <C2 as CurveGroup>::BaseField: PrimeField,
598 <C1 as Group>::ScalarField: Absorb,
599 <C2 as Group>::ScalarField: Absorb,
600 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
601 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
602 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
603{
604 // folds the given cyclefold circuit and its instances
605 #[allow(clippy::type_complexity)]
606 fn fold_cyclefold_circuit(
607 &self,
608 cf_W_i: Witness<C2>, // witness of the running instance
609 cf_U_i: CommittedInstance<C2>, // running instance
610 cf_u_i_x: Vec<C2::ScalarField>,
611 cf_circuit: CycleFoldCircuit<C1, GC1>,
612 ) -> Result<
613 (
614 Witness<C2>,
615 CommittedInstance<C2>, // u_i
616 Witness<C2>, // W_i1
617 CommittedInstance<C2>, // U_i1
618 C2, // cmT
619 C2::ScalarField, // r_Fq
620 ),
621 Error,
622 > {
623 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
624 cf_circuit.generate_constraints(cs2.clone())?;
625
626 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
627 let (cf_w_i, cf_x_i) = extract_w_x::<C1::BaseField>(&cs2);
628 if cf_x_i != cf_u_i_x {
629 return Err(Error::NotEqual);
630 }
631
632 #[cfg(test)]
633 if cf_x_i.len() != CF_IO_LEN {
634 return Err(Error::NotExpectedLength(cf_x_i.len(), CF_IO_LEN));
635 }
636
637 // fold cyclefold instances
638 let cf_w_i = Witness::<C2>::new(cf_w_i.clone(), self.cf_r1cs.A.n_rows);
639 let cf_u_i: CommittedInstance<C2> =
640 cf_w_i.commit::<CS2>(&self.cf_cs_params, cf_x_i.clone())?;
641
642 // compute T* and cmT* for CycleFoldCircuit
643 let (cf_T, cf_cmT) = self.compute_cf_cmT(&cf_w_i, &cf_u_i, &cf_W_i, &cf_U_i)?;
644
645 let cf_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_native(
646 &self.poseidon_config,
647 cf_U_i.clone(),
648 cf_u_i.clone(),
649 cf_cmT,
650 )?;
651 let cf_r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&cf_r_bits))
652 .ok_or(Error::OutOfBounds)?;
653
654 let (cf_W_i1, cf_U_i1) = NIFS::<C2, CS2>::fold_instances(
655 cf_r_Fq, &cf_W_i, &cf_U_i, &cf_w_i, &cf_u_i, &cf_T, cf_cmT,
656 )?;
657 Ok((cf_w_i, cf_u_i, cf_W_i1, cf_U_i1, cf_cmT, cf_r_Fq))
658 }
659}
660
661/// helper method to get the r1cs from the ConstraintSynthesizer
662pub fn get_r1cs_from_cs<F: PrimeField>(
663 circuit: impl ConstraintSynthesizer<F>,
664) -> Result<R1CS<F>, Error> {
665 let cs = ConstraintSystem::<F>::new_ref();
666 circuit.generate_constraints(cs.clone())?;
667 cs.finalize();
668 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
669 let r1cs = extract_r1cs::<F>(&cs);
670 Ok(r1cs)
671}
672
673/// helper method to get the R1CS for both the AugmentedFCircuit and the CycleFold circuit
674#[allow(clippy::type_complexity)]
675pub fn get_r1cs<C1, GC1, C2, GC2, FC>(
676 poseidon_config: &PoseidonConfig<C1::ScalarField>,
677 F_circuit: FC,
678) -> Result<(R1CS<C1::ScalarField>, R1CS<C2::ScalarField>), Error>
679where
680 C1: CurveGroup,
681 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
682 C2: CurveGroup,
683 GC2: CurveVar<C2, CF2<C2>>,
684 FC: FCircuit<C1::ScalarField>,
685 <C1 as CurveGroup>::BaseField: PrimeField,
686 <C2 as CurveGroup>::BaseField: PrimeField,
687 <C1 as Group>::ScalarField: Absorb,
688 <C2 as Group>::ScalarField: Absorb,
689 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
690 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
691 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
692{
693 let augmented_F_circuit =
694 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(poseidon_config, F_circuit);
695 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
696 let r1cs = get_r1cs_from_cs::<C1::ScalarField>(augmented_F_circuit)?;
697 let cf_r1cs = get_r1cs_from_cs::<C2::ScalarField>(cf_circuit)?;
698 Ok((r1cs, cf_r1cs))
699}
700
701/// helper method to get the pedersen params length for both the AugmentedFCircuit and the
702/// CycleFold circuit
703pub fn get_cs_params_len<C1, GC1, C2, GC2, FC>(
704 poseidon_config: &PoseidonConfig<C1::ScalarField>,
705 F_circuit: FC,
706) -> Result<(usize, usize), Error>
707where
708 C1: CurveGroup,
709 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
710 C2: CurveGroup,
711 GC2: CurveVar<C2, CF2<C2>>,
712 FC: FCircuit<C1::ScalarField>,
713 <C1 as CurveGroup>::BaseField: PrimeField,
714 <C2 as CurveGroup>::BaseField: PrimeField,
715 <C1 as Group>::ScalarField: Absorb,
716 <C2 as Group>::ScalarField: Absorb,
717 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
718 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
719 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
720{
721 let (r1cs, cf_r1cs) = get_r1cs::<C1, GC1, C2, GC2, FC>(poseidon_config, F_circuit)?;
722 Ok((r1cs.A.n_rows, cf_r1cs.A.n_rows))
723}
724
725/// returns the coordinates of a commitment point. This is compatible with the arkworks
726/// GC.to_constraint_field()[..2]
727pub(crate) fn get_cm_coordinates<C: CurveGroup>(cm: &C) -> Vec<C::BaseField> {
728 let zero = (&C::BaseField::zero(), &C::BaseField::one());
729 let cm = cm.into_affine();
730 let (cm_x, cm_y) = cm.xy().unwrap_or(zero);
731 vec![*cm_x, *cm_y]
732}
733
734#[cfg(test)]
735pub mod tests {
736 use super::*;
737 use crate::commitment::kzg::{ProverKey as KZGProverKey, KZG};
738 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
739 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
740 use ark_poly_commit::kzg10::VerifierKey as KZGVerifierKey;
741
742 use crate::commitment::pedersen::Pedersen;
743 use crate::frontend::tests::CubicFCircuit;
744 use crate::transcript::poseidon::poseidon_test_config;
745
746 /// This test tests the Nova+CycleFold IVC, and by consequence it is also testing the
747 /// AugmentedFCircuit
748 #[test]
749 fn test_ivc() {
750 let mut rng = ark_std::test_rng();
751 let poseidon_config = poseidon_test_config::<Fr>();
752
753 let F_circuit = CubicFCircuit::<Fr>::new(());
754
755 let (cs_len, cf_cs_len) =
756 get_cs_params_len::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>>(
757 &poseidon_config,
758 F_circuit,
759 )
760 .unwrap();
761 let (kzg_pk, _): (KZGProverKey<Projective>, KZGVerifierKey<Bn254>) =
762 KZG::<Bn254>::setup(&mut rng, cs_len).unwrap();
763 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, cs_len).unwrap();
764 let (cf_pedersen_params, _) = Pedersen::<Projective2>::setup(&mut rng, cf_cs_len).unwrap();
765
766 // run the test using Pedersen commitments on both sides of the curve cycle
767 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>>(
768 poseidon_config.clone(),
769 pedersen_params,
770 cf_pedersen_params.clone(),
771 F_circuit,
772 );
773 // run the test using KZG for the commitments on the main curve, and Pedersen for the
774 // commitments on the secondary curve
775 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>>(
776 poseidon_config,
777 kzg_pk,
778 cf_pedersen_params,
779 F_circuit,
780 );
781 }
782
783 // test_ivc allowing to choose the CommitmentSchemes
784 fn test_ivc_opt<CS1: CommitmentScheme<Projective>, CS2: CommitmentScheme<Projective2>>(
785 poseidon_config: PoseidonConfig<Fr>,
786 cs_params: CS1::ProverParams,
787 cf_cs_params: CS2::ProverParams,
788 F_circuit: CubicFCircuit<Fr>,
789 ) {
790 type NOVA<CS1, CS2> =
791 Nova<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2>;
792
793 let prover_params = ProverParams::<Projective, Projective2, CS1, CS2> {
794 poseidon_config: poseidon_config.clone(),
795 cs_params,
796 cf_cs_params,
797 };
798
799 let z_0 = vec![Fr::from(3_u32)];
800 let mut nova = NOVA::init(&prover_params, F_circuit, z_0.clone()).unwrap();
801
802 let num_steps: usize = 3;
803 for _ in 0..num_steps {
804 nova.prove_step().unwrap();
805 }
806 assert_eq!(Fr::from(num_steps as u32), nova.i);
807
808 let verifier_params = VerifierParams::<Projective, Projective2> {
809 poseidon_config,
810 r1cs: nova.clone().r1cs,
811 cf_r1cs: nova.clone().cf_r1cs,
812 };
813 let (running_instance, incoming_instance, cyclefold_instance) = nova.instances();
814 NOVA::<CS1, CS2>::verify(
815 verifier_params,
816 z_0,
817 nova.z_i,
818 nova.i,
819 running_instance,
820 incoming_instance,
821 cyclefold_instance,
822 )
823 .unwrap();
824 }
825}