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