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) -> 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}