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