1pub mod circom;
  2
  3use crate::Error;
  4use ark_ff::PrimeField;
  5use ark_r1cs_std::fields::fp::FpVar;
  6use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
  7use ark_std::fmt::Debug;
  8
  9/// FCircuit defines the trait of the circuit of the F function, which is the one being folded (ie.
 10/// inside the agmented F' function).
 11pub trait FCircuit<F: PrimeField>: Clone + Copy + Debug {
 12    type Params: Debug;
 13
 14    /// returns a new FCircuit instance
 15    fn new(params: Self::Params) -> Self;
 16
 17    /// computes the next state values in place, assigning z_{i+1} into z_i, and computing the new
 18    /// z_{i+1}
 19    fn step_native(
 20        // this method uses self, so that each FCircuit implementation (and different frontends)
 21        // can hold a state if needed to store data to compute the next state.
 22        self,
 23        z_i: Vec<F>,
 24    ) -> Result<Vec<F>, Error>;
 25
 26    /// generates the constraints for the step of F for the given z_i
 27    fn generate_step_constraints(
 28        // this method uses self, so that each FCircuit implementation (and different frontends)
 29        // can hold a state if needed to store data to generate the constraints.
 30        self,
 31        cs: ConstraintSystemRef<F>,
 32        z_i: Vec<FpVar<F>>,
 33    ) -> Result<Vec<FpVar<F>>, SynthesisError>;
 34}
 35
 36#[cfg(test)]
 37pub mod tests {
 38    use super::*;
 39    use ark_pallas::Fr;
 40    use ark_r1cs_std::{alloc::AllocVar, eq::EqGadget};
 41    use ark_relations::r1cs::{
 42        ConstraintSynthesizer, ConstraintSystem, ConstraintSystemRef, SynthesisError,
 43    };
 44    use core::marker::PhantomData;
 45
 46    /// CubicFCircuit is a struct that implements the FCircuit trait, for the R1CS example circuit
 47    /// from https://www.vitalik.ca/general/2016/12/10/qap.html, which checks `x^3 + x + 5 = y`. It
 48    /// has 2 public inputs which are used as the state. `z_i` is used as `x`, and `z_{i+1}` is
 49    /// used as `y`, and at the next step, `z_{i+1}` will be assigned to `z_i`, and a new `z+{i+1}`
 50    /// will be computted.
 51    #[derive(Clone, Copy, Debug)]
 52    pub struct CubicFCircuit<F: PrimeField> {
 53        _f: PhantomData<F>,
 54    }
 55    impl<F: PrimeField> FCircuit<F> for CubicFCircuit<F> {
 56        type Params = ();
 57        fn new(_params: Self::Params) -> Self {
 58            Self { _f: PhantomData }
 59        }
 60        fn step_native(self, z_i: Vec<F>) -> Result<Vec<F>, Error> {
 61            Ok(vec![z_i[0] * z_i[0] * z_i[0] + z_i[0] + F::from(5_u32)])
 62        }
 63        fn generate_step_constraints(
 64            self,
 65            cs: ConstraintSystemRef<F>,
 66            z_i: Vec<FpVar<F>>,
 67        ) -> Result<Vec<FpVar<F>>, SynthesisError> {
 68            let five = FpVar::<F>::new_constant(cs.clone(), F::from(5u32))?;
 69            let z_i = z_i[0].clone();
 70
 71            Ok(vec![&z_i * &z_i * &z_i + &z_i + &five])
 72        }
 73    }
 74
 75    /// CustomFCircuit is a circuit that has the number of constraints specified in the
 76    /// `n_constraints` parameter. Note that the generated circuit will have very sparse matrices.
 77    #[derive(Clone, Copy, Debug)]
 78    pub struct CustomFCircuit<F: PrimeField> {
 79        _f: PhantomData<F>,
 80        pub n_constraints: usize,
 81    }
 82    impl<F: PrimeField> FCircuit<F> for CustomFCircuit<F> {
 83        type Params = usize;
 84
 85        fn new(params: Self::Params) -> Self {
 86            Self {
 87                _f: PhantomData,
 88                n_constraints: params,
 89            }
 90        }
 91        fn step_native(self, z_i: Vec<F>) -> Result<Vec<F>, Error> {
 92            let mut z_i1 = F::one();
 93            for _ in 0..self.n_constraints - 1 {
 94                z_i1 *= z_i[0];
 95            }
 96            Ok(vec![z_i1])
 97        }
 98        fn generate_step_constraints(
 99            self,
100            cs: ConstraintSystemRef<F>,
101            z_i: Vec<FpVar<F>>,
102        ) -> Result<Vec<FpVar<F>>, SynthesisError> {
103            let mut z_i1 = FpVar::<F>::new_witness(cs.clone(), || Ok(F::one()))?;
104            for _ in 0..self.n_constraints - 1 {
105                z_i1 *= z_i[0].clone();
106            }
107
108            Ok(vec![z_i1])
109        }
110    }
111
112    /// WrapperCircuit is a circuit that wraps any circuit that implements the FCircuit trait. This
113    /// is used to test the `FCircuit.generate_step_constraints` method. This is a similar wrapping
114    /// than the one done in the `AugmentedFCircuit`, but without adding all the extra constraints
115    /// of the AugmentedF circuit logic, in order to run lighter tests when we're not interested in
116    /// the the AugmentedF logic but in the wrapping of the circuits.
117    pub struct WrapperCircuit<F: PrimeField, FC: FCircuit<F>> {
118        pub FC: FC, // F circuit
119        pub z_i: Option<Vec<F>>,
120        pub z_i1: Option<Vec<F>>,
121    }
122    impl<F, FC> ConstraintSynthesizer<F> for WrapperCircuit<F, FC>
123    where
124        F: PrimeField,
125        FC: FCircuit<F>,
126    {
127        fn generate_constraints(self, cs: ConstraintSystemRef<F>) -> Result<(), SynthesisError> {
128            let z_i = Vec::<FpVar<F>>::new_witness(cs.clone(), || {
129                Ok(self.z_i.unwrap_or(vec![F::zero()]))
130            })?;
131            let z_i1 = Vec::<FpVar<F>>::new_input(cs.clone(), || {
132                Ok(self.z_i1.unwrap_or(vec![F::zero()]))
133            })?;
134            let computed_z_i1 = self.FC.generate_step_constraints(cs.clone(), z_i.clone())?;
135
136            computed_z_i1.enforce_equal(&z_i1)?;
137            Ok(())
138        }
139    }
140
141    #[test]
142    fn test_testfcircuit() {
143        let cs = ConstraintSystem::<Fr>::new_ref();
144        let F_circuit = CubicFCircuit::<Fr>::new(());
145
146        let wrapper_circuit = WrapperCircuit::<Fr, CubicFCircuit<Fr>> {
147            FC: F_circuit,
148            z_i: Some(vec![Fr::from(3_u32)]),
149            z_i1: Some(vec![Fr::from(35_u32)]),
150        };
151        wrapper_circuit.generate_constraints(cs.clone()).unwrap();
152        assert_eq!(cs.num_constraints(), 3);
153    }
154
155    #[test]
156    fn test_customtestfcircuit() {
157        let cs = ConstraintSystem::<Fr>::new_ref();
158        let n_constraints = 1000;
159        let custom_circuit = CustomFCircuit::<Fr>::new(n_constraints);
160        let z_i = vec![Fr::from(5_u32)];
161        let wrapper_circuit = WrapperCircuit::<Fr, CustomFCircuit<Fr>> {
162            FC: custom_circuit,
163            z_i: Some(z_i.clone()),
164            z_i1: Some(custom_circuit.step_native(z_i).unwrap()),
165        };
166        wrapper_circuit.generate_constraints(cs.clone()).unwrap();
167        assert_eq!(cs.num_constraints(), n_constraints);
168    }
169}