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