1/// This file implements the onchain (Ethereum's EVM) decider circuit. For non-ethereum use cases,
  2/// other more efficient approaches can be used.
  3/// More details can be found at the documentation page:
  4/// https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-onchain.html
  5use ark_crypto_primitives::sponge::{
  6    constraints::CryptographicSpongeVar,
  7    poseidon::{constraints::PoseidonSpongeVar, PoseidonSponge},
  8    Absorb, CryptographicSponge,
  9};
 10use ark_ec::CurveGroup;
 11use ark_ff::{BigInteger, PrimeField};
 12use ark_r1cs_std::{
 13    alloc::{AllocVar, AllocationMode},
 14    boolean::Boolean,
 15    eq::EqGadget,
 16    fields::fp::FpVar,
 17    prelude::CurveVar,
 18    ToConstraintFieldGadget,
 19};
 20use ark_relations::r1cs::{Namespace, SynthesisError};
 21use ark_std::{borrow::Borrow, marker::PhantomData};
 22
 23use super::{
 24    circuits::{ChallengeGadget, CommittedInstanceVar, NIFSGadget},
 25    nifs::{nova::NIFS, NIFSTrait},
 26    CommittedInstance, Nova, Witness,
 27};
 28use crate::commitment::{pedersen::Params as PedersenParams, CommitmentScheme};
 29use crate::folding::{
 30    circuits::{
 31        decider::on_chain::GenericOnchainDeciderCircuit, nonnative::affine::NonNativeAffineVar,
 32        CF1, CF2,
 33    },
 34    traits::{WitnessOps, WitnessVarOps},
 35};
 36use crate::frontend::FCircuit;
 37use crate::Error;
 38use crate::{
 39    arith::r1cs::{circuits::R1CSMatricesVar, R1CS},
 40    folding::circuits::decider::{DeciderEnabledNIFS, EvalGadget, KZGChallengesGadget},
 41};
 42
 43/// In-circuit representation of the Witness associated to the CommittedInstance.
 44#[derive(Debug, Clone)]
 45pub struct WitnessVar<C: CurveGroup> {
 46    pub E: Vec<FpVar<C::ScalarField>>,
 47    pub rE: FpVar<C::ScalarField>,
 48    pub W: Vec<FpVar<C::ScalarField>>,
 49    pub rW: FpVar<C::ScalarField>,
 50}
 51
 52impl<C> AllocVar<Witness<C>, CF1<C>> for WitnessVar<C>
 53where
 54    C: CurveGroup,
 55{
 56    fn new_variable<T: Borrow<Witness<C>>>(
 57        cs: impl Into<Namespace<CF1<C>>>,
 58        f: impl FnOnce() -> Result<T, SynthesisError>,
 59        mode: AllocationMode,
 60    ) -> Result<Self, SynthesisError> {
 61        f().and_then(|val| {
 62            let cs = cs.into();
 63
 64            let E: Vec<FpVar<C::ScalarField>> =
 65                Vec::new_variable(cs.clone(), || Ok(val.borrow().E.clone()), mode)?;
 66            let rE =
 67                FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().rE), mode)?;
 68
 69            let W: Vec<FpVar<C::ScalarField>> =
 70                Vec::new_variable(cs.clone(), || Ok(val.borrow().W.clone()), mode)?;
 71            let rW =
 72                FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().rW), mode)?;
 73
 74            Ok(Self { E, rE, W, rW })
 75        })
 76    }
 77}
 78
 79impl<C: CurveGroup> WitnessVarOps<C::ScalarField> for WitnessVar<C> {
 80    fn get_openings(&self) -> Vec<(&[FpVar<C::ScalarField>], FpVar<C::ScalarField>)> {
 81        vec![(&self.W, self.rW.clone()), (&self.E, self.rE.clone())]
 82    }
 83}
 84
 85pub type DeciderEthCircuit<C1, C2, GC2> = GenericOnchainDeciderCircuit<
 86    C1,
 87    C2,
 88    GC2,
 89    CommittedInstance<C1>,
 90    CommittedInstance<C1>,
 91    Witness<C1>,
 92    R1CS<CF1<C1>>,
 93    R1CSMatricesVar<CF1<C1>, FpVar<CF1<C1>>>,
 94    DeciderNovaGadget,
 95>;
 96
 97/// returns an instance of the DeciderEthCircuit from the given Nova struct
 98impl<
 99        C1: CurveGroup,
