sonobe/folding-schemes/src/folding/nova/decider_eth.rs
folding-schemes/src/folding/nova/decider_eth.rsRaw
1/// This file implements the Nova's onchain (Ethereum's EVM) decider. For non-ethereum use cases,
2/// the Decider from decider.rs file will be more efficient.
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_bn254::Bn254;
6use ark_crypto_primitives::sponge::Absorb;
7use ark_ec::{AffineRepr, CurveGroup, Group};
8use ark_ff::{BigInteger, PrimeField};
9use ark_groth16::Groth16;
10use ark_r1cs_std::{prelude::CurveVar, ToConstraintFieldGadget};
11use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
12use ark_snark::SNARK;
13use ark_std::rand::{CryptoRng, RngCore};
14use ark_std::{One, Zero};
15use core::marker::PhantomData;
16
17pub use super::decider_eth_circuit::DeciderEthCircuit;
18use super::decider_eth_circuit::DeciderNovaGadget;
19use super::{CommittedInstance, Nova};
20use crate::commitment::{
21 kzg::{Proof as KZGProof, KZG},
22 pedersen::Params as PedersenParams,
23 CommitmentScheme,
24};
25use crate::folding::circuits::decider::DeciderEnabledNIFS;
26use crate::folding::circuits::CF2;
27use crate::folding::traits::{Inputize, WitnessOps};
28use crate::frontend::FCircuit;
29use crate::Error;
30use crate::{Decider as DeciderTrait, FoldingScheme};
31
32#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
33pub struct Proof<C, CS, S>
34where
35 C: CurveGroup,
36 CS: CommitmentScheme<C, ProverChallenge = C::ScalarField, Challenge = C::ScalarField>,
37 S: SNARK<C::ScalarField>,
38{
39 snark_proof: S::Proof,
40 kzg_proofs: [CS::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: C,
44 r: C::ScalarField,
45 // the KZG challenges are provided by the prover, but in-circuit they are checked to match
46 // the in-circuit computed computed ones.
47 kzg_challenges: [C::ScalarField; 2],
48}
49
50#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
51pub struct VerifierParam<C1, CS_VerifyingKey, S_VerifyingKey>
52where
53 C1: CurveGroup,
54 CS_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
55 S_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
56{
57 pub pp_hash: C1::ScalarField,
58 pub snark_vp: S_VerifyingKey,
59 pub cs_vp: CS_VerifyingKey,
60}
61
62/// Onchain Decider, for ethereum use cases
63#[derive(Clone, Debug)]
64pub struct Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS> {
65 _c1: PhantomData<C1>,
66 _gc1: PhantomData<GC1>,
67 _c2: PhantomData<C2>,
68 _gc2: PhantomData<GC2>,
69 _fc: PhantomData<FC>,
70 _cs1: PhantomData<CS1>,
71 _cs2: PhantomData<CS2>,
72 _s: PhantomData<S>,
73 _fs: PhantomData<FS>,
74}
75
76impl<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS> DeciderTrait<C1, C2, FC, FS>
77 for Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS>
78where
79 C1: CurveGroup,
80 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
81 C2: CurveGroup,
82 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
83 FC: FCircuit<C1::ScalarField>,
84 // CS1 is a KZG commitment, where challenge is C1::Fr elem
85 CS1: CommitmentScheme<
86 C1,
87 ProverChallenge = C1::ScalarField,
88 Challenge = C1::ScalarField,
89 Proof = KZGProof<C1>,
90 >,
91 // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
92 CS2: CommitmentScheme<C2, ProverParams = PedersenParams<C2>>,
93 S: SNARK<C1::ScalarField>,
94 FS: FoldingScheme<C1, C2, FC>,
95 <C1 as CurveGroup>::BaseField: PrimeField,
96 <C2 as CurveGroup>::BaseField: PrimeField,
97 <C1 as Group>::ScalarField: Absorb,
98 <C2 as Group>::ScalarField: Absorb,
99 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
100 // constrain FS into Nova, since this is a Decider specifically for Nova
101 Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false>: From<FS>,
102 crate::folding::nova::ProverParams<C1, C2, CS1, CS2, false>:
103 From<<FS as FoldingScheme<C1, C2, FC>>::ProverParam>,
104 crate::folding::nova::VerifierParams<C1, C2, CS1, CS2, false>:
105 From<<FS as FoldingScheme<C1, C2, FC>>::VerifierParam>,
106{
107 type PreprocessorParam = (FS::ProverParam, FS::VerifierParam);
108 type ProverParam = (S::ProvingKey, CS1::ProverParams);
109 type Proof = Proof<C1, CS1, S>;
110 type VerifierParam = VerifierParam<C1, CS1::VerifierParams, S::VerifyingKey>;
111 type PublicInput = Vec<C1::ScalarField>;
112 type CommittedInstance = Vec<C1>;
113
114 fn preprocess(
115 mut rng: impl RngCore + CryptoRng,
116 prep_param: Self::PreprocessorParam,
117 fs: FS,
118 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
119 let circuit = DeciderEthCircuit::<C1, C2, GC2>::try_from(Nova::from(fs))?;
120
121 // get the Groth16 specific setup for the circuit
122 let (g16_pk, g16_vk) = S::circuit_specific_setup(circuit, &mut rng)
123 .map_err(|e| Error::SNARKSetupFail(e.to_string()))?;
124
125 // get the FoldingScheme prover & verifier params from Nova
126 #[allow(clippy::type_complexity)]
127 let nova_pp: <Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false> as FoldingScheme<
128 C1,
129 C2,
130 FC,
131 >>::ProverParam = prep_param.0.clone().into();
132 #[allow(clippy::type_complexity)]
133 let nova_vp: <Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false> as FoldingScheme<
134 C1,
135 C2,
136 FC,
137 >>::VerifierParam = prep_param.1.clone().into();
138 let pp_hash = nova_vp.pp_hash()?;
139
140 let pp = (g16_pk, nova_pp.cs_pp);
141 let vp = Self::VerifierParam {
142 pp_hash,
143 snark_vp: g16_vk,
144 cs_vp: nova_vp.cs_vp,
145 };
146 Ok((pp, vp))
147 }
148
149 fn prove(
150 mut rng: impl RngCore + CryptoRng,
151 pp: Self::ProverParam,
152 folding_scheme: FS,
153 ) -> Result<Self::Proof, Error> {
154 let (snark_pk, cs_pk): (S::ProvingKey, CS1::ProverParams) = pp;
155
156 let circuit = DeciderEthCircuit::<C1, C2, GC2>::try_from(Nova::from(folding_scheme))?;
157
158 let cmT = circuit.proof;
159 let r = circuit.randomness;
160
161 // get the challenges that have been already computed when preparing the circuit inputs in
162 // the above `try_from` call
163 let kzg_challenges = circuit.kzg_challenges.clone();
164
165 // generate KZG proofs
166 let kzg_proofs = circuit
167 .W_i1
168 .get_openings()
169 .iter()
170 .zip(&kzg_challenges)
171 .map(|((v, _), &c)| {
172 CS1::prove_with_challenge(&cs_pk, c, v, &C1::ScalarField::zero(), None)
173 })
174 .collect::<Result<Vec<_>, _>>()?;
175
176 let snark_proof =
177 S::prove(&snark_pk, circuit, &mut rng).map_err(|e| Error::Other(e.to_string()))?;
178
179 Ok(Self::Proof {
180 snark_proof,
181 cmT,
182 r,
183 kzg_proofs: kzg_proofs
184 .try_into()
185 .map_err(|e: Vec<_>| Error::NotExpectedLength(e.len(), 2))?,
186 kzg_challenges: kzg_challenges
187 .try_into()
188 .map_err(|e: Vec<_>| Error::NotExpectedLength(e.len(), 2))?,
189 })
190 }
191
192 fn verify(
193 vp: Self::VerifierParam,
194 i: C1::ScalarField,
195 z_0: Vec<C1::ScalarField>,
196 z_i: Vec<C1::ScalarField>,
197 // we don't use the instances at the verifier level, since we check them in-circuit
198 running_commitments: &Self::CommittedInstance,
199 incoming_commitments: &Self::CommittedInstance,
200 proof: &Self::Proof,
201 ) -> Result<bool, Error> {
202 if i <= C1::ScalarField::one() {
203 return Err(Error::NotEnoughSteps);
204 }
205
206 let Self::VerifierParam {
207 pp_hash,
208 snark_vp,
209 cs_vp,
210 } = vp;
211
212 // 6.2. Fold the commitments
213 let U_final_commitments = DeciderNovaGadget::fold_group_elements_native(
214 running_commitments,
215 incoming_commitments,
216 Some(proof.cmT),
217 proof.r,
218 )?;
219
220 let public_input = [
221 &[pp_hash, i][..],
222 &z_0,
223 &z_i,
224 &U_final_commitments
225 .iter()
226 .flat_map(|c| c.inputize())
227 .collect::<Vec<_>>(),
228 &proof.kzg_challenges,
229 &proof.kzg_proofs.iter().map(|p| p.eval).collect::<Vec<_>>(),
230 &proof.cmT.inputize(),
231 &[proof.r],
232 ]
233 .concat();
234
235 let snark_v = S::verify(&snark_vp, &public_input, &proof.snark_proof)
236 .map_err(|e| Error::Other(e.to_string()))?;
237 if !snark_v {
238 return Err(Error::SNARKVerificationFail);
239 }
240
241 // 7.3. Verify the KZG proofs
242 for ((cm, &c), pi) in U_final_commitments
243 .iter()
244 .zip(&proof.kzg_challenges)
245 .zip(&proof.kzg_proofs)
246 {
247 // we're at the Ethereum EVM case, so the CS1 is KZG commitments
248 CS1::verify_with_challenge(&cs_vp, c, cm, pi)?;
249 }
250
251 Ok(true)
252 }
253}
254
255/// Prepares solidity calldata for calling the NovaDecider contract
256#[allow(clippy::too_many_arguments)]
257pub fn prepare_calldata(
258 function_signature_check: [u8; 4],
259 i: ark_bn254::Fr,
260 z_0: Vec<ark_bn254::Fr>,
261 z_i: Vec<ark_bn254::Fr>,
262 running_instance: &CommittedInstance<ark_bn254::G1Projective>,
263 incoming_instance: &CommittedInstance<ark_bn254::G1Projective>,
264 proof: Proof<ark_bn254::G1Projective, KZG<'static, Bn254>, Groth16<Bn254>>,
265) -> Result<Vec<u8>, Error> {
266 Ok(vec![
267 function_signature_check.to_vec(),
268 i.into_bigint().to_bytes_be(), // i
269 z_0.iter()
270 .flat_map(|v| v.into_bigint().to_bytes_be())
271 .collect::<Vec<u8>>(), // z_0
272 z_i.iter()
273 .flat_map(|v| v.into_bigint().to_bytes_be())
274 .collect::<Vec<u8>>(), // z_i
275 point_to_eth_format(running_instance.cmW.into_affine())?,
276 point_to_eth_format(running_instance.cmE.into_affine())?,
277 point_to_eth_format(incoming_instance.cmW.into_affine())?,
278 point_to_eth_format(proof.cmT.into_affine())?, // cmT
279 proof.r.into_bigint().to_bytes_be(), // r
280 point_to_eth_format(proof.snark_proof.a)?, // pA
281 point2_to_eth_format(proof.snark_proof.b)?, // pB
282 point_to_eth_format(proof.snark_proof.c)?, // pC
283 proof.kzg_challenges[0].into_bigint().to_bytes_be(), // challenge_W
284 proof.kzg_challenges[1].into_bigint().to_bytes_be(), // challenge_E
285 proof.kzg_proofs[0].eval.into_bigint().to_bytes_be(), // eval W
286 proof.kzg_proofs[1].eval.into_bigint().to_bytes_be(), // eval E
287 point_to_eth_format(proof.kzg_proofs[0].proof.into_affine())?, // W kzg_proof
288 point_to_eth_format(proof.kzg_proofs[1].proof.into_affine())?, // E kzg_proof
289 ]
290 .concat())
291}
292
293fn point_to_eth_format<C: AffineRepr>(p: C) -> Result<Vec<u8>, Error>
294where
295 C::BaseField: PrimeField,
296{
297 // the encoding of the additive identity is [0, 0] on the EVM
298 let zero_point = (&C::BaseField::zero(), &C::BaseField::zero());
299 let (x, y) = p.xy().unwrap_or(zero_point);
300
301 Ok([x.into_bigint().to_bytes_be(), y.into_bigint().to_bytes_be()].concat())
302}
303fn point2_to_eth_format(p: ark_bn254::G2Affine) -> Result<Vec<u8>, Error> {
304 let zero_point = (&ark_bn254::Fq2::zero(), &ark_bn254::Fq2::zero());
305 let (x, y) = p.xy().unwrap_or(zero_point);
306
307 Ok([
308 x.c1.into_bigint().to_bytes_be(),
309 x.c0.into_bigint().to_bytes_be(),
310 y.c1.into_bigint().to_bytes_be(),
311 y.c0.into_bigint().to_bytes_be(),
312 ]
313 .concat())
314}
315
316#[cfg(test)]
317pub mod tests {
318 use ark_bn254::{constraints::GVar, Fr, G1Projective as Projective};
319 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
320 use std::time::Instant;
321
322 use super::*;
323 use crate::commitment::pedersen::Pedersen;
324 use crate::folding::nova::{PreprocessorParam, ProverParams as NovaProverParams};
325 use crate::folding::traits::CommittedInstanceOps;
326 use crate::frontend::utils::CubicFCircuit;
327 use crate::transcript::poseidon::poseidon_canonical_config;
328
329 #[test]
330 fn test_decider() {
331 // use Nova as FoldingScheme
332 type N = Nova<
333 Projective,
334 GVar,
335 Projective2,
336 GVar2,
337 CubicFCircuit<Fr>,
338 KZG<'static, Bn254>,
339 Pedersen<Projective2>,
340 false,
341 >;
342 type D = Decider<
343 Projective,
344 GVar,
345 Projective2,
346 GVar2,
347 CubicFCircuit<Fr>,
348 KZG<'static, Bn254>,
349 Pedersen<Projective2>,
350 Groth16<Bn254>, // here we define the Snark to use in the decider
351 N, // here we define the FoldingScheme to use
352 >;
353
354 let mut rng = rand::rngs::OsRng;
355 let poseidon_config = poseidon_canonical_config::<Fr>();
356
357 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
358 let z_0 = vec![Fr::from(3_u32)];
359
360 let preprocessor_param = PreprocessorParam::new(poseidon_config, F_circuit);
361 let nova_params = N::preprocess(&mut rng, &preprocessor_param).unwrap();
362
363 let start = Instant::now();
364 let mut nova = N::init(&nova_params, F_circuit, z_0.clone()).unwrap();
365 println!("Nova initialized, {:?}", start.elapsed());
366
367 // prepare the Decider prover & verifier params
368 let (decider_pp, decider_vp) = D::preprocess(&mut rng, nova_params, nova.clone()).unwrap();
369
370 let start = Instant::now();
371 nova.prove_step(&mut rng, vec![], None).unwrap();
372 println!("prove_step, {:?}", start.elapsed());
373 nova.prove_step(&mut rng, vec![], None).unwrap(); // do a 2nd step
374
375 // decider proof generation
376 let start = Instant::now();
377 let proof = D::prove(rng, decider_pp, nova.clone()).unwrap();
378 println!("Decider prove, {:?}", start.elapsed());
379
380 // decider proof verification
381 let start = Instant::now();
382 let verified = D::verify(
383 decider_vp.clone(),
384 nova.i,
385 nova.z_0.clone(),
386 nova.z_i.clone(),
387 &nova.U_i.get_commitments(),
388 &nova.u_i.get_commitments(),
389 &proof,
390 )
391 .unwrap();
392 assert!(verified);
393 println!("Decider verify, {:?}", start.elapsed());
394
395 // decider proof verification using the deserialized data
396 let verified = D::verify(
397 decider_vp,
398 nova.i,
399 nova.z_0,
400 nova.z_i,
401 &nova.U_i.get_commitments(),
402 &nova.u_i.get_commitments(),
403 &proof,
404 )
405 .unwrap();
406 assert!(verified);
407 }
408
409 // Test to check the serialization and deserialization of diverse Decider related parameters.
410 // This test is the same test as `test_decider` but it serializes values and then uses the
411 // deserialized values to continue the checks.
412 #[test]
413 fn test_decider_serialization() {
414 // use Nova as FoldingScheme
415 type N = Nova<
416 Projective,
417 GVar,
418 Projective2,
419 GVar2,
420 CubicFCircuit<Fr>,
421 KZG<'static, Bn254>,
422 Pedersen<Projective2>,
423 false,
424 >;
425 type D = Decider<
426 Projective,
427 GVar,
428 Projective2,
429 GVar2,
430 CubicFCircuit<Fr>,
431 KZG<'static, Bn254>,
432 Pedersen<Projective2>,
433 Groth16<Bn254>, // here we define the Snark to use in the decider
434 N, // here we define the FoldingScheme to use
435 >;
436
437 let mut rng = rand::rngs::OsRng;
438 let poseidon_config = poseidon_canonical_config::<Fr>();
439
440 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
441 let z_0 = vec![Fr::from(3_u32)];
442
443 let preprocessor_param = PreprocessorParam::new(poseidon_config, F_circuit);
444 let nova_params = N::preprocess(&mut rng, &preprocessor_param).unwrap();
445
446 let start = Instant::now();
447 let nova = N::init(&nova_params, F_circuit, z_0.clone()).unwrap();
448 println!("Nova initialized, {:?}", start.elapsed());
449
450 // prepare the Decider prover & verifier params
451 let (decider_pp, decider_vp) =
452 D::preprocess(&mut rng, nova_params.clone(), nova.clone()).unwrap();
453
454 // serialize the Nova params. These params are the trusted setup of the commitment schemes used
455 // (ie. KZG & Pedersen in this case)
456 let mut nova_pp_serialized = vec![];
457 nova_params
458 .0
459 .serialize_compressed(&mut nova_pp_serialized)
460 .unwrap();
461 let mut nova_vp_serialized = vec![];
462 nova_params
463 .1
464 .serialize_compressed(&mut nova_vp_serialized)
465 .unwrap();
466 // deserialize the Nova params. This would be done by the client reading from a file
467 let nova_pp_deserialized = NovaProverParams::<
468 Projective,
469 Projective2,
470 KZG<'static, Bn254>,
471 Pedersen<Projective2>,
472 >::deserialize_compressed(
473 &mut nova_pp_serialized.as_slice()
474 )
475 .unwrap();
476 let nova_vp_deserialized = <N as FoldingScheme<
477 Projective,
478 Projective2,
479 CubicFCircuit<Fr>,
480 >>::vp_deserialize_with_mode(
481 &mut nova_vp_serialized.as_slice(),
482 ark_serialize::Compress::Yes,
483 ark_serialize::Validate::Yes,
484 (), // fcircuit_params
485 )
486 .unwrap();
487
488 // initialize nova again, but from the deserialized parameters
489 let nova_params = (nova_pp_deserialized, nova_vp_deserialized);
490 let mut nova = N::init(&nova_params, F_circuit, z_0).unwrap();
491
492 let start = Instant::now();
493 nova.prove_step(&mut rng, vec![], None).unwrap();
494 println!("prove_step, {:?}", start.elapsed());
495 nova.prove_step(&mut rng, vec![], None).unwrap(); // do a 2nd step
496
497 // decider proof generation
498 let start = Instant::now();
499 let proof = D::prove(rng, decider_pp, nova.clone()).unwrap();
500 println!("Decider prove, {:?}", start.elapsed());
501
502 // decider proof verification
503 let start = Instant::now();
504 let verified = D::verify(
505 decider_vp.clone(),
506 nova.i,
507 nova.z_0.clone(),
508 nova.z_i.clone(),
509 &nova.U_i.get_commitments(),
510 &nova.u_i.get_commitments(),
511 &proof,
512 )
513 .unwrap();
514 assert!(verified);
515 println!("Decider verify, {:?}", start.elapsed());
516
517 // The rest of this test will serialize the data and deserialize it back, and use it to
518 // verify the proof:
519
520 // serialize the verifier_params, proof and public inputs
521 let mut decider_vp_serialized = vec![];
522 decider_vp
523 .serialize_compressed(&mut decider_vp_serialized)
524 .unwrap();
525 let mut proof_serialized = vec![];
526 proof.serialize_compressed(&mut proof_serialized).unwrap();
527 // serialize the public inputs in a single packet
528 let mut public_inputs_serialized = vec![];
529 nova.i
530 .serialize_compressed(&mut public_inputs_serialized)
531 .unwrap();
532 nova.z_0
533 .serialize_compressed(&mut public_inputs_serialized)
534 .unwrap();
535 nova.z_i
536 .serialize_compressed(&mut public_inputs_serialized)
537 .unwrap();
538
539 // deserialize back the verifier_params, proof and public inputs
540 let decider_vp_deserialized =
541 VerifierParam::<
542 Projective,
543 <KZG<'static, Bn254> as CommitmentScheme<Projective>>::VerifierParams,
544 <Groth16<Bn254> as SNARK<Fr>>::VerifyingKey,
545 >::deserialize_compressed(&mut decider_vp_serialized.as_slice())
546 .unwrap();
547 let proof_deserialized =
548 Proof::<Projective, KZG<'static, Bn254>, Groth16<Bn254>>::deserialize_compressed(
549 &mut proof_serialized.as_slice(),
550 )
551 .unwrap();
552
553 // deserialize the public inputs from the single packet 'public_inputs_serialized'
554 let mut reader = public_inputs_serialized.as_slice();
555 let i_deserialized = Fr::deserialize_compressed(&mut reader).unwrap();
556 let z_0_deserialized = Vec::<Fr>::deserialize_compressed(&mut reader).unwrap();
557 let z_i_deserialized = Vec::<Fr>::deserialize_compressed(&mut reader).unwrap();
558
559 // decider proof verification using the deserialized data
560 let verified = D::verify(
561 decider_vp_deserialized,
562 i_deserialized,
563 z_0_deserialized,
564 z_i_deserialized,
565 &nova.U_i.get_commitments(),
566 &nova.u_i.get_commitments(),
567 &proof_deserialized,
568 )
569 .unwrap();
570 assert!(verified);
571 }
572}