1/// This file implements the offchain decider. For ethereum use cases, use the
  2/// DeciderEth from decider_eth.rs file.
  3/// More details can be found at the documentation page:
  4/// https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-offchain.html
  5use ark_crypto_primitives::sponge::Absorb;
  6use ark_ec::{CurveGroup, Group};
  7use ark_ff::{BigInteger, PrimeField};
  8use ark_r1cs_std::{groups::GroupOpsBounds, prelude::CurveVar, ToConstraintFieldGadget};
  9use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
 10use ark_snark::SNARK;
 11use ark_std::rand::{CryptoRng, RngCore};
 12use ark_std::{One, Zero};
 13use core::marker::PhantomData;
 14
 15use super::decider_circuits::{DeciderCircuit1, DeciderCircuit2};
 16use super::decider_eth_circuit::DeciderNovaGadget;
 17use super::Nova;
 18use crate::commitment::CommitmentScheme;
 19use crate::folding::circuits::decider::DeciderEnabledNIFS;
 20use crate::folding::circuits::{
 21    cyclefold::{CycleFoldCommittedInstance, CycleFoldCommittedInstanceVar},
 22    CF2,
 23};
 24use crate::folding::traits::{CommittedInstanceOps, Inputize, WitnessOps};
 25use crate::frontend::FCircuit;
 26use crate::Error;
 27use crate::{Decider as DeciderTrait, FoldingScheme};
 28
 29#[derive(Debug, Clone, Eq, PartialEq)]
 30pub struct Proof<C1, C2, CS1, CS2, S1, S2>
 31where
 32    C1: CurveGroup,
 33    C2: CurveGroup,
 34    CS1: CommitmentScheme<C1>,
 35    CS2: CommitmentScheme<C2>,
 36    S1: SNARK<C1::ScalarField>,
 37    S2: SNARK<C2::ScalarField>,
 38{
 39    c1_snark_proof: S1::Proof,
 40    c2_snark_proof: S2::Proof,
 41    cs1_proofs: [CS1::Proof; 2],
 42    cs2_proofs: [CS2::Proof; 2],
 43    // cmT and r are values for the last fold, U_{i+1}=NIFS.V(r, U_i, u_i, cmT), and they are
 44    // checked in-circuit
 45    cmT: C1,
 46    r: C1::ScalarField,
 47    // cyclefold committed instance
 48    cf_U_final: CycleFoldCommittedInstance<C2>,
 49    // the CS challenges are provided by the prover, but in-circuit they are checked to match the
 50    // in-circuit computed computed ones.
 51    cs1_challenges: [C1::ScalarField; 2],
 52    cs2_challenges: [C2::ScalarField; 2],
 53}
 54
 55#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 56pub struct ProverParam<CS1_ProvingKey, S1_ProvingKey, CS2_ProvingKey, S2_ProvingKey>
 57where
 58    CS1_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 59    S1_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 60    CS2_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 61    S2_ProvingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 62{
 63    pub c1_snark_pp: S1_ProvingKey,
 64    pub c1_cs_pp: CS1_ProvingKey,
 65    pub c2_snark_pp: S2_ProvingKey,
 66    pub c2_cs_pp: CS2_ProvingKey,
 67}
 68
 69#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 70pub struct VerifierParam<C1, CS1_VerifyingKey, S1_VerifyingKey, CS2_VerifyingKey, S2_VerifyingKey>
 71where
 72    C1: CurveGroup,
 73    CS1_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 74    S1_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 75    CS2_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 76    S2_VerifyingKey: Clone + CanonicalSerialize + CanonicalDeserialize,
 77{
 78    pub pp_hash: C1::ScalarField,
 79    pub c1_snark_vp: S1_VerifyingKey,
 80    pub c1_cs_vp: CS1_VerifyingKey,
 81    pub c2_snark_vp: S2_VerifyingKey,
 82    pub c2_cs_vp: CS2_VerifyingKey,
 83}
 84
 85/// Onchain Decider, for ethereum use cases
 86#[derive(Clone, Debug)]
 87pub struct Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S1, S2, FS> {
 88    _c1: PhantomData<C1>,
 89    _gc1: PhantomData<GC1>,
 90    _c2: PhantomData<C2>,
 91    _gc2: PhantomData<GC2>,
 92    _fc: PhantomData<FC>,
 93    _cs1: PhantomData<CS1>,
 94    _cs2: PhantomData<CS2>,
 95    _s1: PhantomData<S1>,
 96    _s2: PhantomData<S2>,
 97    _fs: PhantomData<FS>,
 98}
 99
