sonobe/folding-schemes/src/folding/hypernova/decider_eth.rs
folding-schemes/src/folding/hypernova/decider_eth.rsRaw
1/// This file implements the HyperNova's onchain (Ethereum's EVM) decider.
2use ark_crypto_primitives::sponge::Absorb;
3use ark_ec::{CurveGroup, Group};
4use ark_ff::PrimeField;
5use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
6use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
7use ark_snark::SNARK;
8use ark_std::rand::{CryptoRng, RngCore};
9use ark_std::{One, Zero};
10use core::marker::PhantomData;
11
12pub use super::decider_eth_circuit::DeciderEthCircuit;
13use super::{lcccs::LCCCS, HyperNova};
14use crate::commitment::{
15 kzg::Proof as KZGProof, pedersen::Params as PedersenParams, CommitmentScheme,
16};
17use crate::folding::circuits::{nonnative::affine::NonNativeAffineVar, CF2};
18use crate::folding::nova::decider_eth::VerifierParam;
19use crate::frontend::FCircuit;
20use crate::Error;
21use crate::{Decider as DeciderTrait, FoldingScheme};
22
23#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
24pub struct Proof<C1, CS1, S>
25where
26 C1: CurveGroup,
27 CS1: CommitmentScheme<C1, ProverChallenge = C1::ScalarField, Challenge = C1::ScalarField>,
28 S: SNARK<C1::ScalarField>,
29{
30 snark_proof: S::Proof,
31 kzg_proof: CS1::Proof,
32 // rho used at the last fold, U_{i+1}=NIMFS.V(rho, U_i, u_i), it is checked in-circuit
33 rho: C1::ScalarField,
34 U_i1: LCCCS<C1>, // U_{i+1}, which is checked in-circuit
35 // the KZG challenge is provided by the prover, but in-circuit it is checked to match
36 // the in-circuit computed computed one.
37 kzg_challenge: C1::ScalarField,
38}
39
40/// Onchain Decider, for ethereum use cases
41#[derive(Clone, Debug)]
42pub struct Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS, const MU: usize, const NU: usize> {
43 _c1: PhantomData<C1>,
44 _gc1: PhantomData<GC1>,
45 _c2: PhantomData<C2>,
46 _gc2: PhantomData<GC2>,
47 _fc: PhantomData<FC>,
48 _cs1: PhantomData<CS1>,
49 _cs2: PhantomData<CS2>,
50 _s: PhantomData<S>,
51 _fs: PhantomData<FS>,
52}
53
54impl<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS, const MU: usize, const NU: usize>
55 DeciderTrait<C1, C2, FC, FS> for Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS, MU, NU>
56where
57 C1: CurveGroup,
58 C2: CurveGroup,
59 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
60 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
61 FC: FCircuit<C1::ScalarField>,
62 // CS1 is a KZG commitment, where challenge is C1::Fr elem
63 CS1: CommitmentScheme<
64 C1,
65 ProverChallenge = C1::ScalarField,
66 Challenge = C1::ScalarField,
67 Proof = KZGProof<C1>,
68 >,
69 // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
70 CS2: CommitmentScheme<C2, ProverParams = PedersenParams<C2>>,
71 S: SNARK<C1::ScalarField>,
72 FS: FoldingScheme<C1, C2, FC>,
73 <C1 as CurveGroup>::BaseField: PrimeField,
74 <C2 as CurveGroup>::BaseField: PrimeField,
75 <C1 as Group>::ScalarField: Absorb,
76 <C2 as Group>::ScalarField: Absorb,
77 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
78 for<'b> &'b GC1: GroupOpsBounds<'b, C1, GC1>,
79 for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
80 // constrain FS into HyperNova, since this is a Decider specifically for HyperNova
81 HyperNova<C1, GC1, C2, GC2, FC, CS1, CS2, MU, NU, false>: From<FS>,
82 crate::folding::hypernova::ProverParams<C1, C2, CS1, CS2, false>:
83 From<<FS as FoldingScheme<C1, C2, FC>>::ProverParam>,
84 crate::folding::hypernova::VerifierParams<C1, C2, CS1, CS2, false>:
85 From<<FS as FoldingScheme<C1, C2, FC>>::VerifierParam>,
86{
87 type PreprocessorParam = (FS::ProverParam, FS::VerifierParam);
88 type ProverParam = (S::ProvingKey, CS1::ProverParams);
89 type Proof = Proof<C1, CS1, S>;
90 type VerifierParam = VerifierParam<C1, CS1::VerifierParams, S::VerifyingKey>;
91 type PublicInput = Vec<C1::ScalarField>;
92 type CommittedInstance = ();
93
94 fn preprocess(
95 mut rng: impl RngCore + CryptoRng,
96 prep_param: Self::PreprocessorParam,
97 fs: FS,
98 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
99 let circuit =
100 DeciderEthCircuit::<C1, GC1, C2, GC2, CS1, CS2>::from_hypernova::<FC, MU, NU>(
101 fs.into(),
102 )
103 .unwrap();
104
105 // get the Groth16 specific setup for the circuit
106 let (g16_pk, g16_vk) = S::circuit_specific_setup(circuit, &mut rng).unwrap();
107
108 // get the FoldingScheme prover & verifier params from HyperNova
109 #[allow(clippy::type_complexity)]
110 let hypernova_pp: <HyperNova<C1, GC1, C2, GC2, FC, CS1, CS2, MU, NU, false> as FoldingScheme<
111 C1,
112 C2,
113 FC,
114 >>::ProverParam = prep_param.0.into();
115 #[allow(clippy::type_complexity)]
116 let hypernova_vp: <HyperNova<C1, GC1, C2, GC2, FC, CS1, CS2, MU, NU, false> as FoldingScheme<
117 C1,
118 C2,
119 FC,
120 >>::VerifierParam = prep_param.1.into();
121 let pp_hash = hypernova_vp.pp_hash()?;
122
123 let pp = (g16_pk, hypernova_pp.cs_pp);
124
125 let vp = VerifierParam {
126 pp_hash,
127 snark_vp: g16_vk,
128 cs_vp: hypernova_vp.cs_vp,
129 };
130 Ok((pp, vp))
131 }
132
133 fn prove(
134 mut rng: impl RngCore + CryptoRng,
135 pp: Self::ProverParam,
136 folding_scheme: FS,
137 ) -> Result<Self::Proof, Error> {
138 let (snark_pk, cs_pk): (S::ProvingKey, CS1::ProverParams) = pp;
139
140 let circuit = DeciderEthCircuit::<C1, GC1, C2, GC2, CS1, CS2>::from_hypernova::<FC, MU, NU>(
141 folding_scheme.into(),
142 )?;
143
144 let snark_proof = S::prove(&snark_pk, circuit.clone(), &mut rng)
145 .map_err(|e| Error::Other(e.to_string()))?;
146
147 // Notice that since the `circuit` has been constructed at the `from_hypernova` call, which
148 // in case of failure it would have returned an error there, the next two unwraps should
149 // never reach an error.
150 let rho_Fr = circuit.rho.ok_or(Error::Empty)?;
151 let W_i1 = circuit.W_i1.ok_or(Error::Empty)?;
152
153 // get the challenges that have been already computed when preparing the circuit inputs in
154 // the above `from_hypernova` call
155 let challenge_W = circuit
156 .kzg_challenge
157 .ok_or(Error::MissingValue("kzg_challenge".to_string()))?;
158
159 // generate KZG proofs
160 let U_cmW_proof = CS1::prove_with_challenge(
161 &cs_pk,
162 challenge_W,
163 &W_i1.w,
164 &C1::ScalarField::zero(),
165 None,
166 )?;
167
168 Ok(Self::Proof {
169 snark_proof,
170 kzg_proof: U_cmW_proof,
171 rho: rho_Fr,
172 U_i1: circuit.U_i1.ok_or(Error::Empty)?,
173 kzg_challenge: challenge_W,
174 })
175 }
176
177 fn verify(
178 vp: Self::VerifierParam,
179 i: C1::ScalarField,
180 z_0: Vec<C1::ScalarField>,
181 z_i: Vec<C1::ScalarField>,
182 // we don't use the instances at the verifier level, since we check them in-circuit
183 _running_instance: &Self::CommittedInstance,
184 _incoming_instance: &Self::CommittedInstance,
185 proof: &Self::Proof,
186 ) -> Result<bool, Error> {
187 if i <= C1::ScalarField::one() {
188 return Err(Error::NotEnoughSteps);
189 }
190
191 let (pp_hash, snark_vk, cs_vk): (C1::ScalarField, S::VerifyingKey, CS1::VerifierParams) =
192 (vp.pp_hash, vp.snark_vp, vp.cs_vp);
193
194 // Note: the NIMFS proof is checked inside the DeciderEthCircuit, which ensures that the
195 // 'proof.U_i1' is correctly computed
196
197 let (cmC_x, cmC_y) = NonNativeAffineVar::inputize(proof.U_i1.C)?;
198
199 let public_input: Vec<C1::ScalarField> = [
200 vec![pp_hash, i],
201 z_0,
202 z_i,
203 // U_i+1:
204 cmC_x,
205 cmC_y,
206 vec![proof.U_i1.u],
207 proof.U_i1.x.clone(),
208 proof.U_i1.r_x.clone(),
209 proof.U_i1.v.clone(),
210 vec![proof.kzg_challenge, proof.kzg_proof.eval, proof.rho],
211 ]
212 .concat();
213
214 let snark_v = S::verify(&snark_vk, &public_input, &proof.snark_proof)
215 .map_err(|e| Error::Other(e.to_string()))?;
216 if !snark_v {
217 return Err(Error::SNARKVerificationFail);
218 }
219
220 // we're at the Ethereum EVM case, so the CS1 is KZG commitments
221 CS1::verify_with_challenge(&cs_vk, proof.kzg_challenge, &proof.U_i1.C, &proof.kzg_proof)?;
222
223 Ok(true)
224 }
225}
226
227#[cfg(test)]
228pub mod tests {
229 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
230 use ark_groth16::Groth16;
231 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
232 use ark_serialize::{Compress, Validate};
233
234 use super::*;
235 use crate::commitment::{kzg::KZG, pedersen::Pedersen};
236 use crate::folding::hypernova::cccs::CCCS;
237 use crate::folding::hypernova::{
238 PreprocessorParam, ProverParams, VerifierParams as HyperNovaVerifierParams,
239 };
240 use crate::folding::nova::decider_eth::VerifierParam;
241 use crate::frontend::utils::CubicFCircuit;
242 use crate::transcript::poseidon::poseidon_canonical_config;
243
244 #[test]
245 fn test_decider() {
246 const MU: usize = 1;
247 const NU: usize = 1;
248 // use HyperNova as FoldingScheme
249 type HN = HyperNova<
250 Projective,
251 GVar,
252 Projective2,
253 GVar2,
254 CubicFCircuit<Fr>,
255 KZG<'static, Bn254>,
256 Pedersen<Projective2>,
257 MU,
258 NU,
259 false,
260 >;
261 type D = Decider<
262 Projective,
263 GVar,
264 Projective2,
265 GVar2,
266 CubicFCircuit<Fr>,
267 KZG<'static, Bn254>,
268 Pedersen<Projective2>,
269 Groth16<Bn254>, // here we define the Snark to use in the decider
270 HN, // here we define the FoldingScheme to use
271 MU,
272 NU,
273 >;
274
275 let mut rng = rand::rngs::OsRng;
276 let poseidon_config = poseidon_canonical_config::<Fr>();
277
278 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
279 let z_0 = vec![Fr::from(3_u32)];
280
281 let prep_param = PreprocessorParam::new(poseidon_config, F_circuit);
282 let hypernova_params = HN::preprocess(&mut rng, &prep_param).unwrap();
283
284 let mut hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
285 hypernova
286 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
287 .unwrap();
288 hypernova
289 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
290 .unwrap(); // do a 2nd step
291
292 // prepare the Decider prover & verifier params
293 let (decider_pp, decider_vp) =
294 D::preprocess(&mut rng, hypernova_params, hypernova.clone()).unwrap();
295
296 // decider proof generation
297 let proof = D::prove(rng, decider_pp, hypernova.clone()).unwrap();
298
299 // decider proof verification
300 let verified = D::verify(
301 decider_vp,
302 hypernova.i,
303 hypernova.z_0,
304 hypernova.z_i,
305 &(),
306 &(),
307 &proof,
308 )
309 .unwrap();
310 assert!(verified);
311 }
312
313 #[test]
314 fn test_decider_serialization() {
315 const MU: usize = 1;
316 const NU: usize = 1;
317 // use HyperNova as FoldingScheme
318 type HN = HyperNova<
319 Projective,
320 GVar,
321 Projective2,
322 GVar2,
323 CubicFCircuit<Fr>,
324 KZG<'static, Bn254>,
325 Pedersen<Projective2>,
326 MU,
327 NU,
328 false,
329 >;
330 type D = Decider<
331 Projective,
332 GVar,
333 Projective2,
334 GVar2,
335 CubicFCircuit<Fr>,
336 KZG<'static, Bn254>,
337 Pedersen<Projective2>,
338 Groth16<Bn254>, // here we define the Snark to use in the decider
339 HN, // here we define the FoldingScheme to use
340 MU,
341 NU,
342 >;
343
344 let mut rng = ark_std::test_rng();
345 let poseidon_config = poseidon_canonical_config::<Fr>();
346
347 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
348 let z_0 = vec![Fr::from(3_u32)];
349
350 let prep_param = PreprocessorParam::new(poseidon_config.clone(), F_circuit);
351 let hypernova_params = HN::preprocess(&mut rng, &prep_param).unwrap();
352
353 let hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
354
355 let mut rng = rand::rngs::OsRng;
356
357 // prepare the Decider prover & verifier params
358 let (decider_pp, decider_vp) =
359 D::preprocess(&mut rng, hypernova_params.clone(), hypernova.clone()).unwrap();
360
361 let mut hypernova_pp_serialized = vec![];
362 hypernova_params
363 .0
364 .clone()
365 .serialize_compressed(&mut hypernova_pp_serialized)
366 .unwrap();
367 let mut hypernova_vp_serialized = vec![];
368 hypernova_params
369 .1
370 .clone()
371 .serialize_compressed(&mut hypernova_vp_serialized)
372 .unwrap();
373
374 let hypernova_pp_deserialized = ProverParams::<
375 Projective,
376 Projective2,
377 KZG<'static, Bn254>,
378 Pedersen<Projective2>,
379 false,
380 >::deserialize_prover_params(
381 hypernova_pp_serialized.as_slice(),
382 Compress::Yes,
383 Validate::No,
384 &hypernova_params.0.ccs,
385 &poseidon_config,
386 )
387 .unwrap();
388
389 let hypernova_vp_deserialized = HyperNovaVerifierParams::<
390 Projective,
391 Projective2,
392 KZG<'static, Bn254>,
393 Pedersen<Projective2>,
394 false,
395 >::deserialize_verifier_params(
396 hypernova_vp_serialized.as_slice(),
397 Compress::Yes,
398 Validate::No,
399 &hypernova_params.0.ccs.unwrap(),
400 &poseidon_config,
401 )
402 .unwrap();
403
404 let hypernova_params = (hypernova_pp_deserialized, hypernova_vp_deserialized);
405 let mut hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
406
407 hypernova
408 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
409 .unwrap();
410 hypernova
411 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
412 .unwrap();
413
414 // decider proof generation
415 let proof = D::prove(rng, decider_pp, hypernova.clone()).unwrap();
416
417 let verified = D::verify(
418 decider_vp.clone(),
419 hypernova.i.clone(),
420 hypernova.z_0.clone(),
421 hypernova.z_i.clone(),
422 &(),
423 &(),
424 &proof,
425 )
426 .unwrap();
427 assert!(verified);
428
429 // The rest of this test will serialize the data and deserialize it back, and use it to
430 // verify the proof:
431
432 // serialize the verifier_params, proof and public inputs
433 let mut decider_vp_serialized = vec![];
434 decider_vp
435 .serialize_compressed(&mut decider_vp_serialized)
436 .unwrap();
437 let mut proof_serialized = vec![];
438 proof.serialize_compressed(&mut proof_serialized).unwrap();
439 // serialize the public inputs in a single packet
440 let mut public_inputs_serialized = vec![];
441 hypernova
442 .i
443 .serialize_compressed(&mut public_inputs_serialized)
444 .unwrap();
445 hypernova
446 .z_0
447 .serialize_compressed(&mut public_inputs_serialized)
448 .unwrap();
449 hypernova
450 .z_i
451 .serialize_compressed(&mut public_inputs_serialized)
452 .unwrap();
453 hypernova
454 .U_i
455 .serialize_compressed(&mut public_inputs_serialized)
456 .unwrap();
457 hypernova
458 .u_i
459 .serialize_compressed(&mut public_inputs_serialized)
460 .unwrap();
461
462 // deserialize back the verifier_params, proof and public inputs
463 let decider_vp_deserialized =
464 VerifierParam::<
465 Projective,
466 <KZG<'static, Bn254> as CommitmentScheme<Projective>>::VerifierParams,
467 <Groth16<Bn254> as SNARK<Fr>>::VerifyingKey,
468 >::deserialize_compressed(&mut decider_vp_serialized.as_slice())
469 .unwrap();
470
471 let proof_deserialized =
472 Proof::<Projective, KZG<'static, Bn254>, Groth16<Bn254>>::deserialize_compressed(
473 &mut proof_serialized.as_slice(),
474 )
475 .unwrap();
476
477 let mut reader = public_inputs_serialized.as_slice();
478 let i_deserialized = Fr::deserialize_compressed(&mut reader).unwrap();
479 let z_0_deserialized = Vec::<Fr>::deserialize_compressed(&mut reader).unwrap();
480 let z_i_deserialized = Vec::<Fr>::deserialize_compressed(&mut reader).unwrap();
481 let _U_i = LCCCS::<Projective>::deserialize_compressed(&mut reader).unwrap();
482 let _u_i = CCCS::<Projective>::deserialize_compressed(&mut reader).unwrap();
483
484 let verified = D::verify(
485 decider_vp_deserialized,
486 i_deserialized.clone(),
487 z_0_deserialized.clone(),
488 z_i_deserialized.clone(),
489 &(),
490 &(),
491 &proof_deserialized,
492 )
493 .unwrap();
494 assert!(verified);
495 }
496}