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