sonobe/folding-schemes/src/folding/nova/decider.rs
folding-schemes/src/folding/nova/decider.rsRaw
1/// This file implements the offchain decider. For ethereum use cases, use the
2/// DeciderEth from decider_eth.rs file.
3/// More details can be found at the documentation page:
4/// https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-offchain.html
5use ark_crypto_primitives::sponge::Absorb;
6use ark_ec::{AffineRepr, CurveGroup, Group};
7use ark_ff::{BigInteger, PrimeField};
8use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
9use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
10use ark_snark::SNARK;
11use ark_std::rand::{CryptoRng, RngCore};
12use ark_std::{One, Zero};
13use core::marker::PhantomData;
14
15use super::decider_circuits::{DeciderCircuit1, DeciderCircuit2};
16use super::{nifs::NIFS, CommittedInstance, Nova};
17use crate::commitment::CommitmentScheme;
18use crate::folding::circuits::{
19 cyclefold::CycleFoldCommittedInstance,
20 nonnative::{affine::NonNativeAffineVar, uint::NonNativeUintVar},
21 CF2,
22};
23use crate::frontend::FCircuit;
24use crate::Error;
25use crate::{Decider as DeciderTrait, FoldingScheme};
26
27#[derive(Debug, Clone, Eq, PartialEq)]
28pub struct Proof<C1, C2, CS1, CS2, S1, S2>
29where
30 C1: CurveGroup,
31 C2: CurveGroup,
32 CS1: CommitmentScheme<C1>,
33 CS2: CommitmentScheme<C2>,
34 S1: SNARK<C1::ScalarField>,
35 S2: SNARK<C2::ScalarField>,
36{
37 c1_snark_proof: S1::Proof,
38 c2_snark_proof: S2::Proof,
39 cs1_proofs: [CS1::Proof; 2],
40 cs2_proofs: [CS2::Proof; 2],
41 // cmT and r are values for the last fold, U_{i+1}=NIFS.V(r, U_i, u_i, cmT), and they are
42 // checked in-circuit
43 cmT: C1,
44 r: C1::ScalarField,
45 // cyclefold committed instance
46 cf_U_i: CycleFoldCommittedInstance<C2>,
47 // the CS challenges are provided by the prover, but in-circuit they are checked to match the
48 // in-circuit computed computed ones.
49 cs1_challenges: [C1::ScalarField; 2],
50 cs2_challenges: [C2::ScalarField; 2],
51}
52
53#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
54pub struct ProverParam<CS1_ProvingKey, S1_ProvingKey, CS2_ProvingKey, S2_ProvingKey>
55where
56 CS1_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
57 S1_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
58 CS2_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
59 S2_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
60{
61 pub c1_snark_pp: S1_ProvingKey,
62 pub c1_cs_pp: CS1_ProvingKey,
63 pub c2_snark_pp: S2_ProvingKey,
64 pub c2_cs_pp: CS2_ProvingKey,
65}
66
67#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
68pub struct VerifierParam<C1, CS1_VerifyingKey, S1_VerifyingKey, CS2_VerifyingKey, S2_VerifyingKey>
69where
70 C1: CurveGroup,
71 CS1_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
72 S1_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
73 CS2_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
74 S2_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
75{
76 pub pp_hash: C1::ScalarField,
77 pub c1_snark_vp: S1_VerifyingKey,
78 pub c1_cs_vp: CS1_VerifyingKey,
79 pub c2_snark_vp: S2_VerifyingKey,
80 pub c2_cs_vp: CS2_VerifyingKey,
81}
82
83/// Onchain Decider, for ethereum use cases
84#[derive(Clone, Debug)]
85pub struct Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S1, S2, FS> {
86 _c1: PhantomData<C1>,
87 _gc1: PhantomData<GC1>,
88 _c2: PhantomData<C2>,
89 _gc2: PhantomData<GC2>,
90 _fc: PhantomData<FC>,
91 _cs1: PhantomData<CS1>,
92 _cs2: PhantomData<CS2>,
93 _s1: PhantomData<S1>,
94 _s2: PhantomData<S2>,
95 _fs: PhantomData<FS>,
96}
97
98impl<C1, GC1, C2, GC2, FC, CS1, CS2, S1, S2, FS> DeciderTrait<C1, C2, FC, FS>
99 for Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S1, S2, FS>
100where
101 C1: CurveGroup,
102 C2: CurveGroup,
103 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
104 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
105 FC: FCircuit<C1::ScalarField>,
106 CS1: CommitmentScheme<
107 C1,
108 ProverChallenge = C1::ScalarField,
109 Challenge = C1::ScalarField,
110 Proof = crate::commitment::kzg::Proof<C1>,
111 >,
112 CS2: CommitmentScheme<
113 C2,
114 ProverChallenge = C2::ScalarField,
115 Challenge = C2::ScalarField,
116 Proof = crate::commitment::kzg::Proof<C2>,
117 >,
118 S1: SNARK<C1::ScalarField>,
119 S2: SNARK<C2::ScalarField>,
120 FS: FoldingScheme<C1, C2, FC>,
121 <C1 as CurveGroup>::BaseField: PrimeField,
122 <C2 as CurveGroup>::BaseField: PrimeField,
123 <C1 as Group>::ScalarField: Absorb,
124 <C2 as Group>::ScalarField: Absorb,
125 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
126 for<'b> &'b GC1: GroupOpsBounds<'b, C1, GC1>,
127 for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
128 // constrain FS into Nova, since this is a Decider specifically for Nova
129 Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false>: From<FS>,
130 crate::folding::nova::ProverParams<C1, C2, CS1, CS2, false>:
131 From<<FS as FoldingScheme<C1, C2, FC>>::ProverParam>,
132 crate::folding::nova::VerifierParams<C1, C2, CS1, CS2, false>:
133 From<<FS as FoldingScheme<C1, C2, FC>>::VerifierParam>,
134{
135 type PreprocessorParam = (FS::ProverParam, FS::VerifierParam);
136 type ProverParam =
137 ProverParam<CS1::ProverParams, S1::ProvingKey, CS2::ProverParams, S2::ProvingKey>;
138 type Proof = Proof<C1, C2, CS1, CS2, S1, S2>;
139 type VerifierParam = VerifierParam<
140 C1,
141 CS1::VerifierParams,
142 S1::VerifyingKey,
143 CS2::VerifierParams,
144 S2::VerifyingKey,
145 >;
146 type PublicInput = Vec<C1::ScalarField>;
147 type CommittedInstance = CommittedInstance<C1>;
148
149 fn preprocess(
150 mut rng: impl RngCore + CryptoRng,
151 prep_param: Self::PreprocessorParam,
152 fs: FS,
153 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
154 let circuit1 = DeciderCircuit1::<C1, C2, GC2>::from_nova::<GC1, CS1, CS2, false, FC>(
155 fs.clone().into(),
156 )?;
157 let circuit2 =
158 DeciderCircuit2::<C1, GC1, C2>::from_nova::<GC2, CS1, CS2, false, FC>(fs.into())?;
159
160 // get the Groth16 specific setup for the circuits
161 let (c1_g16_pk, c1_g16_vk) = S1::circuit_specific_setup(circuit1, &mut rng).unwrap();
162 let (c2_g16_pk, c2_g16_vk) = S2::circuit_specific_setup(circuit2, &mut rng).unwrap();
163
164 // get the FoldingScheme prover & verifier params from Nova
165 #[allow(clippy::type_complexity)]
166 let nova_pp: <Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false> as FoldingScheme<
167 C1,
168 C2,
169 FC,
170 >>::ProverParam = prep_param.0.clone().into();
171 #[allow(clippy::type_complexity)]
172 let nova_vp: <Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false> as FoldingScheme<
173 C1,
174 C2,
175 FC,
176 >>::VerifierParam = prep_param.1.clone().into();
177
178 let pp_hash = nova_vp.pp_hash()?;
179 let pp = Self::ProverParam {
180 c1_snark_pp: c1_g16_pk,
181 c1_cs_pp: nova_pp.cs_pp,
182 c2_snark_pp: c2_g16_pk,
183 c2_cs_pp: nova_pp.cf_cs_pp,
184 };
185 let vp = Self::VerifierParam {
186 pp_hash,
187 c1_snark_vp: c1_g16_vk,
188 c1_cs_vp: nova_vp.cs_vp,
189 c2_snark_vp: c2_g16_vk,
190 c2_cs_vp: nova_vp.cf_cs_vp,
191 };
192 Ok((pp, vp))
193 }
194
195 fn prove(
196 mut rng: impl RngCore + CryptoRng,
197 pp: Self::ProverParam,
198 fs: FS,
199 ) -> Result<Self::Proof, Error> {
200 let circuit1 = DeciderCircuit1::<C1, C2, GC2>::from_nova::<GC1, CS1, CS2, false, FC>(
201 fs.clone().into(),
202 )?;
203 let circuit2 =
204 DeciderCircuit2::<C1, GC1, C2>::from_nova::<GC2, CS1, CS2, false, FC>(fs.into())?;
205
206 let c1_snark_proof = S1::prove(&pp.c1_snark_pp, circuit1.clone(), &mut rng)
207 .map_err(|e| Error::Other(e.to_string()))?;
208 let c2_snark_proof = S2::prove(&pp.c2_snark_pp, circuit2.clone(), &mut rng)
209 .map_err(|e| Error::Other(e.to_string()))?;
210
211 let cmT = circuit1.cmT.unwrap();
212 let r_Fr = circuit1.r.unwrap();
213 let W_i1 = circuit1.W_i1.unwrap();
214 let cf_W_i = circuit2.cf_W_i.unwrap();
215
216 // get the challenges that have been already computed when preparing the circuits inputs in
217 // the above `from_nova` calls
218 let challenge_W = circuit1
219 .cs_c_W
220 .ok_or(Error::MissingValue("cs_c_W".to_string()))?;
221 let challenge_E = circuit1
222 .cs_c_E
223 .ok_or(Error::MissingValue("cs_c_E".to_string()))?;
224 let c2_challenge_W = circuit2
225 .cs_c_W
226 .ok_or(Error::MissingValue("c2's cs_c_W".to_string()))?;
227 let c2_challenge_E = circuit2
228 .cs_c_E
229 .ok_or(Error::MissingValue("c2's cs_c_E".to_string()))?;
230
231 // generate CommitmentScheme proofs for the main instance
232 let U_cmW_proof = CS1::prove_with_challenge(
233 &pp.c1_cs_pp,
234 challenge_W,
235 &W_i1.W,
236 &C1::ScalarField::zero(),
237 None,
238 )?;
239 let U_cmE_proof = CS1::prove_with_challenge(
240 &pp.c1_cs_pp,
241 challenge_E,
242 &W_i1.E,
243 &C1::ScalarField::zero(),
244 None,
245 )?;
246 // CS proofs for the CycleFold instance
247 let cf_cmW_proof = CS2::prove_with_challenge(
248 &pp.c2_cs_pp,
249 c2_challenge_W,
250 &cf_W_i.W,
251 &C2::ScalarField::zero(),
252 None,
253 )?;
254 let cf_cmE_proof = CS2::prove_with_challenge(
255 &pp.c2_cs_pp,
256 c2_challenge_E,
257 &cf_W_i.E,
258 &C2::ScalarField::zero(),
259 None,
260 )?;
261
262 Ok(Self::Proof {
263 c1_snark_proof,
264 c2_snark_proof,
265 cs1_proofs: [U_cmW_proof, U_cmE_proof],
266 cs2_proofs: [cf_cmW_proof, cf_cmE_proof],
267 cmT,
268 r: r_Fr,
269 cf_U_i: circuit1.cf_U_i.unwrap(),
270 cs1_challenges: [challenge_W, challenge_E],
271 cs2_challenges: [c2_challenge_W, c2_challenge_E],
272 })
273 }
274
275 fn verify(
276 vp: Self::VerifierParam,
277 i: C1::ScalarField,
278 z_0: Vec<C1::ScalarField>,
279 z_i: Vec<C1::ScalarField>,
280 running_instance: &Self::CommittedInstance,
281 incoming_instance: &Self::CommittedInstance,
282 proof: &Self::Proof,
283 ) -> Result<bool, Error> {
284 if i <= C1::ScalarField::one() {
285 return Err(Error::NotEnoughSteps);
286 }
287
288 // compute U = U_{d+1}= NIFS.V(U_d, u_d, cmT)
289 let U = NIFS::<C1, CS1>::verify(proof.r, running_instance, incoming_instance, &proof.cmT);
290
291 let (cmE_x, cmE_y) = NonNativeAffineVar::inputize(U.cmE)?;
292 let (cmW_x, cmW_y) = NonNativeAffineVar::inputize(U.cmW)?;
293 let (cmT_x, cmT_y) = NonNativeAffineVar::inputize(proof.cmT)?;
294
295 let zero = (&C2::BaseField::zero(), &C2::BaseField::zero());
296 let cmE_affine = proof.cf_U_i.cmE.into_affine();
297 let cmW_affine = proof.cf_U_i.cmW.into_affine();
298 let (cf_cmE_x, cf_cmE_y) = cmE_affine.xy().unwrap_or(zero);
299 let cf_cmE_z = C1::ScalarField::one();
300 let (cf_cmW_x, cf_cmW_y) = cmW_affine.xy().unwrap_or(zero);
301 let cf_cmW_z = C1::ScalarField::one();
302
303 // snark proof 1
304 let c1_public_input: Vec<C1::ScalarField> = [
305 vec![vp.pp_hash, i],
306 z_0,
307 z_i,
308 // U_{i+1} values:
309 vec![U.u],
310 U.x.clone(),
311 cmE_x,
312 cmE_y,
313 cmW_x,
314 cmW_y,
315 // CS1 values:
316 proof.cs1_challenges.to_vec(), // c_W, c_E
317 vec![
318 proof.cs1_proofs[0].eval, // eval_W
319 proof.cs1_proofs[1].eval, // eval_E
320 ],
321 // cf_U_i values
322 NonNativeUintVar::<CF2<C2>>::inputize(proof.cf_U_i.u),
323 proof
324 .cf_U_i
325 .x
326 .iter()
327 .flat_map(|&x_i| NonNativeUintVar::<CF2<C2>>::inputize(x_i))
328 .collect::<Vec<C1::ScalarField>>(),
329 vec![
330 *cf_cmE_x, *cf_cmE_y, cf_cmE_z, *cf_cmW_x, *cf_cmW_y, cf_cmW_z,
331 ],
332 // NIFS values:
333 cmT_x,
334 cmT_y,
335 vec![proof.r],
336 ]
337 .concat();
338
339 let c1_snark_v = S1::verify(&vp.c1_snark_vp, &c1_public_input, &proof.c1_snark_proof)
340 .map_err(|e| Error::Other(e.to_string()))?;
341 if !c1_snark_v {
342 return Err(Error::SNARKVerificationFail);
343 }
344
345 let (cf2_cmE_x, cf2_cmE_y) = NonNativeAffineVar::inputize(proof.cf_U_i.cmE)?;
346 let (cf2_cmW_x, cf2_cmW_y) = NonNativeAffineVar::inputize(proof.cf_U_i.cmW)?;
347
348 // snark proof 2
349 // migrate pp_hash from C1::Fr to C1::Fq
350 let pp_hash_Fq =
351 C2::ScalarField::from_le_bytes_mod_order(&vp.pp_hash.into_bigint().to_bytes_le());
352 let c2_public_input: Vec<C2::ScalarField> = [
353 vec![pp_hash_Fq],
354 vec![proof.cf_U_i.u],
355 proof.cf_U_i.x.clone(),
356 cf2_cmE_x,
357 cf2_cmE_y,
358 cf2_cmW_x,
359 cf2_cmW_y,
360 proof.cs2_challenges.to_vec(),
361 vec![
362 proof.cs2_proofs[0].eval, // eval_W
363 proof.cs2_proofs[1].eval, // eval_E
364 ],
365 ]
366 .concat();
367
368 let c2_snark_v = S2::verify(&vp.c2_snark_vp, &c2_public_input, &proof.c2_snark_proof)
369 .map_err(|e| Error::Other(e.to_string()))?;
370 if !c2_snark_v {
371 return Err(Error::SNARKVerificationFail);
372 }
373
374 // check C1 commitments (main instance commitments)
375 CS1::verify_with_challenge(
376 &vp.c1_cs_vp,
377 proof.cs1_challenges[0],
378 &U.cmW,
379 &proof.cs1_proofs[0],
380 )?;
381 CS1::verify_with_challenge(
382 &vp.c1_cs_vp,
383 proof.cs1_challenges[1],
384 &U.cmE,
385 &proof.cs1_proofs[1],
386 )?;
387
388 // check C2 commitments (CycleFold instance commitments)
389 CS2::verify_with_challenge(
390 &vp.c2_cs_vp,
391 proof.cs2_challenges[0],
392 &proof.cf_U_i.cmW,
393 &proof.cs2_proofs[0],
394 )?;
395 CS2::verify_with_challenge(
396 &vp.c2_cs_vp,
397 proof.cs2_challenges[1],
398 &proof.cf_U_i.cmE,
399 &proof.cs2_proofs[1],
400 )?;
401
402 Ok(true)
403 }
404}
405
406#[cfg(test)]
407pub mod tests {
408 use ark_groth16::Groth16;
409
410 // Note: do not use the MNTx_298 curves in practice, these are just for tests. Use the MNTx_753
411 // curves instead.
412 use ark_mnt4_298::{
413 constraints::G1Var as GVar, Fr, G1Projective as Projective, MNT4_298 as MNT4,
414 };
415 use ark_mnt6_298::{
416 constraints::G1Var as GVar2, G1Projective as Projective2, MNT6_298 as MNT6,
417 };
418 use std::time::Instant;
419
420 use super::*;
421 use crate::commitment::kzg::KZG;
422 use crate::folding::nova::PreprocessorParam;
423 use crate::frontend::utils::CubicFCircuit;
424 use crate::transcript::poseidon::poseidon_canonical_config;
425
426 #[test]
427 fn test_decider() {
428 // use Nova as FoldingScheme
429 type N = Nova<
430 Projective,
431 GVar,
432 Projective2,
433 GVar2,
434 CubicFCircuit<Fr>,
435 KZG<'static, MNT4>,
436 KZG<'static, MNT6>,
437 false,
438 >;
439 type D = Decider<
440 Projective,
441 GVar,
442 Projective2,
443 GVar2,
444 CubicFCircuit<Fr>,
445 KZG<'static, MNT4>,
446 KZG<'static, MNT6>,
447 Groth16<MNT4>,
448 Groth16<MNT6>,
449 N, // here we define the FoldingScheme to use
450 >;
451
452 let mut rng = ark_std::test_rng();
453 let poseidon_config = poseidon_canonical_config::<Fr>();
454
455 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
456 let z_0 = vec![Fr::from(3_u32)];
457
458 let start = Instant::now();
459 let prep_param = PreprocessorParam::new(poseidon_config, F_circuit);
460 let nova_params = N::preprocess(&mut rng, &prep_param).unwrap();
461 println!("Nova preprocess, {:?}", start.elapsed());
462
463 let start = Instant::now();
464 let mut nova = N::init(&nova_params, F_circuit, z_0.clone()).unwrap();
465 println!("Nova initialized, {:?}", start.elapsed());
466 let start = Instant::now();
467 nova.prove_step(&mut rng, vec![], None).unwrap();
468 println!("prove_step, {:?}", start.elapsed());
469 nova.prove_step(&mut rng, vec![], None).unwrap(); // do a 2nd step
470
471 let mut rng = rand::rngs::OsRng;
472
473 // prepare the Decider prover & verifier params
474 let start = Instant::now();
475 let (decider_pp, decider_vp) = D::preprocess(&mut rng, nova_params, nova.clone()).unwrap();
476 println!("Decider preprocess, {:?}", start.elapsed());
477
478 // decider proof generation
479 let start = Instant::now();
480 let proof = D::prove(rng, decider_pp, nova.clone()).unwrap();
481 println!("Decider prove, {:?}", start.elapsed());
482
483 // decider proof verification
484 let start = Instant::now();
485 let verified = D::verify(
486 decider_vp, nova.i, nova.z_0, nova.z_i, &nova.U_i, &nova.u_i, &proof,
487 )
488 .unwrap();
489 assert!(verified);
490 println!("Decider verify, {:?}", start.elapsed());
491 }
492}