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