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