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