sonobe/folding-schemes/src/folding/nova/cyclefold.rs
folding-schemes/src/folding/nova/cyclefold.rsRaw
1/// contains [CycleFold](https://eprint.iacr.org/2023/1192.pdf) related circuits
2use ark_crypto_primitives::sponge::{
3 constraints::CryptographicSpongeVar,
4 poseidon::{constraints::PoseidonSpongeVar, PoseidonConfig, PoseidonSponge},
5 Absorb, CryptographicSponge,
6};
7use ark_ec::CurveGroup;
8use ark_ff::PrimeField;
9use ark_r1cs_std::{
10 alloc::{AllocVar, AllocationMode},
11 bits::uint8::UInt8,
12 boolean::Boolean,
13 eq::EqGadget,
14 fields::{fp::FpVar, nonnative::NonNativeFieldVar},
15 groups::GroupOpsBounds,
16 prelude::CurveVar,
17 ToBytesGadget,
18};
19use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, Namespace, SynthesisError};
20use ark_serialize::CanonicalSerialize;
21use ark_std::fmt::Debug;
22use ark_std::Zero;
23use core::{borrow::Borrow, marker::PhantomData};
24
25use super::circuits::CF2;
26use super::CommittedInstance;
27use crate::constants::N_BITS_RO;
28use crate::Error;
29
30// publi inputs length for the CycleFoldCircuit, |[p1.x,y, p2.x,y, p3.x,y]|
31pub const CF_IO_LEN: usize = 6;
32
33/// CycleFoldCommittedInstanceVar is the CycleFold CommittedInstance representation in the Nova
34/// circuit.
35#[derive(Debug, Clone)]
36pub struct CycleFoldCommittedInstanceVar<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
37where
38 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
39{
40 _c: PhantomData<C>,
41 pub cmE: GC,
42 pub u: NonNativeFieldVar<C::ScalarField, CF2<C>>,
43 pub cmW: GC,
44 pub x: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>,
45}
46impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CycleFoldCommittedInstanceVar<C, GC>
47where
48 C: CurveGroup,
49 GC: CurveVar<C, CF2<C>>,
50 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
51 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
52{
53 fn new_variable<T: Borrow<CommittedInstance<C>>>(
54 cs: impl Into<Namespace<CF2<C>>>,
55 f: impl FnOnce() -> Result<T, SynthesisError>,
56 mode: AllocationMode,
57 ) -> Result<Self, SynthesisError> {
58 f().and_then(|val| {
59 let cs = cs.into();
60
61 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
62 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
63 let u = NonNativeFieldVar::<C::ScalarField, CF2<C>>::new_variable(
64 cs.clone(),
65 || Ok(val.borrow().u),
66 mode,
67 )?;
68 let x = Vec::<NonNativeFieldVar<C::ScalarField, CF2<C>>>::new_variable(
69 cs.clone(),
70 || Ok(val.borrow().x.clone()),
71 mode,
72 )?;
73
74 Ok(Self {
75 _c: PhantomData,
76 cmE,
77 u,
78 cmW,
79 x,
80 })
81 })
82 }
83}
84
85/// CommittedInstanceInCycleFoldVar represents the Nova CommittedInstance in the CycleFold circuit,
86/// where the commitments to E and W (cmW and cmW) from the CommittedInstance on the E2,
87/// represented as native points, which are folded on the auxiliary curve constraints field (E2::Fr
88/// = E1::Fq).
89#[derive(Debug, Clone)]
90pub struct CommittedInstanceInCycleFoldVar<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
91where
92 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
93{
94 _c: PhantomData<C>,
95 pub cmE: GC,
96 pub cmW: GC,
97}
98
99impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CommittedInstanceInCycleFoldVar<C, GC>
100where
101 C: CurveGroup,
102 GC: CurveVar<C, CF2<C>>,
103 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
104{
105 fn new_variable<T: Borrow<CommittedInstance<C>>>(
106 cs: impl Into<Namespace<CF2<C>>>,
107 f: impl FnOnce() -> Result<T, SynthesisError>,
108 mode: AllocationMode,
109 ) -> Result<Self, SynthesisError> {
110 f().and_then(|val| {
111 let cs = cs.into();
112
113 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
114 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
115
116 Ok(Self {
117 _c: PhantomData,
118 cmE,
119 cmW,
120 })
121 })
122 }
123}
124
125/// This is the gadget used in the AugmentedFCircuit to verify the CycleFold instances folding,
126/// which checks the correct RLC of u,x,cmE,cmW (hence the name containing 'Full', since it checks
127/// all the RLC values, not only the native ones). It assumes that ci2.cmE=0, ci2.u=1.
128pub struct NIFSFullGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
129 _c: PhantomData<C>,
130 _gc: PhantomData<GC>,
131}
132impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> NIFSFullGadget<C, GC>
133where
134 C: CurveGroup,
135 GC: CurveVar<C, CF2<C>>,
136 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
137 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
138{
139 pub fn verify(
140 // assumes that r_bits is equal to r_nonnat just that in a different format
141 r_bits: Vec<Boolean<CF2<C>>>,
142 r_nonnat: NonNativeFieldVar<C::ScalarField, CF2<C>>,
143 cmT: GC,
144 // ci1 is assumed to be always with cmE=0, u=1 (checks done previous to this method)
145 ci1: CycleFoldCommittedInstanceVar<C, GC>,
146 ci2: CycleFoldCommittedInstanceVar<C, GC>,
147 ci3: CycleFoldCommittedInstanceVar<C, GC>,
148 ) -> Result<Boolean<CF2<C>>, SynthesisError> {
149 // cm(E) check: ci3.cmE == ci1.cmE + r * cmT (ci2.cmE=0)
150 let first_check = ci3
151 .cmE
152 .is_eq(&(cmT.scalar_mul_le(r_bits.iter())? + ci1.cmE))?;
153
154 // cm(W) check: ci3.cmW == ci1.cmW + r * ci2.cmW
155 let second_check = ci3
156 .cmW
157 .is_eq(&(ci1.cmW + ci2.cmW.scalar_mul_le(r_bits.iter())?))?;
158
159 let u_rlc: NonNativeFieldVar<C::ScalarField, CF2<C>> = ci1.u + r_nonnat.clone();
160 let third_check = u_rlc.is_eq(&ci3.u)?;
161
162 // ensure that: ci3.x == ci1.x + r * ci2.x
163 let x_rlc: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>> = ci1
164 .x
165 .iter()
166 .zip(ci2.x)
167 .map(|(a, b)| a + &r_nonnat * &b)
168 .collect::<Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>>();
169 let fourth_check = x_rlc.is_eq(&ci3.x)?;
170
171 first_check
172 .and(&second_check)?
173 .and(&third_check)?
174 .and(&fourth_check)
175 }
176}
177
178/// ChallengeGadget computes the RO challenge used for the CycleFold instances NIFS, it contains a
179/// rust-native and a in-circuit compatible versions.
180pub struct CycleFoldChallengeGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
181 _c: PhantomData<C>, // Nova's Curve2, the one used for the CycleFold circuit
182 _gc: PhantomData<GC>,
183}
184impl<C, GC> CycleFoldChallengeGadget<C, GC>
185where
186 C: CurveGroup,
187 GC: CurveVar<C, CF2<C>>,
188 <C as CurveGroup>::BaseField: PrimeField,
189 <C as CurveGroup>::BaseField: Absorb,
190 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
191{
192 pub fn get_challenge_native(
193 poseidon_config: &PoseidonConfig<C::BaseField>,
194 U_i: CommittedInstance<C>,
195 u_i: CommittedInstance<C>,
196 cmT: C,
197 ) -> Result<Vec<bool>, Error> {
198 let mut sponge = PoseidonSponge::<C::BaseField>::new(poseidon_config);
199
200 let U_i_cmE_bytes = point_to_bytes(U_i.cmE)?;
201 let U_i_cmW_bytes = point_to_bytes(U_i.cmW)?;
202 let u_i_cmE_bytes = point_to_bytes(u_i.cmE)?;
203 let u_i_cmW_bytes = point_to_bytes(u_i.cmW)?;
204 let cmT_bytes = point_to_bytes(cmT)?;
205
206 let mut U_i_u_bytes = Vec::new();
207 U_i.u.serialize_uncompressed(&mut U_i_u_bytes)?;
208 let mut U_i_x_bytes = Vec::new();
209 U_i.x.serialize_uncompressed(&mut U_i_x_bytes)?;
210 U_i_x_bytes = U_i_x_bytes[8..].to_vec();
211 let mut u_i_u_bytes = Vec::new();
212 u_i.u.serialize_uncompressed(&mut u_i_u_bytes)?;
213 let mut u_i_x_bytes = Vec::new();
214 u_i.x.serialize_uncompressed(&mut u_i_x_bytes)?;
215 u_i_x_bytes = u_i_x_bytes[8..].to_vec();
216
217 let input: Vec<u8> = [
218 U_i_cmE_bytes,
219 U_i_u_bytes,
220 U_i_cmW_bytes,
221 U_i_x_bytes,
222 u_i_cmE_bytes,
223 u_i_u_bytes,
224 u_i_cmW_bytes,
225 u_i_x_bytes,
226 cmT_bytes,
227 ]
228 .concat();
229 sponge.absorb(&input);
230 let bits = sponge.squeeze_bits(N_BITS_RO);
231 Ok(bits)
232 }
233 // compatible with the native get_challenge_native
234 pub fn get_challenge_gadget(
235 cs: ConstraintSystemRef<C::BaseField>,
236 poseidon_config: &PoseidonConfig<C::BaseField>,
237 U_i: CycleFoldCommittedInstanceVar<C, GC>,
238 u_i: CycleFoldCommittedInstanceVar<C, GC>,
239 cmT: GC,
240 ) -> Result<Vec<Boolean<C::BaseField>>, SynthesisError> {
241 let mut sponge = PoseidonSpongeVar::<C::BaseField>::new(cs, poseidon_config);
242
243 let U_i_x_bytes: Vec<UInt8<CF2<C>>> = U_i
244 .x
245 .iter()
246 .flat_map(|e| e.to_bytes().unwrap_or(vec![]))
247 .collect::<Vec<UInt8<CF2<C>>>>();
248 let u_i_x_bytes: Vec<UInt8<CF2<C>>> = u_i
249 .x
250 .iter()
251 .flat_map(|e| e.to_bytes().unwrap_or(vec![]))
252 .collect::<Vec<UInt8<CF2<C>>>>();
253
254 let input: Vec<UInt8<CF2<C>>> = [
255 U_i.cmE.to_bytes()?,
256 U_i.u.to_bytes()?,
257 U_i.cmW.to_bytes()?,
258 U_i_x_bytes,
259 u_i.cmE.to_bytes()?,
260 u_i.u.to_bytes()?,
261 u_i.cmW.to_bytes()?,
262 u_i_x_bytes,
263 cmT.to_bytes()?,
264 // TODO instead of bytes, use field elements, but needs x,y coordinates from
265 // u_i.{cmE,cmW}, U_i.{cmE,cmW}, cmT. Depends exposing x,y coordinates of GC. Issue to
266 // keep track of this:
267 // https://github.com/privacy-scaling-explorations/folding-schemes/issues/44
268 ]
269 .concat();
270 sponge.absorb(&input)?;
271 let bits = sponge.squeeze_bits(N_BITS_RO)?;
272 Ok(bits)
273 }
274}
275
276/// returns the bytes being compatible with the ark_r1cs_std `.to_bytes` approach
277fn point_to_bytes<C: CurveGroup>(p: C) -> Result<Vec<u8>, Error> {
278 let l = p.uncompressed_size();
279 let mut b = Vec::new();
280 p.serialize_uncompressed(&mut b)?;
281 b[l - 1] = 0;
282 if p.is_zero() {
283 b[l / 2] = 1;
284 b[l - 1] = 1;
285 }
286 Ok(b)
287}
288
289/// CycleFoldCircuit contains the constraints that check the correct fold of the committed
290/// instances from Curve1. Namely, it checks the random linear combinations of the elliptic curve
291/// (Curve1) points of u_i, U_i leading to U_{i+1}
292#[derive(Debug, Clone)]
293pub struct CycleFoldCircuit<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
294 pub _gc: PhantomData<GC>,
295 pub r_bits: Option<Vec<bool>>,
296 pub p1: Option<C>,
297 pub p2: Option<C>,
298 pub p3: Option<C>,
299 pub x: Option<Vec<CF2<C>>>, // public inputs (cf_u_{i+1}.x)
300}
301impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> CycleFoldCircuit<C, GC> {
302 pub fn empty() -> Self {
303 Self {
304 _gc: PhantomData,
305 r_bits: None,
306 p1: None,
307 p2: None,
308 p3: None,
309 x: None,
310 }
311 }
312}
313impl<C, GC> ConstraintSynthesizer<CF2<C>> for CycleFoldCircuit<C, GC>
314where
315 C: CurveGroup,
316 GC: CurveVar<C, CF2<C>>,
317 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
318 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
319{
320 fn generate_constraints(self, cs: ConstraintSystemRef<CF2<C>>) -> Result<(), SynthesisError> {
321 let r_bits: Vec<Boolean<CF2<C>>> = Vec::new_witness(cs.clone(), || {
322 Ok(self.r_bits.unwrap_or(vec![false; N_BITS_RO]))
323 })?;
324 let p1 = GC::new_witness(cs.clone(), || Ok(self.p1.unwrap_or(C::zero())))?;
325 let p2 = GC::new_witness(cs.clone(), || Ok(self.p2.unwrap_or(C::zero())))?;
326 let p3 = GC::new_witness(cs.clone(), || Ok(self.p3.unwrap_or(C::zero())))?;
327
328 let _x = Vec::<FpVar<CF2<C>>>::new_input(cs.clone(), || {
329 Ok(self.x.unwrap_or(vec![CF2::<C>::zero(); CF_IO_LEN]))
330 })?;
331 #[cfg(test)]
332 assert_eq!(_x.len(), CF_IO_LEN); // non-constrained sanity check
333
334 // Fold the original Nova instances natively in CycleFold
335 // For the cmW we're checking: U_i1.cmW == U_i.cmW + r * u_i.cmW
336 // For the cmE we're checking: U_i1.cmE == U_i.cmE + r * cmT + r^2 * u_i.cmE, where u_i.cmE
337 // is assumed to be 0, so, U_i1.cmE == U_i.cmE + r * cmT
338 p3.enforce_equal(&(p1 + p2.scalar_mul_le(r_bits.iter())?))?;
339
340 // check that x == [u_i, U_i, U_{i+1}], check that the cmW & cmW from u_i, U_i, U_{i+1} in
341 // the CycleFoldCircuit are the sames used in the public inputs 'x', which come from the
342 // AugmentedFCircuit.
343 // TODO: Issue to keep track of this: https://github.com/privacy-scaling-explorations/folding-schemes/issues/44
344 // and https://github.com/privacy-scaling-explorations/folding-schemes/issues/48
345
346 Ok(())
347 }
348}
349
350#[cfg(test)]
351pub mod tests {
352 use super::*;
353 use ark_ff::BigInteger;
354 use ark_pallas::{constraints::GVar, Fq, Fr, Projective};
355 use ark_r1cs_std::{alloc::AllocVar, R1CSVar};
356 use ark_relations::r1cs::ConstraintSystem;
357 use ark_std::UniformRand;
358
359 use crate::folding::nova::get_cm_coordinates;
360 use crate::folding::nova::nifs::tests::prepare_simple_fold_inputs;
361 use crate::transcript::poseidon::poseidon_test_config;
362
363 #[test]
364 fn test_committed_instance_cyclefold_var() {
365 let mut rng = ark_std::test_rng();
366
367 let ci = CommittedInstance::<Projective> {
368 cmE: Projective::rand(&mut rng),
369 u: Fr::rand(&mut rng),
370 cmW: Projective::rand(&mut rng),
371 x: vec![Fr::rand(&mut rng); 1],
372 };
373
374 // check the instantiation of the CycleFold side:
375 let cs = ConstraintSystem::<Fq>::new_ref();
376 let ciVar =
377 CommittedInstanceInCycleFoldVar::<Projective, GVar>::new_witness(cs.clone(), || {
378 Ok(ci.clone())
379 })
380 .unwrap();
381 assert_eq!(ciVar.cmE.value().unwrap(), ci.cmE);
382 assert_eq!(ciVar.cmW.value().unwrap(), ci.cmW);
383 }
384
385 #[test]
386 fn test_CycleFoldCircuit_constraints() {
387 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, _) = prepare_simple_fold_inputs();
388
389 // cs is the Constraint System on the Curve Cycle auxiliary curve constraints field
390 // (E1::Fq=E2::Fr)
391 let cs = ConstraintSystem::<Fq>::new_ref();
392
393 let cfW_u_i_x = [
394 get_cm_coordinates(&ci1.cmW),
395 get_cm_coordinates(&ci2.cmW),
396 get_cm_coordinates(&ci3.cmW),
397 ]
398 .concat();
399 let cfW_circuit = CycleFoldCircuit::<Projective, GVar> {
400 _gc: PhantomData,
401 r_bits: Some(r_bits.clone()),
402 p1: Some(ci1.clone().cmW),
403 p2: Some(ci2.clone().cmW),
404 p3: Some(ci3.clone().cmW),
405 x: Some(cfW_u_i_x.clone()),
406 };
407 cfW_circuit.generate_constraints(cs.clone()).unwrap();
408 assert!(cs.is_satisfied().unwrap());
409 dbg!(cs.num_constraints());
410
411 // same for E:
412 let cs = ConstraintSystem::<Fq>::new_ref();
413 let cfE_u_i_x = [
414 get_cm_coordinates(&ci1.cmE),
415 get_cm_coordinates(&ci2.cmE),
416 get_cm_coordinates(&ci3.cmE),
417 ]
418 .concat();
419 let cfE_circuit = CycleFoldCircuit::<Projective, GVar> {
420 _gc: PhantomData,
421 r_bits: Some(r_bits.clone()),
422 p1: Some(ci1.clone().cmE),
423 p2: Some(cmT),
424 p3: Some(ci3.clone().cmE),
425 x: Some(cfE_u_i_x.clone()),
426 };
427 cfE_circuit.generate_constraints(cs.clone()).unwrap();
428 assert!(cs.is_satisfied().unwrap());
429 }
430
431 #[test]
432 fn test_nifs_full_gadget() {
433 let (_, _, _, _, ci1, _, ci2, _, ci3, _, cmT, r_bits, r_Fr) = prepare_simple_fold_inputs();
434
435 let cs = ConstraintSystem::<Fq>::new_ref();
436
437 let r_nonnatVar =
438 NonNativeFieldVar::<Fr, Fq>::new_witness(cs.clone(), || Ok(r_Fr)).unwrap();
439 let r_bitsVar = Vec::<Boolean<Fq>>::new_witness(cs.clone(), || Ok(r_bits)).unwrap();
440
441 let ci1Var =
442 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
443 Ok(ci1.clone())
444 })
445 .unwrap();
446 let ci2Var =
447 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
448 Ok(ci2.clone())
449 })
450 .unwrap();
451 let ci3Var =
452 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
453 Ok(ci3.clone())
454 })
455 .unwrap();
456 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
457
458 let nifs_check = NIFSFullGadget::<Projective, GVar>::verify(
459 r_bitsVar,
460 r_nonnatVar,
461 cmTVar,
462 ci1Var,
463 ci2Var,
464 ci3Var,
465 )
466 .unwrap();
467 nifs_check.enforce_equal(&Boolean::<Fq>::TRUE).unwrap();
468 assert!(cs.is_satisfied().unwrap());
469 }
470
471 #[test]
472 fn test_cyclefold_challenge_gadget() {
473 let mut rng = ark_std::test_rng();
474 let poseidon_config = poseidon_test_config::<Fq>();
475
476 let u_i = CommittedInstance::<Projective> {
477 cmE: Projective::zero(), // zero on purpose, so we test also the zero point case
478 u: Fr::zero(),
479 cmW: Projective::rand(&mut rng),
480 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
481 .take(CF_IO_LEN)
482 .collect(),
483 };
484 let U_i = CommittedInstance::<Projective> {
485 cmE: Projective::rand(&mut rng),
486 u: Fr::rand(&mut rng),
487 cmW: Projective::rand(&mut rng),
488 x: std::iter::repeat_with(|| Fr::rand(&mut rng))
489 .take(CF_IO_LEN)
490 .collect(),
491 };
492 let cmT = Projective::rand(&mut rng);
493
494 // compute the challenge natively
495 let r_bits = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_native(
496 &poseidon_config,
497 U_i.clone(),
498 u_i.clone(),
499 cmT,
500 )
501 .unwrap();
502
503 let cs = ConstraintSystem::<Fq>::new_ref();
504 let u_iVar =
505 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
506 Ok(u_i.clone())
507 })
508 .unwrap();
509 let U_iVar =
510 CycleFoldCommittedInstanceVar::<Projective, GVar>::new_witness(cs.clone(), || {
511 Ok(U_i.clone())
512 })
513 .unwrap();
514 let cmTVar = GVar::new_witness(cs.clone(), || Ok(cmT)).unwrap();
515
516 let r_bitsVar = CycleFoldChallengeGadget::<Projective, GVar>::get_challenge_gadget(
517 cs.clone(),
518 &poseidon_config,
519 U_iVar,
520 u_iVar,
521 cmTVar,
522 )
523 .unwrap();
524 assert!(cs.is_satisfied().unwrap());
525
526 // check that the natively computed and in-circuit computed hashes match
527 let rVar = Boolean::le_bits_to_fp_var(&r_bitsVar).unwrap();
528 let r = Fq::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
529 assert_eq!(rVar.value().unwrap(), r);
530 assert_eq!(r_bitsVar.value().unwrap(), r_bits);
531 }
532}