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