sonobe/folding-schemes/src/folding/nova/circuits.rs
folding-schemes/src/folding/nova/circuits.rsRaw
1/// contains [Nova](https://eprint.iacr.org/2021/370.pdf) related circuits
2use ark_crypto_primitives::sponge::{
3 constraints::{AbsorbGadget, CryptographicSpongeVar},
4 poseidon::{constraints::PoseidonSpongeVar, PoseidonConfig},
5 Absorb, CryptographicSponge,
6};
7use ark_ec::{CurveGroup, Group};
8use ark_ff::PrimeField;
9use ark_r1cs_std::{
10 alloc::{AllocVar, AllocationMode},
11 boolean::Boolean,
12 eq::EqGadget,
13 fields::{fp::FpVar, FieldVar},
14 groups::GroupOpsBounds,
15 prelude::CurveVar,
16 uint8::UInt8,
17 R1CSVar, ToConstraintFieldGadget,
18};
19use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, Namespace, SynthesisError};
20use ark_std::{fmt::Debug, One, Zero};
21use core::{borrow::Borrow, marker::PhantomData};
22
23use super::{CommittedInstance, NovaCycleFoldConfig};
24use crate::folding::circuits::{
25 cyclefold::{
26 CycleFoldChallengeGadget, CycleFoldCommittedInstance, CycleFoldCommittedInstanceVar,
27 CycleFoldConfig, NIFSFullGadget,
28 },
29 nonnative::{affine::NonNativeAffineVar, uint::NonNativeUintVar},
30 CF1, CF2,
31};
32use crate::frontend::FCircuit;
33use crate::transcript::{AbsorbNonNativeGadget, Transcript, TranscriptVar};
34use crate::{
35 constants::NOVA_N_BITS_RO,
36 folding::traits::{CommittedInstanceVarOps, Dummy},
37};
38
39/// CommittedInstanceVar contains the u, x, cmE and cmW values which are folded on the main Nova
40/// constraints field (E1::Fr, where E1 is the main curve). The peculiarity is that cmE and cmW are
41/// represented non-natively over the constraint field.
42#[derive(Debug, Clone)]
43pub struct CommittedInstanceVar<C: CurveGroup> {
44 pub u: FpVar<C::ScalarField>,
45 pub x: Vec<FpVar<C::ScalarField>>,
46 pub cmE: NonNativeAffineVar<C>,
47 pub cmW: NonNativeAffineVar<C>,
48}
49
50impl<C> AllocVar<CommittedInstance<C>, CF1<C>> for CommittedInstanceVar<C>
51where
52 C: CurveGroup,
53{
54 fn new_variable<T: Borrow<CommittedInstance<C>>>(
55 cs: impl Into<Namespace<CF1<C>>>,
56 f: impl FnOnce() -> Result<T, SynthesisError>,
57 mode: AllocationMode,
58 ) -> Result<Self, SynthesisError> {
59 f().and_then(|val| {
60 let cs = cs.into();
61
62 let u = FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().u), mode)?;
63 let x: Vec<FpVar<C::ScalarField>> =
64 Vec::new_variable(cs.clone(), || Ok(val.borrow().x.clone()), mode)?;
65
66 let cmE =
67 NonNativeAffineVar::<C>::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
68 let cmW =
69 NonNativeAffineVar::<C>::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
70
71 Ok(Self { u, x, cmE, cmW })
72 })
73 }
74}
75
76impl<C> AbsorbGadget<C::ScalarField> for CommittedInstanceVar<C>
77where
78 C: CurveGroup,
79 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
80{
81 fn to_sponge_bytes(&self) -> Result<Vec<UInt8<C::ScalarField>>, SynthesisError> {
82 FpVar::batch_to_sponge_bytes(&self.to_sponge_field_elements()?)
83 }
84
85 fn to_sponge_field_elements(&self) -> Result<Vec<FpVar<C::ScalarField>>, SynthesisError> {
86 Ok([
87 vec![self.u.clone()],
88 self.x.clone(),
89 self.cmE.to_constraint_field()?,
90 self.cmW.to_constraint_field()?,
91 ]
92 .concat())
93 }
94}
95
96impl<C: CurveGroup> CommittedInstanceVarOps<C> for CommittedInstanceVar<C> {
97 type PointVar = NonNativeAffineVar<C>;
98
99 fn get_commitments(&self) -> Vec<Self::PointVar> {
100 vec![self.cmW.clone(), self.cmE.clone()]
101 }
102
103 fn get_public_inputs(&self) -> &[FpVar<CF1<C>>] {
104 &self.x
105 }
106
107 fn enforce_incoming(&self) -> Result<(), SynthesisError> {
108 let zero = NonNativeUintVar::new_constant(ConstraintSystemRef::None, CF2::<C>::zero())?;
109 self.cmE.x.enforce_equal_unaligned(&zero)?;
110 self.cmE.y.enforce_equal_unaligned(&zero)?;
111 self.u.enforce_equal(&FpVar::one())
112 }
113
114 fn enforce_partial_equal(&self, other: &Self) -> Result<(), SynthesisError> {
115 self.u.enforce_equal(&other.u)?;
116 self.x.enforce_equal(&other.x)
117 }
118}
119
120/// Implements the circuit that does the checks of the Non-Interactive Folding Scheme Verifier
121/// described in section 4 of [Nova](https://eprint.iacr.org/2021/370.pdf), where the cmE & cmW checks are
122/// delegated to the NIFSCycleFoldGadget.
123pub struct NIFSGadget<C: CurveGroup> {
124 _c: PhantomData<C>,
125}
126
127impl<C: CurveGroup> NIFSGadget<C>
128where
129 C: CurveGroup,
130 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
131{
132 pub fn fold_committed_instance(
133 r: FpVar<CF1<C>>,
134 ci1: CommittedInstanceVar<C>, // U_i
135 ci2: CommittedInstanceVar<C>, // u_i
136 ) -> Result<CommittedInstanceVar<C>, SynthesisError> {
137 Ok(CommittedInstanceVar {
138 cmE: NonNativeAffineVar::new_constant(ConstraintSystemRef::None, C::zero())?,
139 cmW: NonNativeAffineVar::new_constant(ConstraintSystemRef::None, C::zero())?,
140 // ci3.u = ci1.u + r * ci2.u
141 u: ci1.u + &r * ci2.u,
142 // ci3.x = ci1.x + r * ci2.x
143 x: ci1
144 .x
145 .iter()
146 .zip(ci2.x)
147 .map(|(a, b)| a + &r * &b)
148 .collect::<Vec<FpVar<CF1<C>>>>(),
149 })
150 }
151
152 /// Implements the constraints for NIFS.V for u and x, since cm(E) and cm(W) are delegated to
153 /// the CycleFold circuit.
154 pub fn verify(
155 r: FpVar<CF1<C>>,
156 ci1: CommittedInstanceVar<C>, // U_i
157 ci2: CommittedInstanceVar<C>, // u_i
158 ci3: CommittedInstanceVar<C>, // U_{i+1}
159 ) -> Result<(), SynthesisError> {
160 let ci = Self::fold_committed_instance(r, ci1, ci2)?;
161
162 ci.u.enforce_equal(&ci3.u)?;
163 ci.x.enforce_equal(&ci3.x)?;
164
165 Ok(())
166 }
167}
168
169/// ChallengeGadget computes the RO challenge used for the Nova instances NIFS, it contains a
170/// rust-native and a in-circuit compatible versions.
171pub struct ChallengeGadget<C: CurveGroup, CI: Absorb> {
172 _c: PhantomData<C>,
173 _ci: PhantomData<CI>,
174}
175impl<C: CurveGroup, CI: Absorb> ChallengeGadget<C, CI>
176where
177 C: CurveGroup,
178 <C as CurveGroup>::BaseField: PrimeField,
179 <C as Group>::ScalarField: Absorb,
180{
181 pub fn get_challenge_native<T: Transcript<C::ScalarField>>(
182 transcript: &mut T,
183 pp_hash: C::ScalarField, // public params hash
184 U_i: &CI,
185 u_i: &CI,
186 cmT: Option<&C>,
187 ) -> Vec<bool> {
188 transcript.absorb(&pp_hash);
189 transcript.absorb(&U_i);
190 transcript.absorb(&u_i);
191 // in the Nova case we absorb the cmT, in Ova case we don't since it is not used.
192 if let Some(cmT_value) = cmT {
193 transcript.absorb_nonnative(cmT_value);
194 }
195 transcript.squeeze_bits(NOVA_N_BITS_RO)
196 }
197
198 // compatible with the native get_challenge_native
199 pub fn get_challenge_gadget<S: CryptographicSponge, T: TranscriptVar<CF1<C>, S>>(
200 transcript: &mut T,
201 pp_hash: FpVar<CF1<C>>, // public params hash
202 U_i_vec: Vec<FpVar<CF1<C>>>, // apready processed input, so we don't have to recompute these values
203 u_i: CommittedInstanceVar<C>,
204 cmT: Option<NonNativeAffineVar<C>>,
205 ) -> Result<Vec<Boolean<C::ScalarField>>, SynthesisError> {
206 transcript.absorb(&pp_hash)?;
207 transcript.absorb(&U_i_vec)?;
208 transcript.absorb(&u_i)?;
209 // in the Nova case we absorb the cmT, in Ova case we don't since it is not used.
210 if let Some(cmT_value) = cmT {
211 transcript.absorb_nonnative(&cmT_value)?;
212 }
213 transcript.squeeze_bits(NOVA_N_BITS_RO)
214 }
215}
216
217/// `AugmentedFCircuit` enhances the original step function `F`, so that it can
218/// be used in recursive arguments such as IVC.
219///
220/// The method for converting `F` to `AugmentedFCircuit` (`F'`) is defined in
221/// [Nova](https://eprint.iacr.org/2021/370.pdf), where `AugmentedFCircuit` not
222/// only invokes `F`, but also adds additional constraints for verifying the
223/// correct folding of primary instances (i.e., Nova's `CommittedInstance`s over
224/// `C1`).
225///
226/// Furthermore, to reduce circuit size over `C2`, we implement the constraints
227/// defined in [CycleFold](https://eprint.iacr.org/2023/1192.pdf). These extra
228/// constraints verify the correct folding of CycleFold instances.
229#[derive(Debug, Clone)]
230pub struct AugmentedFCircuit<
231 C1: CurveGroup,
232 C2: CurveGroup,
233 GC2: CurveVar<C2, CF2<C2>>,
234 FC: FCircuit<CF1<C1>>,
235> where
236 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
237{
238 pub(super) _gc2: PhantomData<GC2>,
239 pub(super) poseidon_config: PoseidonConfig<CF1<C1>>,
240 pub(super) pp_hash: Option<CF1<C1>>,
241 pub(super) i: Option<CF1<C1>>,
242 pub(super) i_usize: Option<usize>,
243 pub(super) z_0: Option<Vec<C1::ScalarField>>,
244 pub(super) z_i: Option<Vec<C1::ScalarField>>,
245 pub(super) external_inputs: Option<Vec<C1::ScalarField>>,
246 pub(super) u_i_cmW: Option<C1>,
247 pub(super) U_i: Option<CommittedInstance<C1>>,
248 pub(super) U_i1_cmE: Option<C1>,
249 pub(super) U_i1_cmW: Option<C1>,
250 pub(super) cmT: Option<C1>,
251 pub(super) F: FC, // F circuit
252 pub(super) x: Option<CF1<C1>>, // public input (u_{i+1}.x[0])
253
254 // cyclefold verifier on C1
255 // Here 'cf1, cf2' are for each of the CycleFold circuits, corresponding to the fold of cmW and
256 // cmE respectively
257 pub(super) cf1_u_i_cmW: Option<C2>, // input
258 pub(super) cf2_u_i_cmW: Option<C2>, // input
259 pub(super) cf_U_i: Option<CycleFoldCommittedInstance<C2>>, // input
260 pub(super) cf1_cmT: Option<C2>,
261 pub(super) cf2_cmT: Option<C2>,
262 pub(super) cf_x: Option<CF1<C1>>, // public input (u_{i+1}.x[1])
263}
264
265impl<C1: CurveGroup, C2: CurveGroup, GC2: CurveVar<C2, CF2<C2>>, FC: FCircuit<CF1<C1>>>
266 AugmentedFCircuit<C1, C2, GC2, FC>
267where
268 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
269{
270 pub fn empty(poseidon_config: &PoseidonConfig<CF1<C1>>, F_circuit: FC) -> Self {
271 Self {
272 _gc2: PhantomData,
273 poseidon_config: poseidon_config.clone(),
274 pp_hash: None,
275 i: None,
276 i_usize: None,
277 z_0: None,
278 z_i: None,
279 external_inputs: None,
280 u_i_cmW: None,
281 U_i: None,
282 U_i1_cmE: None,
283 U_i1_cmW: None,
284 cmT: None,
285 F: F_circuit,
286 x: None,
287 // cyclefold values
288 cf1_u_i_cmW: None,
289 cf2_u_i_cmW: None,
290 cf_U_i: None,
291 cf1_cmT: None,
292 cf2_cmT: None,
293 cf_x: None,
294 }
295 }
296}
297
298impl<C1, C2, GC2, FC> ConstraintSynthesizer<CF1<C1>> for AugmentedFCircuit<C1, C2, GC2, FC>
299where
300 C1: CurveGroup,
301 C2: CurveGroup,
302 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
303 FC: FCircuit<CF1<C1>>,
304 <C1 as CurveGroup>::BaseField: PrimeField,
305 <C2 as CurveGroup>::BaseField: PrimeField,
306 <C1 as Group>::ScalarField: Absorb,
307 <C2 as Group>::ScalarField: Absorb,
308 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
309 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
310{
311 fn generate_constraints(self, cs: ConstraintSystemRef<CF1<C1>>) -> Result<(), SynthesisError> {
312 let pp_hash = FpVar::<CF1<C1>>::new_witness(cs.clone(), || {
313 Ok(self.pp_hash.unwrap_or_else(CF1::<C1>::zero))
314 })?;
315 let i = FpVar::<CF1<C1>>::new_witness(cs.clone(), || {
316 Ok(self.i.unwrap_or_else(CF1::<C1>::zero))
317 })?;
318 let z_0 = Vec::<FpVar<CF1<C1>>>::new_witness(cs.clone(), || {
319 Ok(self
320 .z_0
321 .unwrap_or(vec![CF1::<C1>::zero(); self.F.state_len()]))
322 })?;
323 let z_i = Vec::<FpVar<CF1<C1>>>::new_witness(cs.clone(), || {
324 Ok(self
325 .z_i
326 .unwrap_or(vec![CF1::<C1>::zero(); self.F.state_len()]))
327 })?;
328 let external_inputs = Vec::<FpVar<CF1<C1>>>::new_witness(cs.clone(), || {
329 Ok(self
330 .external_inputs
331 .unwrap_or(vec![CF1::<C1>::zero(); self.F.external_inputs_len()]))
332 })?;
333
334 let u_dummy = CommittedInstance::dummy(2);
335 let U_i = CommittedInstanceVar::<C1>::new_witness(cs.clone(), || {
336 Ok(self.U_i.unwrap_or(u_dummy.clone()))
337 })?;
338 let U_i1_cmE = NonNativeAffineVar::new_witness(cs.clone(), || {
339 Ok(self.U_i1_cmE.unwrap_or_else(C1::zero))
340 })?;
341 let U_i1_cmW = NonNativeAffineVar::new_witness(cs.clone(), || {
342 Ok(self.U_i1_cmW.unwrap_or_else(C1::zero))
343 })?;
344
345 let cmT =
346 NonNativeAffineVar::new_witness(cs.clone(), || Ok(self.cmT.unwrap_or_else(C1::zero)))?;
347
348 let cf_u_dummy = CycleFoldCommittedInstance::dummy(NovaCycleFoldConfig::<C1>::IO_LEN);
349 let cf_U_i = CycleFoldCommittedInstanceVar::<C2, GC2>::new_witness(cs.clone(), || {
350 Ok(self.cf_U_i.unwrap_or(cf_u_dummy.clone()))
351 })?;
352 let cf1_cmT = GC2::new_witness(cs.clone(), || Ok(self.cf1_cmT.unwrap_or_else(C2::zero)))?;
353 let cf2_cmT = GC2::new_witness(cs.clone(), || Ok(self.cf2_cmT.unwrap_or_else(C2::zero)))?;
354
355 // `sponge` is for digest computation.
356 let sponge = PoseidonSpongeVar::<C1::ScalarField>::new(cs.clone(), &self.poseidon_config);
357 // `transcript` is for challenge generation.
358 let mut transcript = sponge.clone();
359
360 let is_basecase = i.is_zero()?;
361
362 // Primary Part
363 // P.1. Compute u_i.x
364 // u_i.x[0] = H(i, z_0, z_i, U_i)
365 let (u_i_x, U_i_vec) = U_i.clone().hash(&sponge, &pp_hash, &i, &z_0, &z_i)?;
366 // u_i.x[1] = H(cf_U_i)
367 let (cf_u_i_x, cf_U_i_vec) = cf_U_i.clone().hash(&sponge, pp_hash.clone())?;
368
369 // P.2. Construct u_i
370 let u_i = CommittedInstanceVar {
371 // u_i.cmE = cm(0)
372 cmE: NonNativeAffineVar::new_constant(cs.clone(), C1::zero())?,
373 // u_i.u = 1
374 u: FpVar::one(),
375 // u_i.cmW is provided by the prover as witness
376 cmW: NonNativeAffineVar::new_witness(cs.clone(), || {
377 Ok(self.u_i_cmW.unwrap_or(C1::zero()))
378 })?,
379 // u_i.x is computed in step 1
380 x: vec![u_i_x, cf_u_i_x],
381 };
382
383 // P.3. nifs.verify, obtains U_{i+1} by folding u_i & U_i .
384
385 // compute r = H(u_i, U_i, cmT)
386 let r_bits = ChallengeGadget::<C1, CommittedInstance<C1>>::get_challenge_gadget(
387 &mut transcript,
388 pp_hash.clone(),
389 U_i_vec,
390 u_i.clone(),
391 Some(cmT.clone()),
392 )?;
393 let r = Boolean::le_bits_to_fp_var(&r_bits)?;
394 // Also convert r_bits to a `NonNativeFieldVar`
395 let r_nonnat = {
396 let mut bits = r_bits;
397 bits.resize(C1::BaseField::MODULUS_BIT_SIZE as usize, Boolean::FALSE);
398 NonNativeUintVar::from(&bits)
399 };
400
401 // Notice that NIFSGadget::fold_committed_instance does not fold cmE & cmW.
402 // We set `U_i1.cmE` and `U_i1.cmW` to unconstrained witnesses `U_i1_cmE` and `U_i1_cmW`
403 // respectively.
404 // The correctness of them will be checked on the other curve.
405 let mut U_i1 = NIFSGadget::<C1>::fold_committed_instance(r, U_i.clone(), u_i.clone())?;
406 U_i1.cmE = U_i1_cmE;
407 U_i1.cmW = U_i1_cmW;
408
409 // P.4.a compute and check the first output of F'
410
411 // get z_{i+1} from the F circuit
412 let i_usize = self.i_usize.unwrap_or(0);
413 let z_i1 = self
414 .F
415 .generate_step_constraints(cs.clone(), i_usize, z_i, external_inputs)?;
416
417 // Base case: u_{i+1}.x[0] == H((i+1, z_0, z_{i+1}, U_{\bot})
418 // Non-base case: u_{i+1}.x[0] == H((i+1, z_0, z_{i+1}, U_{i+1})
419 let (u_i1_x, _) = U_i1.clone().hash(
420 &sponge,
421 &pp_hash,
422 &(i + FpVar::<CF1<C1>>::one()),
423 &z_0,
424 &z_i1,
425 )?;
426 let (u_i1_x_base, _) = CommittedInstanceVar::new_constant(cs.clone(), u_dummy)?.hash(
427 &sponge,
428 &pp_hash,
429 &FpVar::<CF1<C1>>::one(),
430 &z_0,
431 &z_i1,
432 )?;
433 let x = FpVar::new_input(cs.clone(), || Ok(self.x.unwrap_or(u_i1_x_base.value()?)))?;
434 x.enforce_equal(&is_basecase.select(&u_i1_x_base, &u_i1_x)?)?;
435
436 // CycleFold part
437 // C.1. Compute cf1_u_i.x and cf2_u_i.x
438 let cfW_x = vec![
439 r_nonnat.clone(),
440 U_i.cmW.x,
441 U_i.cmW.y,
442 u_i.cmW.x,
443 u_i.cmW.y,
444 U_i1.cmW.x,
445 U_i1.cmW.y,
446 ];
447 let cfE_x = vec![
448 r_nonnat, U_i.cmE.x, U_i.cmE.y, cmT.x, cmT.y, U_i1.cmE.x, U_i1.cmE.y,
449 ];
450
451 // ensure that cf1_u & cf2_u have as public inputs the cmW & cmE from main instances U_i,
452 // u_i, U_i+1 coordinates of the commitments
453 // C.2. Construct `cf1_u_i` and `cf2_u_i`
454 let cf1_u_i = CycleFoldCommittedInstanceVar {
455 // cf1_u_i.cmE = 0
456 cmE: GC2::zero(),
457 // cf1_u_i.u = 1
458 u: NonNativeUintVar::new_constant(cs.clone(), C1::BaseField::one())?,
459 // cf1_u_i.cmW is provided by the prover as witness
460 cmW: GC2::new_witness(cs.clone(), || Ok(self.cf1_u_i_cmW.unwrap_or(C2::zero())))?,
461 // cf1_u_i.x is computed in step 1
462 x: cfW_x,
463 };
464 let cf2_u_i = CycleFoldCommittedInstanceVar {
465 // cf2_u_i.cmE = 0
466 cmE: GC2::zero(),
467 // cf2_u_i.u = 1
468 u: NonNativeUintVar::new_constant(cs.clone(), C1::BaseField::one())?,
469 // cf2_u_i.cmW is provided by the prover as witness
470 cmW: GC2::new_witness(cs.clone(), || Ok(self.cf2_u_i_cmW.unwrap_or(C2::zero())))?,
471 // cf2_u_i.x is computed in step 1
472 x: cfE_x,
473 };
474
475 // C.3. nifs.verify, obtains cf1_U_{i+1} by folding cf1_u_i & cf_U_i, and then cf_U_{i+1}
476 // by folding cf2_u_i & cf1_U_{i+1}.
477
478 // compute cf1_r = H(cf1_u_i, cf_U_i, cf1_cmT)
479 // cf_r_bits is denoted by rho* in the paper.
480 let cf1_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_gadget(
481 &mut transcript,
482 pp_hash.clone(),
483 cf_U_i_vec,
484 cf1_u_i.clone(),
485 cf1_cmT.clone(),
486 )?;
487 // Fold cf1_u_i & cf_U_i into cf1_U_{i+1}
488 let cf1_U_i1 = NIFSFullGadget::<C2, GC2>::fold_committed_instance(
489 cf1_r_bits, cf1_cmT, cf_U_i, cf1_u_i,
490 )?;
491
492 // same for cf2_r:
493 let cf2_r_bits = CycleFoldChallengeGadget::<C2, GC2>::get_challenge_gadget(
494 &mut transcript,
495 pp_hash.clone(),
496 cf1_U_i1.to_native_sponge_field_elements()?,
497 cf2_u_i.clone(),
498 cf2_cmT.clone(),
499 )?;
500 let cf_U_i1 = NIFSFullGadget::<C2, GC2>::fold_committed_instance(
501 cf2_r_bits, cf2_cmT, cf1_U_i1, // the output from NIFS.V(cf1_r, cf_U, cfE_u)
502 cf2_u_i,
503 )?;
504
505 // Back to Primary Part
506 // P.4.b compute and check the second output of F'
507 // Base case: u_{i+1}.x[1] == H(cf_U_{\bot})
508 // Non-base case: u_{i+1}.x[1] == H(cf_U_{i+1})
509 let (cf_u_i1_x, _) = cf_U_i1.clone().hash(&sponge, pp_hash.clone())?;
510 let (cf_u_i1_x_base, _) =
511 CycleFoldCommittedInstanceVar::new_constant(cs.clone(), cf_u_dummy)?
512 .hash(&sponge, pp_hash)?;
513 let cf_x = FpVar::new_input(cs.clone(), || {
514 Ok(self.cf_x.unwrap_or(cf_u_i1_x_base.value()?))
515 })?;
516 cf_x.enforce_equal(&is_basecase.select(&cf_u_i1_x_base, &cf_u_i1_x)?)?;
517
518 Ok(())
519 }
520}
521
522#[cfg(test)]
523pub mod tests {
524 use super::*;
525 use ark_bn254::{Fr, G1Projective as Projective};
526 use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
527 use ark_ff::BigInteger;
528 use ark_relations::r1cs::ConstraintSystem;
529 use ark_std::UniformRand;
530
531 use crate::commitment::pedersen::Pedersen;
532 use crate::folding::nova::nifs::{nova::NIFS, NIFSTrait};
533 use crate::folding::traits::CommittedInstanceOps;
534 use crate::transcript::poseidon::poseidon_canonical_config;
535
536 #[test]
537 fn test_committed_instance_var() {
538 let mut rng = ark_std::test_rng();
539
540 let ci = CommittedInstance::<Projective> {
541 cmE: Projective::rand(&mut rng),
542 u: Fr::rand(&mut rng),
543 cmW: Projective::rand(&mut rng),
544 x: vec![Fr::rand(&mut rng); 1],
545 };
546
547 let cs = ConstraintSystem::<Fr>::new_ref();
548 let ciVar =
549 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(ci.clone())).unwrap();
550 assert_eq!(ciVar.u.value().unwrap(), ci.u);
551 assert_eq!(ciVar.x.value().unwrap(), ci.x);
552 // the values cmE and cmW are checked in the CycleFold's circuit
553 // CommittedInstanceInCycleFoldVar in
554 // cyclefold::tests::test_committed_instance_cyclefold_var
555 }
556
557 #[test]
558 fn test_nifs_gadget() {
559 let mut rng = ark_std::test_rng();
560
561 // prepare the committed instances to test in-circuit
562 let ci: Vec<CommittedInstance<Projective>> = (0..2)
563 .into_iter()
564 .map(|_| CommittedInstance::<Projective> {
565 cmE: Projective::rand(&mut rng),
566 u: Fr::rand(&mut rng),
567 cmW: Projective::rand(&mut rng),
568 x: vec![Fr::rand(&mut rng); 1],
569 })
570 .collect();
571 let (ci1, ci2) = (ci[0].clone(), ci[1].clone());
572 let pp_hash = Fr::rand(&mut rng);
573 let cmT = Projective::rand(&mut rng);
574 let poseidon_config = poseidon_canonical_config::<Fr>();
575 let mut transcript = PoseidonSponge::<Fr>::new(&poseidon_config);
576 let (ci3, r_bits) = NIFS::<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>::verify(
577 &mut transcript,
578 pp_hash,
579 &ci1,
580 &ci2,
581 &cmT,
582 )
583 .unwrap();
584 let r_Fr = Fr::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
585
586 let cs = ConstraintSystem::<Fr>::new_ref();
587
588 let rVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(r_Fr)).unwrap();
589 let ci1Var =
590 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(ci1.clone()))
591 .unwrap();
592 let ci2Var =
593 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(ci2.clone()))
594 .unwrap();
595 let ci3Var =
596 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(ci3.clone()))
597 .unwrap();
598
599 NIFSGadget::<Projective>::verify(
600 rVar.clone(),
601 ci1Var.clone(),
602 ci2Var.clone(),
603 ci3Var.clone(),
604 )
605 .unwrap();
606 assert!(cs.is_satisfied().unwrap());
607 }
608
609 /// test that checks the native CommittedInstance.to_sponge_{bytes,field_elements}
610 /// vs the R1CS constraints version
611 #[test]
612 pub fn test_committed_instance_to_sponge_preimage() {
613 let mut rng = ark_std::test_rng();
614
615 let ci = CommittedInstance::<Projective> {
616 cmE: Projective::rand(&mut rng),
617 u: Fr::rand(&mut rng),
618 cmW: Projective::rand(&mut rng),
619 x: vec![Fr::rand(&mut rng); 1],
620 };
621
622 let bytes = ci.to_sponge_bytes_as_vec();
623 let field_elements = ci.to_sponge_field_elements_as_vec();
624
625 let cs = ConstraintSystem::<Fr>::new_ref();
626
627 let ciVar =
628 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(ci.clone())).unwrap();
629 let bytes_var = ciVar.to_sponge_bytes().unwrap();
630 let field_elements_var = ciVar.to_sponge_field_elements().unwrap();
631
632 assert!(cs.is_satisfied().unwrap());
633
634 // check that the natively computed and in-circuit computed hashes match
635 assert_eq!(bytes_var.value().unwrap(), bytes);
636 assert_eq!(field_elements_var.value().unwrap(), field_elements);
637 }
638
639 #[test]
640 fn test_committed_instance_hash() {
641 let mut rng = ark_std::test_rng();
642 let poseidon_config = poseidon_canonical_config::<Fr>();
643 let sponge = PoseidonSponge::<Fr>::new(&poseidon_config);
644 let pp_hash = Fr::from(42u32); // only for test
645
646 let i = Fr::from(3_u32);
647 let z_0 = vec![Fr::from(3_u32)];
648 let z_i = vec![Fr::from(3_u32)];
649 let ci = CommittedInstance::<Projective> {
650 cmE: Projective::rand(&mut rng),
651 u: Fr::rand(&mut rng),
652 cmW: Projective::rand(&mut rng),
653 x: vec![Fr::rand(&mut rng); 1],
654 };
655
656 // compute the CommittedInstance hash natively
657 let h = ci.hash(&sponge, pp_hash, i, &z_0, &z_i);
658
659 let cs = ConstraintSystem::<Fr>::new_ref();
660
661 let pp_hashVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
662 let iVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(i)).unwrap();
663 let z_0Var = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_0.clone())).unwrap();
664 let z_iVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_i.clone())).unwrap();
665 let ciVar =
666 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(ci.clone())).unwrap();
667
668 let sponge = PoseidonSpongeVar::<Fr>::new(cs.clone(), &poseidon_config);
669
670 // compute the CommittedInstance hash in-circuit
671 let (hVar, _) = ciVar
672 .hash(&sponge, &pp_hashVar, &iVar, &z_0Var, &z_iVar)
673 .unwrap();
674 assert!(cs.is_satisfied().unwrap());
675
676 // check that the natively computed and in-circuit computed hashes match
677 assert_eq!(hVar.value().unwrap(), h);
678 }
679
680 // checks that the gadget and native implementations of the challenge computation match
681 #[test]
682 fn test_challenge_gadget() {
683 let mut rng = ark_std::test_rng();
684 let poseidon_config = poseidon_canonical_config::<Fr>();
685 let mut transcript = PoseidonSponge::<Fr>::new(&poseidon_config);
686
687 let u_i = CommittedInstance::<Projective> {
688 cmE: Projective::rand(&mut rng),
689 u: Fr::rand(&mut rng),
690 cmW: Projective::rand(&mut rng),
691 x: vec![Fr::rand(&mut rng); 1],
692 };
693 let U_i = CommittedInstance::<Projective> {
694 cmE: Projective::rand(&mut rng),
695 u: Fr::rand(&mut rng),
696 cmW: Projective::rand(&mut rng),
697 x: vec![Fr::rand(&mut rng); 1],
698 };
699 let cmT = Projective::rand(&mut rng);
700
701 let pp_hash = Fr::from(42u32); // only for testing
702
703 // compute the challenge natively
704 let r_bits =
705 ChallengeGadget::<Projective, CommittedInstance<Projective>>::get_challenge_native(
706 &mut transcript,
707 pp_hash,
708 &U_i,
709 &u_i,
710 Some(&cmT),
711 );
712 let r = Fr::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
713
714 let cs = ConstraintSystem::<Fr>::new_ref();
715 let pp_hashVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
716 let u_iVar =
717 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(u_i.clone()))
718 .unwrap();
719 let U_iVar =
720 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(U_i.clone()))
721 .unwrap();
722 let cmTVar = NonNativeAffineVar::<Projective>::new_witness(cs.clone(), || Ok(cmT)).unwrap();
723 let mut transcriptVar = PoseidonSpongeVar::<Fr>::new(cs.clone(), &poseidon_config);
724
725 // compute the challenge in-circuit
726 let U_iVar_vec = [
727 vec![U_iVar.u.clone()],
728 U_iVar.x.clone(),
729 U_iVar.cmE.to_constraint_field().unwrap(),
730 U_iVar.cmW.to_constraint_field().unwrap(),
731 ]
732 .concat();
733 let r_bitsVar =
734 ChallengeGadget::<Projective, CommittedInstance<Projective>>::get_challenge_gadget(
735 &mut transcriptVar,
736 pp_hashVar,
737 U_iVar_vec,
738 u_iVar,
739 Some(cmTVar),
740 )
741 .unwrap();
742 assert!(cs.is_satisfied().unwrap());
743
744 // check that the natively computed and in-circuit computed hashes match
745 let rVar = Boolean::le_bits_to_fp_var(&r_bitsVar).unwrap();
746 assert_eq!(rVar.value().unwrap(), r);
747 assert_eq!(r_bitsVar.value().unwrap(), r_bits);
748 }
749}