1/// This file implements the onchain (Ethereum's EVM) decider circuit. For non-ethereum use cases,
  2/// other more efficient approaches can be used.
  3use ark_crypto_primitives::sponge::{
  4    constraints::CryptographicSpongeVar,
  5    poseidon::{constraints::PoseidonSpongeVar, PoseidonSponge},
  6    Absorb, CryptographicSponge,
  7};
  8use ark_ec::CurveGroup;
  9use ark_ff::PrimeField;
 10use ark_r1cs_std::{
 11    alloc::{AllocVar, AllocationMode},
 12    eq::EqGadget,
 13    fields::fp::FpVar,
 14    groups::CurveVar,
 15    ToConstraintFieldGadget,
 16};
 17use ark_relations::r1cs::{Namespace, SynthesisError};
 18use ark_std::{borrow::Borrow, marker::PhantomData};
 19
 20use crate::{
 21    arith::r1cs::{circuits::R1CSMatricesVar, R1CS},
 22    commitment::{pedersen::Params as PedersenParams, CommitmentScheme},
 23    folding::{
 24        circuits::{
 25            decider::{
 26                on_chain::GenericOnchainDeciderCircuit, DeciderEnabledNIFS, EvalGadget,
 27                KZGChallengesGadget,
 28            },
 29            CF1, CF2,
 30        },
 31        traits::{WitnessOps, WitnessVarOps},
 32    },
 33    frontend::FCircuit,
 34    Error,
 35};
 36
 37use super::{
 38    circuits::FoldingGadget,
 39    constants::{INCOMING, RUNNING},
 40    folding::{Folding, ProtoGalaxyProof},
 41    CommittedInstance, CommittedInstanceVar, ProtoGalaxy, Witness,
 42};
 43
 44/// In-circuit representation of the Witness associated to the CommittedInstance.
 45#[derive(Debug, Clone)]
 46pub struct WitnessVar<F: PrimeField> {
 47    pub W: Vec<FpVar<F>>,
 48    pub rW: FpVar<F>,
 49}
 50
 51impl<F: PrimeField> AllocVar<Witness<F>, F> for WitnessVar<F> {
 52    fn new_variable<T: Borrow<Witness<F>>>(
 53        cs: impl Into<Namespace<F>>,
 54        f: impl FnOnce() -> Result<T, SynthesisError>,
 55        mode: AllocationMode,
 56    ) -> Result<Self, SynthesisError> {
 57        f().and_then(|val| {
 58            let cs = cs.into();
 59
 60            let W = Vec::new_variable(cs.clone(), || Ok(val.borrow().w.to_vec()), mode)?;
 61            let rW = FpVar::new_variable(cs.clone(), || Ok(val.borrow().r_w), mode)?;
 62
 63            Ok(Self { W, rW })
 64        })
 65    }
 66}
 67
 68impl<F: PrimeField> WitnessVarOps<F> for WitnessVar<F> {
 69    fn get_openings(&self) -> Vec<(&[FpVar<F>], FpVar<F>)> {
 70        vec![(&self.W, self.rW.clone())]
 71    }
 72}
 73
 74pub type DeciderEthCircuit<C1, C2, GC2> = GenericOnchainDeciderCircuit<
 75    C1,
 76    C2,
 77    GC2,
 78    CommittedInstance<C1, RUNNING>,
 79    CommittedInstance<C1, INCOMING>,
 80    Witness<CF1<C1>>,
 81    R1CS<CF1<C1>>,
 82    R1CSMatricesVar<CF1<C1>, FpVar<CF1<C1>>>,
 83    DeciderProtoGalaxyGadget,
 84>;
 85
 86/// returns an instance of the DeciderEthCircuit from the given ProtoGalaxy struct
 87impl<
 88        C1: CurveGroup,
 89        GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
 90        C2: CurveGroup,
 91        GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
 92        FC: FCircuit<C1::ScalarField>,
 93        CS1: CommitmentScheme<C1, false>,
 94        // enforce that the CS2 is Pedersen commitment scheme, since we're at Ethereum's EVM decider
 95        CS2: CommitmentScheme<C2, false, ProverParams = PedersenParams<C2>>,
 96    > TryFrom<ProtoGalaxy<C1, GC1, C2, GC2, FC, CS1, CS2>> for DeciderEthCircuit<C1, C2, GC2>
 97where
 98    CF1<C1>: Absorb,
 99{
100    type Error = Error;
101
102    fn try_from(protogalaxy: ProtoGalaxy<C1, GC1, C2, GC2, FC, CS1, CS2>) -> Result<Self, Error> {
103        let mut transcript = PoseidonSponge::<C1::ScalarField>::new(&protogalaxy.poseidon_config);
104
105        let (U_i1, W_i1, proof, aux) = Folding::prove(
106            &mut transcript,
107            &protogalaxy.r1cs,
108            &protogalaxy.U_i,
109            &protogalaxy.W_i,
110            &[protogalaxy.u_i.clone()],
111            &[protogalaxy.w_i.clone()],
112        )?;
113
114        // compute the KZG challenges used as inputs in the circuit
115        let kzg_challenges = KZGChallengesGadget::get_challenges_native(&mut transcript, &U_i1);
116
117        // get KZG evals
118        let kzg_evaluations = W_i1
119            .get_openings()
120            .iter()
121            .zip(&kzg_challenges)
122            .map(|((v, _), &c)| EvalGadget::evaluate_native(v, c))
123            .collect::<Result<Vec<_>, _>>()?;
124
125        Ok(Self {
126            _gc2: PhantomData,
127            _avar: PhantomData,
128            arith: protogalaxy.r1cs,
129            cf_arith: protogalaxy.cf_r1cs,
130            cf_pedersen_params: protogalaxy.cf_cs_params,
131            poseidon_config: protogalaxy.poseidon_config,
132            pp_hash: protogalaxy.pp_hash,
133            i: protogalaxy.i,
134            z_0: protogalaxy.z_0,
135            z_i: protogalaxy.z_i,
136            U_i: protogalaxy.U_i,
137            W_i: protogalaxy.W_i,
138            u_i: protogalaxy.u_i,
139            w_i: protogalaxy.w_i,
140            U_i1,
141            W_i1,
142            proof,
143            randomness: aux.L_X_evals,
144            cf_U_i: protogalaxy.cf_U_i,
145            cf_W_i: protogalaxy.cf_W_i,
146            kzg_challenges,
147            kzg_evaluations,
148        })
149    }
150}
151
152pub struct DeciderProtoGalaxyGadget;
153
154impl<C: CurveGroup>
155    DeciderEnabledNIFS<
156        C,
157        CommittedInstance<C, RUNNING>,
158        CommittedInstance<C, INCOMING>,
159        Witness<CF1<C>>,
160        R1CS<CF1<C>>,
161    > for DeciderProtoGalaxyGadget
162{
163    type Proof = ProtoGalaxyProof<CF1<C>>;
164    type ProofDummyCfg = (usize, usize, usize);
165    type Randomness = Vec<CF1<C>>;
166    type RandomnessDummyCfg = usize;
167
168    fn fold_field_elements_gadget(
169        _arith: &R1CS<CF1<C>>,
170        transcript: &mut PoseidonSpongeVar<CF1<C>>,
171        _pp_hash: FpVar<CF1<C>>,
172        U: CommittedInstanceVar<C, RUNNING>,
173        _U_vec: Vec<FpVar<CF1<C>>>,
174        u: CommittedInstanceVar<C, INCOMING>,
175        proof: Self::Proof,
176        randomness: Self::Randomness,
177    ) -> Result<CommittedInstanceVar<C, RUNNING>, SynthesisError> {
178        let cs = transcript.cs();
179        let F_coeffs = Vec::new_witness(cs.clone(), || Ok(&proof.F_coeffs[..]))?;
180        let K_coeffs = Vec::new_witness(cs.clone(), || Ok(&proof.K_coeffs[..]))?;
181        let randomness = Vec::new_input(cs.clone(), || Ok(randomness))?;
182
183        let (U_next, L_X_evals) =
184            FoldingGadget::fold_committed_instance(transcript, &U, &[u], F_coeffs, K_coeffs)?;
185        L_X_evals.enforce_equal(&randomness)?;
186
187        Ok(U_next)
188    }
189
190    fn fold_group_elements_native(
191        U_commitments: &[C],
192        u_commitments: &[C],
193        _: Option<Self::Proof>,
194        L_X_evals: Self::Randomness,
195    ) -> Result<Vec<C>, Error> {
196        let U_phi = U_commitments[0];
197        let u_phi = u_commitments[0];
198        Ok(vec![U_phi * L_X_evals[0] + u_phi * L_X_evals[1]])
199    }
200}
201
202#[cfg(test)]
203pub mod tests {
204    use ark_bn254::{constraints::GVar, Fr, G1Projective as Projective};
205    use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
206    use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
207
208    use super::*;
209    use crate::commitment::pedersen::Pedersen;
210    use crate::folding::protogalaxy::ProtoGalaxy;
211    use crate::frontend::{utils::CubicFCircuit, FCircuit};
212    use crate::transcript::poseidon::poseidon_canonical_config;
213    use crate::FoldingScheme;
214
215    #[test]
216    fn test_decider_circuit() {
217        let mut rng = ark_std::test_rng();
218        let poseidon_config = poseidon_canonical_config::<Fr>();
219
220        let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
221        let z_0 = vec![Fr::from(3_u32)];
222
223        type PG = ProtoGalaxy<
224            Projective,
225            GVar,
226            Projective2,
227            GVar2,
228            CubicFCircuit<Fr>,
229            Pedersen<Projective>,
230            Pedersen<Projective2>,
231        >;
232        let pg_params = PG::preprocess(&mut rng, &(poseidon_config, F_circuit)).unwrap();
233
234        // generate a Nova instance and do a step of it
235        let mut protogalaxy = PG::init(&pg_params, F_circuit, z_0.clone()).unwrap();
236        protogalaxy.prove_step(&mut rng, vec![], None).unwrap();
237
238        let ivc_proof = protogalaxy.ivc_proof();
239        PG::verify(pg_params.1, ivc_proof).unwrap();
240
241        // load the DeciderEthCircuit from the generated Nova instance
242        let decider_circuit =
243            DeciderEthCircuit::<Projective, Projective2, GVar2>::try_from(protogalaxy).unwrap();
244
245        let cs = ConstraintSystem::<Fr>::new_ref();
246
247        // generate the constraints and check that are satisfied by the inputs
248        decider_circuit.generate_constraints(cs.clone()).unwrap();
249        assert!(cs.is_satisfied().unwrap());
250        dbg!(cs.num_constraints());
251    }
252}