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