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::nova::{
157 decider_eth::{prepare_calldata, Decider as DeciderEth},
158 Nova, PreprocessorParam,
159 },
160 frontend::FCircuit,
161 transcript::poseidon::poseidon_canonical_config,
162 Decider, Error, FoldingScheme,
163 };
164
165 use super::{DeciderVerifierParam, NovaCycleFoldDecider};
166 use crate::verifiers::tests::{setup, DEFAULT_SETUP_LEN};
167 use crate::{
168 evm::{compile_solidity, save_solidity, Evm},
169 utils::{get_function_selector_for_nova_cyclefold_verifier, HeaderInclusion},
170 verifiers::nova_cyclefold::get_decider_template_for_cyclefold_decider,
171 NovaCycleFoldVerifierKey, ProtocolVerifierKey,
172 };
173
174 type NOVA<FC> = Nova<G1, GVar, G2, GVar2, FC, KZG<'static, Bn254>, Pedersen<G2>, false>;
175 type DECIDER<FC> = DeciderEth<
176 G1,
177 GVar,
178 G2,
179 GVar2,
180 FC,
181 KZG<'static, Bn254>,
182 Pedersen<G2>,
183 Groth16<Bn254>,
184 NOVA<FC>,
185 >;
186
187 type FS_PP<FC> = <NOVA<FC> as FoldingScheme<G1, G2, FC>>::ProverParam;
188 type FS_VP<FC> = <NOVA<FC> as FoldingScheme<G1, G2, FC>>::VerifierParam;
189 type DECIDER_PP<FC> = <DECIDER<FC> as Decider<G1, G2, FC, NOVA<FC>>>::ProverParam;
190 type DECIDER_VP<FC> = <DECIDER<FC> as Decider<G1, G2, FC, NOVA<FC>>>::VerifierParam;
191
192 /// Test circuit to be folded
193 #[derive(Clone, Copy, Debug)]
194 pub struct CubicFCircuit<F: PrimeField> {
195 _f: PhantomData<F>,
196 }
197 impl<F: PrimeField> FCircuit<F> for CubicFCircuit<F> {
198 type Params = ();
199 fn new(_params: Self::Params) -> Result<Self, Error> {
200 Ok(Self { _f: PhantomData })
201 }
202 fn state_len(&self) -> usize {
203 1
204 }
205 fn external_inputs_len(&self) -> usize {
206 0
207 }
208 fn step_native(
209 &self,
210 _i: usize,
211 z_i: Vec<F>,
212 _external_inputs: Vec<F>,
213 ) -> Result<Vec<F>, Error> {
214 Ok(vec![z_i[0] * z_i[0] * z_i[0] + z_i[0] + F::from(5_u32)])
215 }
216 fn generate_step_constraints(
217 &self,
218 cs: ConstraintSystemRef<F>,
219 _i: usize,
220 z_i: Vec<FpVar<F>>,
221 _external_inputs: Vec<FpVar<F>>,
222 ) -> Result<Vec<FpVar<F>>, SynthesisError> {
223 let five = FpVar::<F>::new_constant(cs.clone(), F::from(5u32))?;
224 let z_i = z_i[0].clone();
225
226 Ok(vec![&z_i * &z_i * &z_i + &z_i + &five])
227 }
228 }
229
230 /// This is the circuit that we want to fold, it implements the FCircuit trait. The parameter z_i
231 /// denotes the current state which contains 5 elements, and z_{i+1} denotes the next state which
232 /// we get by applying the step.
233 /// In this example we set z_i and z_{i+1} to have five elements, and at each step we do different
234 /// operations on each of them.
235 #[derive(Clone, Copy, Debug)]
236 pub struct MultiInputsFCircuit<F: PrimeField> {
237 _f: PhantomData<F>,
238 }
239 impl<F: PrimeField> FCircuit<F> for MultiInputsFCircuit<F> {
240 type Params = ();
241
242 fn new(_params: Self::Params) -> Result<Self, Error> {
243 Ok(Self { _f: PhantomData })
244 }
245 fn state_len(&self) -> usize {
246 5
247 }
248 fn external_inputs_len(&self) -> usize {
249 0
250 }
251
252 /// computes the next state values in place, assigning z_{i+1} into z_i, and computing the new
253 /// z_{i+1}
254 fn step_native(
255 &self,
256 _i: usize,
257 z_i: Vec<F>,
258 _external_inputs: Vec<F>,
259 ) -> Result<Vec<F>, Error> {
260 let a = z_i[0] + F::from(4_u32);
261 let b = z_i[1] + F::from(40_u32);
262 let c = z_i[2] * F::from(4_u32);
263 let d = z_i[3] * F::from(40_u32);
264 let e = z_i[4] + F::from(100_u32);
265
266 Ok(vec![a, b, c, d, e])
267 }
268
269 /// generates the constraints for the step of F for the given z_i
270 fn generate_step_constraints(
271 &self,
272 cs: ConstraintSystemRef<F>,
273 _i: usize,
274 z_i: Vec<FpVar<F>>,
275 _external_inputs: Vec<FpVar<F>>,
276 ) -> Result<Vec<FpVar<F>>, SynthesisError> {
277 let four = FpVar::<F>::new_constant(cs.clone(), F::from(4u32))?;
278 let forty = FpVar::<F>::new_constant(cs.clone(), F::from(40u32))?;
279 let onehundred = FpVar::<F>::new_constant(cs.clone(), F::from(100u32))?;
280 let a = z_i[0].clone() + four.clone();
281 let b = z_i[1].clone() + forty.clone();
282 let c = z_i[2].clone() * four;
283 let d = z_i[3].clone() * forty;
284 let e = z_i[4].clone() + onehundred;
285
286 Ok(vec![a, b, c, d, e])
287 }
288 }
289
290 #[test]
291 fn nova_cyclefold_vk_serde_roundtrip() {
292 let (pp_hash, _, kzg_vk, _, g16_vk, _) = setup(DEFAULT_SETUP_LEN);
293
294 let decider_vp = DeciderVerifierParam {
295 pp_hash,
296 snark_vp: g16_vk,
297 cs_vp: kzg_vk,
298 };
299 let nova_cyclefold_vk = NovaCycleFoldVerifierKey::from((decider_vp, 1));
300
301 let mut bytes = vec![];
302 nova_cyclefold_vk
303 .serialize_protocol_verifier_key(&mut bytes)
304 .unwrap();
305 let obtained_nova_cyclefold_vk =
306 NovaCycleFoldVerifierKey::deserialize_protocol_verifier_key(bytes.as_slice()).unwrap();
307
308 assert_eq!(nova_cyclefold_vk, obtained_nova_cyclefold_vk)
309 }
310
311 #[test]
312 fn nova_cyclefold_decider_template_renders() {
313 let (pp_hash, _, kzg_vk, _, g16_vk, _) = setup(DEFAULT_SETUP_LEN);
314 let decider_vp = DeciderVerifierParam {
315 pp_hash,
316 snark_vp: g16_vk,
317 cs_vp: kzg_vk,
318 };
319 let nova_cyclefold_vk = NovaCycleFoldVerifierKey::from((decider_vp, 1));
320
321 let decider_solidity_code = HeaderInclusion::<NovaCycleFoldDecider>::builder()
322 .template(nova_cyclefold_vk)
323 .build();
324
325 save_solidity("NovaDecider.sol", &decider_solidity_code.render().unwrap());
326 }
327
328 /// Initializes Nova parameters and DeciderEth parameters. Only for test purposes.
329 #[allow(clippy::type_complexity)]
330 fn init_params<FC: FCircuit<Fr, Params = ()>>(
331 ) -> ((FS_PP<FC>, FS_VP<FC>), (DECIDER_PP<FC>, DECIDER_VP<FC>)) {
332 let mut rng = rand::rngs::OsRng;
333 let poseidon_config = poseidon_canonical_config::<Fr>();
334
335 let f_circuit = FC::new(()).unwrap();
336 let prep_param =
337 PreprocessorParam::<G1, G2, FC, KZG<'static, Bn254>, Pedersen<G2>, false>::new(
338 poseidon_config,
339 f_circuit.clone(),
340 );
341 let nova_params = NOVA::preprocess(&mut rng, &prep_param).unwrap();
342 let nova = NOVA::init(
343 &nova_params,
344 f_circuit.clone(),
345 vec![Fr::zero(); f_circuit.state_len()].clone(),
346 )
347 .unwrap();
348 let decider_params =
349 DECIDER::preprocess(&mut rng, &nova_params.clone(), nova.clone()).unwrap();
350
351 (nova_params, decider_params)
352 }
353
354 /// This function allows to define which FCircuit to use for the test, and how many prove_step
355 /// rounds to perform.
356 /// Actions performed by this test:
357 /// - runs the NovaCycleFold folding scheme for the given FCircuit and n_steps times
358 /// - generates a DeciderEth proof, and executes it through the EVM
359 /// - modifies the calldata and checks that it does not pass the EVM check
360 /// - modifies the z_0 and checks that it does not pass the EVM check
361 #[allow(clippy::type_complexity)]
362 fn nova_cyclefold_solidity_verifier_opt<FC: FCircuit<Fr, Params = ()>>(
363 fs_params: (FS_PP<FC>, FS_VP<FC>),
364 decider_params: (DECIDER_PP<FC>, DECIDER_VP<FC>),
365 z_0: Vec<Fr>,
366 n_steps: usize,
367 ) {
368 let (decider_pp, decider_vp) = decider_params;
369
370 let f_circuit = FC::new(()).unwrap();
371
372 let nova_cyclefold_vk =
373 NovaCycleFoldVerifierKey::from((decider_vp.clone(), f_circuit.state_len()));
374
375 let mut rng = rand::rngs::OsRng;
376
377 let mut nova = NOVA::<FC>::init(&fs_params, f_circuit, z_0).unwrap();
378 for _ in 0..n_steps {
379 nova.prove_step(&mut rng, vec![], None).unwrap();
380 }
381
382 let start = Instant::now();
383 let proof = DECIDER::<FC>::prove(rng, decider_pp, nova.clone()).unwrap();
384 println!("generated Decider proof: {:?}", start.elapsed());
385
386 let verified = DECIDER::<FC>::verify(
387 decider_vp,
388 nova.i,
389 nova.z_0.clone(),
390 nova.z_i.clone(),
391 &nova.U_i,
392 &nova.u_i,
393 &proof,
394 )
395 .unwrap();
396 assert!(verified);
397
398 let function_selector =
399 get_function_selector_for_nova_cyclefold_verifier(nova.z_0.len() * 2 + 1);
400
401 let calldata: Vec<u8> = prepare_calldata(
402 function_selector,
403 nova.i,
404 nova.z_0,
405 nova.z_i,
406 &nova.U_i,
407 &nova.u_i,
408 proof,
409 )
410 .unwrap();
411
412 let decider_solidity_code = get_decider_template_for_cyclefold_decider(nova_cyclefold_vk);
413
414 let nova_cyclefold_verifier_bytecode =
415 compile_solidity(decider_solidity_code, "NovaDecider");
416
417 let mut evm = Evm::default();
418 let verifier_address = evm.create(nova_cyclefold_verifier_bytecode);
419
420 let (_, output) = evm.call(verifier_address, calldata.clone());
421 assert_eq!(*output.last().unwrap(), 1);
422
423 // change i to make calldata invalid, placed between bytes 4 - 35
424 let mut invalid_calldata = calldata.clone();
425 invalid_calldata[35] += 1;
426 let (_, output) = evm.call(verifier_address, invalid_calldata.clone());
427 assert_eq!(*output.last().unwrap(), 0);
428
429 // change z_0 to make the EVM check fail, placed between bytes 35 - 67
430 let mut invalid_calldata = calldata.clone();
431 invalid_calldata[67] += 1;
432 let (_, output) = evm.call(verifier_address, invalid_calldata.clone());
433 assert_eq!(*output.last().unwrap(), 0);
434
435 // change z_i to make the EVM check fail, placed between bytes 68 - 100
436 let mut invalid_calldata = calldata.clone();
437 invalid_calldata[99] += 1;
438 let (_, output) = evm.call(verifier_address, invalid_calldata.clone());
439 assert_eq!(*output.last().unwrap(), 0);
440 }
441
442 #[test]
443 fn nova_cyclefold_solidity_verifier() {
444 let (nova_params, decider_params) = init_params::<CubicFCircuit<Fr>>();
445 let z_0 = vec![Fr::from(3_u32)];
446 nova_cyclefold_solidity_verifier_opt::<CubicFCircuit<Fr>>(
447 nova_params.clone(),
448 decider_params.clone(),
449 z_0.clone(),
450 2,
451 );
452 nova_cyclefold_solidity_verifier_opt::<CubicFCircuit<Fr>>(
453 nova_params,
454 decider_params,
455 z_0,
456 3,
457 );
458
459 let (nova_params, decider_params) = init_params::<MultiInputsFCircuit<Fr>>();
460 let z_0 = vec![
461 Fr::from(1_u32),
462 Fr::from(1_u32),
463 Fr::from(1_u32),
464 Fr::from(1_u32),
465 Fr::from(1_u32),
466 ];
467 nova_cyclefold_solidity_verifier_opt::<MultiInputsFCircuit<Fr>>(
468 nova_params.clone(),
469 decider_params.clone(),
470 z_0.clone(),
471 2,
472 );
473 nova_cyclefold_solidity_verifier_opt::<MultiInputsFCircuit<Fr>>(
474 nova_params,
475 decider_params,
476 z_0.clone(),
477 3,
478 );
479 }
480}