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