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