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 of the Augmented Function circuit
37 pub r1cs: R1CS<C1::ScalarField>,
38 /// R1CS of the CycleFold circuit
39 pub cf_r1cs: R1CS<C2::ScalarField>,
40 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
41 /// PedersenParams over C1
42 pub pedersen_params: PedersenParams<C1>,
43 /// CycleFold PedersenParams, over C2
44 pub cf_pedersen_params: PedersenParams<C2>,
45 /// F circuit, the circuit that is being folded
46 pub F: FC,
47 pub i: C1::ScalarField,
48 /// initial state
49 pub z_0: Vec<C1::ScalarField>,
50 /// current i-th state
51 pub z_i: Vec<C1::ScalarField>,
52 /// Nova instances
53 pub w_i: Witness<C1>,
54 pub u_i: CommittedInstance<C1>,
55 pub W_i: Witness<C1>,
56 pub U_i: CommittedInstance<C1>,
57
58 /// CycleFold running instance
59 pub cf_W_i: Witness<C2>,
60 pub cf_U_i: CommittedInstance<C2>,
61}
62
63impl<C1, GC1, C2, GC2, FC> IVC<C1, GC1, C2, GC2, FC>
64where
65 C1: CurveGroup,
66 GC1: CurveVar<C1, CF2<C1>>,
67 C2: CurveGroup,
68 GC2: CurveVar<C2, CF2<C2>>,
69 FC: FCircuit<C1::ScalarField>,
70 <C1 as CurveGroup>::BaseField: PrimeField,
71 <C2 as CurveGroup>::BaseField: PrimeField,
72 <C1 as Group>::ScalarField: Absorb,
73 <C2 as Group>::ScalarField: Absorb,
74 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
75 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
76 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
77{
78 /// Initializes the IVC for the given parameters and initial state `z_0`.
79 pub fn new<R: Rng>(
80 rng: &mut R,
81 poseidon_config: PoseidonConfig<C1::ScalarField>,
82 F: FC,
83 z_0: Vec<C1::ScalarField>,
84 ) -> Result<Self, Error> {
85 // prepare the circuit to obtain its R1CS
86 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
87 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
88
89 let augmented_F_circuit = AugmentedFCircuit::<C1, C2, GC2, FC>::empty(&poseidon_config, F);
90 let cf_circuit = CycleFoldCircuit::<C1, GC1>::empty();
91
92 augmented_F_circuit.generate_constraints(cs.clone())?;
93 cs.finalize();
94 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
95 let r1cs = extract_r1cs::<C1::ScalarField>(&cs);
96
97 cf_circuit.generate_constraints(cs2.clone())?;
98 cs2.finalize();
99 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
100 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2);
101
102 // this will not be randomly generated in this method, and will come from above levels, so
103 // the same params can be loaded on multiple instances
104 let pedersen_params = Pedersen::<C1>::new_params(rng, r1cs.A.n_rows);
105 let cf_pedersen_params = Pedersen::<C2>::new_params(rng, cf_r1cs.A.n_rows);
106
107 // setup the dummy instances
108 let (w_dummy, u_dummy) = r1cs.dummy_instance();
109 let (cf_w_dummy, cf_u_dummy) = cf_r1cs.dummy_instance();
110
111 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
112 // R1CS that we're working with.
113 Ok(Self {
114 _gc1: PhantomData,
115 _c2: PhantomData,
116 _gc2: PhantomData,
117 r1cs,
118 cf_r1cs,
119 poseidon_config,
120 pedersen_params,
121 cf_pedersen_params,
122 F,
123 i: C1::ScalarField::zero(),
124 z_0: z_0.clone(),
125 z_i: z_0,
126 w_i: w_dummy.clone(),
127 u_i: u_dummy.clone(),
128 W_i: w_dummy,
129 U_i: u_dummy,
130 // cyclefold running instance
131 cf_W_i: cf_w_dummy.clone(),
132 cf_U_i: cf_u_dummy.clone(),
133 })
134 }
135
136 /// Implements IVC.P
137 pub fn prove_step(&mut self) -> Result<(), Error> {
138 let augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
139 let cf_circuit: CycleFoldCircuit<C1, GC1>;
140
141 let z_i1 = self.F.step_native(self.z_i.clone());
142
143 // compute T and cmT for AugmentedFCircuit
144 let (T, cmT) = self.compute_cmT()?;
145
146 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
147 &self.poseidon_config,
148 self.u_i.clone(),
149 self.U_i.clone(),
150 cmT,
151 )?;
152 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
153 .ok_or(Error::OutOfBounds)?;
154
155 // fold Nova instances
156 let (W_i1, U_i1): (Witness<C1>, CommittedInstance<C1>) =
157 NIFS::<C1>::fold_instances(r_Fr, &self.w_i, &self.u_i, &self.W_i, &self.U_i, &T, cmT)?;
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::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(&self.cf_pedersen_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>::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(&self.pedersen_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>::compute_cmT(
356 &self.pedersen_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>::compute_cyclefold_cmT(
371 &self.cf_pedersen_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)]
395mod 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::folding::nova::circuits::tests::TestFCircuit;
401 use crate::transcript::poseidon::tests::poseidon_test_config;
402
403 #[test]
404 fn test_ivc() {
405 let mut rng = ark_std::test_rng();
406 let poseidon_config = poseidon_test_config::<Fr>();
407
408 let F_circuit = TestFCircuit::<Fr>::new();
409 let z_0 = vec![Fr::from(3_u32)];
410
411 let mut ivc = IVC::<Projective, GVar, Projective2, GVar2, TestFCircuit<Fr>>::new(
412 &mut rng,
413 poseidon_config,
414 F_circuit,
415 z_0.clone(),
416 )
417 .unwrap();
418
419 let num_steps: usize = 3;
420 for _ in 0..num_steps {
421 ivc.prove_step().unwrap();
422 }
423
424 ivc.verify(z_0, num_steps as u32).unwrap();
425 }
426}