sonobe/folding-schemes/src/folding/nova/decider_eth_circuit.rs
folding-schemes/src/folding/nova/decider_eth_circuit.rsRaw
1/// This file implements the onchain (Ethereum's EVM) decider circuit. For non-ethereum use cases,
2/// other more efficient approaches can be used.
3use ark_crypto_primitives::crh::poseidon::constraints::CRHParametersVar;
4use ark_crypto_primitives::sponge::{poseidon::PoseidonConfig, Absorb};
5use ark_ec::{CurveGroup, Group};
6use ark_ff::PrimeField;
7use ark_r1cs_std::{
8 alloc::{AllocVar, AllocationMode},
9 boolean::Boolean,
10 eq::EqGadget,
11 fields::{fp::FpVar, nonnative::NonNativeFieldVar, FieldVar},
12 groups::GroupOpsBounds,
13 prelude::CurveVar,
14 ToConstraintFieldGadget,
15};
16use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, Namespace, SynthesisError};
17use ark_std::{One, Zero};
18use core::{borrow::Borrow, marker::PhantomData};
19
20use crate::ccs::r1cs::R1CS;
21use crate::commitment::{pedersen::Params as PedersenParams, CommitmentProver};
22use crate::folding::nova::{
23 circuits::{CommittedInstanceVar, CF1, CF2},
24 CommittedInstance, Nova, Witness,
25};
26use crate::frontend::FCircuit;
27use crate::utils::gadgets::{
28 hadamard, mat_vec_mul_sparse, vec_add, vec_scalar_mul, SparseMatrixVar,
29};
30
31#[derive(Debug, Clone)]
32pub struct RelaxedR1CSGadget<F: PrimeField, CF: PrimeField, FV: FieldVar<F, CF>> {
33 _f: PhantomData<F>,
34 _cf: PhantomData<CF>,
35 _fv: PhantomData<FV>,
36}
37impl<F: PrimeField, CF: PrimeField, FV: FieldVar<F, CF>> RelaxedR1CSGadget<F, CF, FV> {
38 /// performs the RelaxedR1CS check (Az∘Bz==uCz+E)
39 pub fn check(
40 r1cs: R1CSVar<F, CF, FV>,
41 E: Vec<FV>,
42 u: FV,
43 z: Vec<FV>,
44 ) -> Result<(), SynthesisError> {
45 let Az = mat_vec_mul_sparse(r1cs.A, z.clone());
46 let Bz = mat_vec_mul_sparse(r1cs.B, z.clone());
47 let Cz = mat_vec_mul_sparse(r1cs.C, z.clone());
48 let uCz = vec_scalar_mul(&Cz, &u);
49 let uCzE = vec_add(&uCz, &E)?;
50 let AzBz = hadamard(&Az, &Bz)?;
51 for i in 0..AzBz.len() {
52 AzBz[i].enforce_equal(&uCzE[i].clone())?;
53 }
54 Ok(())
55 }
56}
57
58#[derive(Debug, Clone)]
59pub struct R1CSVar<F: PrimeField, CF: PrimeField, FV: FieldVar<F, CF>> {
60 _f: PhantomData<F>,
61 _cf: PhantomData<CF>,
62 _fv: PhantomData<FV>,
63 pub A: SparseMatrixVar<F, CF, FV>,
64 pub B: SparseMatrixVar<F, CF, FV>,
65 pub C: SparseMatrixVar<F, CF, FV>,
66}
67
68impl<F, CF, FV> AllocVar<R1CS<F>, CF> for R1CSVar<F, CF, FV>
69where
70 F: PrimeField,
71 CF: PrimeField,
72 FV: FieldVar<F, CF>,
73{
74 fn new_variable<T: Borrow<R1CS<F>>>(
75 cs: impl Into<Namespace<CF>>,
76 f: impl FnOnce() -> Result<T, SynthesisError>,
77 _mode: AllocationMode,
78 ) -> Result<Self, SynthesisError> {
79 f().and_then(|val| {
80 let cs = cs.into();
81
82 let A = SparseMatrixVar::<F, CF, FV>::new_constant(cs.clone(), &val.borrow().A)?;
83 let B = SparseMatrixVar::<F, CF, FV>::new_constant(cs.clone(), &val.borrow().B)?;
84 let C = SparseMatrixVar::<F, CF, FV>::new_constant(cs.clone(), &val.borrow().C)?;
85
86 Ok(Self {
87 _f: PhantomData,
88 _cf: PhantomData,
89 _fv: PhantomData,
90 A,
91 B,
92 C,
93 })
94 })
95 }
96}
97
98/// In-circuit representation of the Witness associated to the CommittedInstance.
99#[derive(Debug, Clone)]
100pub struct WitnessVar<C: CurveGroup> {
101 pub E: Vec<FpVar<C::ScalarField>>,
102 pub rE: FpVar<C::ScalarField>,
103 pub W: Vec<FpVar<C::ScalarField>>,
104 pub rW: FpVar<C::ScalarField>,
105}
106
107impl<C> AllocVar<Witness<C>, CF1<C>> for WitnessVar<C>
108where
109 C: CurveGroup,
110 <C as ark_ec::CurveGroup>::BaseField: PrimeField,
111{
112 fn new_variable<T: Borrow<Witness<C>>>(
113 cs: impl Into<Namespace<CF1<C>>>,
114 f: impl FnOnce() -> Result<T, SynthesisError>,
115 mode: AllocationMode,
116 ) -> Result<Self, SynthesisError> {
117 f().and_then(|val| {
118 let cs = cs.into();
119
120 let E: Vec<FpVar<C::ScalarField>> =
121 Vec::new_variable(cs.clone(), || Ok(val.borrow().E.clone()), mode)?;
122 let rE =
123 FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().rE), mode)?;
124
125 let W: Vec<FpVar<C::ScalarField>> =
126 Vec::new_variable(cs.clone(), || Ok(val.borrow().W.clone()), mode)?;
127 let rW =
128 FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().rW), mode)?;
129
130 Ok(Self { E, rE, W, rW })
131 })
132 }
133}
134
135/// In-circuit representation of the Witness associated to the CommittedInstance, but with
136/// non-native representation, since it is used to represent the CycleFold witness.
137#[derive(Debug, Clone)]
138pub struct CycleFoldWitnessVar<C: CurveGroup> {
139 pub E: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>,
140 pub rE: NonNativeFieldVar<C::ScalarField, CF2<C>>,
141 pub W: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>,
142 pub rW: NonNativeFieldVar<C::ScalarField, CF2<C>>,
143}
144
145impl<C> AllocVar<Witness<C>, CF2<C>> for CycleFoldWitnessVar<C>
146where
147 C: CurveGroup,
148 <C as ark_ec::CurveGroup>::BaseField: PrimeField,
149{
150 fn new_variable<T: Borrow<Witness<C>>>(
151 cs: impl Into<Namespace<CF2<C>>>,
152 f: impl FnOnce() -> Result<T, SynthesisError>,
153 mode: AllocationMode,
154 ) -> Result<Self, SynthesisError> {
155 f().and_then(|val| {
156 let cs = cs.into();
157
158 let E: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>> =
159 Vec::new_variable(cs.clone(), || Ok(val.borrow().E.clone()), mode)?;
160 let rE = NonNativeFieldVar::<C::ScalarField, CF2<C>>::new_variable(
161 cs.clone(),
162 || Ok(val.borrow().rE),
163 mode,
164 )?;
165
166 let W: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>> =
167 Vec::new_variable(cs.clone(), || Ok(val.borrow().W.clone()), mode)?;
168 let rW = NonNativeFieldVar::<C::ScalarField, CF2<C>>::new_variable(
169 cs.clone(),
170 || Ok(val.borrow().rW),
171 mode,
172 )?;
173
174 Ok(Self { E, rE, W, rW })
175 })
176 }
177}
178
179/// Circuit that implements the in-circuit checks needed for the onchain (Ethereum's EVM)
180/// verification.
181#[derive(Clone, Debug)]
182pub struct DeciderEthCircuit<C1, GC1, C2, GC2, CP1, CP2>
183where
184 C1: CurveGroup,
185 GC1: CurveVar<C1, CF2<C1>>,
186 C2: CurveGroup,
187 GC2: CurveVar<C2, CF2<C2>>,
188 CP1: CommitmentProver<C1>,
189 CP2: CommitmentProver<C2>,
190{
191 _c1: PhantomData<C1>,
192 _gc1: PhantomData<GC1>,
193 _c2: PhantomData<C2>,
194 _gc2: PhantomData<GC2>,
195 _cp1: PhantomData<CP1>,
196 _cp2: PhantomData<CP2>,
197
198 /// E vector's length of the Nova instance witness
199 pub E_len: usize,
200 /// E vector's length of the CycleFold instance witness
201 pub cf_E_len: usize,
202 /// R1CS of the Augmented Function circuit
203 pub r1cs: R1CS<C1::ScalarField>,
204 /// R1CS of the CycleFold circuit
205 pub cf_r1cs: R1CS<C2::ScalarField>,
206 /// CycleFold PedersenParams over C2
207 pub cf_pedersen_params: PedersenParams<C2>,
208 pub poseidon_config: PoseidonConfig<CF1<C1>>,
209 pub i: Option<CF1<C1>>,
210 /// initial state
211 pub z_0: Option<Vec<C1::ScalarField>>,
212 /// current i-th state
213 pub z_i: Option<Vec<C1::ScalarField>>,
214 /// Nova instances
215 pub u_i: Option<CommittedInstance<C1>>,
216 pub w_i: Option<Witness<C1>>,
217 pub U_i: Option<CommittedInstance<C1>>,
218 pub W_i: Option<Witness<C1>>,
219 /// CycleFold running instance
220 pub cf_U_i: Option<CommittedInstance<C2>>,
221 pub cf_W_i: Option<Witness<C2>>,
222}
223impl<C1, GC1, C2, GC2, CP1, CP2> DeciderEthCircuit<C1, GC1, C2, GC2, CP1, CP2>
224where
225 C1: CurveGroup,
226 C2: CurveGroup,
227 GC1: CurveVar<C1, CF2<C1>>,
228 GC2: CurveVar<C2, CF2<C2>>,
229 CP1: CommitmentProver<C1>,
230 // enforce that the CP2 is Pedersen commitment, since we're at Ethereum's EVM decider
231 CP2: CommitmentProver<C2, Params = PedersenParams<C2>>,
232{
233 pub fn from_nova<FC: FCircuit<C1::ScalarField>>(
234 nova: Nova<C1, GC1, C2, GC2, FC, CP1, CP2>,
235 ) -> Self {
236 Self {
237 _c1: PhantomData,
238 _gc1: PhantomData,
239 _c2: PhantomData,
240 _gc2: PhantomData,
241 _cp1: PhantomData,
242 _cp2: PhantomData,
243
244 E_len: nova.W_i.E.len(),
245 cf_E_len: nova.cf_W_i.E.len(),
246 r1cs: nova.r1cs,
247 cf_r1cs: nova.cf_r1cs,
248 cf_pedersen_params: nova.cf_cm_params,
249 poseidon_config: nova.poseidon_config,
250 i: Some(nova.i),
251 z_0: Some(nova.z_0),
252 z_i: Some(nova.z_i),
253 u_i: Some(nova.u_i),
254 w_i: Some(nova.w_i),
255 U_i: Some(nova.U_i),
256 W_i: Some(nova.W_i),
257 cf_U_i: Some(nova.cf_U_i),
258 cf_W_i: Some(nova.cf_W_i),
259 }
260 }
261}
262
263impl<C1, GC1, C2, GC2, CP1, CP2> ConstraintSynthesizer<CF1<C1>>
264 for DeciderEthCircuit<C1, GC1, C2, GC2, CP1, CP2>
265where
266 C1: CurveGroup,
267 C2: CurveGroup,
268 GC1: CurveVar<C1, CF2<C1>>,
269 GC2: CurveVar<C2, CF2<C2>>,
270 CP1: CommitmentProver<C1>,
271 CP2: CommitmentProver<C2>,
272 <C1 as CurveGroup>::BaseField: PrimeField,
273 <C2 as CurveGroup>::BaseField: PrimeField,
274 <C1 as Group>::ScalarField: Absorb,
275 <C2 as Group>::ScalarField: Absorb,
276 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
277 for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
278{
279 fn generate_constraints(self, cs: ConstraintSystemRef<CF1<C1>>) -> Result<(), SynthesisError> {
280 let r1cs =
281 R1CSVar::<C1::ScalarField, CF1<C1>, FpVar<CF1<C1>>>::new_witness(cs.clone(), || {
282 Ok(self.r1cs.clone())
283 })?;
284
285 let i =
286 FpVar::<CF1<C1>>::new_input(cs.clone(), || Ok(self.i.unwrap_or_else(CF1::<C1>::zero)))?;
287 let z_0 = Vec::<FpVar<CF1<C1>>>::new_input(cs.clone(), || {
288 Ok(self.z_0.unwrap_or(vec![CF1::<C1>::zero()]))
289 })?;
290 let z_i = Vec::<FpVar<CF1<C1>>>::new_input(cs.clone(), || {
291 Ok(self.z_i.unwrap_or(vec![CF1::<C1>::zero()]))
292 })?;
293
294 let u_dummy_native = CommittedInstance::<C1>::dummy(1);
295 let w_dummy_native = Witness::<C1>::new(
296 vec![C1::ScalarField::zero(); self.r1cs.A.n_cols - 2 /* (2=1+1, since u_i.x.len=1) */],
297 self.E_len,
298 );
299
300 let u_i = CommittedInstanceVar::<C1>::new_witness(cs.clone(), || {
301 Ok(self.u_i.unwrap_or(u_dummy_native.clone()))
302 })?;
303 let w_i = WitnessVar::<C1>::new_witness(cs.clone(), || {
304 Ok(self.w_i.unwrap_or(w_dummy_native.clone()))
305 })?;
306 let U_i = CommittedInstanceVar::<C1>::new_input(cs.clone(), || {
307 Ok(self.U_i.unwrap_or(u_dummy_native.clone()))
308 })?;
309 let W_i = WitnessVar::<C1>::new_witness(cs.clone(), || {
310 Ok(self.W_i.unwrap_or(w_dummy_native.clone()))
311 })?;
312
313 let crh_params = CRHParametersVar::<C1::ScalarField>::new_constant(
314 cs.clone(),
315 self.poseidon_config.clone(),
316 )?;
317
318 // 1. check RelaxedR1CS of u_i
319 let z_u: Vec<FpVar<CF1<C1>>> = [
320 vec![FpVar::<CF1<C1>>::one()],
321 u_i.x.to_vec(),
322 w_i.W.to_vec(),
323 ]
324 .concat();
325 RelaxedR1CSGadget::<C1::ScalarField, CF1<C1>, FpVar<CF1<C1>>>::check(
326 r1cs.clone(),
327 w_i.E,
328 u_i.u.clone(),
329 z_u,
330 )?;
331
332 // 2. check RelaxedR1CS of U_i
333 let z_U: Vec<FpVar<CF1<C1>>> =
334 [vec![U_i.u.clone()], U_i.x.to_vec(), W_i.W.to_vec()].concat();
335 RelaxedR1CSGadget::<C1::ScalarField, CF1<C1>, FpVar<CF1<C1>>>::check(
336 r1cs,
337 W_i.E,
338 U_i.u.clone(),
339 z_U,
340 )?;
341
342 // 3. u_i.cmE==cm(0), u_i.u==1
343 // Here zero_x & zero_y are the x & y coordinates of the zero point affine representation.
344 let zero_x = NonNativeFieldVar::<C1::BaseField, C1::ScalarField>::new_constant(
345 cs.clone(),
346 C1::BaseField::zero(),
347 )?
348 .to_constraint_field()?;
349 let zero_y = NonNativeFieldVar::<C1::BaseField, C1::ScalarField>::new_constant(
350 cs.clone(),
351 C1::BaseField::one(),
352 )?
353 .to_constraint_field()?;
354 (u_i.cmE.x.is_eq(&zero_x)?).enforce_equal(&Boolean::TRUE)?;
355 (u_i.cmE.y.is_eq(&zero_y)?).enforce_equal(&Boolean::TRUE)?;
356 (u_i.u.is_one()?).enforce_equal(&Boolean::TRUE)?;
357
358 // 4. u_i.x == H(i, z_0, z_i, U_i)
359 let u_i_x = U_i
360 .clone()
361 .hash(&crh_params, i.clone(), z_0.clone(), z_i.clone())?;
362 (u_i.x[0]).enforce_equal(&u_i_x)?;
363
364 // The following two checks (and their respective allocations) are disabled for normal
365 // tests since they take ~24.5M constraints and would take several minutes (and RAM) to run
366 // the test
367 #[cfg(not(test))]
368 {
369 // imports here instead of at the top of the file, so we avoid having multiple
370 // `#[cfg(not(test))]`
371 use crate::commitment::pedersen::PedersenGadget;
372 use crate::folding::nova::cyclefold::{CycleFoldCommittedInstanceVar, CF_IO_LEN};
373
374 let cf_u_dummy_native = CommittedInstance::<C2>::dummy(CF_IO_LEN);
375 let w_dummy_native = Witness::<C2>::new(
376 vec![C2::ScalarField::zero(); self.cf_r1cs.A.n_cols - 1 - self.cf_r1cs.l],
377 self.cf_E_len,
378 );
379 let cf_U_i = CycleFoldCommittedInstanceVar::<C2, GC2>::new_witness(cs.clone(), || {
380 Ok(self.cf_U_i.unwrap_or_else(|| cf_u_dummy_native.clone()))
381 })?;
382 let cf_W_i = CycleFoldWitnessVar::<C2>::new_witness(cs.clone(), || {
383 Ok(self.cf_W_i.unwrap_or(w_dummy_native.clone()))
384 })?;
385
386 // 5. check Pedersen commitments of cf_U_i.{cmE, cmW}
387 let H = GC2::new_constant(cs.clone(), self.cf_pedersen_params.h)?;
388 let G = Vec::<GC2>::new_constant(cs.clone(), self.cf_pedersen_params.generators)?;
389
390 let computed_cmE = PedersenGadget::<C2, GC2>::commit(
391 H.clone(),
392 G.clone(),
393 cf_W_i.E.clone(),
394 cf_W_i.rE,
395 )?;
396 cf_U_i.cmE.enforce_equal(&computed_cmE)?;
397 let computed_cmW =
398 PedersenGadget::<C2, GC2>::commit(H, G, cf_W_i.W.clone(), cf_W_i.rW)?;
399 cf_U_i.cmW.enforce_equal(&computed_cmW)?;
400
401 let cf_r1cs = R1CSVar::<
402 C1::BaseField,
403 CF1<C1>,
404 NonNativeFieldVar<C1::BaseField, CF1<C1>>,
405 >::new_witness(cs.clone(), || Ok(self.cf_r1cs.clone()))?;
406
407 // 6. check RelaxedR1CS of cf_U_i
408 let cf_z_U: Vec<NonNativeFieldVar<C2::ScalarField, CF1<C1>>> =
409 [vec![cf_U_i.u.clone()], cf_U_i.x.to_vec(), cf_W_i.W.to_vec()].concat();
410 RelaxedR1CSGadget::<
411 C2::ScalarField,
412 CF1<C1>,
413 NonNativeFieldVar<C2::ScalarField, CF1<C1>>,
414 >::check(cf_r1cs, cf_W_i.E, cf_U_i.u.clone(), cf_z_U)?;
415 }
416
417 Ok(())
418 }
419}
420
421#[cfg(test)]
422pub mod tests {
423 use super::*;
424 use ark_crypto_primitives::crh::{
425 sha256::{
426 constraints::{Sha256Gadget, UnitVar},
427 Sha256,
428 },
429 CRHScheme, CRHSchemeGadget,
430 };
431 use ark_ff::BigInteger;
432 use ark_pallas::{constraints::GVar, Fq, Fr, Projective};
433 use ark_r1cs_std::{
434 alloc::AllocVar,
435 bits::uint8::UInt8,
436 eq::EqGadget,
437 fields::{fp::FpVar, nonnative::NonNativeFieldVar},
438 };
439 use ark_relations::r1cs::ConstraintSystem;
440 use ark_vesta::{constraints::GVar as GVar2, Projective as Projective2};
441
442 use crate::commitment::pedersen::Pedersen;
443 use crate::folding::nova::{get_pedersen_params_len, ProverParams, VerifierParams};
444 use crate::frontend::tests::{CubicFCircuit, CustomFCircuit, WrapperCircuit};
445 use crate::transcript::poseidon::poseidon_test_config;
446 use crate::FoldingScheme;
447
448 use crate::ccs::r1cs::{extract_r1cs, extract_w_x};
449 use crate::ccs::r1cs::{
450 tests::{get_test_r1cs, get_test_z},
451 R1CS,
452 };
453
454 #[test]
455 fn test_relaxed_r1cs_small_gadget_handcrafted() {
456 let r1cs: R1CS<Fr> = get_test_r1cs();
457 let rel_r1cs = r1cs.clone().relax();
458 let z = get_test_z(3);
459
460 let cs = ConstraintSystem::<Fr>::new_ref();
461
462 let zVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
463 let EVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(rel_r1cs.E)).unwrap();
464 let uVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(rel_r1cs.u)).unwrap();
465 let r1csVar = R1CSVar::<Fr, Fr, FpVar<Fr>>::new_witness(cs.clone(), || Ok(r1cs)).unwrap();
466
467 RelaxedR1CSGadget::<Fr, Fr, FpVar<Fr>>::check(r1csVar, EVar, uVar, zVar).unwrap();
468 assert!(cs.is_satisfied().unwrap());
469 }
470
471 // gets as input a circuit that implements the ConstraintSynthesizer trait, and that has been
472 // initialized.
473 fn test_relaxed_r1cs_gadget<CS: ConstraintSynthesizer<Fr>>(circuit: CS) {
474 let cs = ConstraintSystem::<Fr>::new_ref();
475
476 circuit.generate_constraints(cs.clone()).unwrap();
477 cs.finalize();
478 assert!(cs.is_satisfied().unwrap());
479
480 let cs = cs.into_inner().unwrap();
481
482 let r1cs = extract_r1cs::<Fr>(&cs);
483 let (w, x) = extract_w_x::<Fr>(&cs);
484 let z = [vec![Fr::one()], x, w].concat();
485 r1cs.check_relation(&z).unwrap();
486
487 let relaxed_r1cs = r1cs.clone().relax();
488 relaxed_r1cs.check_relation(&z).unwrap();
489
490 // set new CS for the circuit that checks the RelaxedR1CS of our original circuit
491 let cs = ConstraintSystem::<Fr>::new_ref();
492 // prepare the inputs for our circuit
493 let zVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
494 let EVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.E)).unwrap();
495 let uVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
496 let r1csVar = R1CSVar::<Fr, Fr, FpVar<Fr>>::new_witness(cs.clone(), || Ok(r1cs)).unwrap();
497
498 RelaxedR1CSGadget::<Fr, Fr, FpVar<Fr>>::check(r1csVar, EVar, uVar, zVar).unwrap();
499 assert!(cs.is_satisfied().unwrap());
500 }
501
502 #[test]
503 fn test_relaxed_r1cs_small_gadget_arkworks() {
504 let z_i = vec![Fr::from(3_u32)];
505 let cubic_circuit = CubicFCircuit::<Fr>::new(());
506 let circuit = WrapperCircuit::<Fr, CubicFCircuit<Fr>> {
507 FC: cubic_circuit,
508 z_i: Some(z_i.clone()),
509 z_i1: Some(cubic_circuit.step_native(z_i).unwrap()),
510 };
511
512 test_relaxed_r1cs_gadget(circuit);
513 }
514
515 struct Sha256TestCircuit<F: PrimeField> {
516 _f: PhantomData<F>,
517 pub x: Vec<u8>,
518 pub y: Vec<u8>,
519 }
520 impl<F: PrimeField> ConstraintSynthesizer<F> for Sha256TestCircuit<F> {
521 fn generate_constraints(self, cs: ConstraintSystemRef<F>) -> Result<(), SynthesisError> {
522 let x = Vec::<UInt8<F>>::new_witness(cs.clone(), || Ok(self.x))?;
523 let y = Vec::<UInt8<F>>::new_input(cs.clone(), || Ok(self.y))?;
524
525 let unitVar = UnitVar::default();
526 let comp_y = <Sha256Gadget<F> as CRHSchemeGadget<Sha256, F>>::evaluate(&unitVar, &x)?;
527 comp_y.0.enforce_equal(&y)?;
528 Ok(())
529 }
530 }
531 #[test]
532 fn test_relaxed_r1cs_medium_gadget_arkworks() {
533 let x = Fr::from(5_u32).into_bigint().to_bytes_le();
534 let y = <Sha256 as CRHScheme>::evaluate(&(), x.clone()).unwrap();
535
536 let circuit = Sha256TestCircuit::<Fr> {
537 _f: PhantomData,
538 x,
539 y,
540 };
541 test_relaxed_r1cs_gadget(circuit);
542 }
543
544 #[test]
545 fn test_relaxed_r1cs_custom_circuit() {
546 let n_constraints = 10_000;
547 let custom_circuit = CustomFCircuit::<Fr>::new(n_constraints);
548 let z_i = vec![Fr::from(5_u32)];
549 let circuit = WrapperCircuit::<Fr, CustomFCircuit<Fr>> {
550 FC: custom_circuit,
551 z_i: Some(z_i.clone()),
552 z_i1: Some(custom_circuit.step_native(z_i).unwrap()),
553 };
554 test_relaxed_r1cs_gadget(circuit);
555 }
556
557 #[test]
558 fn test_relaxed_r1cs_nonnative_circuit() {
559 let cs = ConstraintSystem::<Fq>::new_ref();
560 // in practice we would use CycleFoldCircuit, but is a very big circuit (when computed
561 // non-natively inside the RelaxedR1CS circuit), so in order to have a short test we use a
562 // custom circuit.
563 let custom_circuit = CustomFCircuit::<Fq>::new(10);
564 let z_i = vec![Fq::from(5_u32)];
565 let circuit = WrapperCircuit::<Fq, CustomFCircuit<Fq>> {
566 FC: custom_circuit,
567 z_i: Some(z_i.clone()),
568 z_i1: Some(custom_circuit.step_native(z_i).unwrap()),
569 };
570 circuit.generate_constraints(cs.clone()).unwrap();
571 cs.finalize();
572 let cs = cs.into_inner().unwrap();
573 let r1cs = extract_r1cs::<Fq>(&cs);
574 let (w, x) = extract_w_x::<Fq>(&cs);
575 let z = [vec![Fq::one()], x, w].concat();
576
577 let relaxed_r1cs = r1cs.clone().relax();
578
579 // natively
580 let cs = ConstraintSystem::<Fq>::new_ref();
581 let zVar = Vec::<FpVar<Fq>>::new_witness(cs.clone(), || Ok(z.clone())).unwrap();
582 let EVar =
583 Vec::<FpVar<Fq>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.clone().E)).unwrap();
584 let uVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
585 let r1csVar =
586 R1CSVar::<Fq, Fq, FpVar<Fq>>::new_witness(cs.clone(), || Ok(r1cs.clone())).unwrap();
587 RelaxedR1CSGadget::<Fq, Fq, FpVar<Fq>>::check(r1csVar, EVar, uVar, zVar).unwrap();
588
589 // non-natively
590 let cs = ConstraintSystem::<Fr>::new_ref();
591 let zVar = Vec::<NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
592 let EVar = Vec::<NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.E))
593 .unwrap();
594 let uVar =
595 NonNativeFieldVar::<Fq, Fr>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
596 let r1csVar =
597 R1CSVar::<Fq, Fr, NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(r1cs))
598 .unwrap();
599 RelaxedR1CSGadget::<Fq, Fr, NonNativeFieldVar<Fq, Fr>>::check(r1csVar, EVar, uVar, zVar)
600 .unwrap();
601 }
602
603 #[test]
604 fn test_decider_circuit() {
605 let mut rng = ark_std::test_rng();
606 let poseidon_config = poseidon_test_config::<Fr>();
607
608 let F_circuit = CubicFCircuit::<Fr>::new(());
609 let z_0 = vec![Fr::from(3_u32)];
610
611 // get the CM & CF_CM len
612 let (cm_len, cf_cm_len) =
613 get_pedersen_params_len::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>>(
614 &poseidon_config,
615 F_circuit,
616 )
617 .unwrap();
618 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, cm_len);
619 let cf_pedersen_params = Pedersen::<Projective2>::new_params(&mut rng, cf_cm_len);
620
621 let prover_params =
622 ProverParams::<Projective, Projective2, Pedersen<Projective>, Pedersen<Projective2>> {
623 poseidon_config: poseidon_config.clone(),
624 cm_params: pedersen_params,
625 cf_cm_params: cf_pedersen_params,
626 };
627
628 type NOVA = Nova<
629 Projective,
630 GVar,
631 Projective2,
632 GVar2,
633 CubicFCircuit<Fr>,
634 Pedersen<Projective>,
635 Pedersen<Projective2>,
636 >;
637
638 // generate a Nova instance and do a step of it
639 let mut nova = NOVA::init(&prover_params, F_circuit, z_0.clone()).unwrap();
640 nova.prove_step().unwrap();
641 let ivc_v = nova.clone();
642 let verifier_params = VerifierParams::<Projective, Projective2> {
643 poseidon_config: poseidon_config.clone(),
644 r1cs: ivc_v.r1cs,
645 cf_r1cs: ivc_v.cf_r1cs,
646 };
647 NOVA::verify(
648 verifier_params,
649 z_0,
650 ivc_v.z_i,
651 Fr::one(),
652 (ivc_v.U_i, ivc_v.W_i),
653 (ivc_v.u_i, ivc_v.w_i),
654 (ivc_v.cf_U_i, ivc_v.cf_W_i),
655 )
656 .unwrap();
657
658 // load the DeciderEthCircuit from the generated Nova instance
659 let decider_circuit = DeciderEthCircuit::<
660 Projective,
661 GVar,
662 Projective2,
663 GVar2,
664 Pedersen<Projective>,
665 Pedersen<Projective2>,
666 >::from_nova(nova);
667
668 let cs = ConstraintSystem::<Fr>::new_ref();
669
670 // generate the constraints and check that are satisfied by the inputs
671 decider_circuit.generate_constraints(cs.clone()).unwrap();
672 assert!(cs.is_satisfied().unwrap());
673 }
674}