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