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