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::{BigInteger, PrimeField};
7use ark_poly::Polynomial;
8use ark_r1cs_std::{
9 alloc::{AllocVar, AllocationMode},
10 boolean::Boolean,
11 eq::EqGadget,
12 fields::{fp::FpVar, nonnative::NonNativeFieldVar, FieldVar},
13 groups::GroupOpsBounds,
14 poly::{domain::Radix2DomainVar, evaluations::univariate::EvaluationsVar},
15 prelude::CurveVar,
16 ToConstraintFieldGadget,
17};
18use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, Namespace, SynthesisError};
19use ark_std::{log2, Zero};
20use core::{borrow::Borrow, marker::PhantomData};
21
22use super::{circuits::ChallengeGadget, nifs::NIFS};
23use crate::ccs::r1cs::R1CS;
24use crate::commitment::{pedersen::Params as PedersenParams, CommitmentScheme};
25use crate::folding::circuits::nonnative::{point_to_nonnative_limbs, NonNativeAffineVar};
26use crate::folding::nova::{
27 circuits::{CommittedInstanceVar, CF1, CF2},
28 CommittedInstance, Nova, Witness,
29};
30use crate::frontend::FCircuit;
31use crate::transcript::{
32 poseidon::{PoseidonTranscript, PoseidonTranscriptVar},
33 Transcript, TranscriptVar,
34};
35use crate::utils::{
36 gadgets::{hadamard, mat_vec_mul_sparse, vec_add, vec_scalar_mul, SparseMatrixVar},
37 vec::poly_from_vec,
38};
39use crate::Error;
40
41#[derive(Debug, Clone)]
42pub struct RelaxedR1CSGadget<F: PrimeField, CF: PrimeField, FV: FieldVar<F, CF>> {
43 _f: PhantomData<F>,
44 _cf: PhantomData<CF>,
45 _fv: PhantomData<FV>,
46}
47impl<F: PrimeField, CF: PrimeField, FV: FieldVar<F, CF>> RelaxedR1CSGadget<F, CF, FV> {
48 /// performs the RelaxedR1CS check (Az∘Bz==uCz+E)
49 pub fn check(
50 r1cs: R1CSVar<F, CF, FV>,
51 E: Vec<FV>,
52 u: FV,
53 z: Vec<FV>,
54 ) -> Result<(), SynthesisError> {
55 let Az = mat_vec_mul_sparse(r1cs.A, z.clone());
56 let Bz = mat_vec_mul_sparse(r1cs.B, z.clone());
57 let Cz = mat_vec_mul_sparse(r1cs.C, z.clone());
58 let uCz = vec_scalar_mul(&Cz, &u);
59 let uCzE = vec_add(&uCz, &E)?;
60 let AzBz = hadamard(&Az, &Bz)?;
61 for i in 0..AzBz.len() {
62 AzBz[i].enforce_equal(&uCzE[i].clone())?;
63 }
64 Ok(())
65 }
66}
67
68#[derive(Debug, Clone)]
69pub struct R1CSVar<F: PrimeField, CF: PrimeField, FV: FieldVar<F, CF>> {
70 _f: PhantomData<F>,
71 _cf: PhantomData<CF>,
72 _fv: PhantomData<FV>,
73 pub A: SparseMatrixVar<F, CF, FV>,
74 pub B: SparseMatrixVar<F, CF, FV>,
75 pub C: SparseMatrixVar<F, CF, FV>,
76}
77
78impl<F, CF, FV> AllocVar<R1CS<F>, CF> for R1CSVar<F, CF, FV>
79where
80 F: PrimeField,
81 CF: PrimeField,
82 FV: FieldVar<F, CF>,
83{
84 fn new_variable<T: Borrow<R1CS<F>>>(
85 cs: impl Into<Namespace<CF>>,
86 f: impl FnOnce() -> Result<T, SynthesisError>,
87 _mode: AllocationMode,
88 ) -> Result<Self, SynthesisError> {
89 f().and_then(|val| {
90 let cs = cs.into();
91
92 let A = SparseMatrixVar::<F, CF, FV>::new_constant(cs.clone(), &val.borrow().A)?;
93 let B = SparseMatrixVar::<F, CF, FV>::new_constant(cs.clone(), &val.borrow().B)?;
94 let C = SparseMatrixVar::<F, CF, FV>::new_constant(cs.clone(), &val.borrow().C)?;
95
96 Ok(Self {
97 _f: PhantomData,
98 _cf: PhantomData,
99 _fv: PhantomData,
100 A,
101 B,
102 C,
103 })
104 })
105 }
106}
107
108/// In-circuit representation of the Witness associated to the CommittedInstance.
109#[derive(Debug, Clone)]
110pub struct WitnessVar<C: CurveGroup> {
111 pub E: Vec<FpVar<C::ScalarField>>,
112 pub rE: FpVar<C::ScalarField>,
113 pub W: Vec<FpVar<C::ScalarField>>,
114 pub rW: FpVar<C::ScalarField>,
115}
116
117impl<C> AllocVar<Witness<C>, CF1<C>> for WitnessVar<C>
118where
119 C: CurveGroup,
120 <C as ark_ec::CurveGroup>::BaseField: PrimeField,
121{
122 fn new_variable<T: Borrow<Witness<C>>>(
123 cs: impl Into<Namespace<CF1<C>>>,
124 f: impl FnOnce() -> Result<T, SynthesisError>,
125 mode: AllocationMode,
126 ) -> Result<Self, SynthesisError> {
127 f().and_then(|val| {
128 let cs = cs.into();
129
130 let E: Vec<FpVar<C::ScalarField>> =
131 Vec::new_variable(cs.clone(), || Ok(val.borrow().E.clone()), mode)?;
132 let rE =
133 FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().rE), mode)?;
134
135 let W: Vec<FpVar<C::ScalarField>> =
136 Vec::new_variable(cs.clone(), || Ok(val.borrow().W.clone()), mode)?;
137 let rW =
138 FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().rW), mode)?;
139
140 Ok(Self { E, rE, W, rW })
141 })
142 }
143}
144
145/// In-circuit representation of the Witness associated to the CommittedInstance, but with
146/// non-native representation, since it is used to represent the CycleFold witness.
147#[derive(Debug, Clone)]
148pub struct CycleFoldWitnessVar<C: CurveGroup> {
149 pub E: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>,
150 pub rE: NonNativeFieldVar<C::ScalarField, CF2<C>>,
151 pub W: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>>,
152 pub rW: NonNativeFieldVar<C::ScalarField, CF2<C>>,
153}
154
155impl<C> AllocVar<Witness<C>, CF2<C>> for CycleFoldWitnessVar<C>
156where
157 C: CurveGroup,
158 <C as ark_ec::CurveGroup>::BaseField: PrimeField,
159{
160 fn new_variable<T: Borrow<Witness<C>>>(
161 cs: impl Into<Namespace<CF2<C>>>,
162 f: impl FnOnce() -> Result<T, SynthesisError>,
163 mode: AllocationMode,
164 ) -> Result<Self, SynthesisError> {
165 f().and_then(|val| {
166 let cs = cs.into();
167
168 let E: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>> =
169 Vec::new_variable(cs.clone(), || Ok(val.borrow().E.clone()), mode)?;
170 let rE = NonNativeFieldVar::<C::ScalarField, CF2<C>>::new_variable(
171 cs.clone(),
172 || Ok(val.borrow().rE),
173 mode,
174 )?;
175
176 let W: Vec<NonNativeFieldVar<C::ScalarField, CF2<C>>> =
177 Vec::new_variable(cs.clone(), || Ok(val.borrow().W.clone()), mode)?;
178 let rW = NonNativeFieldVar::<C::ScalarField, CF2<C>>::new_variable(
179 cs.clone(),
180 || Ok(val.borrow().rW),
181 mode,
182 )?;
183
184 Ok(Self { E, rE, W, rW })
185 })
186 }
187}
188
189/// Circuit that implements the in-circuit checks needed for the onchain (Ethereum's EVM)
190/// verification.
191#[derive(Clone, Debug)]
192pub struct DeciderEthCircuit<C1, GC1, C2, GC2, CS1, CS2>
193where
194 C1: CurveGroup,
195 GC1: CurveVar<C1, CF2<C1>>,
196 C2: CurveGroup,
197 GC2: CurveVar<C2, CF2<C2>>,
198 CS1: CommitmentScheme<C1>,
199 CS2: CommitmentScheme<C2>,
200{
201 _c1: PhantomData<C1>,
202 _gc1: PhantomData<GC1>,
203 _c2: PhantomData<C2>,
204 _gc2: PhantomData<GC2>,
205 _cs1: PhantomData<CS1>,
206 _cs2: PhantomData<CS2>,
207
208 /// E vector's length of the Nova instance witness
209 pub E_len: usize,
210 /// E vector's length of the CycleFold instance witness
211 pub cf_E_len: usize,
212 /// R1CS of the Augmented Function circuit
213 pub r1cs: R1CS<C1::ScalarField>,
214 /// R1CS of the CycleFold circuit
215 pub cf_r1cs: R1CS<C2::ScalarField>,
216 /// CycleFold PedersenParams over C2
217 pub cf_pedersen_params: PedersenParams<C2>,
218 pub poseidon_config: PoseidonConfig<CF1<C1>>,
219 pub i: Option<CF1<C1>>,
220 /// initial state
221 pub z_0: Option<Vec<C1::ScalarField>>,
222 /// current i-th state
223 pub z_i: Option<Vec<C1::ScalarField>>,
224 /// Nova instances
225 pub u_i: Option<CommittedInstance<C1>>,
226 pub w_i: Option<Witness<C1>>,
227 pub U_i: Option<CommittedInstance<C1>>,
228 pub W_i: Option<Witness<C1>>,
229 pub U_i1: Option<CommittedInstance<C1>>,
230 pub W_i1: Option<Witness<C1>>,
231 pub cmT: Option<C1>,
232 pub r: Option<C1::ScalarField>,
233 /// CycleFold running instance
234 pub cf_U_i: Option<CommittedInstance<C2>>,
235 pub cf_W_i: Option<Witness<C2>>,
236
237 /// KZG challenges
238 pub kzg_c_W: Option<C1::ScalarField>,
239 pub kzg_c_E: Option<C1::ScalarField>,
240 pub eval_W: Option<C1::ScalarField>,
241 pub eval_E: Option<C1::ScalarField>,
242}
243impl<C1, GC1, C2, GC2, CS1, CS2> DeciderEthCircuit<C1, GC1, C2, GC2, CS1, CS2>
244where
245 C1: CurveGroup,
246 C2: CurveGroup,
247 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
248 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
249 CS1: CommitmentScheme<C1>,
250 // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
251 CS2: CommitmentScheme<C2, ProverParams = PedersenParams<C2>>,
252 <C1 as Group>::ScalarField: Absorb,
253 <C1 as CurveGroup>::BaseField: PrimeField,
254{
255 pub fn from_nova<FC: FCircuit<C1::ScalarField>>(
256 nova: Nova<C1, GC1, C2, GC2, FC, CS1, CS2>,
257 ) -> Result<Self, Error> {
258 // compute the U_{i+1}, W_{i+1}
259 let (T, cmT) = NIFS::<C1, CS1>::compute_cmT(
260 &nova.cs_params,
261 &nova.r1cs.clone(),
262 &nova.w_i.clone(),
263 &nova.u_i.clone(),
264 &nova.W_i.clone(),
265 &nova.U_i.clone(),
266 )?;
267 let r_bits = ChallengeGadget::<C1>::get_challenge_native(
268 &nova.poseidon_config,
269 nova.U_i.clone(),
270 nova.u_i.clone(),
271 cmT,
272 )?;
273 let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
274 .ok_or(Error::OutOfBounds)?;
275 let (W_i1, U_i1) = NIFS::<C1, CS1>::fold_instances(
276 r_Fr, &nova.W_i, &nova.U_i, &nova.w_i, &nova.u_i, &T, cmT,
277 )?;
278
279 // compute the KZG challenges used as inputs in the circuit
280 let (kzg_challenge_W, kzg_challenge_E) =
281 KZGChallengesGadget::<C1>::get_challenges_native(&nova.poseidon_config, U_i1.clone())?;
282
283 // get KZG evals
284 let mut W = W_i1.W.clone();
285 W.extend(
286 std::iter::repeat(C1::ScalarField::zero())
287 .take(W_i1.W.len().next_power_of_two() - W_i1.W.len()),
288 );
289 let mut E = W_i1.E.clone();
290 E.extend(
291 std::iter::repeat(C1::ScalarField::zero())
292 .take(W_i1.E.len().next_power_of_two() - W_i1.E.len()),
293 );
294 let p_W = poly_from_vec(W.to_vec())?;
295 let eval_W = p_W.evaluate(&kzg_challenge_W);
296 let p_E = poly_from_vec(E.to_vec())?;
297 let eval_E = p_E.evaluate(&kzg_challenge_E);
298
299 Ok(Self {
300 _c1: PhantomData,
301 _gc1: PhantomData,
302 _c2: PhantomData,
303 _gc2: PhantomData,
304 _cs1: PhantomData,
305 _cs2: PhantomData,
306
307 E_len: nova.W_i.E.len(),
308 cf_E_len: nova.cf_W_i.E.len(),
309 r1cs: nova.r1cs,
310 cf_r1cs: nova.cf_r1cs,
311 cf_pedersen_params: nova.cf_cs_params,
312 poseidon_config: nova.poseidon_config,
313 i: Some(nova.i),
314 z_0: Some(nova.z_0),
315 z_i: Some(nova.z_i),
316 u_i: Some(nova.u_i),
317 w_i: Some(nova.w_i),
318 U_i: Some(nova.U_i),
319 W_i: Some(nova.W_i),
320 U_i1: Some(U_i1),
321 W_i1: Some(W_i1),
322 cmT: Some(cmT),
323 r: Some(r_Fr),
324 cf_U_i: Some(nova.cf_U_i),
325 cf_W_i: Some(nova.cf_W_i),
326 kzg_c_W: Some(kzg_challenge_W),
327 kzg_c_E: Some(kzg_challenge_E),
328 eval_W: Some(eval_W),
329 eval_E: Some(eval_E),
330 })
331 }
332}
333
334impl<C1, GC1, C2, GC2, CS1, CS2> ConstraintSynthesizer<CF1<C1>>
335 for DeciderEthCircuit<C1, GC1, C2, GC2, CS1, CS2>
336where
337 C1: CurveGroup,
338 C2: CurveGroup,
339 GC1: CurveVar<C1, CF2<C1>>,
340 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
341 CS1: CommitmentScheme<C1>,
342 CS2: CommitmentScheme<C2>,
343 <C1 as CurveGroup>::BaseField: PrimeField,
344 <C2 as CurveGroup>::BaseField: PrimeField,
345 <C1 as Group>::ScalarField: Absorb,
346 <C2 as Group>::ScalarField: Absorb,
347 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
348 for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
349{
350 fn generate_constraints(self, cs: ConstraintSystemRef<CF1<C1>>) -> Result<(), SynthesisError> {
351 let r1cs =
352 R1CSVar::<C1::ScalarField, CF1<C1>, FpVar<CF1<C1>>>::new_witness(cs.clone(), || {
353 Ok(self.r1cs.clone())
354 })?;
355
356 let i =
357 FpVar::<CF1<C1>>::new_input(cs.clone(), || Ok(self.i.unwrap_or_else(CF1::<C1>::zero)))?;
358 let z_0 = Vec::<FpVar<CF1<C1>>>::new_input(cs.clone(), || {
359 Ok(self.z_0.unwrap_or(vec![CF1::<C1>::zero()]))
360 })?;
361 let z_i = Vec::<FpVar<CF1<C1>>>::new_input(cs.clone(), || {
362 Ok(self.z_i.unwrap_or(vec![CF1::<C1>::zero()]))
363 })?;
364
365 let u_dummy_native = CommittedInstance::<C1>::dummy(2);
366 let w_dummy_native = Witness::<C1>::new(
367 vec![C1::ScalarField::zero(); self.r1cs.A.n_cols - 3 /* (3=2+1, since u_i.x.len=2) */],
368 self.E_len,
369 );
370
371 let u_i = CommittedInstanceVar::<C1>::new_witness(cs.clone(), || {
372 Ok(self.u_i.unwrap_or(u_dummy_native.clone()))
373 })?;
374 let U_i = CommittedInstanceVar::<C1>::new_witness(cs.clone(), || {
375 Ok(self.U_i.unwrap_or(u_dummy_native.clone()))
376 })?;
377 // here (U_i1, W_i1) = NIFS.P( (U_i,W_i), (u_i,w_i))
378 let U_i1 = CommittedInstanceVar::<C1>::new_input(cs.clone(), || {
379 Ok(self.U_i1.unwrap_or(u_dummy_native.clone()))
380 })?;
381 let W_i1 = WitnessVar::<C1>::new_witness(cs.clone(), || {
382 Ok(self.W_i1.unwrap_or(w_dummy_native.clone()))
383 })?;
384
385 // allocate the inputs for the check 6
386 let kzg_c_W = FpVar::<CF1<C1>>::new_input(cs.clone(), || {
387 Ok(self.kzg_c_W.unwrap_or_else(CF1::<C1>::zero))
388 })?;
389 let kzg_c_E = FpVar::<CF1<C1>>::new_input(cs.clone(), || {
390 Ok(self.kzg_c_E.unwrap_or_else(CF1::<C1>::zero))
391 })?;
392 let _eval_W = FpVar::<CF1<C1>>::new_input(cs.clone(), || {
393 Ok(self.eval_W.unwrap_or_else(CF1::<C1>::zero))
394 })?;
395 let _eval_E = FpVar::<CF1<C1>>::new_input(cs.clone(), || {
396 Ok(self.eval_E.unwrap_or_else(CF1::<C1>::zero))
397 })?;
398
399 let crh_params = CRHParametersVar::<C1::ScalarField>::new_constant(
400 cs.clone(),
401 self.poseidon_config.clone(),
402 )?;
403
404 // 1. check RelaxedR1CS of U_{i+1}
405 let z_U1: Vec<FpVar<CF1<C1>>> =
406 [vec![U_i1.u.clone()], U_i1.x.to_vec(), W_i1.W.to_vec()].concat();
407 RelaxedR1CSGadget::<C1::ScalarField, CF1<C1>, FpVar<CF1<C1>>>::check(
408 r1cs,
409 W_i1.E.clone(),
410 U_i1.u.clone(),
411 z_U1,
412 )?;
413
414 // 2. u_i.cmE==cm(0), u_i.u==1
415 // Here zero is the x & y coordinates of the zero point affine representation.
416 let zero = NonNativeFieldVar::<C1::BaseField, C1::ScalarField>::zero();
417 u_i.cmE.x.enforce_equal(&zero)?;
418 u_i.cmE.y.enforce_equal(&zero)?;
419 (u_i.u.is_one()?).enforce_equal(&Boolean::TRUE)?;
420
421 // 3.a u_i.x[0] == H(i, z_0, z_i, U_i)
422 let (u_i_x, U_i_vec) =
423 U_i.clone()
424 .hash(&crh_params, i.clone(), z_0.clone(), z_i.clone())?;
425 (u_i.x[0]).enforce_equal(&u_i_x)?;
426
427 // The following two checks (and their respective allocations) are disabled for normal
428 // tests since they take several millions of constraints and would take several minutes
429 // (and RAM) to run the test.
430 #[cfg(not(test))]
431 {
432 // imports here instead of at the top of the file, so we avoid having multiple
433 // `#[cfg(not(test))]`
434 use crate::commitment::pedersen::PedersenGadget;
435 use crate::folding::nova::cyclefold::{CycleFoldCommittedInstanceVar, CF_IO_LEN};
436 use ark_r1cs_std::ToBitsGadget;
437
438 let cf_u_dummy_native = CommittedInstance::<C2>::dummy(CF_IO_LEN);
439 let w_dummy_native = Witness::<C2>::new(
440 vec![C2::ScalarField::zero(); self.cf_r1cs.A.n_cols - 1 - self.cf_r1cs.l],
441 self.cf_E_len,
442 );
443 let cf_U_i = CycleFoldCommittedInstanceVar::<C2, GC2>::new_witness(cs.clone(), || {
444 Ok(self.cf_U_i.unwrap_or_else(|| cf_u_dummy_native.clone()))
445 })?;
446 let cf_W_i = CycleFoldWitnessVar::<C2>::new_witness(cs.clone(), || {
447 Ok(self.cf_W_i.unwrap_or(w_dummy_native.clone()))
448 })?;
449
450 // 3.b u_i.x[1] == H(cf_U_i)
451 let (cf_u_i_x, _) = cf_U_i.clone().hash(&crh_params)?;
452 (u_i.x[1]).enforce_equal(&cf_u_i_x)?;
453
454 // 4. check Pedersen commitments of cf_U_i.{cmE, cmW}
455 let H = GC2::new_constant(cs.clone(), self.cf_pedersen_params.h)?;
456 let G = Vec::<GC2>::new_constant(cs.clone(), self.cf_pedersen_params.generators)?;
457 let cf_W_i_E_bits: Result<Vec<Vec<Boolean<CF1<C1>>>>, SynthesisError> =
458 cf_W_i.E.iter().map(|E_i| E_i.to_bits_le()).collect();
459 let cf_W_i_W_bits: Result<Vec<Vec<Boolean<CF1<C1>>>>, SynthesisError> =
460 cf_W_i.W.iter().map(|W_i| W_i.to_bits_le()).collect();
461
462 let computed_cmE = PedersenGadget::<C2, GC2>::commit(
463 H.clone(),
464 G.clone(),
465 cf_W_i_E_bits?,
466 cf_W_i.rE.to_bits_le()?,
467 )?;
468 cf_U_i.cmE.enforce_equal(&computed_cmE)?;
469 let computed_cmW =
470 PedersenGadget::<C2, GC2>::commit(H, G, cf_W_i_W_bits?, cf_W_i.rW.to_bits_le()?)?;
471 cf_U_i.cmW.enforce_equal(&computed_cmW)?;
472
473 let cf_r1cs = R1CSVar::<
474 C1::BaseField,
475 CF1<C1>,
476 NonNativeFieldVar<C1::BaseField, CF1<C1>>,
477 >::new_witness(cs.clone(), || Ok(self.cf_r1cs.clone()))?;
478
479 // 5. check RelaxedR1CS of cf_U_i
480 let cf_z_U: Vec<NonNativeFieldVar<C2::ScalarField, CF1<C1>>> =
481 [vec![cf_U_i.u.clone()], cf_U_i.x.to_vec(), cf_W_i.W.to_vec()].concat();
482 RelaxedR1CSGadget::<
483 C2::ScalarField,
484 CF1<C1>,
485 NonNativeFieldVar<C2::ScalarField, CF1<C1>>,
486 >::check(cf_r1cs, cf_W_i.E, cf_U_i.u.clone(), cf_z_U)?;
487 }
488
489 // 6. check KZG challenges
490 let (incircuit_c_W, incircuit_c_E) = KZGChallengesGadget::<C1>::get_challenges_gadget(
491 cs.clone(),
492 &self.poseidon_config,
493 U_i1.clone(),
494 )?;
495 incircuit_c_W.enforce_equal(&kzg_c_W)?;
496 incircuit_c_E.enforce_equal(&kzg_c_E)?;
497
498 // Check 7 is temporary disabled due
499 // https://github.com/privacy-scaling-explorations/folding-schemes/issues/80
500 //
501 // 7. check eval_W==p_W(c_W) and eval_E==p_E(c_E)
502 // let incircuit_eval_W = evaluate_gadget::<CF1<C1>>(W_i1.W, incircuit_c_W)?;
503 // let incircuit_eval_E = evaluate_gadget::<CF1<C1>>(W_i1.E, incircuit_c_E)?;
504 // incircuit_eval_W.enforce_equal(&eval_W)?;
505 // incircuit_eval_E.enforce_equal(&eval_E)?;
506
507 // 8. compute the NIFS.V challenge and check that matches the one from the public input (so we
508 // avoid the verifier computing it)
509 let cmT =
510 NonNativeAffineVar::new_input(cs.clone(), || Ok(self.cmT.unwrap_or_else(C1::zero)))?;
511 let r_bits = ChallengeGadget::<C1>::get_challenge_gadget(
512 cs.clone(),
513 &self.poseidon_config,
514 U_i_vec,
515 u_i.clone(),
516 cmT.clone(),
517 )?;
518 let r_Fr = Boolean::le_bits_to_fp_var(&r_bits)?;
519 // check that the in-circuit computed r is equal to the inputted r
520 let r =
521 FpVar::<CF1<C1>>::new_input(cs.clone(), || Ok(self.r.unwrap_or_else(CF1::<C1>::zero)))?;
522 r_Fr.enforce_equal(&r)?;
523
524 Ok(())
525 }
526}
527
528/// Interpolates the polynomial from the given vector, and then returns it's evaluation at the
529/// given point.
530#[allow(unused)] // unused while check 7 is disabled
531fn evaluate_gadget<F: PrimeField>(
532 v: Vec<FpVar<F>>,
533 point: FpVar<F>,
534) -> Result<FpVar<F>, SynthesisError> {
535 if !v.len().is_power_of_two() {
536 return Err(SynthesisError::Unsatisfiable);
537 }
538 let n = v.len() as u64;
539 let gen = F::get_root_of_unity(n).unwrap();
540 let domain = Radix2DomainVar::new(gen, log2(v.len()) as u64, FpVar::one()).unwrap();
541
542 let evaluations_var = EvaluationsVar::from_vec_and_domain(v, domain, true);
543 evaluations_var.interpolate_and_evaluate(&point)
544}
545
546/// Gadget that computes the KZG challenges, also offers the rust native implementation compatible
547/// with the gadget.
548pub struct KZGChallengesGadget<C: CurveGroup> {
549 _c: PhantomData<C>,
550}
551#[allow(clippy::type_complexity)]
552impl<C> KZGChallengesGadget<C>
553where
554 C: CurveGroup,
555 C::ScalarField: PrimeField,
556 <C as CurveGroup>::BaseField: PrimeField,
557 C::ScalarField: Absorb,
558{
559 pub fn get_challenges_native(
560 poseidon_config: &PoseidonConfig<C::ScalarField>,
561 U_i: CommittedInstance<C>,
562 ) -> Result<(C::ScalarField, C::ScalarField), Error> {
563 let (cmE_x_limbs, cmE_y_limbs): (Vec<C::ScalarField>, Vec<C::ScalarField>) =
564 point_to_nonnative_limbs::<C>(U_i.cmE)?;
565 let (cmW_x_limbs, cmW_y_limbs): (Vec<C::ScalarField>, Vec<C::ScalarField>) =
566 point_to_nonnative_limbs::<C>(U_i.cmW)?;
567
568 let transcript = &mut PoseidonTranscript::<C>::new(poseidon_config);
569 // compute the KZG challenges, which are computed in-circuit and checked that it matches
570 // the inputted one
571 transcript.absorb_vec(&cmW_x_limbs);
572 transcript.absorb_vec(&cmW_y_limbs);
573 let challenge_W = transcript.get_challenge();
574 transcript.absorb_vec(&cmE_x_limbs);
575 transcript.absorb_vec(&cmE_y_limbs);
576 let challenge_E = transcript.get_challenge();
577
578 Ok((challenge_W, challenge_E))
579 }
580 // compatible with the native get_challenges_native
581 pub fn get_challenges_gadget(
582 cs: ConstraintSystemRef<C::ScalarField>,
583 poseidon_config: &PoseidonConfig<C::ScalarField>,
584 U_i: CommittedInstanceVar<C>,
585 ) -> Result<(FpVar<C::ScalarField>, FpVar<C::ScalarField>), SynthesisError> {
586 let mut transcript =
587 PoseidonTranscriptVar::<CF1<C>>::new(cs.clone(), &poseidon_config.clone());
588
589 let cmW_x_limbs = U_i.cmW.x.to_constraint_field()?;
590 let cmW_y_limbs = U_i.cmW.y.to_constraint_field()?;
591 transcript.absorb_vec(&cmW_x_limbs)?;
592 transcript.absorb_vec(&cmW_y_limbs)?;
593 let challenge_W = transcript.get_challenge()?;
594
595 let cmE_x_limbs = U_i.cmE.x.to_constraint_field()?;
596 let cmE_y_limbs = U_i.cmE.y.to_constraint_field()?;
597 transcript.absorb_vec(&cmE_x_limbs)?;
598 transcript.absorb_vec(&cmE_y_limbs)?;
599 let challenge_E = transcript.get_challenge()?;
600
601 Ok((challenge_W, challenge_E))
602 }
603}
604
605#[cfg(test)]
606pub mod tests {
607 use super::*;
608 use ark_crypto_primitives::crh::{
609 sha256::{
610 constraints::{Sha256Gadget, UnitVar},
611 Sha256,
612 },
613 CRHScheme, CRHSchemeGadget,
614 };
615 use ark_pallas::{constraints::GVar, Fq, Fr, Projective};
616 use ark_r1cs_std::bits::uint8::UInt8;
617 use ark_relations::r1cs::ConstraintSystem;
618 use ark_std::{One, UniformRand};
619 use ark_vesta::{constraints::GVar as GVar2, Projective as Projective2};
620
621 use crate::commitment::pedersen::Pedersen;
622 use crate::folding::nova::{get_cs_params_len, ProverParams, VerifierParams};
623 use crate::frontend::tests::{CubicFCircuit, CustomFCircuit, WrapperCircuit};
624 use crate::transcript::poseidon::poseidon_test_config;
625 use crate::FoldingScheme;
626
627 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
628 use crate::ccs::r1cs::{extract_r1cs, extract_w_x};
629
630 #[test]
631 fn test_relaxed_r1cs_small_gadget_handcrafted() {
632 let r1cs: R1CS<Fr> = get_test_r1cs();
633 let rel_r1cs = r1cs.clone().relax();
634 let z = get_test_z(3);
635
636 let cs = ConstraintSystem::<Fr>::new_ref();
637
638 let zVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
639 let EVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(rel_r1cs.E)).unwrap();
640 let uVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(rel_r1cs.u)).unwrap();
641 let r1csVar = R1CSVar::<Fr, Fr, FpVar<Fr>>::new_witness(cs.clone(), || Ok(r1cs)).unwrap();
642
643 RelaxedR1CSGadget::<Fr, Fr, FpVar<Fr>>::check(r1csVar, EVar, uVar, zVar).unwrap();
644 assert!(cs.is_satisfied().unwrap());
645 }
646
647 // gets as input a circuit that implements the ConstraintSynthesizer trait, and that has been
648 // initialized.
649 fn test_relaxed_r1cs_gadget<CS: ConstraintSynthesizer<Fr>>(circuit: CS) {
650 let cs = ConstraintSystem::<Fr>::new_ref();
651
652 circuit.generate_constraints(cs.clone()).unwrap();
653 cs.finalize();
654 assert!(cs.is_satisfied().unwrap());
655
656 let cs = cs.into_inner().unwrap();
657
658 let r1cs = extract_r1cs::<Fr>(&cs);
659 let (w, x) = extract_w_x::<Fr>(&cs);
660 let z = [vec![Fr::one()], x, w].concat();
661 r1cs.check_relation(&z).unwrap();
662
663 let relaxed_r1cs = r1cs.clone().relax();
664 relaxed_r1cs.check_relation(&z).unwrap();
665
666 // set new CS for the circuit that checks the RelaxedR1CS of our original circuit
667 let cs = ConstraintSystem::<Fr>::new_ref();
668 // prepare the inputs for our circuit
669 let zVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
670 let EVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.E)).unwrap();
671 let uVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
672 let r1csVar = R1CSVar::<Fr, Fr, FpVar<Fr>>::new_witness(cs.clone(), || Ok(r1cs)).unwrap();
673
674 RelaxedR1CSGadget::<Fr, Fr, FpVar<Fr>>::check(r1csVar, EVar, uVar, zVar).unwrap();
675 assert!(cs.is_satisfied().unwrap());
676 }
677
678 #[test]
679 fn test_relaxed_r1cs_small_gadget_arkworks() {
680 let z_i = vec![Fr::from(3_u32)];
681 let cubic_circuit = CubicFCircuit::<Fr>::new(());
682 let circuit = WrapperCircuit::<Fr, CubicFCircuit<Fr>> {
683 FC: cubic_circuit,
684 z_i: Some(z_i.clone()),
685 z_i1: Some(cubic_circuit.step_native(0, z_i).unwrap()),
686 };
687
688 test_relaxed_r1cs_gadget(circuit);
689 }
690
691 struct Sha256TestCircuit<F: PrimeField> {
692 _f: PhantomData<F>,
693 pub x: Vec<u8>,
694 pub y: Vec<u8>,
695 }
696 impl<F: PrimeField> ConstraintSynthesizer<F> for Sha256TestCircuit<F> {
697 fn generate_constraints(self, cs: ConstraintSystemRef<F>) -> Result<(), SynthesisError> {
698 let x = Vec::<UInt8<F>>::new_witness(cs.clone(), || Ok(self.x))?;
699 let y = Vec::<UInt8<F>>::new_input(cs.clone(), || Ok(self.y))?;
700
701 let unitVar = UnitVar::default();
702 let comp_y = <Sha256Gadget<F> as CRHSchemeGadget<Sha256, F>>::evaluate(&unitVar, &x)?;
703 comp_y.0.enforce_equal(&y)?;
704 Ok(())
705 }
706 }
707 #[test]
708 fn test_relaxed_r1cs_medium_gadget_arkworks() {
709 let x = Fr::from(5_u32).into_bigint().to_bytes_le();
710 let y = <Sha256 as CRHScheme>::evaluate(&(), x.clone()).unwrap();
711
712 let circuit = Sha256TestCircuit::<Fr> {
713 _f: PhantomData,
714 x,
715 y,
716 };
717 test_relaxed_r1cs_gadget(circuit);
718 }
719
720 #[test]
721 fn test_relaxed_r1cs_custom_circuit() {
722 let n_constraints = 10_000;
723 let custom_circuit = CustomFCircuit::<Fr>::new(n_constraints);
724 let z_i = vec![Fr::from(5_u32)];
725 let circuit = WrapperCircuit::<Fr, CustomFCircuit<Fr>> {
726 FC: custom_circuit,
727 z_i: Some(z_i.clone()),
728 z_i1: Some(custom_circuit.step_native(0, z_i).unwrap()),
729 };
730 test_relaxed_r1cs_gadget(circuit);
731 }
732
733 #[test]
734 fn test_relaxed_r1cs_nonnative_circuit() {
735 let cs = ConstraintSystem::<Fq>::new_ref();
736 // in practice we would use CycleFoldCircuit, but is a very big circuit (when computed
737 // non-natively inside the RelaxedR1CS circuit), so in order to have a short test we use a
738 // custom circuit.
739 let custom_circuit = CustomFCircuit::<Fq>::new(10);
740 let z_i = vec![Fq::from(5_u32)];
741 let circuit = WrapperCircuit::<Fq, CustomFCircuit<Fq>> {
742 FC: custom_circuit,
743 z_i: Some(z_i.clone()),
744 z_i1: Some(custom_circuit.step_native(0, z_i).unwrap()),
745 };
746 circuit.generate_constraints(cs.clone()).unwrap();
747 cs.finalize();
748 let cs = cs.into_inner().unwrap();
749 let r1cs = extract_r1cs::<Fq>(&cs);
750 let (w, x) = extract_w_x::<Fq>(&cs);
751 let z = [vec![Fq::one()], x, w].concat();
752
753 let relaxed_r1cs = r1cs.clone().relax();
754
755 // natively
756 let cs = ConstraintSystem::<Fq>::new_ref();
757 let zVar = Vec::<FpVar<Fq>>::new_witness(cs.clone(), || Ok(z.clone())).unwrap();
758 let EVar =
759 Vec::<FpVar<Fq>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.clone().E)).unwrap();
760 let uVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
761 let r1csVar =
762 R1CSVar::<Fq, Fq, FpVar<Fq>>::new_witness(cs.clone(), || Ok(r1cs.clone())).unwrap();
763 RelaxedR1CSGadget::<Fq, Fq, FpVar<Fq>>::check(r1csVar, EVar, uVar, zVar).unwrap();
764
765 // non-natively
766 let cs = ConstraintSystem::<Fr>::new_ref();
767 let zVar = Vec::<NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
768 let EVar = Vec::<NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.E))
769 .unwrap();
770 let uVar =
771 NonNativeFieldVar::<Fq, Fr>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
772 let r1csVar =
773 R1CSVar::<Fq, Fr, NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(r1cs))
774 .unwrap();
775 RelaxedR1CSGadget::<Fq, Fr, NonNativeFieldVar<Fq, Fr>>::check(r1csVar, EVar, uVar, zVar)
776 .unwrap();
777 }
778
779 #[test]
780 fn test_decider_circuit() {
781 let mut rng = ark_std::test_rng();
782 let poseidon_config = poseidon_test_config::<Fr>();
783
784 let F_circuit = CubicFCircuit::<Fr>::new(());
785 let z_0 = vec![Fr::from(3_u32)];
786
787 // get the CS & CF_CS len
788 let (cs_len, cf_cs_len) =
789 get_cs_params_len::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>>(
790 &poseidon_config,
791 F_circuit,
792 )
793 .unwrap();
794 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, cs_len).unwrap();
795 let (cf_pedersen_params, _) = Pedersen::<Projective2>::setup(&mut rng, cf_cs_len).unwrap();
796
797 let prover_params =
798 ProverParams::<Projective, Projective2, Pedersen<Projective>, Pedersen<Projective2>> {
799 poseidon_config: poseidon_config.clone(),
800 cs_params: pedersen_params,
801 cf_cs_params: cf_pedersen_params,
802 };
803
804 type NOVA = Nova<
805 Projective,
806 GVar,
807 Projective2,
808 GVar2,
809 CubicFCircuit<Fr>,
810 Pedersen<Projective>,
811 Pedersen<Projective2>,
812 >;
813
814 // generate a Nova instance and do a step of it
815 let mut nova = NOVA::init(&prover_params, F_circuit, z_0.clone()).unwrap();
816 nova.prove_step().unwrap();
817 let ivc_v = nova.clone();
818 let verifier_params = VerifierParams::<Projective, Projective2> {
819 poseidon_config: poseidon_config.clone(),
820 r1cs: ivc_v.clone().r1cs,
821 cf_r1cs: ivc_v.clone().cf_r1cs,
822 };
823 let (running_instance, incoming_instance, cyclefold_instance) = ivc_v.instances();
824 NOVA::verify(
825 verifier_params,
826 z_0,
827 ivc_v.z_i,
828 Fr::one(),
829 running_instance,
830 incoming_instance,
831 cyclefold_instance,
832 )
833 .unwrap();
834
835 // load the DeciderEthCircuit from the generated Nova instance
836 let decider_circuit = DeciderEthCircuit::<
837 Projective,
838 GVar,
839 Projective2,
840 GVar2,
841 Pedersen<Projective>,
842 Pedersen<Projective2>,
843 >::from_nova(nova)
844 .unwrap();
845
846 let cs = ConstraintSystem::<Fr>::new_ref();
847
848 // generate the constraints and check that are satisfied by the inputs
849 decider_circuit.generate_constraints(cs.clone()).unwrap();
850 assert!(cs.is_satisfied().unwrap());
851 }
852
853 // checks that the gadget and native implementations of the challenge computation match
854 #[test]
855 fn test_kzg_challenge_gadget() {
856 let mut rng = ark_std::test_rng();
857 let poseidon_config = poseidon_test_config::<Fr>();
858
859 let U_i = CommittedInstance::<Projective> {
860 cmE: Projective::rand(&mut rng),
861 u: Fr::rand(&mut rng),
862 cmW: Projective::rand(&mut rng),
863 x: vec![Fr::rand(&mut rng); 1],
864 };
865
866 // compute the challenge natively
867 let (challenge_W, challenge_E) =
868 KZGChallengesGadget::<Projective>::get_challenges_native(&poseidon_config, U_i.clone())
869 .unwrap();
870
871 let cs = ConstraintSystem::<Fr>::new_ref();
872 let U_iVar =
873 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(U_i.clone()))
874 .unwrap();
875
876 let (challenge_W_Var, challenge_E_Var) =
877 KZGChallengesGadget::<Projective>::get_challenges_gadget(
878 cs.clone(),
879 &poseidon_config,
880 U_iVar,
881 )
882 .unwrap();
883 assert!(cs.is_satisfied().unwrap());
884
885 // check that the natively computed and in-circuit computed hashes match
886 use ark_r1cs_std::R1CSVar;
887 assert_eq!(challenge_W_Var.value().unwrap(), challenge_W);
888 assert_eq!(challenge_E_Var.value().unwrap(), challenge_E);
889 }
890
891 // The test test_polynomial_interpolation is temporary disabled due
892 // https://github.com/privacy-scaling-explorations/folding-schemes/issues/80
893 // for n<=11 it will work, but for n>11 it will fail with stack overflow.
894 #[ignore]
895 #[test]
896 fn test_polynomial_interpolation() {
897 let mut rng = ark_std::test_rng();
898 let n = 12;
899 let l = 1 << n;
900
901 let v: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(&mut rng))
902 .take(l)
903 .collect();
904 let challenge = Fr::rand(&mut rng);
905
906 use ark_poly::Polynomial;
907 let polynomial = poly_from_vec(v.to_vec()).unwrap();
908 let eval = polynomial.evaluate(&challenge);
909
910 let cs = ConstraintSystem::<Fr>::new_ref();
911 let vVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(v)).unwrap();
912 let challengeVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(challenge)).unwrap();
913
914 let evalVar = evaluate_gadget::<Fr>(vVar, challengeVar).unwrap();
915
916 use ark_r1cs_std::R1CSVar;
917 assert_eq!(evalVar.value().unwrap(), eval);
918 assert!(cs.is_satisfied().unwrap());
919 }
920}