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