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::PreprocessorParam;
238 use crate::folding::nova::decider_eth::VerifierParam;
239 use crate::frontend::utils::CubicFCircuit;
240 use crate::transcript::poseidon::poseidon_canonical_config;
241
242 #[test]
243 fn test_decider() {
244 const MU: usize = 1;
245 const NU: usize = 1;
246 // use HyperNova as FoldingScheme
247 type HN = HyperNova<
248 Projective,
249 GVar,
250 Projective2,
251 GVar2,
252 CubicFCircuit<Fr>,
253 KZG<'static, Bn254>,
254 Pedersen<Projective2>,
255 MU,
256 NU,
257 false,
258 >;
259 type D = Decider<
260 Projective,
261 GVar,
262 Projective2,
263 GVar2,
264 CubicFCircuit<Fr>,
265 KZG<'static, Bn254>,
266 Pedersen<Projective2>,
267 Groth16<Bn254>, // here we define the Snark to use in the decider
268 HN, // here we define the FoldingScheme to use
269 MU,
270 NU,
271 >;
272
273 let mut rng = rand::rngs::OsRng;
274 let poseidon_config = poseidon_canonical_config::<Fr>();
275
276 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
277 let z_0 = vec![Fr::from(3_u32)];
278
279 let prep_param = PreprocessorParam::new(poseidon_config, F_circuit);
280 let hypernova_params = HN::preprocess(&mut rng, &prep_param).unwrap();
281
282 let mut hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
283 hypernova
284 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
285 .unwrap();
286 hypernova
287 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
288 .unwrap(); // do a 2nd step
289
290 // prepare the Decider prover & verifier params
291 let (decider_pp, decider_vp) =
292 D::preprocess(&mut rng, hypernova_params, hypernova.clone()).unwrap();
293
294 // decider proof generation
295 let proof = D::prove(rng, decider_pp, hypernova.clone()).unwrap();
296
297 // decider proof verification
298 let verified = D::verify(
299 decider_vp,
300 hypernova.i,
301 hypernova.z_0,
302 hypernova.z_i,
303 &(),
304 &(),
305 &proof,
306 )
307 .unwrap();
308 assert!(verified);
309 }
310
311 #[test]
312 fn test_decider_serialization() {
313 const MU: usize = 1;
314 const NU: usize = 1;
315 // use HyperNova as FoldingScheme
316 type HN = HyperNova<
317 Projective,
318 GVar,
319 Projective2,
320 GVar2,
321 CubicFCircuit<Fr>,
322 KZG<'static, Bn254>,
323 Pedersen<Projective2>,
324 MU,
325 NU,
326 false,
327 >;
328 type D = Decider<
329 Projective,
330 GVar,
331 Projective2,
332 GVar2,
333 CubicFCircuit<Fr>,
334 KZG<'static, Bn254>,
335 Pedersen<Projective2>,
336 Groth16<Bn254>, // here we define the Snark to use in the decider
337 HN, // here we define the FoldingScheme to use
338 MU,
339 NU,
340 >;
341
342 let mut rng = ark_std::test_rng();
343 let poseidon_config = poseidon_canonical_config::<Fr>();
344
345 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
346 let z_0 = vec![Fr::from(3_u32)];
347
348 let prep_param = PreprocessorParam::new(poseidon_config.clone(), F_circuit);
349 let hypernova_params = HN::preprocess(&mut rng, &prep_param).unwrap();
350
351 let hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
352
353 let mut rng = rand::rngs::OsRng;
354
355 // prepare the Decider prover & verifier params
356 let (decider_pp, decider_vp) =
357 D::preprocess(&mut rng, hypernova_params.clone(), hypernova.clone()).unwrap();
358
359 let mut hypernova_pp_serialized = vec![];
360 hypernova_params
361 .0
362 .clone()
363 .serialize_compressed(&mut hypernova_pp_serialized)
364 .unwrap();
365 let mut hypernova_vp_serialized = vec![];
366 hypernova_params
367 .1
368 .clone()
369 .serialize_compressed(&mut hypernova_vp_serialized)
370 .unwrap();
371
372 let hypernova_pp_deserialized = HN::pp_deserialize_with_mode(
373 hypernova_pp_serialized.as_slice(),
374 Compress::Yes,
375 Validate::No,
376 (), // FCircuit's Params
377 )
378 .unwrap();
379
380 let hypernova_vp_deserialized = HN::vp_deserialize_with_mode(
381 hypernova_vp_serialized.as_slice(),
382 Compress::Yes,
383 Validate::No,
384 (), // FCircuit's Params
385 )
386 .unwrap();
387
388 let hypernova_params = (hypernova_pp_deserialized, hypernova_vp_deserialized);
389 let mut hypernova = HN::init(&hypernova_params, F_circuit, z_0.clone()).unwrap();
390
391 hypernova
392 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
393 .unwrap();
394 hypernova
395 .prove_step(&mut rng, vec![], Some((vec![], vec![])))
396 .unwrap();
397
398 // decider proof generation
399 let proof = D::prove(rng, decider_pp, hypernova.clone()).unwrap();
400
401 let verified = D::verify(
402 decider_vp.clone(),
403 hypernova.i,
404 hypernova.z_0.clone(),
405 hypernova.z_i.clone(),
406 &(),
407 &(),
408 &proof,
409 )
410 .unwrap();
411 assert!(verified);
412
413 // The rest of this test will serialize the data and deserialize it back, and use it to
414 // verify the proof:
415
416 // serialize the verifier_params, proof and public inputs
417 let mut decider_vp_serialized = vec![];
418 decider_vp
419 .serialize_compressed(&mut decider_vp_serialized)
420 .unwrap();
421 let mut proof_serialized = vec![];
422 proof.serialize_compressed(&mut proof_serialized).unwrap();
423 // serialize the public inputs in a single packet
424 let mut public_inputs_serialized = vec![];
425 hypernova
426 .i
427 .serialize_compressed(&mut public_inputs_serialized)
428 .unwrap();
429 hypernova
430 .z_0
431 .serialize_compressed(&mut public_inputs_serialized)
432 .unwrap();
433 hypernova
434 .z_i
435 .serialize_compressed(&mut public_inputs_serialized)
436 .unwrap();
437 hypernova
438 .U_i
439 .serialize_compressed(&mut public_inputs_serialized)
440 .unwrap();
441 hypernova
442 .u_i
443 .serialize_compressed(&mut public_inputs_serialized)
444 .unwrap();
445
446 // deserialize back the verifier_params, proof and public inputs
447 let decider_vp_deserialized =
448 VerifierParam::<
449 Projective,
450 <KZG<'static, Bn254> as CommitmentScheme<Projective>>::VerifierParams,
451 <Groth16<Bn254> as SNARK<Fr>>::VerifyingKey,
452 >::deserialize_compressed(&mut decider_vp_serialized.as_slice())
453 .unwrap();
454
455 let proof_deserialized =
456 Proof::<Projective, KZG<'static, Bn254>, Groth16<Bn254>>::deserialize_compressed(
457 &mut proof_serialized.as_slice(),
458 )
459 .unwrap();
460
461 let mut reader = public_inputs_serialized.as_slice();
462 let i_deserialized = Fr::deserialize_compressed(&mut reader).unwrap();
463 let z_0_deserialized = Vec::<Fr>::deserialize_compressed(&mut reader).unwrap();
464 let z_i_deserialized = Vec::<Fr>::deserialize_compressed(&mut reader).unwrap();
465 let _U_i = LCCCS::<Projective>::deserialize_compressed(&mut reader).unwrap();
466 let _u_i = CCCS::<Projective>::deserialize_compressed(&mut reader).unwrap();
467
468 let verified = D::verify(
469 decider_vp_deserialized,
470 i_deserialized,
471 z_0_deserialized.clone(),
472 z_i_deserialized.clone(),
473 &(),
474 &(),
475 &proof_deserialized,
476 )
477 .unwrap();
478 assert!(verified);
479 }
480}