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