sonobe/folding-schemes/src/folding/nova/decider_eth.rs
folding-schemes/src/folding/nova/decider_eth.rsRaw
1/// This file implements the onchain (Ethereum's EVM) decider.
2use ark_bn254::Bn254;
3use ark_crypto_primitives::sponge::Absorb;
4use ark_ec::{AffineRepr, CurveGroup, Group};
5use ark_ff::{BigInteger, PrimeField};
6use ark_groth16::Groth16;
7use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
8use ark_snark::SNARK;
9use ark_std::rand::{CryptoRng, RngCore};
10use ark_std::{One, Zero};
11use core::marker::PhantomData;
12
13pub use super::decider_eth_circuit::{DeciderEthCircuit, KZGChallengesGadget};
14use super::{nifs::NIFS, CommittedInstance, Nova};
15use crate::commitment::{
16 kzg::{Proof as KZGProof, KZG},
17 pedersen::Params as PedersenParams,
18 CommitmentScheme,
19};
20use crate::folding::circuits::{nonnative::affine::NonNativeAffineVar, CF2};
21use crate::frontend::FCircuit;
22use crate::Error;
23use crate::{Decider as DeciderTrait, FoldingScheme};
24
25#[derive(Debug, Clone, Eq, PartialEq)]
26pub struct Proof<C1, CS1, S>
27where
28 C1: CurveGroup,
29 CS1: CommitmentScheme<C1, ProverChallenge = C1::ScalarField, Challenge = C1::ScalarField>,
30 S: SNARK<C1::ScalarField>,
31{
32 snark_proof: S::Proof,
33 kzg_proofs: [CS1::Proof; 2],
34 // cmT and r are values for the last fold, U_{i+1}=NIFS.V(r, U_i, u_i, cmT), and they are
35 // checked in-circuit
36 cmT: C1,
37 r: C1::ScalarField,
38 // the KZG challenges are provided by the prover, but in-circuit they are checked to match
39 // the in-circuit computed computed ones.
40 kzg_challenges: [C1::ScalarField; 2],
41}
42
43/// Onchain Decider, for ethereum use cases
44#[derive(Clone, Debug)]
45pub struct Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS> {
46 _c1: PhantomData<C1>,
47 _gc1: PhantomData<GC1>,
48 _c2: PhantomData<C2>,
49 _gc2: PhantomData<GC2>,
50 _fc: PhantomData<FC>,
51 _cs1: PhantomData<CS1>,
52 _cs2: PhantomData<CS2>,
53 _s: PhantomData<S>,
54 _fs: PhantomData<FS>,
55}
56
57impl<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS> DeciderTrait<C1, C2, FC, FS>
58 for Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS>
59where
60 C1: CurveGroup,
61 C2: CurveGroup,
62 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
63 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
64 FC: FCircuit<C1::ScalarField>,
65 // CS1 is a KZG commitment, where challenge is C1::Fr elem
66 CS1: CommitmentScheme<
67 C1,
68 ProverChallenge = C1::ScalarField,
69 Challenge = C1::ScalarField,
70 Proof = KZGProof<C1>,
71 >,
72 // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
73 CS2: CommitmentScheme<C2, ProverParams = PedersenParams<C2>>,
74 S: SNARK<C1::ScalarField>,
75 FS: FoldingScheme<C1, C2, FC>,
76 <C1 as CurveGroup>::BaseField: PrimeField,
77 <C2 as CurveGroup>::BaseField: PrimeField,
78 <C1 as Group>::ScalarField: Absorb,
79 <C2 as Group>::ScalarField: Absorb,
80 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
81 for<'b> &'b GC1: GroupOpsBounds<'b, C1, GC1>,
82 for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
83 // constrain FS into Nova, since this is a Decider specifically for Nova
84 Nova<C1, GC1, C2, GC2, FC, CS1, CS2>: From<FS>,
85 crate::folding::nova::ProverParams<C1, C2, CS1, CS2>:
86 From<<FS as FoldingScheme<C1, C2, FC>>::ProverParam>,
87 crate::folding::nova::VerifierParams<C1, C2, CS1, CS2>:
88 From<<FS as FoldingScheme<C1, C2, FC>>::VerifierParam>,
89{
90 type PreprocessorParam = (FS::ProverParam, FS::VerifierParam);
91 type ProverParam = (S::ProvingKey, CS1::ProverParams);
92 type Proof = Proof<C1, CS1, S>;
93 type VerifierParam = (S::VerifyingKey, CS1::VerifierParams);
94 type PublicInput = Vec<C1::ScalarField>;
95 type CommittedInstance = CommittedInstance<C1>;
96
97 fn preprocess(
98 mut rng: impl RngCore + CryptoRng,
99 prep_param: &Self::PreprocessorParam,
100 fs: FS,
101 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
102 let circuit =
103 DeciderEthCircuit::<C1, GC1, C2, GC2, CS1, CS2>::from_nova::<FC>(fs.into()).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 Nova
109 #[allow(clippy::type_complexity)]
110 let nova_pp:
111 <Nova<C1, GC1, C2, GC2, FC, CS1, CS2> as FoldingScheme<C1, C2, FC>>::ProverParam =
112 prep_param.0.clone().into()
113 ;
114 #[allow(clippy::type_complexity)]
115 let nova_vp:
116 <Nova<C1, GC1, C2, GC2, FC, CS1, CS2> as FoldingScheme<C1, C2, FC>>::VerifierParam =
117 prep_param.1.clone().into();
118
119 let pp = (g16_pk, nova_pp.cs_pp);
120 let vp = (g16_vk, nova_vp.cs_vp);
121 Ok((pp, vp))
122 }
123
124 fn prove(
125 mut rng: impl RngCore + CryptoRng,
126 pp: Self::ProverParam,
127 folding_scheme: FS,
128 ) -> Result<Self::Proof, Error> {
129 let (snark_pk, cs_pk): (S::ProvingKey, CS1::ProverParams) = pp;
130
131 let circuit = DeciderEthCircuit::<C1, GC1, C2, GC2, CS1, CS2>::from_nova::<FC>(
132 folding_scheme.into(),
133 )?;
134
135 let snark_proof = S::prove(&snark_pk, circuit.clone(), &mut rng)
136 .map_err(|e| Error::Other(e.to_string()))?;
137
138 let cmT = circuit.cmT.unwrap();
139 let r_Fr = circuit.r.unwrap();
140 let W_i1 = circuit.W_i1.unwrap();
141
142 // get the challenges that have been already computed when preparing the circuit inputs in
143 // the above `from_nova` call
144 let challenge_W = circuit
145 .kzg_c_W
146 .ok_or(Error::MissingValue("kzg_c_W".to_string()))?;
147 let challenge_E = circuit
148 .kzg_c_E
149 .ok_or(Error::MissingValue("kzg_c_E".to_string()))?;
150
151 // generate KZG proofs
152 let U_cmW_proof = CS1::prove_with_challenge(
153 &cs_pk,
154 challenge_W,
155 &W_i1.W,
156 &C1::ScalarField::zero(),
157 None,
158 )?;
159 let U_cmE_proof = CS1::prove_with_challenge(
160 &cs_pk,
161 challenge_E,
162 &W_i1.E,
163 &C1::ScalarField::zero(),
164 None,
165 )?;
166
167 Ok(Self::Proof {
168 snark_proof,
169 kzg_proofs: [U_cmW_proof, U_cmE_proof],
170 cmT,
171 r: r_Fr,
172 kzg_challenges: [challenge_W, challenge_E],
173 })
174 }
175
176 fn verify(
177 vp: Self::VerifierParam,
178 i: C1::ScalarField,
179 z_0: Vec<C1::ScalarField>,
180 z_i: Vec<C1::ScalarField>,
181 running_instance: &Self::CommittedInstance,
182 incoming_instance: &Self::CommittedInstance,
183 proof: &Self::Proof,
184 ) -> Result<bool, Error> {
185 if i <= C1::ScalarField::one() {
186 return Err(Error::NotEnoughSteps);
187 }
188
189 let (snark_vk, cs_vk): (S::VerifyingKey, CS1::VerifierParams) = vp;
190
191 // compute U = U_{d+1}= NIFS.V(U_d, u_d, cmT)
192 let U = NIFS::<C1, CS1>::verify(proof.r, running_instance, incoming_instance, &proof.cmT);
193
194 let (cmE_x, cmE_y) = NonNativeAffineVar::inputize(U.cmE)?;
195 let (cmW_x, cmW_y) = NonNativeAffineVar::inputize(U.cmW)?;
196 let (cmT_x, cmT_y) = NonNativeAffineVar::inputize(proof.cmT)?;
197
198 let public_input: Vec<C1::ScalarField> = vec![
199 vec![i],
200 z_0,
201 z_i,
202 vec![U.u],
203 U.x.clone(),
204 cmE_x,
205 cmE_y,
206 cmW_x,
207 cmW_y,
208 proof.kzg_challenges.to_vec(),
209 vec![
210 proof.kzg_proofs[0].eval, // eval_W
211 proof.kzg_proofs[1].eval, // eval_E
212 ],
213 cmT_x,
214 cmT_y,
215 vec![proof.r],
216 ]
217 .concat();
218
219 let snark_v = S::verify(&snark_vk, &public_input, &proof.snark_proof)
220 .map_err(|e| Error::Other(e.to_string()))?;
221 if !snark_v {
222 return Err(Error::SNARKVerificationFail);
223 }
224
225 // we're at the Ethereum EVM case, so the CS1 is KZG commitments
226 CS1::verify_with_challenge(
227 &cs_vk,
228 proof.kzg_challenges[0],
229 &U.cmW,
230 &proof.kzg_proofs[0],
231 )?;
232 CS1::verify_with_challenge(
233 &cs_vk,
234 proof.kzg_challenges[1],
235 &U.cmE,
236 &proof.kzg_proofs[1],
237 )?;
238
239 Ok(true)
240 }
241}
242
243/// Prepares solidity calldata for calling the NovaDecider contract
244pub fn prepare_calldata(
245 function_signature_check: [u8; 4],
246 i: ark_bn254::Fr,
247 z_0: Vec<ark_bn254::Fr>,
248 z_i: Vec<ark_bn254::Fr>,
249 running_instance: &CommittedInstance<ark_bn254::G1Projective>,
250 incoming_instance: &CommittedInstance<ark_bn254::G1Projective>,
251 proof: Proof<ark_bn254::G1Projective, KZG<'static, Bn254>, Groth16<Bn254>>,
252) -> Result<Vec<u8>, Error> {
253 Ok(vec![
254 function_signature_check.to_vec(),
255 i.into_bigint().to_bytes_be(), // i
256 z_0.iter()
257 .flat_map(|v| v.into_bigint().to_bytes_be())
258 .collect::<Vec<u8>>(), // z_0
259 z_i.iter()
260 .flat_map(|v| v.into_bigint().to_bytes_be())
261 .collect::<Vec<u8>>(), // z_i
262 point_to_eth_format(running_instance.cmW.into_affine())?, // U_i_cmW
263 point_to_eth_format(running_instance.cmE.into_affine())?, // U_i_cmE
264 running_instance.u.into_bigint().to_bytes_be(), // U_i_u
265 incoming_instance.u.into_bigint().to_bytes_be(), // u_i_u
266 proof.r.into_bigint().to_bytes_be(), // r
267 running_instance
268 .x
269 .iter()
270 .flat_map(|v| v.into_bigint().to_bytes_be())
271 .collect::<Vec<u8>>(), // U_i_x
272 point_to_eth_format(incoming_instance.cmW.into_affine())?, // u_i_cmW
273 incoming_instance
274 .x
275 .iter()
276 .flat_map(|v| v.into_bigint().to_bytes_be())
277 .collect::<Vec<u8>>(), // u_i_x
278 point_to_eth_format(proof.cmT.into_affine())?, // cmT
279 point_to_eth_format(proof.snark_proof.a)?, // pA
280 point2_to_eth_format(proof.snark_proof.b)?, // pB
281 point_to_eth_format(proof.snark_proof.c)?, // pC
282 proof.kzg_challenges[0].into_bigint().to_bytes_be(), // challenge_W
283 proof.kzg_challenges[1].into_bigint().to_bytes_be(), // challenge_E
284 proof.kzg_proofs[0].eval.into_bigint().to_bytes_be(), // eval W
285 proof.kzg_proofs[1].eval.into_bigint().to_bytes_be(), // eval E
286 point_to_eth_format(proof.kzg_proofs[0].proof.into_affine())?, // W kzg_proof
287 point_to_eth_format(proof.kzg_proofs[1].proof.into_affine())?, // E kzg_proof
288 ]
289 .concat())
290}
291
292fn point_to_eth_format<C: AffineRepr>(p: C) -> Result<Vec<u8>, Error>
293where
294 C::BaseField: PrimeField,
295{
296 // the encoding of the additive identity is [0, 0] on the EVM
297 let zero_point = (&C::BaseField::zero(), &C::BaseField::zero());
298 let (x, y) = p.xy().unwrap_or(zero_point);
299
300 Ok([x.into_bigint().to_bytes_be(), y.into_bigint().to_bytes_be()].concat())
301}
302fn point2_to_eth_format(p: ark_bn254::G2Affine) -> Result<Vec<u8>, Error> {
303 let zero_point = (&ark_bn254::Fq2::zero(), &ark_bn254::Fq2::zero());
304 let (x, y) = p.xy().unwrap_or(zero_point);
305
306 Ok([
307 x.c1.into_bigint().to_bytes_be(),
308 x.c0.into_bigint().to_bytes_be(),
309 y.c1.into_bigint().to_bytes_be(),
310 y.c0.into_bigint().to_bytes_be(),
311 ]
312 .concat())
313}
314
315#[cfg(test)]
316pub mod tests {
317 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
318 use ark_groth16::Groth16;
319 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
320 use ark_poly_commit::kzg10::VerifierKey as KZGVerifierKey;
321 use std::time::Instant;
322
323 use super::*;
324 use crate::commitment::kzg::{ProverKey as KZGProverKey, KZG};
325 use crate::commitment::pedersen::Pedersen;
326 use crate::folding::nova::{get_cs_params_len, ProverParams};
327 use crate::frontend::tests::CubicFCircuit;
328 use crate::transcript::poseidon::poseidon_canonical_config;
329
330 #[test]
331 fn test_decider() {
332 // use Nova as FoldingScheme
333 type N = Nova<
334 Projective,
335 GVar,
336 Projective2,
337 GVar2,
338 CubicFCircuit<Fr>,
339 KZG<'static, Bn254>,
340 Pedersen<Projective2>,
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 = ark_std::test_rng();
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 (cs_len, cf_cs_len) =
361 get_cs_params_len::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>>(
362 &poseidon_config,
363 F_circuit,
364 )
365 .unwrap();
366 let start = Instant::now();
367 let (kzg_pk, kzg_vk): (KZGProverKey<Projective>, KZGVerifierKey<Bn254>) =
368 KZG::<Bn254>::setup(&mut rng, cs_len).unwrap();
369 let (cf_pedersen_params, _) = Pedersen::<Projective2>::setup(&mut rng, cf_cs_len).unwrap();
370 println!("generated KZG params, {:?}", start.elapsed());
371
372 let prover_params =
373 ProverParams::<Projective, Projective2, KZG<Bn254>, Pedersen<Projective2>> {
374 poseidon_config: poseidon_config.clone(),
375 cs_pp: kzg_pk.clone(),
376 cf_cs_pp: cf_pedersen_params,
377 };
378
379 let start = Instant::now();
380 let mut nova = N::init(&prover_params, F_circuit, z_0.clone()).unwrap();
381 println!("Nova initialized, {:?}", start.elapsed());
382 let start = Instant::now();
383 nova.prove_step(&mut rng, vec![]).unwrap();
384 println!("prove_step, {:?}", start.elapsed());
385 nova.prove_step(&mut rng, vec![]).unwrap(); // do a 2nd step
386
387 // generate Groth16 setup
388 let circuit = DeciderEthCircuit::<
389 Projective,
390 GVar,
391 Projective2,
392 GVar2,
393 KZG<Bn254>,
394 Pedersen<Projective2>,
395 >::from_nova::<CubicFCircuit<Fr>>(nova.clone())
396 .unwrap();
397 let mut rng = rand::rngs::OsRng;
398
399 let start = Instant::now();
400 let (g16_pk, g16_vk) =
401 Groth16::<Bn254>::circuit_specific_setup(circuit.clone(), &mut rng).unwrap();
402 println!("Groth16 setup, {:?}", start.elapsed());
403
404 // decider proof generation
405 let start = Instant::now();
406 let decider_pp = (g16_pk, kzg_pk);
407 let proof = D::prove(rng, decider_pp, nova.clone()).unwrap();
408 println!("Decider prove, {:?}", start.elapsed());
409
410 // decider proof verification
411 let start = Instant::now();
412 let decider_vp = (g16_vk, kzg_vk);
413 let verified = D::verify(
414 decider_vp, nova.i, nova.z_0, nova.z_i, &nova.U_i, &nova.u_i, &proof,
415 )
416 .unwrap();
417 assert!(verified);
418 println!("Decider verify, {:?}", start.elapsed());
419 }
420}