sonobe/src/folding/nova/ivc.rs
src/folding/nova/ivc.rsRaw
1use ark_crypto_primitives::sponge::{poseidon::PoseidonConfig, Absorb};
2use ark_ec::{AffineRepr, CurveGroup, Group};
3use ark_ff::{BigInteger, PrimeField};
4use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar};
5use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
6use ark_std::{One, Zero};
7use core::marker::PhantomData;
8
9use super::{
10 circuits::{AugmentedFCircuit, ChallengeGadget, CF2},
11 cyclefold::{CycleFoldChallengeGadget, CycleFoldCircuit},
12};
13use super::{nifs::NIFS, traits::NovaR1CS, CommittedInstance, Witness};
14use crate::ccs::r1cs::{extract_r1cs, extract_w_x, R1CS};
15use crate::commitment::CommitmentProver;
16use crate::frontend::FCircuit;
17use crate::Error;
18
19#[cfg(test)]
20use super::cyclefold::CF_IO_LEN;
21
22/// Implements the Incremental Verifiable Computation described in sections 1.2 and 5 of
23/// [Nova](https://eprint.iacr.org/2021/370.pdf)
24pub struct IVC<C1, GC1, C2, GC2, FC, CP1, CP2>
25where
26 C1: CurveGroup,
27 GC1: CurveVar<C1, CF2<C1>>,
28 C2: CurveGroup,
29 GC2: CurveVar<C2, CF2<C2>>,
30 FC: FCircuit<C1::ScalarField>,
31 CP1: CommitmentProver<C1>,
32 CP2: CommitmentProver<C2>,
33{
34 _gc1: PhantomData<GC1>,
35 _c2: PhantomData<C2>,
36 _gc2: PhantomData<GC2>,
37 /// R1CS of the Augmented Function circuit
38 pub r1cs: R1CS<C1::ScalarField>,
39 /// R1CS of the CycleFold circuit
40 pub cf_r1cs: R1CS<C2::ScalarField>,
41 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
42 /// CommitmentProver::Params over C1
43 pub cm_params: CP1::Params,
44 /// CycleFold CommitmentProver::Params, over C2
45 pub cf_cm_params: CP2::Params,
46 /// F circuit, the circuit that is being folded
47 pub F: FC,
48 pub i: C1::ScalarField,
49 /// initial state
50 pub z_0: Vec<C1::ScalarField>,
51 /// current i-th state
52 pub z_i: Vec<C1::ScalarField>,
53 /// Nova instances
54 pub w_i: Witness<C1>,
55 pub u_i: CommittedInstance<C1>,
56 pub W_i: Witness<C1>,
57 pub U_i: CommittedInstance<C1>,
58
59 /// CycleFold running instance
60 pub cf_W_i: Witness<C2>,
61 pub cf_U_i: CommittedInstance<C2>,
62}
63
64impl<C1, GC1, C2, GC2, FC, CP1, CP2> IVC<C1, GC1, C2, GC2, FC, CP1, CP2>
65where
66 C1: CurveGroup,
67 GC1: CurveVar<C1, CF2<C1>>,
68 C2: CurveGroup,
69 GC2: CurveVar<C2, CF2<C2>>,
70 FC: FCircuit<C1::ScalarField>,
71 CP1: CommitmentProver<C1>,
72 CP2: CommitmentProver<C2>,
73 <C1 as CurveGroup>::BaseField: PrimeField,
74 <C2 as CurveGroup>::BaseField: PrimeField,
75 <C1 as Group>::ScalarField: Absorb,
76 <C2 as Group>::ScalarField: Absorb,
77 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
78 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
79 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
80{
81 /// Initializes the IVC for the given parameters and initial state `z_0`.
82 pub fn new(
83 poseidon_config: PoseidonConfig<C1::ScalarField>,
84 cm_params: CP1::Params,
85 cf_cm_params: CP2::Params,
86 F: FC,
87 z_0: Vec<C1::ScalarField>,
88 ) -> Result<Self, Error> {
89 // prepare the circuit to obtain its R1CS
90 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
91 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
92
93 let augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&poseidon_config, F);
94 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
95
96 augmented_F_circuit.generate_constraints(cs.clone())?;
97 cs.finalize();
98 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
99 let r1cs = extract_r1cs::<C1::ScalarField>(&cs);
100
101 cf_circuit.generate_constraints(cs2.clone())?;
102 cs2.finalize();
103 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
104 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2);
105
106 // setup the dummy instances
107 let (w_dummy, u_dummy) = r1cs.dummy_instance();
108 let (cf_w_dummy, cf_u_dummy) = cf_r1cs.dummy_instance();
109
110 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
111 // R1CS that we're working with.
112 Ok(Self {
113 _gc1: PhantomData,
114 _c2: PhantomData,
115 _gc2: PhantomData,
116 r1cs,
117 cf_r1cs,
118 poseidon_config,
119 cm_params,
120 cf_cm_params,
121 F,
122 i: C1::ScalarField::zero(),
123 z_0: z_0.clone(),
124 z_i: z_0,
125 w_i: w_dummy.clone(),
126 u_i: u_dummy.clone(),
127 W_i: w_dummy,
128 U_i: u_dummy,
129 // cyclefold running instance
130 cf_W_i: cf_w_dummy.clone(),
131 cf_U_i: cf_u_dummy.clone(),
132 })
133 }
134
135 /// Implements IVC.P
136 pub fn prove_step(&mut self) -> Result<(), Error> {
137 let augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
138 let cf_circuit: CycleFoldCircuit<C1, GC1>;
139
140 let z_i1 = self.F.step_native(self.z_i.clone())?;
141
142 // compute T and cmT for AugmentedFCircuit
143 let (T, cmT) = self.compute_cmT()?;
144
145 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
146 &self.poseidon_config,
147 self.u_i.clone(),
148 self.U_i.clone(),
149 cmT,
150 )?;
151 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
152 .ok_or(Error::OutOfBounds)?;
153
154 // fold Nova instances
155 let (W_i1, U_i1): (Witness<C1>, CommittedInstance<C1>) = NIFS::<C1, CP1>::fold_instances(
156 r_Fr, &self.w_i, &self.u_i, &self.W_i, &self.U_i, &T, cmT,
157 )?;
158
159 // folded instance output (public input, x)
160 // u_{i+1}.x = H(i+1, z_0, z_{i+1}, U_{i+1})
161 let u_i1_x = U_i1.hash(
162 &self.poseidon_config,
163 self.i + C1::ScalarField::one(),
164 self.z_0.clone(),
165 z_i1.clone(),
166 )?;
167
168 if self.i == C1::ScalarField::zero() {
169 // base case
170 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
171 _gc2: PhantomData,
172 poseidon_config: self.poseidon_config.clone(),
173 i: Some(C1::ScalarField::zero()), // = i=0
174 z_0: Some(self.z_0.clone()), // = z_i
175 z_i: Some(self.z_i.clone()),
176 u_i: Some(self.u_i.clone()), // = dummy
177 U_i: Some(self.U_i.clone()), // = dummy
178 U_i1: Some(U_i1.clone()),
179 cmT: Some(cmT),
180 F: self.F,
181 x: Some(u_i1_x),
182 cf_u_i: None,
183 cf_U_i: None,
184 cf_U_i1: None,
185 cf_cmT: None,
186 cf_r_nonnat: None,
187 };
188
189 #[cfg(test)]
190 NIFS::<C1, CP1>::verify_folded_instance(r_Fr, &self.u_i, &self.U_i, &U_i1, &cmT)?;
191 } else {
192 // CycleFold part:
193 // get the vector used as public inputs 'x' in the CycleFold circuit
194 let cf_u_i_x = [
195 get_committed_instance_coordinates(&self.u_i),
196 get_committed_instance_coordinates(&self.U_i),
197 get_committed_instance_coordinates(&U_i1),
198 ]
199 .concat();
200
201 cf_circuit = CycleFoldCircuit::<C1, GC1> {
202 _gc: PhantomData,
203 r_bits: Some(r_bits.clone()),
204 cmT: Some(cmT),
205 u_i: Some(self.u_i.clone()),
206 U_i: Some(self.U_i.clone()),
207 U_i1: Some(U_i1.clone()),
208 x: Some(cf_u_i_x.clone()),
209 };
210
211 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
212 cf_circuit.generate_constraints(cs2.clone())?;
213
214 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
215 let (cf_w_i, cf_x_i) = extract_w_x::<C1::BaseField>(&cs2);
216 if cf_x_i != cf_u_i_x {
217 return Err(Error::NotEqual);
218 }
219
220 #[cfg(test)]
221 if cf_x_i.len() != CF_IO_LEN {
222 return Err(Error::NotExpectedLength(cf_x_i.len(), CF_IO_LEN));
223 }
224
225 // fold cyclefold instances
226 let cf_w_i = Witness::<C2>::new(cf_w_i.clone(), self.cf_r1cs.A.n_rows);
227 let cf_u_i: CommittedInstance<C2> =
228 cf_w_i.commit::<CP2>(&self.cf_cm_params, cf_x_i.clone())?;
229
230 // compute T* and cmT* for CycleFoldCircuit
231 let (cf_T, cf_cmT) = self.compute_cf_cmT(&cf_w_i, &cf_u_i)?;
232
233 let cf_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_native(
234 &self.poseidon_config,
235 cf_u_i.clone(),
236 self.cf_U_i.clone(),
237 cf_cmT,
238 )?;
239 let cf_r_Fq = C1::BaseField::from_bigint(BigInteger::from_bits_le(&cf_r_bits))
240 .ok_or(Error::OutOfBounds)?;
241
242 let (cf_W_i1, cf_U_i1) = NIFS::<C2, CP2>::fold_instances(
243 cf_r_Fq,
244 &self.cf_W_i,
245 &self.cf_U_i,
246 &cf_w_i,
247 &cf_u_i,
248 &cf_T,
249 cf_cmT,
250 )?;
251
252 augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC> {
253 _gc2: PhantomData,
254 poseidon_config: self.poseidon_config.clone(),
255 i: Some(self.i),
256 z_0: Some(self.z_0.clone()),
257 z_i: Some(self.z_i.clone()),
258 u_i: Some(self.u_i.clone()),
259 U_i: Some(self.U_i.clone()),
260 U_i1: Some(U_i1.clone()),
261 cmT: Some(cmT),
262 F: self.F,
263 x: Some(u_i1_x),
264 // cyclefold values
265 cf_u_i: Some(cf_u_i.clone()),
266 cf_U_i: Some(self.cf_U_i.clone()),
267 cf_U_i1: Some(cf_U_i1.clone()),
268 cf_cmT: Some(cf_cmT),
269 cf_r_nonnat: Some(cf_r_Fq),
270 };
271
272 self.cf_W_i = cf_W_i1.clone();
273 self.cf_U_i = cf_U_i1.clone();
274
275 #[cfg(test)]
276 {
277 self.cf_r1cs.check_instance_relation(&cf_w_i, &cf_u_i)?;
278 self.cf_r1cs
279 .check_relaxed_instance_relation(&self.cf_W_i, &self.cf_U_i)?;
280 }
281 }
282
283 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
284
285 augmented_F_circuit.generate_constraints(cs.clone())?;
286
287 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
288 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
289 if x_i1[0] != u_i1_x {
290 return Err(Error::NotEqual);
291 }
292
293 #[cfg(test)]
294 if x_i1.len() != 1 {
295 return Err(Error::NotExpectedLength(x_i1.len(), 1));
296 }
297
298 // set values for next iteration
299 self.i += C1::ScalarField::one();
300 self.z_i = z_i1.clone();
301 self.w_i = Witness::<C1>::new(w_i1, self.r1cs.A.n_rows);
302 self.u_i = self.w_i.commit::<CP1>(&self.cm_params, vec![u_i1_x])?;
303 self.W_i = W_i1.clone();
304 self.U_i = U_i1.clone();
305
306 #[cfg(test)]
307 {
308 self.r1cs.check_instance_relation(&self.w_i, &self.u_i)?;
309 self.r1cs
310 .check_relaxed_instance_relation(&self.W_i, &self.U_i)?;
311 }
312
313 Ok(())
314 }
315
316 /// Implements IVC.V
317 pub fn verify(&mut self, z_0: Vec<C1::ScalarField>, num_steps: u32) -> Result<(), Error> {
318 if self.i != C1::ScalarField::from(num_steps) {
319 return Err(Error::IVCVerificationFail);
320 }
321
322 if self.u_i.x.len() != 1 || self.U_i.x.len() != 1 {
323 return Err(Error::IVCVerificationFail);
324 }
325
326 // check that u_i's output points to the running instance
327 // u_i.X == H(i, z_0, z_i, U_i)
328 let expected_u_i_x = self
329 .U_i
330 .hash(&self.poseidon_config, self.i, z_0, self.z_i.clone())?;
331 if expected_u_i_x != self.u_i.x[0] {
332 return Err(Error::IVCVerificationFail);
333 }
334
335 // check u_i.cmE==0, u_i.u==1 (=u_i is a un-relaxed instance)
336 if !self.u_i.cmE.is_zero() || !self.u_i.u.is_one() {
337 return Err(Error::IVCVerificationFail);
338 }
339
340 // check R1CS satisfiability
341 self.r1cs.check_instance_relation(&self.w_i, &self.u_i)?;
342 // check RelaxedR1CS satisfiability
343 self.r1cs
344 .check_relaxed_instance_relation(&self.W_i, &self.U_i)?;
345
346 // check CycleFold RelaxedR1CS satisfiability
347 self.cf_r1cs
348 .check_relaxed_instance_relation(&self.cf_W_i, &self.cf_U_i)?;
349
350 Ok(())
351 }
352
353 // computes T and cmT for the AugmentedFCircuit
354 fn compute_cmT(&self) -> Result<(Vec<C1::ScalarField>, C1), Error> {
355 NIFS::<C1, CP1>::compute_cmT(
356 &self.cm_params,
357 &self.r1cs,
358 &self.w_i,
359 &self.u_i,
360 &self.W_i,
361 &self.U_i,
362 )
363 }
364 // computes T* and cmT* for the CycleFoldCircuit
365 fn compute_cf_cmT(
366 &self,
367 cf_w_i: &Witness<C2>,
368 cf_u_i: &CommittedInstance<C2>,
369 ) -> Result<(Vec<C2::ScalarField>, C2), Error> {
370 NIFS::<C2, CP2>::compute_cyclefold_cmT(
371 &self.cf_cm_params,
372 &self.cf_r1cs,
373 cf_w_i,
374 cf_u_i,
375 &self.cf_W_i,
376 &self.cf_U_i,
377 )
378 }
379}
380
381pub(crate) fn get_committed_instance_coordinates<C: CurveGroup>(
382 u: &CommittedInstance<C>,
383) -> Vec<C::BaseField> {
384 let zero = (&C::BaseField::zero(), &C::BaseField::one());
385
386 let cmE = u.cmE.into_affine();
387 let (cmE_x, cmE_y) = cmE.xy().unwrap_or(zero);
388
389 let cmW = u.cmW.into_affine();
390 let (cmW_x, cmW_y) = cmW.xy().unwrap_or(zero);
391 vec![*cmE_x, *cmE_y, *cmW_x, *cmW_y]
392}
393
394#[cfg(test)]
395pub mod tests {
396 use super::*;
397 use ark_pallas::{constraints::GVar, Fr, Projective};
398 use ark_vesta::{constraints::GVar as GVar2, Projective as Projective2};
399
400 use crate::commitment::pedersen::Pedersen;
401 use crate::frontend::tests::CubicFCircuit;
402 use crate::transcript::poseidon::tests::poseidon_test_config;
403
404 /// helper method to get the r1cs from the circuit
405 pub fn get_r1cs<F: PrimeField>(
406 circuit: impl ConstraintSynthesizer<F>,
407 ) -> Result<R1CS<F>, Error> {
408 let cs = ConstraintSystem::<F>::new_ref();
409 circuit.generate_constraints(cs.clone())?;
410 cs.finalize();
411 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
412 let r1cs = extract_r1cs::<F>(&cs);
413 Ok(r1cs)
414 }
415
416 /// helper method to get the pedersen params length for both the AugmentedFCircuit and the
417 /// CycleFold circuit
418 pub fn get_pedersen_params_len<FC: FCircuit<Fr>>(
419 poseidon_config: &PoseidonConfig<Fr>,
420 F_circuit: FC,
421 ) -> Result<(usize, usize), Error> {
422 let augmented_F_circuit = AugmentedFCircuit::<Projective, Projective2, GVar2, FC>::empty(
423 poseidon_config,
424 F_circuit,
425 );
426 let cf_circuit = CycleFoldCircuit::<Projective, GVar>::empty();
427 let r1cs = get_r1cs(augmented_F_circuit)?;
428 let cf_r1cs = get_r1cs(cf_circuit)?;
429 Ok((r1cs.A.n_rows, cf_r1cs.A.n_rows))
430 }
431
432 #[test]
433 fn test_ivc() {
434 let mut rng = ark_std::test_rng();
435 let poseidon_config = poseidon_test_config::<Fr>();
436
437 let F_circuit = CubicFCircuit::<Fr>::new(());
438 let z_0 = vec![Fr::from(3_u32)];
439
440 let (pedersen_len, cf_pedersen_len) =
441 get_pedersen_params_len::<CubicFCircuit<Fr>>(&poseidon_config, F_circuit).unwrap();
442 // generate the Pedersen params
443 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, pedersen_len);
444 let cf_pedersen_params = Pedersen::<Projective2>::new_params(&mut rng, cf_pedersen_len);
445
446 let mut ivc = IVC::<
447 Projective,
448 GVar,
449 Projective2,
450 GVar2,
451 CubicFCircuit<Fr>,
452 Pedersen<Projective>,
453 Pedersen<Projective2>,
454 >::new(
455 poseidon_config,
456 pedersen_params,
457 cf_pedersen_params,
458 F_circuit,
459 z_0.clone(),
460 )
461 .unwrap();
462
463 let num_steps: usize = 3;
464 for _ in 0..num_steps {
465 ivc.prove_step().unwrap();
466 }
467
468 ivc.verify(z_0, num_steps as u32).unwrap();
469 }
470}