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, One, 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>>,
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>>,
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(1);
366 let w_dummy_native = Witness::<C1>::new(
367 vec![C1::ScalarField::zero(); self.r1cs.A.n_cols - 2 /* (2=1+1, since u_i.x.len=1) */],
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_x & zero_y are the x & y coordinates of the zero point affine representation.
416 let zero_x = NonNativeFieldVar::<C1::BaseField, C1::ScalarField>::new_constant(
417 cs.clone(),
418 C1::BaseField::zero(),
419 )?;
420 let zero_y = NonNativeFieldVar::<C1::BaseField, C1::ScalarField>::new_constant(
421 cs.clone(),
422 C1::BaseField::one(),
423 )?;
424 u_i.cmE.x.enforce_equal(&zero_x)?;
425 u_i.cmE.y.enforce_equal(&zero_y)?;
426 (u_i.u.is_one()?).enforce_equal(&Boolean::TRUE)?;
427
428 // 3. u_i.x == H(i, z_0, z_i, U_i)
429 let (u_i_x, U_i_vec) =
430 U_i.clone()
431 .hash(&crh_params, i.clone(), z_0.clone(), z_i.clone())?;
432 (u_i.x[0]).enforce_equal(&u_i_x)?;
433
434 // The following two checks (and their respective allocations) are disabled for normal
435 // tests since they take several millions of constraints and would take several minutes
436 // (and RAM) to run the test.
437 #[cfg(not(test))]
438 {
439 // imports here instead of at the top of the file, so we avoid having multiple
440 // `#[cfg(not(test))]`
441 use crate::commitment::pedersen::PedersenGadget;
442 use crate::folding::nova::cyclefold::{CycleFoldCommittedInstanceVar, CF_IO_LEN};
443 use ark_r1cs_std::ToBitsGadget;
444
445 let cf_u_dummy_native = CommittedInstance::<C2>::dummy(CF_IO_LEN);
446 let w_dummy_native = Witness::<C2>::new(
447 vec![C2::ScalarField::zero(); self.cf_r1cs.A.n_cols - 1 - self.cf_r1cs.l],
448 self.cf_E_len,
449 );
450 let cf_U_i = CycleFoldCommittedInstanceVar::<C2, GC2>::new_witness(cs.clone(), || {
451 Ok(self.cf_U_i.unwrap_or_else(|| cf_u_dummy_native.clone()))
452 })?;
453 let cf_W_i = CycleFoldWitnessVar::<C2>::new_witness(cs.clone(), || {
454 Ok(self.cf_W_i.unwrap_or(w_dummy_native.clone()))
455 })?;
456
457 // 4. check Pedersen commitments of cf_U_i.{cmE, cmW}
458 let H = GC2::new_constant(cs.clone(), self.cf_pedersen_params.h)?;
459 let G = Vec::<GC2>::new_constant(cs.clone(), self.cf_pedersen_params.generators)?;
460 let cf_W_i_E_bits: Result<Vec<Vec<Boolean<CF1<C1>>>>, SynthesisError> =
461 cf_W_i.E.iter().map(|E_i| E_i.to_bits_le()).collect();
462 let cf_W_i_W_bits: Result<Vec<Vec<Boolean<CF1<C1>>>>, SynthesisError> =
463 cf_W_i.W.iter().map(|W_i| W_i.to_bits_le()).collect();
464
465 let computed_cmE = PedersenGadget::<C2, GC2>::commit(
466 H.clone(),
467 G.clone(),
468 cf_W_i_E_bits?,
469 cf_W_i.rE.to_bits_le()?,
470 )?;
471 cf_U_i.cmE.enforce_equal(&computed_cmE)?;
472 let computed_cmW =
473 PedersenGadget::<C2, GC2>::commit(H, G, cf_W_i_W_bits?, cf_W_i.rW.to_bits_le()?)?;
474 cf_U_i.cmW.enforce_equal(&computed_cmW)?;
475
476 let cf_r1cs = R1CSVar::<
477 C1::BaseField,
478 CF1<C1>,
479 NonNativeFieldVar<C1::BaseField, CF1<C1>>,
480 >::new_witness(cs.clone(), || Ok(self.cf_r1cs.clone()))?;
481
482 // 5. check RelaxedR1CS of cf_U_i
483 let cf_z_U: Vec<NonNativeFieldVar<C2::ScalarField, CF1<C1>>> =
484 [vec![cf_U_i.u.clone()], cf_U_i.x.to_vec(), cf_W_i.W.to_vec()].concat();
485 RelaxedR1CSGadget::<
486 C2::ScalarField,
487 CF1<C1>,
488 NonNativeFieldVar<C2::ScalarField, CF1<C1>>,
489 >::check(cf_r1cs, cf_W_i.E, cf_U_i.u.clone(), cf_z_U)?;
490 }
491
492 // 6. check KZG challenges
493 let (incircuit_c_W, incircuit_c_E) = KZGChallengesGadget::<C1>::get_challenges_gadget(
494 cs.clone(),
495 &self.poseidon_config,
496 U_i1.clone(),
497 )?;
498 incircuit_c_W.enforce_equal(&kzg_c_W)?;
499 incircuit_c_E.enforce_equal(&kzg_c_E)?;
500
501 // Check 7 is temporary disabled due
502 // https://github.com/privacy-scaling-explorations/folding-schemes/issues/80
503 //
504 // 7. check eval_W==p_W(c_W) and eval_E==p_E(c_E)
505 // let incircuit_eval_W = evaluate_gadget::<CF1<C1>>(W_i1.W, incircuit_c_W)?;
506 // let incircuit_eval_E = evaluate_gadget::<CF1<C1>>(W_i1.E, incircuit_c_E)?;
507 // incircuit_eval_W.enforce_equal(&eval_W)?;
508 // incircuit_eval_E.enforce_equal(&eval_E)?;
509
510 // 8. compute the NIFS.V challenge and check that matches the one from the public input (so we
511 // avoid the verifier computing it)
512 let cmT =
513 NonNativeAffineVar::new_input(cs.clone(), || Ok(self.cmT.unwrap_or_else(C1::zero)))?;
514 let r_bits = ChallengeGadget::<C1>::get_challenge_gadget(
515 cs.clone(),
516 &self.poseidon_config,
517 U_i_vec,
518 u_i.clone(),
519 cmT.clone(),
520 )?;
521 let r_Fr = Boolean::le_bits_to_fp_var(&r_bits)?;
522 // check that the in-circuit computed r is equal to the inputted r
523 let r =
524 FpVar::<CF1<C1>>::new_input(cs.clone(), || Ok(self.r.unwrap_or_else(CF1::<C1>::zero)))?;
525 r_Fr.enforce_equal(&r)?;
526
527 Ok(())
528 }
529}
530
531/// Interpolates the polynomial from the given vector, and then returns it's evaluation at the
532/// given point.
533#[allow(unused)] // unused while check 7 is disabled
534fn evaluate_gadget<F: PrimeField>(
535 v: Vec<FpVar<F>>,
536 point: FpVar<F>,
537) -> Result<FpVar<F>, SynthesisError> {
538 if !v.len().is_power_of_two() {
539 return Err(SynthesisError::Unsatisfiable);
540 }
541 let n = v.len() as u64;
542 let gen = F::get_root_of_unity(n).unwrap();
543 let domain = Radix2DomainVar::new(gen, log2(v.len()) as u64, FpVar::one()).unwrap();
544
545 let evaluations_var = EvaluationsVar::from_vec_and_domain(v, domain, true);
546 evaluations_var.interpolate_and_evaluate(&point)
547}
548
549/// Gadget that computes the KZG challenges, also offers the rust native implementation compatible
550/// with the gadget.
551pub struct KZGChallengesGadget<C: CurveGroup> {
552 _c: PhantomData<C>,
553}
554#[allow(clippy::type_complexity)]
555impl<C> KZGChallengesGadget<C>
556where
557 C: CurveGroup,
558 C::ScalarField: PrimeField,
559 <C as CurveGroup>::BaseField: PrimeField,
560 C::ScalarField: Absorb,
561{
562 pub fn get_challenges_native(
563 poseidon_config: &PoseidonConfig<C::ScalarField>,
564 U_i: CommittedInstance<C>,
565 ) -> Result<(C::ScalarField, C::ScalarField), Error> {
566 let (cmE_x_limbs, cmE_y_limbs): (Vec<C::ScalarField>, Vec<C::ScalarField>) =
567 point_to_nonnative_limbs::<C>(U_i.cmE)?;
568 let (cmW_x_limbs, cmW_y_limbs): (Vec<C::ScalarField>, Vec<C::ScalarField>) =
569 point_to_nonnative_limbs::<C>(U_i.cmW)?;
570
571 let transcript = &mut PoseidonTranscript::<C>::new(poseidon_config);
572 // compute the KZG challenges, which are computed in-circuit and checked that it matches
573 // the inputted one
574 transcript.absorb_vec(&cmW_x_limbs);
575 transcript.absorb_vec(&cmW_y_limbs);
576 let challenge_W = transcript.get_challenge();
577 transcript.absorb_vec(&cmE_x_limbs);
578 transcript.absorb_vec(&cmE_y_limbs);
579 let challenge_E = transcript.get_challenge();
580
581 Ok((challenge_W, challenge_E))
582 }
583 // compatible with the native get_challenges_native
584 pub fn get_challenges_gadget(
585 cs: ConstraintSystemRef<C::ScalarField>,
586 poseidon_config: &PoseidonConfig<C::ScalarField>,
587 U_i: CommittedInstanceVar<C>,
588 ) -> Result<(FpVar<C::ScalarField>, FpVar<C::ScalarField>), SynthesisError> {
589 let mut transcript =
590 PoseidonTranscriptVar::<CF1<C>>::new(cs.clone(), &poseidon_config.clone());
591
592 let cmW_x_limbs = U_i.cmW.x.to_constraint_field()?;
593 let cmW_y_limbs = U_i.cmW.y.to_constraint_field()?;
594 transcript.absorb_vec(&cmW_x_limbs)?;
595 transcript.absorb_vec(&cmW_y_limbs)?;
596 let challenge_W = transcript.get_challenge()?;
597
598 let cmE_x_limbs = U_i.cmE.x.to_constraint_field()?;
599 let cmE_y_limbs = U_i.cmE.y.to_constraint_field()?;
600 transcript.absorb_vec(&cmE_x_limbs)?;
601 transcript.absorb_vec(&cmE_y_limbs)?;
602 let challenge_E = transcript.get_challenge()?;
603
604 Ok((challenge_W, challenge_E))
605 }
606}
607
608#[cfg(test)]
609pub mod tests {
610 use super::*;
611 use ark_crypto_primitives::crh::{
612 sha256::{
613 constraints::{Sha256Gadget, UnitVar},
614 Sha256,
615 },
616 CRHScheme, CRHSchemeGadget,
617 };
618 use ark_ff::BigInteger;
619 use ark_pallas::{constraints::GVar, Fq, Fr, Projective};
620 use ark_r1cs_std::{
621 alloc::AllocVar,
622 bits::uint8::UInt8,
623 eq::EqGadget,
624 fields::{fp::FpVar, nonnative::NonNativeFieldVar},
625 };
626 use ark_relations::r1cs::ConstraintSystem;
627 use ark_std::UniformRand;
628 use ark_vesta::{constraints::GVar as GVar2, Projective as Projective2};
629
630 use crate::commitment::pedersen::Pedersen;
631 use crate::folding::nova::{get_cs_params_len, ProverParams, VerifierParams};
632 use crate::frontend::tests::{CubicFCircuit, CustomFCircuit, WrapperCircuit};
633 use crate::transcript::poseidon::poseidon_test_config;
634 use crate::FoldingScheme;
635
636 use crate::ccs::r1cs::{extract_r1cs, extract_w_x};
637 use crate::ccs::r1cs::{
638 tests::{get_test_r1cs, get_test_z},
639 R1CS,
640 };
641
642 #[test]
643 fn test_relaxed_r1cs_small_gadget_handcrafted() {
644 let r1cs: R1CS<Fr> = get_test_r1cs();
645 let rel_r1cs = r1cs.clone().relax();
646 let z = get_test_z(3);
647
648 let cs = ConstraintSystem::<Fr>::new_ref();
649
650 let zVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
651 let EVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(rel_r1cs.E)).unwrap();
652 let uVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(rel_r1cs.u)).unwrap();
653 let r1csVar = R1CSVar::<Fr, Fr, FpVar<Fr>>::new_witness(cs.clone(), || Ok(r1cs)).unwrap();
654
655 RelaxedR1CSGadget::<Fr, Fr, FpVar<Fr>>::check(r1csVar, EVar, uVar, zVar).unwrap();
656 assert!(cs.is_satisfied().unwrap());
657 }
658
659 // gets as input a circuit that implements the ConstraintSynthesizer trait, and that has been
660 // initialized.
661 fn test_relaxed_r1cs_gadget<CS: ConstraintSynthesizer<Fr>>(circuit: CS) {
662 let cs = ConstraintSystem::<Fr>::new_ref();
663
664 circuit.generate_constraints(cs.clone()).unwrap();
665 cs.finalize();
666 assert!(cs.is_satisfied().unwrap());
667
668 let cs = cs.into_inner().unwrap();
669
670 let r1cs = extract_r1cs::<Fr>(&cs);
671 let (w, x) = extract_w_x::<Fr>(&cs);
672 let z = [vec![Fr::one()], x, w].concat();
673 r1cs.check_relation(&z).unwrap();
674
675 let relaxed_r1cs = r1cs.clone().relax();
676 relaxed_r1cs.check_relation(&z).unwrap();
677
678 // set new CS for the circuit that checks the RelaxedR1CS of our original circuit
679 let cs = ConstraintSystem::<Fr>::new_ref();
680 // prepare the inputs for our circuit
681 let zVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
682 let EVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.E)).unwrap();
683 let uVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
684 let r1csVar = R1CSVar::<Fr, Fr, FpVar<Fr>>::new_witness(cs.clone(), || Ok(r1cs)).unwrap();
685
686 RelaxedR1CSGadget::<Fr, Fr, FpVar<Fr>>::check(r1csVar, EVar, uVar, zVar).unwrap();
687 assert!(cs.is_satisfied().unwrap());
688 }
689
690 #[test]
691 fn test_relaxed_r1cs_small_gadget_arkworks() {
692 let z_i = vec![Fr::from(3_u32)];
693 let cubic_circuit = CubicFCircuit::<Fr>::new(());
694 let circuit = WrapperCircuit::<Fr, CubicFCircuit<Fr>> {
695 FC: cubic_circuit,
696 z_i: Some(z_i.clone()),
697 z_i1: Some(cubic_circuit.step_native(0, z_i).unwrap()),
698 };
699
700 test_relaxed_r1cs_gadget(circuit);
701 }
702
703 struct Sha256TestCircuit<F: PrimeField> {
704 _f: PhantomData<F>,
705 pub x: Vec<u8>,
706 pub y: Vec<u8>,
707 }
708 impl<F: PrimeField> ConstraintSynthesizer<F> for Sha256TestCircuit<F> {
709 fn generate_constraints(self, cs: ConstraintSystemRef<F>) -> Result<(), SynthesisError> {
710 let x = Vec::<UInt8<F>>::new_witness(cs.clone(), || Ok(self.x))?;
711 let y = Vec::<UInt8<F>>::new_input(cs.clone(), || Ok(self.y))?;
712
713 let unitVar = UnitVar::default();
714 let comp_y = <Sha256Gadget<F> as CRHSchemeGadget<Sha256, F>>::evaluate(&unitVar, &x)?;
715 comp_y.0.enforce_equal(&y)?;
716 Ok(())
717 }
718 }
719 #[test]
720 fn test_relaxed_r1cs_medium_gadget_arkworks() {
721 let x = Fr::from(5_u32).into_bigint().to_bytes_le();
722 let y = <Sha256 as CRHScheme>::evaluate(&(), x.clone()).unwrap();
723
724 let circuit = Sha256TestCircuit::<Fr> {
725 _f: PhantomData,
726 x,
727 y,
728 };
729 test_relaxed_r1cs_gadget(circuit);
730 }
731
732 #[test]
733 fn test_relaxed_r1cs_custom_circuit() {
734 let n_constraints = 10_000;
735 let custom_circuit = CustomFCircuit::<Fr>::new(n_constraints);
736 let z_i = vec![Fr::from(5_u32)];
737 let circuit = WrapperCircuit::<Fr, CustomFCircuit<Fr>> {
738 FC: custom_circuit,
739 z_i: Some(z_i.clone()),
740 z_i1: Some(custom_circuit.step_native(0, z_i).unwrap()),
741 };
742 test_relaxed_r1cs_gadget(circuit);
743 }
744
745 #[test]
746 fn test_relaxed_r1cs_nonnative_circuit() {
747 let cs = ConstraintSystem::<Fq>::new_ref();
748 // in practice we would use CycleFoldCircuit, but is a very big circuit (when computed
749 // non-natively inside the RelaxedR1CS circuit), so in order to have a short test we use a
750 // custom circuit.
751 let custom_circuit = CustomFCircuit::<Fq>::new(10);
752 let z_i = vec![Fq::from(5_u32)];
753 let circuit = WrapperCircuit::<Fq, CustomFCircuit<Fq>> {
754 FC: custom_circuit,
755 z_i: Some(z_i.clone()),
756 z_i1: Some(custom_circuit.step_native(0, z_i).unwrap()),
757 };
758 circuit.generate_constraints(cs.clone()).unwrap();
759 cs.finalize();
760 let cs = cs.into_inner().unwrap();
761 let r1cs = extract_r1cs::<Fq>(&cs);
762 let (w, x) = extract_w_x::<Fq>(&cs);
763 let z = [vec![Fq::one()], x, w].concat();
764
765 let relaxed_r1cs = r1cs.clone().relax();
766
767 // natively
768 let cs = ConstraintSystem::<Fq>::new_ref();
769 let zVar = Vec::<FpVar<Fq>>::new_witness(cs.clone(), || Ok(z.clone())).unwrap();
770 let EVar =
771 Vec::<FpVar<Fq>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.clone().E)).unwrap();
772 let uVar = FpVar::<Fq>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
773 let r1csVar =
774 R1CSVar::<Fq, Fq, FpVar<Fq>>::new_witness(cs.clone(), || Ok(r1cs.clone())).unwrap();
775 RelaxedR1CSGadget::<Fq, Fq, FpVar<Fq>>::check(r1csVar, EVar, uVar, zVar).unwrap();
776
777 // non-natively
778 let cs = ConstraintSystem::<Fr>::new_ref();
779 let zVar = Vec::<NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(z)).unwrap();
780 let EVar = Vec::<NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(relaxed_r1cs.E))
781 .unwrap();
782 let uVar =
783 NonNativeFieldVar::<Fq, Fr>::new_witness(cs.clone(), || Ok(relaxed_r1cs.u)).unwrap();
784 let r1csVar =
785 R1CSVar::<Fq, Fr, NonNativeFieldVar<Fq, Fr>>::new_witness(cs.clone(), || Ok(r1cs))
786 .unwrap();
787 RelaxedR1CSGadget::<Fq, Fr, NonNativeFieldVar<Fq, Fr>>::check(r1csVar, EVar, uVar, zVar)
788 .unwrap();
789 }
790
791 #[test]
792 fn test_decider_circuit() {
793 let mut rng = ark_std::test_rng();
794 let poseidon_config = poseidon_test_config::<Fr>();
795
796 let F_circuit = CubicFCircuit::<Fr>::new(());
797 let z_0 = vec![Fr::from(3_u32)];
798
799 // get the CS & CF_CS len
800 let (cs_len, cf_cs_len) =
801 get_cs_params_len::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>>(
802 &poseidon_config,
803 F_circuit,
804 )
805 .unwrap();
806 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, cs_len).unwrap();
807 let (cf_pedersen_params, _) = Pedersen::<Projective2>::setup(&mut rng, cf_cs_len).unwrap();
808
809 let prover_params =
810 ProverParams::<Projective, Projective2, Pedersen<Projective>, Pedersen<Projective2>> {
811 poseidon_config: poseidon_config.clone(),
812 cs_params: pedersen_params,
813 cf_cs_params: cf_pedersen_params,
814 };
815
816 type NOVA = Nova<
817 Projective,
818 GVar,
819 Projective2,
820 GVar2,
821 CubicFCircuit<Fr>,
822 Pedersen<Projective>,
823 Pedersen<Projective2>,
824 >;
825
826 // generate a Nova instance and do a step of it
827 let mut nova = NOVA::init(&prover_params, F_circuit, z_0.clone()).unwrap();
828 nova.prove_step().unwrap();
829 let ivc_v = nova.clone();
830 let verifier_params = VerifierParams::<Projective, Projective2> {
831 poseidon_config: poseidon_config.clone(),
832 r1cs: ivc_v.clone().r1cs,
833 cf_r1cs: ivc_v.clone().cf_r1cs,
834 };
835 let (running_instance, incoming_instance, cyclefold_instance) = ivc_v.instances();
836 NOVA::verify(
837 verifier_params,
838 z_0,
839 ivc_v.z_i,
840 Fr::one(),
841 running_instance,
842 incoming_instance,
843 cyclefold_instance,
844 )
845 .unwrap();
846
847 // load the DeciderEthCircuit from the generated Nova instance
848 let decider_circuit = DeciderEthCircuit::<
849 Projective,
850 GVar,
851 Projective2,
852 GVar2,
853 Pedersen<Projective>,
854 Pedersen<Projective2>,
855 >::from_nova(nova)
856 .unwrap();
857
858 let cs = ConstraintSystem::<Fr>::new_ref();
859
860 // generate the constraints and check that are satisfied by the inputs
861 decider_circuit.generate_constraints(cs.clone()).unwrap();
862 assert!(cs.is_satisfied().unwrap());
863 }
864
865 // checks that the gadget and native implementations of the challenge computation match
866 #[test]
867 fn test_kzg_challenge_gadget() {
868 let mut rng = ark_std::test_rng();
869 let poseidon_config = poseidon_test_config::<Fr>();
870
871 let U_i = CommittedInstance::<Projective> {
872 cmE: Projective::rand(&mut rng),
873 u: Fr::rand(&mut rng),
874 cmW: Projective::rand(&mut rng),
875 x: vec![Fr::rand(&mut rng); 1],
876 };
877
878 // compute the challenge natively
879 let (challenge_W, challenge_E) =
880 KZGChallengesGadget::<Projective>::get_challenges_native(&poseidon_config, U_i.clone())
881 .unwrap();
882
883 let cs = ConstraintSystem::<Fr>::new_ref();
884 let U_iVar =
885 CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(U_i.clone()))
886 .unwrap();
887
888 let (challenge_W_Var, challenge_E_Var) =
889 KZGChallengesGadget::<Projective>::get_challenges_gadget(
890 cs.clone(),
891 &poseidon_config,
892 U_iVar,
893 )
894 .unwrap();
895 assert!(cs.is_satisfied().unwrap());
896
897 // check that the natively computed and in-circuit computed hashes match
898 use ark_r1cs_std::R1CSVar;
899 assert_eq!(challenge_W_Var.value().unwrap(), challenge_W);
900 assert_eq!(challenge_E_Var.value().unwrap(), challenge_E);
901 }
902
903 // The test test_polynomial_interpolation is temporary disabled due
904 // https://github.com/privacy-scaling-explorations/folding-schemes/issues/80
905 // for n<=11 it will work, but for n>11 it will fail with stack overflow.
906 #[ignore]
907 #[test]
908 fn test_polynomial_interpolation() {
909 let mut rng = ark_std::test_rng();
910 let n = 12;
911 let l = 1 << n;
912
913 let v: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(&mut rng))
914 .take(l)
915 .collect();
916 let challenge = Fr::rand(&mut rng);
917
918 use ark_poly::Polynomial;
919 let polynomial = poly_from_vec(v.to_vec()).unwrap();
920 let eval = polynomial.evaluate(&challenge);
921
922 let cs = ConstraintSystem::<Fr>::new_ref();
923 let vVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(v)).unwrap();
924 let challengeVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(challenge)).unwrap();
925
926 let evalVar = evaluate_gadget::<Fr>(vVar, challengeVar).unwrap();
927
928 use ark_r1cs_std::R1CSVar;
929 assert_eq!(evalVar.value().unwrap(), eval);
930 assert!(cs.is_satisfied().unwrap());
931 }
932}