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