1/// This file implements the onchain (Ethereum's EVM) decider.
  2use ark_crypto_primitives::sponge::Absorb;
  3use ark_ec::{CurveGroup, Group};
  4use ark_ff::PrimeField;
  5use ark_r1cs_std::fields::nonnative::params::OptimizationType;
  6use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
  7use ark_snark::SNARK;
  8use ark_std::rand::{CryptoRng, RngCore};
  9use ark_std::Zero;
 10use core::marker::PhantomData;
 11
 12pub use super::decider_eth_circuit::{DeciderEthCircuit, KZGChallengesGadget};
 13use super::{circuits::CF2, nifs::NIFS, CommittedInstance, Nova};
 14use crate::commitment::{
 15    kzg::Proof as KZGProof, pedersen::Params as PedersenParams, CommitmentScheme,
 16};
 17use crate::folding::circuits::nonnative::point_to_nonnative_limbs_custom_opt;
 18use crate::frontend::FCircuit;
 19use crate::Error;
 20use crate::{Decider as DeciderTrait, FoldingScheme};
 21
 22#[derive(Debug, Clone, Eq, PartialEq)]
 23pub struct Proof<C1, CS1, S>
 24where
 25    C1: CurveGroup,
 26    CS1: CommitmentScheme<C1, ProverChallenge = C1::ScalarField, Challenge = C1::ScalarField>,
 27    S: SNARK<C1::ScalarField>,
 28{
 29    snark_proof: S::Proof,
 30    kzg_proofs: [CS1::Proof; 2],
 31    // cmT and r are values for the last fold, U_{i+1}=NIFS.V(r, U_i, u_i, cmT), and they are
 32    // checked in-circuit
 33    cmT: C1,
 34    r: C1::ScalarField,
 35    // the KZG challenges are provided by the prover, but in-circuit they are checked to match
 36    // the in-circuit computed computed ones.
 37    kzg_challenges: [C1::ScalarField; 2],
 38}
 39
 40/// Onchain Decider, for ethereum use cases
 41#[derive(Clone, Debug)]
 42pub struct Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS> {
 43    _c1: PhantomData<C1>,
 44    _gc1: PhantomData<GC1>,
 45    _c2: PhantomData<C2>,
 46    _gc2: PhantomData<GC2>,
 47    _fc: PhantomData<FC>,
 48    _cs1: PhantomData<CS1>,
 49    _cs2: PhantomData<CS2>,
 50    _s: PhantomData<S>,
 51    _fs: PhantomData<FS>,
 52}
 53
 54impl<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS> DeciderTrait<C1, C2, FC, FS>
 55    for Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S, FS>
 56where
 57    C1: CurveGroup,
 58    C2: CurveGroup,
 59    GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
 60    GC2: CurveVar<C2, CF2<C2>>,
 61    FC: FCircuit<C1::ScalarField>,
 62    CS1: CommitmentScheme<
 63        C1,
 64        ProverChallenge = C1::ScalarField,
 65        Challenge = C1::ScalarField,
 66        Proof = KZGProof<C1>,
 67    >, // KZG commitment, where challenge is C1::Fr elem
 68    // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
 69    CS2: CommitmentScheme<C2, ProverParams = PedersenParams<C2>>,
 70    S: SNARK<C1::ScalarField>,
 71    FS: FoldingScheme<C1, C2, FC>,
 72    <C1 as CurveGroup>::BaseField: PrimeField,
 73    <C2 as CurveGroup>::BaseField: PrimeField,
 74    <C1 as Group>::ScalarField: Absorb,
 75    <C2 as Group>::ScalarField: Absorb,
 76    C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
 77    for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
 78    // constrain FS into Nova, since this is a Decider specifically for Nova
 79    Nova<C1, GC1, C2, GC2, FC, CS1, CS2>: From<FS>,
 80{
 81    type ProverParam = (S::ProvingKey, CS1::ProverParams);
 82    type Proof = Proof<C1, CS1, S>;
 83    type VerifierParam = (S::VerifyingKey, CS1::VerifierParams);
 84    type PublicInput = Vec<C1::ScalarField>;
 85    type CommittedInstanceWithWitness = ();
 86    type CommittedInstance = CommittedInstance<C1>;
 87
 88    fn prove(
 89        pp: Self::ProverParam,
 90        mut rng: impl RngCore + CryptoRng,
 91        folding_scheme: FS,
 92    ) -> Result<Self::Proof, Error> {
 93        let (snark_pk, cs_pk): (S::ProvingKey, CS1::ProverParams) = pp;
 94
 95        let circuit = DeciderEthCircuit::<C1, GC1, C2, GC2, CS1, CS2>::from_nova::<FC>(
 96            folding_scheme.into(),
 97        )?;
 98
 99        let snark_proof = S::prove(&snark_pk, circuit.clone(), &mut rng)
100            .map_err(|e| Error::Other(e.to_string()))?;
101
102        let cmT = circuit.cmT.unwrap();
103        let r_Fr = circuit.r.unwrap();
104        let W_i1 = circuit.W_i1.unwrap();
105
106        // get the challenges that have been already computed when preparing the circuit inputs in
107        // the above `from_nova` call
108        let challenge_W = circuit
109            .kzg_c_W
110            .ok_or(Error::MissingValue("kzg_c_W".to_string()))?;
111        let challenge_E = circuit
112            .kzg_c_E
113            .ok_or(Error::MissingValue("kzg_c_E".to_string()))?;
114
115        // generate KZG proofs
116        let U_cmW_proof = CS1::prove_with_challenge(
117            &cs_pk,
118            challenge_W,
119            &W_i1.W,
120            &C1::ScalarField::zero(),
121            None,
122        )?;
123        let U_cmE_proof = CS1::prove_with_challenge(
124            &cs_pk,
125            challenge_E,
126            &W_i1.E,
127            &C1::ScalarField::zero(),
128            None,
129        )?;
130
131        Ok(Self::Proof {
132            snark_proof,
133            kzg_proofs: [U_cmW_proof, U_cmE_proof],
134            cmT,
135            r: r_Fr,
136            kzg_challenges: [challenge_W, challenge_E],
137        })
138    }
139
140    fn verify(
141        vp: Self::VerifierParam,
142        i: C1::ScalarField,
143        z_0: Vec<C1::ScalarField>,
144        z_i: Vec<C1::ScalarField>,
145        running_instance: &Self::CommittedInstance,
146        incoming_instance: &Self::CommittedInstance,
147        proof: Self::Proof,
148    ) -> Result<bool, Error> {
149        let (snark_vk, cs_vk): (S::VerifyingKey, CS1::VerifierParams) = vp;
150
151        // compute U = U_{d+1}= NIFS.V(U_d, u_d, cmT)
152        let U = NIFS::<C1, CS1>::verify(proof.r, running_instance, incoming_instance, &proof.cmT);
153
154        let (cmE_x, cmE_y) =
155            point_to_nonnative_limbs_custom_opt::<C1>(U.cmE, OptimizationType::Constraints)?;
156        let (cmW_x, cmW_y) =
157            point_to_nonnative_limbs_custom_opt::<C1>(U.cmW, OptimizationType::Constraints)?;
158        let (cmT_x, cmT_y) =
159            point_to_nonnative_limbs_custom_opt::<C1>(proof.cmT, OptimizationType::Constraints)?;
160
161        let public_input: Vec<C1::ScalarField> = vec![
162            vec![i],
163            z_0,
164            z_i,
165            vec![U.u],
166            U.x.clone(),
167            cmE_x,
168            cmE_y,
169            cmW_x,
170            cmW_y,
171            proof.kzg_challenges.to_vec(),
172            vec![
173                proof.kzg_proofs[0].eval, // eval_W
174                proof.kzg_proofs[1].eval, // eval_E
175            ],
176            cmT_x,
177            cmT_y,
178            vec![proof.r],
179        ]
180        .concat();
181
182        let snark_v = S::verify(&snark_vk, &public_input, &proof.snark_proof)
183            .map_err(|e| Error::Other(e.to_string()))?;
184        if !snark_v {
185            return Err(Error::SNARKVerificationFail);
186        }
187
188        // we're at the Ethereum EVM case, so the CS1 is KZG commitments
189        CS1::verify_with_challenge(
190            &cs_vk,
191            proof.kzg_challenges[0],
192            &U.cmW,
193            &proof.kzg_proofs[0],
194        )?;
195        CS1::verify_with_challenge(
196            &cs_vk,
197            proof.kzg_challenges[1],
198            &U.cmE,
199            &proof.kzg_proofs[1],
200        )?;
201
202        Ok(true)
203    }
204}
205
206#[cfg(test)]
207pub mod tests {
208    use super::*;
209    use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
210    use ark_groth16::Groth16;
211    use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
212    use ark_poly_commit::kzg10::VerifierKey as KZGVerifierKey;
213    use std::time::Instant;
214
215    use crate::commitment::kzg::{ProverKey as KZGProverKey, KZG};
216    use crate::commitment::pedersen::Pedersen;
217    use crate::folding::nova::{get_cs_params_len, ProverParams};
218    use crate::frontend::tests::CubicFCircuit;
219    use crate::transcript::poseidon::poseidon_test_config;
220
221    #[test]
222    fn test_decider() {
223        // use Nova as FoldingScheme
224        type NOVA = Nova<
225            Projective,
226            GVar,
227            Projective2,
228            GVar2,
229            CubicFCircuit<Fr>,
230            KZG<'static, Bn254>,
231            Pedersen<Projective2>,
232        >;
233        type DECIDER = Decider<
234            Projective,
235            GVar,
236            Projective2,
237            GVar2,
238            CubicFCircuit<Fr>,
239            KZG<'static, Bn254>,
240            Pedersen<Projective2>,
241            Groth16<Bn254>, // here we define the Snark to use in the decider
242            NOVA,           // here we define the FoldingScheme to use
243        >;
244
245        let mut rng = ark_std::test_rng();
246        let poseidon_config = poseidon_test_config::<Fr>();
247
248        let F_circuit = CubicFCircuit::<Fr>::new(());
249        let z_0 = vec![Fr::from(3_u32)];
250
251        let (cs_len, cf_cs_len) =
252            get_cs_params_len::<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>>(
253                &poseidon_config,
254                F_circuit,
255            )
256            .unwrap();
257        let start = Instant::now();
258        let (kzg_pk, kzg_vk): (KZGProverKey<Projective>, KZGVerifierKey<Bn254>) =
259            KZG::<Bn254>::setup(&mut rng, cs_len).unwrap();
260        let (cf_pedersen_params, _) = Pedersen::<Projective2>::setup(&mut rng, cf_cs_len).unwrap();
261        println!("generated KZG params, {:?}", start.elapsed());
262
263        let prover_params =
264            ProverParams::<Projective, Projective2, KZG<Bn254>, Pedersen<Projective2>> {
265                poseidon_config: poseidon_config.clone(),
266                cs_params: kzg_pk.clone(),
267                cf_cs_params: cf_pedersen_params,
268            };
269
270        let start = Instant::now();
271        let mut nova = NOVA::init(&prover_params, F_circuit, z_0.clone()).unwrap();
272        println!("Nova initialized, {:?}", start.elapsed());
273        let start = Instant::now();
274        nova.prove_step().unwrap();
275        println!("prove_step, {:?}", start.elapsed());
276        nova.prove_step().unwrap(); // do a 2nd step
277
278        // generate Groth16 setup
279        let circuit = DeciderEthCircuit::<
280            Projective,
281            GVar,
282            Projective2,
283            GVar2,
284            KZG<Bn254>,
285            Pedersen<Projective2>,
286        >::from_nova::<CubicFCircuit<Fr>>(nova.clone())
287        .unwrap();
288        let mut rng = rand::rngs::OsRng;
289
290        let start = Instant::now();
291        let (g16_pk, g16_vk) =
292            Groth16::<Bn254>::circuit_specific_setup(circuit.clone(), &mut rng).unwrap();
293        println!("Groth16 setup, {:?}", start.elapsed());
294
295        // decider proof generation
296        let start = Instant::now();
297        let decider_pp = (g16_pk, kzg_pk);
298        let proof = DECIDER::prove(decider_pp, rng, nova.clone()).unwrap();
299        println!("Decider prove, {:?}", start.elapsed());
300
301        // decider proof verification
302        let start = Instant::now();
303        let decider_vp = (g16_vk, kzg_vk);
304        let verified = DECIDER::verify(
305            decider_vp, nova.i, nova.z_0, nova.z_i, &nova.U_i, &nova.u_i, proof,
306        )
307        .unwrap();
308        assert!(verified);
309        println!("Decider verify, {:?}", start.elapsed());
310    }
311}