sonobe/solidity-verifiers/src/verifiers/nova_cyclefold.rs
solidity-verifiers/src/verifiers/nova_cyclefold.rsRaw
1#![allow(non_snake_case)]
2#![allow(non_camel_case_types)]
3
4use ark_bn254::{Bn254, Fq, G1Affine};
5use ark_groth16::VerifyingKey;
6use ark_poly_commit::kzg10::VerifierKey;
7use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
8use askama::Template;
9
10use folding_schemes::folding::circuits::nonnative::uint::NonNativeUintVar;
11
12use super::g16::Groth16Verifier;
13use super::kzg::KZG10Verifier;
14use crate::utils::HeaderInclusion;
15use crate::{Groth16VerifierKey, KZG10VerifierKey, ProtocolVerifierKey, PRAGMA_GROTH16_VERIFIER};
16
17pub fn get_decider_template_for_cyclefold_decider(
18 nova_cyclefold_vk: NovaCycleFoldVerifierKey,
19) -> String {
20 HeaderInclusion::<NovaCycleFoldDecider>::builder()
21 .template(nova_cyclefold_vk)
22 .build()
23 .render()
24 .unwrap()
25}
26
27#[derive(Template, Default)]
28#[template(path = "nova_cyclefold_decider.askama.sol", ext = "sol")]
29pub struct NovaCycleFoldDecider {
30 groth16_verifier: Groth16Verifier,
31 kzg10_verifier: KZG10Verifier,
32 // z_len denotes the FCircuit state (z_i) length
33 z_len: usize,
34 public_inputs_len: usize,
35 num_limbs: usize,
36 bits_per_limb: usize,
37}
38
39impl From<NovaCycleFoldVerifierKey> for NovaCycleFoldDecider {
40 fn from(value: NovaCycleFoldVerifierKey) -> Self {
41 let groth16_verifier = Groth16Verifier::from(value.g16_vk);
42 let public_inputs_len = groth16_verifier.gamma_abc_len;
43 let bits_per_limb = NonNativeUintVar::<Fq>::bits_per_limb();
44 Self {
45 groth16_verifier,
46 kzg10_verifier: KZG10Verifier::from(value.kzg_vk),
47 z_len: value.z_len,
48 public_inputs_len,
49 num_limbs: (250_f32 / (bits_per_limb as f32)).ceil() as usize,
50 bits_per_limb,
51 }
52 }
53}
54
55#[derive(CanonicalDeserialize, CanonicalSerialize, PartialEq, Debug, Clone)]
56pub struct NovaCycleFoldVerifierKey {
57 g16_vk: Groth16VerifierKey,
58 kzg_vk: KZG10VerifierKey,
59 z_len: usize,
60}
61
62impl ProtocolVerifierKey for NovaCycleFoldVerifierKey {
63 const PROTOCOL_NAME: &'static str = "NovaCycleFold";
64
65 fn render_as_template(self, pragma: Option<String>) -> Vec<u8> {
66 HeaderInclusion::<NovaCycleFoldDecider>::builder()
67 .pragma_version(pragma.unwrap_or(PRAGMA_GROTH16_VERIFIER.to_string()))
68 .template(self)
69 .build()
70 .render()
71 .unwrap()
72 .into_bytes()
73 }
74}
75
76impl From<(Groth16VerifierKey, KZG10VerifierKey, usize)> for NovaCycleFoldVerifierKey {
77 fn from(value: (Groth16VerifierKey, KZG10VerifierKey, usize)) -> Self {
78 Self {
79 g16_vk: value.0,
80 kzg_vk: value.1,
81 z_len: value.2,
82 }
83 }
84}
85
86// implements From assuming that the 'batchCheck' method from the KZG10 template will not be used
87// in the NovaCycleFoldDecider verifier contract
88impl From<((VerifyingKey<Bn254>, VerifierKey<Bn254>), usize)> for NovaCycleFoldVerifierKey {
89 fn from(value: ((VerifyingKey<Bn254>, VerifierKey<Bn254>), usize)) -> Self {
90 let decider_vp = value.0;
91 let g16_vk = Groth16VerifierKey::from(decider_vp.0);
92 // pass `Vec::new()` since batchCheck will not be used
93 let kzg_vk = KZG10VerifierKey::from((decider_vp.1, Vec::new()));
94 Self {
95 g16_vk,
96 kzg_vk,
97 z_len: value.1,
98 }
99 }
100}
101
102impl NovaCycleFoldVerifierKey {
103 pub fn new(
104 vkey_g16: VerifyingKey<Bn254>,
105 vkey_kzg: VerifierKey<Bn254>,
106 crs_points: Vec<G1Affine>,
107 z_len: usize,
108 ) -> Self {
109 Self {
110 g16_vk: Groth16VerifierKey::from(vkey_g16),
111 kzg_vk: KZG10VerifierKey::from((vkey_kzg, crs_points)),
112 z_len,
113 }
114 }
115}
116
117#[cfg(test)]
118mod tests {
119 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as G1};
120 use ark_crypto_primitives::snark::SNARK;
121 use ark_ff::PrimeField;
122 use ark_groth16::VerifyingKey as G16VerifierKey;
123 use ark_groth16::{Groth16, ProvingKey};
124 use ark_grumpkin::{constraints::GVar as GVar2, Projective as G2};
125 use ark_poly_commit::kzg10::VerifierKey as KZGVerifierKey;
126 use ark_r1cs_std::alloc::AllocVar;
127 use ark_r1cs_std::fields::fp::FpVar;
128 use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
129 use ark_std::Zero;
130 use askama::Template;
131 use std::marker::PhantomData;
132 use std::time::Instant;
133
134 use folding_schemes::{
135 commitment::{
136 kzg::{ProverKey as KZGProverKey, KZG},
137 pedersen::Pedersen,
138 CommitmentScheme,
139 },
140 folding::nova::{
141 decider_eth::{prepare_calldata, Decider as DeciderEth},
142 decider_eth_circuit::DeciderEthCircuit,
143 get_cs_params_len, Nova, ProverParams,
144 },
145 frontend::FCircuit,
146 transcript::poseidon::poseidon_canonical_config,
147 Decider, Error, FoldingScheme,
148 };
149
150 use super::NovaCycleFoldDecider;
151 use crate::verifiers::tests::{setup, DEFAULT_SETUP_LEN};
152 use crate::{
153 evm::{compile_solidity, save_solidity, Evm},
154 utils::{get_function_selector_for_nova_cyclefold_verifier, HeaderInclusion},
155 verifiers::nova_cyclefold::get_decider_template_for_cyclefold_decider,
156 NovaCycleFoldVerifierKey, ProtocolVerifierKey,
157 };
158
159 /// Test circuit to be folded
160 #[derive(Clone, Copy, Debug)]
161 pub struct CubicFCircuit<F: PrimeField> {
162 _f: PhantomData<F>,
163 }
164 impl<F: PrimeField> FCircuit<F> for CubicFCircuit<F> {
165 type Params = ();
166 fn new(_params: Self::Params) -> Result<Self, Error> {
167 Ok(Self { _f: PhantomData })
168 }
169 fn state_len(&self) -> usize {
170 1
171 }
172 fn external_inputs_len(&self) -> usize {
173 0
174 }
175 fn step_native(
176 &self,
177 _i: usize,
178 z_i: Vec<F>,
179 _external_inputs: Vec<F>,
180 ) -> Result<Vec<F>, Error> {
181 Ok(vec![z_i[0] * z_i[0] * z_i[0] + z_i[0] + F::from(5_u32)])
182 }
183 fn generate_step_constraints(
184 &self,
185 cs: ConstraintSystemRef<F>,
186 _i: usize,
187 z_i: Vec<FpVar<F>>,
188 _external_inputs: Vec<FpVar<F>>,
189 ) -> Result<Vec<FpVar<F>>, SynthesisError> {
190 let five = FpVar::<F>::new_constant(cs.clone(), F::from(5u32))?;
191 let z_i = z_i[0].clone();
192
193 Ok(vec![&z_i * &z_i * &z_i + &z_i + &five])
194 }
195 }
196
197 /// This is the circuit that we want to fold, it implements the FCircuit trait. The parameter z_i
198 /// denotes the current state which contains 5 elements, and z_{i+1} denotes the next state which
199 /// we get by applying the step.
200 /// In this example we set z_i and z_{i+1} to have five elements, and at each step we do different
201 /// operations on each of them.
202 #[derive(Clone, Copy, Debug)]
203 pub struct MultiInputsFCircuit<F: PrimeField> {
204 _f: PhantomData<F>,
205 }
206 impl<F: PrimeField> FCircuit<F> for MultiInputsFCircuit<F> {
207 type Params = ();
208
209 fn new(_params: Self::Params) -> Result<Self, Error> {
210 Ok(Self { _f: PhantomData })
211 }
212 fn state_len(&self) -> usize {
213 5
214 }
215 fn external_inputs_len(&self) -> usize {
216 0
217 }
218
219 /// computes the next state values in place, assigning z_{i+1} into z_i, and computing the new
220 /// z_{i+1}
221 fn step_native(
222 &self,
223 _i: usize,
224 z_i: Vec<F>,
225 _external_inputs: Vec<F>,
226 ) -> Result<Vec<F>, Error> {
227 let a = z_i[0] + F::from(4_u32);
228 let b = z_i[1] + F::from(40_u32);
229 let c = z_i[2] * F::from(4_u32);
230 let d = z_i[3] * F::from(40_u32);
231 let e = z_i[4] + F::from(100_u32);
232
233 Ok(vec![a, b, c, d, e])
234 }
235
236 /// generates the constraints for the step of F for the given z_i
237 fn generate_step_constraints(
238 &self,
239 cs: ConstraintSystemRef<F>,
240 _i: usize,
241 z_i: Vec<FpVar<F>>,
242 _external_inputs: Vec<FpVar<F>>,
243 ) -> Result<Vec<FpVar<F>>, SynthesisError> {
244 let four = FpVar::<F>::new_constant(cs.clone(), F::from(4u32))?;
245 let forty = FpVar::<F>::new_constant(cs.clone(), F::from(40u32))?;
246 let onehundred = FpVar::<F>::new_constant(cs.clone(), F::from(100u32))?;
247 let a = z_i[0].clone() + four.clone();
248 let b = z_i[1].clone() + forty.clone();
249 let c = z_i[2].clone() * four;
250 let d = z_i[3].clone() * forty;
251 let e = z_i[4].clone() + onehundred;
252
253 Ok(vec![a, b, c, d, e])
254 }
255 }
256
257 #[test]
258 fn nova_cyclefold_vk_serde_roundtrip() {
259 let (_, kzg_vk, _, g16_vk, _) = setup(DEFAULT_SETUP_LEN);
260
261 let mut bytes = vec![];
262 let nova_cyclefold_vk = NovaCycleFoldVerifierKey::from(((g16_vk, kzg_vk), 1));
263
264 nova_cyclefold_vk
265 .serialize_protocol_verifier_key(&mut bytes)
266 .unwrap();
267 let obtained_nova_cyclefold_vk =
268 NovaCycleFoldVerifierKey::deserialize_protocol_verifier_key(bytes.as_slice()).unwrap();
269
270 assert_eq!(nova_cyclefold_vk, obtained_nova_cyclefold_vk)
271 }
272
273 #[test]
274 fn nova_cyclefold_decider_template_renders() {
275 let (_, kzg_vk, _, g16_vk, _) = setup(DEFAULT_SETUP_LEN);
276 let nova_cyclefold_vk = NovaCycleFoldVerifierKey::from(((g16_vk, kzg_vk), 1));
277
278 let decider_solidity_code = HeaderInclusion::<NovaCycleFoldDecider>::builder()
279 .template(nova_cyclefold_vk)
280 .build();
281
282 save_solidity("NovaDecider.sol", &decider_solidity_code.render().unwrap());
283 }
284
285 #[allow(clippy::type_complexity)]
286 fn init_test_prover_params<FC: FCircuit<Fr, Params = ()>>() -> (
287 ProverParams<G1, G2, KZG<'static, Bn254>, Pedersen<G2>>,
288 KZGVerifierKey<Bn254>,
289 ) {
290 let mut rng = ark_std::test_rng();
291 let poseidon_config = poseidon_canonical_config::<Fr>();
292 let f_circuit = FC::new(()).unwrap();
293 let (cs_len, cf_cs_len) =
294 get_cs_params_len::<G1, GVar, G2, GVar2, FC>(&poseidon_config, f_circuit).unwrap();
295 let (kzg_pk, kzg_vk): (KZGProverKey<G1>, KZGVerifierKey<Bn254>) =
296 KZG::<Bn254>::setup(&mut rng, cs_len).unwrap();
297 let (cf_pedersen_params, _) = Pedersen::<G2>::setup(&mut rng, cf_cs_len).unwrap();
298 let fs_prover_params = ProverParams::<G1, G2, KZG<Bn254>, Pedersen<G2>> {
299 poseidon_config: poseidon_config.clone(),
300 cs_pp: kzg_pk.clone(),
301 cf_cs_pp: cf_pedersen_params,
302 };
303 (fs_prover_params, kzg_vk)
304 }
305
306 /// Initializes Nova parameters and DeciderEth parameters. Only for test purposes.
307 #[allow(clippy::type_complexity)]
308 fn init_params<FC: FCircuit<Fr, Params = ()>>() -> (
309 ProverParams<G1, G2, KZG<'static, Bn254>, Pedersen<G2>>,
310 KZGVerifierKey<Bn254>,
311 ProvingKey<Bn254>,
312 G16VerifierKey<Bn254>,
313 ) {
314 let mut rng = rand::rngs::OsRng;
315 let start = Instant::now();
316 let (fs_prover_params, kzg_vk) = init_test_prover_params::<FC>();
317 println!("generated Nova folding params: {:?}", start.elapsed());
318 let f_circuit = FC::new(()).unwrap();
319
320 pub type NOVA_FCircuit<FC> =
321 Nova<G1, GVar, G2, GVar2, FC, KZG<'static, Bn254>, Pedersen<G2>>;
322 let z_0 = vec![Fr::zero(); f_circuit.state_len()];
323 let nova = NOVA_FCircuit::init(&fs_prover_params, f_circuit, z_0.clone()).unwrap();
324
325 let decider_circuit =
326 DeciderEthCircuit::<G1, GVar, G2, GVar2, KZG<Bn254>, Pedersen<G2>>::from_nova::<FC>(
327 nova.clone(),
328 )
329 .unwrap();
330 let start = Instant::now();
331 let (g16_pk, g16_vk) =
332 Groth16::<Bn254>::circuit_specific_setup(decider_circuit.clone(), &mut rng).unwrap();
333 println!(
334 "generated G16 (Decider circuit) params: {:?}",
335 start.elapsed()
336 );
337 (fs_prover_params, kzg_vk, g16_pk, g16_vk)
338 }
339
340 /// This function allows to define which FCircuit to use for the test, and how many prove_step
341 /// rounds to perform.
342 /// Actions performed by this test:
343 /// - runs the NovaCycleFold folding scheme for the given FCircuit and n_steps times
344 /// - generates a DeciderEth proof, and executes it through the EVM
345 /// - modifies the calldata and checks that it does not pass the EVM check
346 /// - modifies the z_0 and checks that it does not pass the EVM check
347 #[allow(clippy::type_complexity)]
348 fn nova_cyclefold_solidity_verifier_opt<FC: FCircuit<Fr, Params = ()>>(
349 params: (
350 ProverParams<G1, G2, KZG<'static, Bn254>, Pedersen<G2>>,
351 KZGVerifierKey<Bn254>,
352 ProvingKey<Bn254>,
353 G16VerifierKey<Bn254>,
354 ),
355 z_0: Vec<Fr>,
356 n_steps: usize,
357 ) {
358 let (fs_prover_params, kzg_vk, g16_pk, g16_vk) = params.clone();
359
360 pub type NOVA_FCircuit<FC> =
361 Nova<G1, GVar, G2, GVar2, FC, KZG<'static, Bn254>, Pedersen<G2>>;
362 pub type DECIDERETH_FCircuit<FC> = DeciderEth<
363 G1,
364 GVar,
365 G2,
366 GVar2,
367 FC,
368 KZG<'static, Bn254>,
369 Pedersen<G2>,
370 Groth16<Bn254>,
371 NOVA_FCircuit<FC>,
372 >;
373 let f_circuit = FC::new(()).unwrap();
374
375 let nova_cyclefold_vk = NovaCycleFoldVerifierKey::from((
376 (g16_vk.clone(), kzg_vk.clone()),
377 f_circuit.state_len(),
378 ));
379
380 let mut rng = rand::rngs::OsRng;
381
382 let mut nova = NOVA_FCircuit::init(&fs_prover_params, f_circuit, z_0).unwrap();
383 for _ in 0..n_steps {
384 nova.prove_step(&mut rng, vec![]).unwrap();
385 }
386
387 let start = Instant::now();
388 let proof =
389 DECIDERETH_FCircuit::prove(rng, (g16_pk, fs_prover_params.cs_pp.clone()), nova.clone())
390 .unwrap();
391 println!("generated Decider proof: {:?}", start.elapsed());
392
393 let verified = DECIDERETH_FCircuit::<FC>::verify(
394 (g16_vk, kzg_vk),
395 nova.i,
396 nova.z_0.clone(),
397 nova.z_i.clone(),
398 &nova.U_i,
399 &nova.u_i,
400 &proof,
401 )
402 .unwrap();
403 assert!(verified);
404
405 let function_selector =
406 get_function_selector_for_nova_cyclefold_verifier(nova.z_0.len() * 2 + 1);
407
408 let calldata: Vec<u8> = prepare_calldata(
409 function_selector,
410 nova.i,
411 nova.z_0,
412 nova.z_i,
413 &nova.U_i,
414 &nova.u_i,
415 proof,
416 )
417 .unwrap();
418
419 let decider_solidity_code = get_decider_template_for_cyclefold_decider(nova_cyclefold_vk);
420
421 let nova_cyclefold_verifier_bytecode =
422 compile_solidity(decider_solidity_code, "NovaDecider");
423
424 let mut evm = Evm::default();
425 let verifier_address = evm.create(nova_cyclefold_verifier_bytecode);
426
427 let (_, output) = evm.call(verifier_address, calldata.clone());
428 assert_eq!(*output.last().unwrap(), 1);
429
430 // change i to make calldata invalid, placed between bytes 4 - 35
431 let mut invalid_calldata = calldata.clone();
432 invalid_calldata[35] += 1;
433 let (_, output) = evm.call(verifier_address, invalid_calldata.clone());
434 assert_eq!(*output.last().unwrap(), 0);
435
436 // change z_0 to make the EVM check fail, placed between bytes 35 - 67
437 let mut invalid_calldata = calldata.clone();
438 invalid_calldata[67] += 1;
439 let (_, output) = evm.call(verifier_address, invalid_calldata.clone());
440 assert_eq!(*output.last().unwrap(), 0);
441
442 // change z_i to make the EVM check fail, placed between bytes 68 - 100
443 let mut invalid_calldata = calldata.clone();
444 invalid_calldata[99] += 1;
445 let (_, output) = evm.call(verifier_address, invalid_calldata.clone());
446 assert_eq!(*output.last().unwrap(), 0);
447 }
448
449 #[test]
450 fn nova_cyclefold_solidity_verifier() {
451 let params = init_params::<CubicFCircuit<Fr>>();
452 let z_0 = vec![Fr::from(3_u32)];
453 nova_cyclefold_solidity_verifier_opt::<CubicFCircuit<Fr>>(params.clone(), z_0.clone(), 2);
454 nova_cyclefold_solidity_verifier_opt::<CubicFCircuit<Fr>>(params.clone(), z_0.clone(), 3);
455
456 let params = init_params::<MultiInputsFCircuit<Fr>>();
457 let z_0 = vec![
458 Fr::from(1_u32),
459 Fr::from(1_u32),
460 Fr::from(1_u32),
461 Fr::from(1_u32),
462 Fr::from(1_u32),
463 ];
464 nova_cyclefold_solidity_verifier_opt::<MultiInputsFCircuit<Fr>>(
465 params.clone(),
466 z_0.clone(),
467 2,
468 );
469 nova_cyclefold_solidity_verifier_opt::<MultiInputsFCircuit<Fr>>(
470 params.clone(),
471 z_0.clone(),
472 3,
473 );
474 }
475}