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