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