1use ark_ff::PrimeField;
  2use ark_relations::r1cs::ConstraintSystem;
  3use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
  4use ark_std::rand::Rng;
  5
  6use super::ccs::CCS;
  7use super::{Arith, ArithSerializer};
  8use crate::utils::vec::{
  9    hadamard, is_zero_vec, mat_vec_mul, vec_scalar_mul, vec_sub, SparseMatrix,
 10};
 11use crate::Error;
 12
 13pub mod circuits;
 14
 15#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 16pub struct R1CS<F: PrimeField> {
 17    pub l: usize, // io len
 18    pub A: SparseMatrix<F>,
 19    pub B: SparseMatrix<F>,
 20    pub C: SparseMatrix<F>,
 21}
 22
 23impl<F: PrimeField> R1CS<F> {
 24    /// Evaluates the CCS relation at a given vector of variables `z`
 25    pub fn eval_at_z(&self, z: &[F]) -> Result<Vec<F>, Error> {
 26        if z.len() != self.A.n_cols {
 27            return Err(Error::NotSameLength(
 28                "z.len()".to_string(),
 29                z.len(),
 30                "number of variables in R1CS".to_string(),
 31                self.A.n_cols,
 32            ));
 33        }
 34
 35        let Az = mat_vec_mul(&self.A, z)?;
 36        let Bz = mat_vec_mul(&self.B, z)?;
 37        let Cz = mat_vec_mul(&self.C, z)?;
 38        // Multiply Cz by z[0] (u) here, allowing this method to be reused for
 39        // both relaxed and plain R1CS.
 40        let uCz = vec_scalar_mul(&Cz, &z[0]);
 41        let AzBz = hadamard(&Az, &Bz)?;
 42        vec_sub(&AzBz, &uCz)
 43    }
 44}
 45
 46impl<F: PrimeField, W: AsRef<[F]>, U: AsRef<[F]>> Arith<W, U> for R1CS<F> {
 47    type Evaluation = Vec<F>;
 48
 49    fn eval_relation(&self, w: &W, u: &U) -> Result<Self::Evaluation, Error> {
 50        self.eval_at_z(&[&[F::one()], u.as_ref(), w.as_ref()].concat())
 51    }
 52
 53    fn check_evaluation(_w: &W, _u: &U, e: Self::Evaluation) -> Result<(), Error> {
 54        is_zero_vec(&e).then_some(()).ok_or(Error::NotSatisfied)
 55    }
 56}
 57
 58impl<F: PrimeField> ArithSerializer for R1CS<F> {
 59    fn params_to_le_bytes(&self) -> Vec<u8> {
 60        [
 61            self.l.to_le_bytes(),
 62            self.A.n_rows.to_le_bytes(),
 63            self.A.n_cols.to_le_bytes(),
 64        ]
 65        .concat()
 66    }
 67}
 68
 69impl<F: PrimeField> R1CS<F> {
 70    pub fn empty() -> Self {
 71        R1CS {
 72            l: 0,
 73            A: SparseMatrix::empty(),
 74            B: SparseMatrix::empty(),
 75            C: SparseMatrix::empty(),
 76        }
 77    }
 78    pub fn rand<R: Rng>(rng: &mut R, n_rows: usize, n_cols: usize) -> Self {
 79        Self {
 80            l: 1,
 81            A: SparseMatrix::rand(rng, n_rows, n_cols),
 82            B: SparseMatrix::rand(rng, n_rows, n_cols),
 83            C: SparseMatrix::rand(rng, n_rows, n_cols),
 84        }
 85    }
 86
 87    #[inline]
 88    pub fn num_constraints(&self) -> usize {
 89        self.A.n_rows
 90    }
 91
 92    #[inline]
 93    pub fn num_public_inputs(&self) -> usize {
 94        self.l
 95    }
 96
 97    #[inline]
 98    pub fn num_variables(&self) -> usize {
 99        self.A.n_cols
100    }
101
102    #[inline]
103    pub fn num_witnesses(&self) -> usize {
104        self.num_variables() - self.num_public_inputs() - 1
105    }
106
107    /// returns a tuple containing (w, x) (witness and public inputs respectively)
108    pub fn split_z(&self, z: &[F]) -> (Vec<F>, Vec<F>) {
109        (z[self.l + 1..].to_vec(), z[1..self.l + 1].to_vec())
110    }
111}
112
113impl<F: PrimeField> From<CCS<F>> for R1CS<F> {
114    fn from(ccs: CCS<F>) -> Self {
115        R1CS::<F> {
116            l: ccs.l,
117            A: ccs.M[0].clone(),
118            B: ccs.M[1].clone(),
119            C: ccs.M[2].clone(),
120        }
121    }
122}
123
124/// extracts arkworks ConstraintSystem matrices into crate::utils::vec::SparseMatrix format as R1CS
125/// struct.
126pub fn extract_r1cs<F: PrimeField>(cs: &ConstraintSystem<F>) -> Result<R1CS<F>, Error> {
127    let m = cs.to_matrices().ok_or_else(|| {
128        Error::ConversionError(
129            "ConstraintSystem".into(),
130            "ConstraintMatrices".into(),
131            "The matrices have not been generated yet".into(),
132        )
133    })?;
134
135    let n_rows = cs.num_constraints;
136    let n_cols = cs.num_instance_variables + cs.num_witness_variables; // cs.num_instance_variables already counts the 1
137
138    let A = SparseMatrix::<F> {
139        n_rows,
140        n_cols,
141        coeffs: m.a,
142    };
143    let B = SparseMatrix::<F> {
144        n_rows,
145        n_cols,
146        coeffs: m.b,
147    };
148    let C = SparseMatrix::<F> {
149        n_rows,
150        n_cols,
151        coeffs: m.c,
152    };
153
154    Ok(R1CS::<F> {
155        l: cs.num_instance_variables - 1, // -1 to subtract the first '1'
156        A,
157        B,
158        C,
159    })
160}
161
162/// extracts the witness and the public inputs from arkworks ConstraintSystem.
163pub fn extract_w_x<F: PrimeField>(cs: &ConstraintSystem<F>) -> (Vec<F>, Vec<F>) {
164    (
165        cs.witness_assignment.clone(),
166        // skip the first element which is '1'
167        cs.instance_assignment[1..].to_vec(),
168    )
169}
170
171#[cfg(test)]
172pub mod tests {
173    use super::*;
174    use crate::utils::vec::{
175        is_zero_vec,
176        tests::{to_F_matrix, to_F_vec},
177    };
178
179    use ark_pallas::Fr;
180
181    pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
182        // R1CS for: x^3 + x + 5 = y (example from article
183        // https://www.vitalik.ca/general/2016/12/10/qap.html )
184        let A = to_F_matrix::<F>(vec![
185            vec![0, 1, 0, 0, 0, 0],
186            vec![0, 0, 0, 1, 0, 0],
187            vec![0, 1, 0, 0, 1, 0],
188            vec![5, 0, 0, 0, 0, 1],
189        ]);
190        let B = to_F_matrix::<F>(vec![
191            vec![0, 1, 0, 0, 0, 0],
192            vec![0, 1, 0, 0, 0, 0],
193            vec![1, 0, 0, 0, 0, 0],
194            vec![1, 0, 0, 0, 0, 0],
195        ]);
196        let C = to_F_matrix::<F>(vec![
197            vec![0, 0, 0, 1, 0, 0],
198            vec![0, 0, 0, 0, 1, 0],
199            vec![0, 0, 0, 0, 0, 1],
200            vec![0, 0, 1, 0, 0, 0],
201        ]);
202
203        R1CS::<F> { l: 1, A, B, C }
204    }
205
206    pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
207        // z = (1, io, w)
208        to_F_vec(vec![
209            1,
210            input,                             // io
211            input * input * input + input + 5, // x^3 + x + 5
212            input * input,                     // x^2
213            input * input * input,             // x^2 * x
214            input * input * input + input,     // x^3 + x
215        ])
216    }
217
218    pub fn get_test_z_split<F: PrimeField>(input: usize) -> (F, Vec<F>, Vec<F>) {
219        // z = (1, io, w)
220        (
221            F::one(),
222            to_F_vec(vec![
223                input, // io
224            ]),
225            to_F_vec(vec![
226                input * input * input + input + 5, // x^3 + x + 5
227                input * input,                     // x^2
228                input * input * input,             // x^2 * x
229                input * input * input + input,     // x^3 + x
230            ]),
231        )
232    }
233
234    #[test]
235    fn test_eval_r1cs_relation() {
236        let mut rng = ark_std::test_rng();
237        let r1cs = get_test_r1cs::<Fr>();
238        let (_, x, mut w) = get_test_z_split::<Fr>(rng.gen::<u16>() as usize);
239
240        let f_w = r1cs.eval_relation(&w, &x).unwrap();
241        assert!(is_zero_vec(&f_w));
242
243        w[1] = Fr::from(111);
244        let f_w = r1cs.eval_relation(&w, &x).unwrap();
245        assert!(!is_zero_vec(&f_w));
246    }
247
248    #[test]
249    fn test_check_r1cs_relation() {
250        let r1cs = get_test_r1cs::<Fr>();
251        let (_, x, w) = get_test_z_split(5);
252        r1cs.check_relation(&w, &x).unwrap();
253    }
254}