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