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