100        GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
101        C2: CurveGroup,
102        GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
103        FC: FCircuit<C1::ScalarField>,
104        CS1: CommitmentScheme<C1, H>,
105        // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
106        CS2: CommitmentScheme<C2, H, ProverParams = PedersenParams<C2>>,
107        const H: bool,
108    > TryFrom<Nova<C1, GC1, C2, GC2, FC, CS1, CS2, H>> for DeciderEthCircuit<C1, C2, GC2>
109where
110    CF1<C1>: Absorb,
111{
112    type Error = Error;
113
114    fn try_from(nova: Nova<C1, GC1, C2, GC2, FC, CS1, CS2, H>) -> Result<Self, Error> {
115        let mut transcript = PoseidonSponge::<C1::ScalarField>::new(&nova.poseidon_config);
116
117        // compute the U_{i+1}, W_{i+1}
118        let (W_i1, U_i1, cmT, r_bits) = NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, H>::prove(
119            &nova.cs_pp,
120            &nova.r1cs.clone(),
121            &mut transcript,
122            nova.pp_hash,
123            &nova.W_i,
124            &nova.U_i,
125            &nova.w_i,
126            &nova.u_i,
127        )?;
128        let r_Fr = C1::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
129            .ok_or(Error::OutOfBounds)?;
130
131        // compute the KZG challenges used as inputs in the circuit
132        let kzg_challenges = KZGChallengesGadget::get_challenges_native(&mut transcript, &U_i1);
133
134        // get KZG evals
135        let kzg_evaluations = W_i1
136            .get_openings()
137            .iter()
138            .zip(&kzg_challenges)
139            .map(|((v, _), &c)| EvalGadget::evaluate_native(v, c))
140            .collect::<Result<Vec<_>, _>>()?;
141
142        Ok(Self {
143            _gc2: PhantomData,
144            _avar: PhantomData,
145            arith: nova.r1cs,
146            cf_arith: nova.cf_r1cs,
147            cf_pedersen_params: nova.cf_cs_pp,
148            poseidon_config: nova.poseidon_config,
149            pp_hash: nova.pp_hash,
150            i: nova.i,
151            z_0: nova.z_0,
152            z_i: nova.z_i,
153            U_i: nova.U_i,
154            W_i: nova.W_i,
155            u_i: nova.u_i,
156            w_i: nova.w_i,
157            U_i1,
158            W_i1,
159            proof: cmT,
160            randomness: r_Fr,
161            cf_U_i: nova.cf_U_i,
162            cf_W_i: nova.cf_W_i,
163            kzg_challenges,
164            kzg_evaluations,
165        })
166    }
167}
168
169pub struct DeciderNovaGadget;
170
171impl<C: CurveGroup>
172    DeciderEnabledNIFS<C, CommittedInstance<C>, CommittedInstance<C>, Witness<C>, R1CS<CF1<C>>>
173    for DeciderNovaGadget
174where
175    CF1<C>: Absorb,
176{
177    type ProofDummyCfg = ();
178    type Proof = C;
179    type RandomnessDummyCfg = ();
180    type Randomness = CF1<C>;
181
182    fn fold_field_elements_gadget(
183        _arith: &R1CS<CF1<C>>,
184        transcript: &mut PoseidonSpongeVar<CF1<C>>,
185        pp_hash: FpVar<CF1<C>>,
186        U: CommittedInstanceVar<C>,
187        U_vec: Vec<FpVar<CF1<C>>>,
188        u: CommittedInstanceVar<C>,
189        proof: C,
190        randomness: CF1<C>,
191    ) -> Result<CommittedInstanceVar<C>, SynthesisError> {
192        let cs = transcript.cs();
193        let cmT = NonNativeAffineVar::new_input(cs.clone(), || Ok(proof))?;
194        let r = FpVar::new_input(cs.clone(), || Ok(randomness))?;
195        let r_bits = ChallengeGadget::<C, CommittedInstance<C>>::get_challenge_gadget(
196            transcript,
197            pp_hash,
198            U_vec,
199            u.clone(),
200            Some(cmT),
201        )?;
202        Boolean::le_bits_to_fp_var(&r_bits)?.enforce_equal(&r)?;
203
204        NIFSGadget::<C>::fold_committed_instance(r, U, u)
205    }
206
207    fn fold_group_elements_native(
208        U_commitments: &[C],
209        u_commitments: &[C],
210        cmT: Option<Self::Proof>,
211        r: Self::Randomness,
212    ) -> Result<Vec<C>, Error> {
213        let cmT = cmT.ok_or(Error::Empty)?;
214        let U_cmW = U_commitments[0];
215        let U_cmE = U_commitments[1];
216        let u_cmW = u_commitments[0];
217        let u_cmE = u_commitments[1];
218        if !u_cmE.is_zero() {
219            return Err(Error::NotIncomingCommittedInstance);
220        }
221        let cmW = U_cmW + u_cmW.mul(r);
222        let cmE = U_cmE + cmT.mul(r);
223        Ok(vec![cmW, cmE])
224    }
225}
226
227#[cfg(test)]
228pub mod tests {
229    use ark_pallas::{constraints::GVar, Fr, Projective};
230    use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
231    use ark_vesta::{constraints::GVar as GVar2, Projective as Projective2};
232
233    use super::*;
234    use crate::commitment::pedersen::Pedersen;
235    use crate::folding::nova::PreprocessorParam;
236    use crate::frontend::utils::CubicFCircuit;
237    use crate::transcript::poseidon::poseidon_canonical_config;
238    use crate::FoldingScheme;
239
240    #[test]
241    fn test_decider_circuit() {
242        let mut rng = ark_std::test_rng();
243        let poseidon_config = poseidon_canonical_config::<Fr>();
244
245        let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
246        let z_0 = vec![Fr::from(3_u32)];
247
248        type N = Nova<
249            Projective,
250            GVar,
251            Projective2,
252            GVar2,
253            CubicFCircuit<Fr>,
254            Pedersen<Projective>,
255            Pedersen<Projective2>,
256            false,
257        >;
258
259        let prep_param = PreprocessorParam::<
260            Projective,
261            Projective2,
262            CubicFCircuit<Fr>,
263            Pedersen<Projective>,
264            Pedersen<Projective2>,
265            false,
266        >::new(poseidon_config, F_circuit);
267        let nova_params = N::preprocess(&mut rng, &prep_param).unwrap();
268
269        // generate a Nova instance and do a step of it
270        let mut nova = N::init(&nova_params, F_circuit, z_0.clone()).unwrap();
271        nova.prove_step(&mut rng, vec![], None).unwrap();
272        let ivc_proof = nova.ivc_proof();
273        N::verify(nova_params.1, ivc_proof).unwrap();
274
275        // load the DeciderEthCircuit from the generated Nova instance
276        let decider_circuit =
277            DeciderEthCircuit::<Projective, Projective2, GVar2>::try_from(nova).unwrap();
278
279        let cs = ConstraintSystem::<Fr>::new_ref();
280
281        // generate the constraints and check that are satisfied by the inputs
282        decider_circuit.generate_constraints(cs.clone()).unwrap();
283        assert!(cs.is_satisfied().unwrap());
284    }
285}