100impl<C1, GC1, C2, GC2, FC, CS1, CS2, S1, S2, FS> DeciderTrait<C1, C2, FC, FS>
101    for Decider<C1, GC1, C2, GC2, FC, CS1, CS2, S1, S2, FS>
102where
103    C1: CurveGroup,
104    C2: CurveGroup,
105    GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
106    GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
107    FC: FCircuit<C1::ScalarField>,
108    CS1: CommitmentScheme<
109        C1,
110        ProverChallenge = C1::ScalarField,
111        Challenge = C1::ScalarField,
112        Proof = crate::commitment::kzg::Proof<C1>,
113    >,
114    CS2: CommitmentScheme<
115        C2,
116        ProverChallenge = C2::ScalarField,
117        Challenge = C2::ScalarField,
118        Proof = crate::commitment::kzg::Proof<C2>,
119    >,
120    S1: SNARK<C1::ScalarField>,
121    S2: SNARK<C2::ScalarField>,
122    FS: FoldingScheme<C1, C2, FC>,
123    <C1 as CurveGroup>::BaseField: PrimeField,
124    <C2 as CurveGroup>::BaseField: PrimeField,
125    <C1 as Group>::ScalarField: Absorb,
126    <C2 as Group>::ScalarField: Absorb,
127    C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
128    for<'b> &'b GC1: GroupOpsBounds<'b, C1, GC1>,
129    for<'b> &'b GC2: GroupOpsBounds<'b, C2, GC2>,
130    // constrain FS into Nova, since this is a Decider specifically for Nova
131    Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false>: From<FS>,
132    crate::folding::nova::ProverParams<C1, C2, CS1, CS2, false>:
133        From<<FS as FoldingScheme<C1, C2, FC>>::ProverParam>,
134    crate::folding::nova::VerifierParams<C1, C2, CS1, CS2, false>:
135        From<<FS as FoldingScheme<C1, C2, FC>>::VerifierParam>,
136{
137    type PreprocessorParam = (FS::ProverParam, FS::VerifierParam);
138    type ProverParam =
139        ProverParam<CS1::ProverParams, S1::ProvingKey, CS2::ProverParams, S2::ProvingKey>;
140    type Proof = Proof<C1, C2, CS1, CS2, S1, S2>;
141    type VerifierParam = VerifierParam<
142        C1,
143        CS1::VerifierParams,
144        S1::VerifyingKey,
145        CS2::VerifierParams,
146        S2::VerifyingKey,
147    >;
148    type PublicInput = Vec<C1::ScalarField>;
149    type CommittedInstance = Vec<C1>;
150
151    fn preprocess(
152        mut rng: impl RngCore + CryptoRng,
153        prep_param: Self::PreprocessorParam,
154        fs: FS,
155    ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
156        let circuit1 = DeciderCircuit1::<C1, C2, GC2>::try_from(Nova::from(fs.clone()))?;
157        let circuit2 = DeciderCircuit2::<C2>::try_from(Nova::from(fs))?;
158
159        // get the Groth16 specific setup for the circuits
160        let (c1_g16_pk, c1_g16_vk) = S1::circuit_specific_setup(circuit1, &mut rng)
161            .map_err(|e| Error::SNARKSetupFail(e.to_string()))?;
162        let (c2_g16_pk, c2_g16_vk) = S2::circuit_specific_setup(circuit2, &mut rng)
163            .map_err(|e| Error::SNARKSetupFail(e.to_string()))?;
164
165        // get the FoldingScheme prover & verifier params from Nova
166        #[allow(clippy::type_complexity)]
167        let nova_pp: <Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false> as FoldingScheme<
168            C1,
169            C2,
170            FC,
171        >>::ProverParam = prep_param.0.clone().into();
172        #[allow(clippy::type_complexity)]
173        let nova_vp: <Nova<C1, GC1, C2, GC2, FC, CS1, CS2, false> as FoldingScheme<
174            C1,
175            C2,
176            FC,
177        >>::VerifierParam = prep_param.1.clone().into();
178
179        let pp_hash = nova_vp.pp_hash()?;
180        let pp = Self::ProverParam {
181            c1_snark_pp: c1_g16_pk,
182            c1_cs_pp: nova_pp.cs_pp,
183            c2_snark_pp: c2_g16_pk,
184            c2_cs_pp: nova_pp.cf_cs_pp,
185        };
186        let vp = Self::VerifierParam {
187            pp_hash,
188            c1_snark_vp: c1_g16_vk,
189            c1_cs_vp: nova_vp.cs_vp,
190            c2_snark_vp: c2_g16_vk,
191            c2_cs_vp: nova_vp.cf_cs_vp,
192        };
193        Ok((pp, vp))
194    }
195
196    fn prove(
197        mut rng: impl RngCore + CryptoRng,
198        pp: Self::ProverParam,
199        fs: FS,
200    ) -> Result<Self::Proof, Error> {
201        let circuit1 = DeciderCircuit1::<C1, C2, GC2>::try_from(Nova::from(fs.clone()))?;
202        let circuit2 = DeciderCircuit2::<C2>::try_from(Nova::from(fs))?;
203
204        let cmT = circuit1.proof;
205        let r = circuit1.randomness;
206        let cf_U_final = circuit1.cf_U_i.clone();
207
208        let c1_kzg_challenges = circuit1.kzg_challenges.clone();
209        let c1_kzg_proofs = circuit1
210            .W_i1
211            .get_openings()
212            .iter()
213            .zip(&c1_kzg_challenges)
214            .map(|((v, _), &c)| {
215                CS1::prove_with_challenge(&pp.c1_cs_pp, c, v, &C1::ScalarField::zero(), None)
216            })
217            .collect::<Result<Vec<_>, _>>()?;
218        let c2_kzg_challenges = circuit2.kzg_challenges.clone();
219        let c2_kzg_proofs = circuit2
220            .cf_W_i
221            .get_openings()
222            .iter()
223            .zip(&c2_kzg_challenges)
224            .map(|((v, _), &c)| {
225                CS2::prove_with_challenge(&pp.c2_cs_pp, c, v, &C2::ScalarField::zero(), None)
226            })
227            .collect::<Result<Vec<_>, _>>()?;
228
229        let c1_snark_proof = S1::prove(&pp.c1_snark_pp, circuit1, &mut rng)
230            .map_err(|e| Error::Other(e.to_string()))?;
231        let c2_snark_proof = S2::prove(&pp.c2_snark_pp, circuit2, &mut rng)
232            .map_err(|e| Error::Other(e.to_string()))?;
233
234        Ok(Self::Proof {
235            c1_snark_proof,
236            c2_snark_proof,
237            cs1_proofs: c1_kzg_proofs
238                .try_into()
239                .map_err(|e: Vec<_>| Error::NotExpectedLength(e.len(), 2))?,
240            cs2_proofs: c2_kzg_proofs
241                .try_into()
242                .map_err(|e: Vec<_>| Error::NotExpectedLength(e.len(), 2))?,
243            cmT,
244            r,
245            cf_U_final,
246            cs1_challenges: c1_kzg_challenges
247                .try_into()
248                .map_err(|e: Vec<_>| Error::NotExpectedLength(e.len(), 2))?,
249            cs2_challenges: c2_kzg_challenges
250                .try_into()
251                .map_err(|e: Vec<_>| Error::NotExpectedLength(e.len(), 2))?,
252        })
253    }
254
255    fn verify(
256        vp: Self::VerifierParam,
257        i: C1::ScalarField,
258        z_0: Vec<C1::ScalarField>,
259        z_i: Vec<C1::ScalarField>,
260        // we don't use the instances at the verifier level, since we check them in-circuit
261        running_commitments: &Self::CommittedInstance,
262        incoming_commitments: &Self::CommittedInstance,
263        proof: &Self::Proof,
264    ) -> Result<bool, Error> {
265        if i <= C1::ScalarField::one() {
266            return Err(Error::NotEnoughSteps);
267        }
268
269        // 6.2. Fold the commitments
270        let U_final_commitments = DeciderNovaGadget::fold_group_elements_native(
271            running_commitments,
272            incoming_commitments,
273            Some(proof.cmT),
274            proof.r,
275        )?;
276        let cf_U = proof.cf_U_final.clone();
277
278        // snark proof 1
279        let c1_public_input = [
280            &[vp.pp_hash, i][..],
281            &z_0,
282            &z_i,
283            &U_final_commitments
284                .iter()
285                .flat_map(|c| c.inputize())
286                .collect::<Vec<_>>(),
287            &Inputize::<CF2<C2>, CycleFoldCommittedInstanceVar<C2, GC2>>::inputize(&cf_U),
288            &proof.cs1_challenges,
289            &proof.cs1_proofs.iter().map(|p| p.eval).collect::<Vec<_>>(),
290            &proof.cmT.inputize(),
291        ]
292        .concat();
293
294        let c1_snark_v = S1::verify(&vp.c1_snark_vp, &c1_public_input, &proof.c1_snark_proof)
295            .map_err(|e| Error::Other(e.to_string()))?;
296        if !c1_snark_v {
297            return Err(Error::SNARKVerificationFail);
298        }
299
300        // snark proof 2
301        // migrate pp_hash from C1::Fr to C1::Fq
302        let pp_hash_Fq =
303            C2::ScalarField::from_le_bytes_mod_order(&vp.pp_hash.into_bigint().to_bytes_le());
304        let c2_public_input: Vec<C2::ScalarField> = [
305            &[pp_hash_Fq][..],
306            &cf_U.inputize(),
307            &proof.cs2_challenges,
308            &proof.cs2_proofs.iter().map(|p| p.eval).collect::<Vec<_>>(),
309        ]
310        .concat();
311
312        let c2_snark_v = S2::verify(&vp.c2_snark_vp, &c2_public_input, &proof.c2_snark_proof)
313            .map_err(|e| Error::Other(e.to_string()))?;
314        if !c2_snark_v {
315            return Err(Error::SNARKVerificationFail);
316        }
317
318        // 7.3. check C1 commitments (main instance commitments)
319        for ((cm, &c), pi) in U_final_commitments
320            .iter()
321            .zip(&proof.cs1_challenges)
322            .zip(&proof.cs1_proofs)
323        {
324            CS1::verify_with_challenge(&vp.c1_cs_vp, c, cm, pi)?;
325        }
326
327        // 4.3. check C2 commitments (CycleFold instance commitments)
328        for ((cm, &c), pi) in cf_U
329            .get_commitments()
330            .iter()
331            .zip(&proof.cs2_challenges)
332            .zip(&proof.cs2_proofs)
333        {
334            CS2::verify_with_challenge(&vp.c2_cs_vp, c, cm, pi)?;
335        }
336
337        Ok(true)
338    }
339}
340
341#[cfg(test)]
342pub mod tests {
343    use ark_groth16::Groth16;
344
345    // Note: do not use the MNTx_298 curves in practice, these are just for tests. Use the MNTx_753
346    // curves instead.
347    use ark_mnt4_298::{
348        constraints::G1Var as GVar, Fr, G1Projective as Projective, MNT4_298 as MNT4,
349    };
350    use ark_mnt6_298::{
351        constraints::G1Var as GVar2, G1Projective as Projective2, MNT6_298 as MNT6,
352    };
353    use std::time::Instant;
354
355    use super::*;
356    use crate::commitment::kzg::KZG;
357    use crate::folding::nova::PreprocessorParam;
358    use crate::frontend::utils::CubicFCircuit;
359    use crate::transcript::poseidon::poseidon_canonical_config;
360
361    #[test]
362    fn test_decider() {
363        // use Nova as FoldingScheme
364        type N = Nova<
365            Projective,
366            GVar,
367            Projective2,
368            GVar2,
369            CubicFCircuit<Fr>,
370            KZG<'static, MNT4>,
371            KZG<'static, MNT6>,
372            false,
373        >;
374        type D = Decider<
375            Projective,
376            GVar,
377            Projective2,
378            GVar2,
379            CubicFCircuit<Fr>,
380            KZG<'static, MNT4>,
381            KZG<'static, MNT6>,
382            Groth16<MNT4>,
383            Groth16<MNT6>,
384            N, // here we define the FoldingScheme to use
385        >;
386
387        let mut rng = ark_std::test_rng();
388        let poseidon_config = poseidon_canonical_config::<Fr>();
389
390        let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
391        let z_0 = vec![Fr::from(3_u32)];
392
393        let start = Instant::now();
394        let prep_param = PreprocessorParam::new(poseidon_config, F_circuit);
395        let nova_params = N::preprocess(&mut rng, &prep_param).unwrap();
396        println!("Nova preprocess, {:?}", start.elapsed());
397
398        let start = Instant::now();
399        let mut nova = N::init(&nova_params, F_circuit, z_0.clone()).unwrap();
400        println!("Nova initialized, {:?}", start.elapsed());
401        let start = Instant::now();
402        nova.prove_step(&mut rng, vec![], None).unwrap();
403        println!("prove_step, {:?}", start.elapsed());
404        nova.prove_step(&mut rng, vec![], None).unwrap(); // do a 2nd step
405
406        let mut rng = rand::rngs::OsRng;
407
408        // prepare the Decider prover & verifier params
409        let start = Instant::now();
410        let (decider_pp, decider_vp) = D::preprocess(&mut rng, nova_params, nova.clone()).unwrap();
411        println!("Decider preprocess, {:?}", start.elapsed());
412
413        // decider proof generation
414        let start = Instant::now();
415        let proof = D::prove(rng, decider_pp, nova.clone()).unwrap();
416        println!("Decider prove, {:?}", start.elapsed());
417
418        // decider proof verification
419        let start = Instant::now();
420        let verified = D::verify(
421            decider_vp,
422            nova.i,
423            nova.z_0,
424            nova.z_i,
425            &nova.U_i.get_commitments(),
426            &nova.u_i.get_commitments(),
427            &proof,
428        )
429        .unwrap();
430        assert!(verified);
431        println!("Decider verify, {:?}", start.elapsed());
432    }
433}