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