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