sonobe_primitives/arithmetizations/r1cs/
mod.rs

1//! This module implements the Rank-1 Constraint System (R1CS) and its relation
2//! checks against plain and relaxed witnesses and instances.
3
4use ark_ff::Field;
5use ark_relations::gr1cs::{ConstraintSystem, Matrix, R1CS_PREDICATE_LABEL};
6use ark_serialize::{
7    CanonicalDeserialize, CanonicalSerialize, Compress, Read, SerializationError, Valid, Validate,
8};
9use ark_std::{cfg_into_iter, cfg_iter};
10#[cfg(feature = "parallel")]
11use rayon::prelude::*;
12
13use super::{Arith, ArithConfig, ArithRelation, Error, ccs::CCS};
14use crate::circuits::Assignments;
15
16pub mod circuits;
17
18/// [`R1CS`] holds the three sparse matrices `A`, `B`, `C` together with the
19/// configuration.
20#[derive(Debug, Clone, Default, PartialEq, CanonicalSerialize)]
21pub struct R1CS<F: Field> {
22    m: usize, // number of constraints
23    n: usize, // number of variables
24    l: usize, // io len
25    matrices: [Matrix<F>; 3],
26}
27
28impl<F: Field> Arith for R1CS<F> {
29    #[inline]
30    fn config(&self) -> ArithConfig {
31        ArithConfig {
32            degree: 2,
33            n_constraints: self.m,
34            n_variables: self.n,
35            n_public_inputs: self.l,
36            n_witnesses: self.n - self.l - 1,
37        }
38    }
39}
40
41impl<F: Field> CCS for R1CS<F> {
42    type Field = F;
43
44    fn matrices(&self) -> &[Matrix<Self::Field>] {
45        &self.matrices[..]
46    }
47}
48
49impl<F: Field> R1CS<F> {
50    /// [`R1CS::new`] creates a new R1CS structure from the given configuration
51    /// and matrices.
52    pub fn new(
53        n_constraints: usize,
54        n_variables: usize,
55        n_public_inputs: usize,
56        matrices: [Matrix<F>; 3],
57    ) -> Result<Self, Error> {
58        let r1cs =
59            Self::new_without_validity_check(n_constraints, n_variables, n_public_inputs, matrices);
60        r1cs.validate()?;
61        Ok(r1cs)
62    }
63
64    /// [`R1CS::validate`] checks that the structural invariant of the R1CS
65    /// holds, i.w., every matrix has exactly `m` rows (one per constraint), and
66    /// no column index reaches beyond the `n` variables.
67    pub fn validate(&self) -> Result<(), Error> {
68        for matrix in &self.matrices {
69            if matrix.len() != self.m {
70                return Err(Error::InvalidNumberOfConstraints(self.m, matrix.len()));
71            }
72            for row in matrix {
73                if let Some(max) = row.iter().map(|(_, i)| *i).max()
74                    && max >= self.n
75                {
76                    return Err(Error::InvalidNumberOfVariables(self.n, max + 1));
77                }
78            }
79        }
80        Ok(())
81    }
82
83    /// [`R1CS::new_without_validity_check`] creates a new R1CS structure from
84    /// the given configuration and matrices without checking their validity.
85    pub fn new_without_validity_check(
86        n_constraints: usize,
87        n_variables: usize,
88        n_public_inputs: usize,
89        matrices: [Matrix<F>; 3],
90    ) -> Self {
91        Self {
92            m: n_constraints,
93            l: n_public_inputs,
94            n: n_variables,
95            matrices,
96        }
97    }
98
99    /// [`R1CS::evaluate_r1cs`] evaluates the R1CS relation at a given vector of
100    /// assignments `z`.
101    ///
102    /// This method is simply a wrapper of [`CCS::evaluate_ccs`] with fixed
103    /// coefficients and multisets.
104    pub fn evaluate_r1cs(
105        &self,
106        z: Assignments<F, impl AsRef<[F]> + Sync>,
107    ) -> Result<Vec<F>, Error> {
108        let u = z[0];
109        self.evaluate_ccs(z, [vec![0, 1], vec![2]], [F::one(), -u])
110    }
111}
112
113impl<F: Field> Valid for R1CS<F> {
114    fn check(&self) -> Result<(), SerializationError> {
115        self.matrices.check()?;
116        self.validate().map_err(|_| SerializationError::InvalidData)
117    }
118}
119
120impl<F: Field> CanonicalDeserialize for R1CS<F> {
121    fn deserialize_with_mode<R: Read>(
122        mut reader: R,
123        compress: Compress,
124        validate: Validate,
125    ) -> Result<Self, SerializationError> {
126        let m = usize::deserialize_with_mode(&mut reader, compress, Validate::No)?;
127        let n = usize::deserialize_with_mode(&mut reader, compress, Validate::No)?;
128        let l = usize::deserialize_with_mode(&mut reader, compress, Validate::No)?;
129        let matrices =
130            <[Matrix<F>; 3]>::deserialize_with_mode(&mut reader, compress, Validate::No)?;
131
132        let r1cs = Self::new_without_validity_check(m, n, l, matrices);
133        if validate == Validate::Yes {
134            r1cs.check()?;
135        }
136        Ok(r1cs)
137    }
138}
139
140impl<F: Field> From<&ConstraintSystem<F>> for R1CS<F> {
141    fn from(cs: &ConstraintSystem<F>) -> Self {
142        // Get the R1CS predicate matrices
143        let r1cs_predicate = &cs.predicate_constraint_systems[R1CS_PREDICATE_LABEL];
144        let matrices = r1cs_predicate.to_matrices(cs);
145
146        // matrices are extracted from a circuit, which we assume is trusted
147        R1CS::new_without_validity_check(
148            cs.num_constraints(),
149            cs.num_instance_variables + cs.num_witness_variables,
150            cs.num_instance_variables - 1, // -1 to subtract the first '1'
151            matrices.try_into().unwrap(),  // safe as R1CS always has 3 matrices
152        )
153    }
154}
155
156impl<F: Field> From<ConstraintSystem<F>> for R1CS<F> {
157    fn from(cs: ConstraintSystem<F>) -> Self {
158        Self::from(&cs)
159    }
160}
161
162impl<F: Field, W: AsRef<[F]>, U: AsRef<[F]>> ArithRelation<W, U> for R1CS<F> {
163    type Evaluation = Vec<F>;
164
165    fn eval_relation(&self, w: &W, x: &U) -> Result<Self::Evaluation, Error> {
166        self.evaluate_r1cs((F::one(), x.as_ref(), w.as_ref()).into())
167    }
168
169    fn check_evaluation(_w: &W, _x: &U, e: Self::Evaluation) -> Result<(), Error> {
170        cfg_into_iter!(e)
171            .all(|i| i.is_zero())
172            .then_some(())
173            .ok_or(Error::UnsatisfiedAssignments(
174                "Evaluation contains non-zero values".into(),
175            ))
176    }
177}
178
179/// [`RelaxedWitness`] defines a relaxed version of R1CS witness.
180///
181/// It is the basis of witnesses in many folding schemes that support R1CS.
182pub struct RelaxedWitness<V> {
183    /// [`RelaxedWitness::w`] is the witness vector
184    pub w: V,
185    /// [`RelaxedWitness::e`] is the error term
186    pub e: V,
187}
188
189/// [`RelaxedInstance`] defines a relaxed version of R1CS instance.
190///
191/// It is the basis of instances in many folding schemes that support R1CS.
192pub struct RelaxedInstance<V: IntoIterator> {
193    /// [`RelaxedInstance::x`] is the public input vector
194    pub x: V,
195    /// [`RelaxedInstance::u`] is the constant term
196    pub u: V::Item,
197}
198
199impl<F: Field> ArithRelation<RelaxedWitness<&[F]>, RelaxedInstance<&[F]>> for R1CS<F> {
200    type Evaluation = Vec<F>;
201
202    fn eval_relation(
203        &self,
204        w: &RelaxedWitness<&[F]>,
205        u: &RelaxedInstance<&[F]>,
206    ) -> Result<Self::Evaluation, Error> {
207        self.evaluate_r1cs((*u.u, u.x, w.w).into())
208    }
209
210    fn check_evaluation(
211        w: &RelaxedWitness<&[F]>,
212        _u: &RelaxedInstance<&[F]>,
213        v: Self::Evaluation,
214    ) -> Result<(), Error> {
215        if w.e.len() != v.len() {
216            return Err(Error::MalformedAssignments(format!(
217                "The number of constraints in R1CS ({}) does not match the length of the provided relaxed witness's error term ({}).",
218                v.len(),
219                w.e.len()
220            )));
221        }
222
223        cfg_iter!(w.e)
224            .zip(&v)
225            .all(|(e, v)| e == v)
226            .then_some(())
227            .ok_or(Error::UnsatisfiedAssignments(
228                "Evaluation does not match error term".into(),
229            ))
230    }
231}
232
233#[cfg(test)]
234mod tests {
235    use ark_bn254::Fr;
236    use ark_ff::UniformRand;
237    use ark_std::{error::Error, rand::thread_rng};
238
239    use super::*;
240    use crate::{
241        circuits::utils::{constraints_for_test, satisfying_assignments_for_test},
242        relations::Relation,
243    };
244
245    #[test]
246    fn test_check() -> Result<(), Box<dyn Error>> {
247        let mut rng = thread_rng();
248        let r1cs = constraints_for_test::<Fr>();
249
250        let assignments = satisfying_assignments_for_test(Fr::rand(&mut rng));
251
252        assert!(
253            r1cs.check_relation(&assignments.private, &assignments.public)
254                .is_ok()
255        );
256        assert!(
257            r1cs.check_relation(
258                &[
259                    Fr::rand(&mut rng),
260                    Fr::rand(&mut rng),
261                    Fr::rand(&mut rng),
262                    Fr::rand(&mut rng),
263                ],
264                &[Fr::rand(&mut rng)]
265            )
266            .is_err()
267        );
268
269        Ok(())
270    }
271
272    #[test]
273    fn test_deserialize_rejects_malformed() -> Result<(), Box<dyn Error>> {
274        let valid = R1CS::<Fr>::new(1, 1, 0, [vec![vec![]], vec![vec![]], vec![vec![]]]).unwrap();
275        let mut bytes = vec![];
276        valid.serialize_compressed(&mut bytes)?;
277        assert_eq!(valid, R1CS::<Fr>::deserialize_compressed(&bytes[..])?);
278
279        let mismatched_constraints = R1CS::<Fr>::new_without_validity_check(
280            2,
281            1,
282            0,
283            [vec![vec![]], vec![vec![]], vec![vec![]]],
284        );
285        let mut bytes = vec![];
286        mismatched_constraints
287            .serialize_compressed(&mut bytes)
288            .unwrap();
289        assert!(R1CS::<Fr>::deserialize_compressed_unchecked(&bytes[..]).is_ok());
290        assert!(R1CS::<Fr>::deserialize_compressed(&bytes[..]).is_err());
291
292        let out_of_range_variable = R1CS::<Fr>::new_without_validity_check(
293            1,
294            1,
295            0,
296            [vec![vec![(Fr::from(1u64), 5)]], vec![vec![]], vec![vec![]]],
297        );
298        let mut bytes = vec![];
299        out_of_range_variable.serialize_compressed(&mut bytes)?;
300        assert!(R1CS::<Fr>::deserialize_compressed_unchecked(&bytes[..]).is_ok());
301        assert!(R1CS::<Fr>::deserialize_compressed(&bytes[..]).is_err());
302
303        Ok(())
304    }
305}
sonobe_primitives/arithmetizations/r1cs/mod.rs

sonobe_primitives/arithmetizations/r1cs/
mod.rs
