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