1use ark_ff::PrimeField;
  2
  3use crate::utils::vec::*;
  4use crate::Error;
  5
  6#[derive(Debug, Clone, Eq, PartialEq)]
  7pub struct R1CS<F: PrimeField> {
  8    pub l: usize, // io len
  9    pub A: SparseMatrix<F>,
 10    pub B: SparseMatrix<F>,
 11    pub C: SparseMatrix<F>,
 12}
 13
 14impl<F: PrimeField> R1CS<F> {
 15    /// returns a tuple containing (w, x) (witness and public inputs respectively)
 16    pub fn split_z(&self, z: &[F]) -> (Vec<F>, Vec<F>) {
 17        (z[self.l + 1..].to_vec(), z[1..self.l + 1].to_vec())
 18    }
 19
 20    /// check that a R1CS structure is satisfied by a z vector. Only for testing.
 21    pub fn check_relation(&self, z: &[F]) -> Result<(), Error> {
 22        let Az = mat_vec_mul_sparse(&self.A, z);
 23        let Bz = mat_vec_mul_sparse(&self.B, z);
 24        let Cz = mat_vec_mul_sparse(&self.C, z);
 25        let AzBz = hadamard(&Az, &Bz);
 26        assert_eq!(AzBz, Cz);
 27
 28        Ok(())
 29    }
 30
 31    /// converts the R1CS instance into a RelaxedR1CS as described in
 32    /// [Nova](https://eprint.iacr.org/2021/370.pdf) section 4.1.
 33    pub fn relax(self) -> RelaxedR1CS<F> {
 34        RelaxedR1CS::<F> {
 35            l: self.l,
 36            E: vec![F::zero(); self.A.n_rows],
 37            A: self.A,
 38            B: self.B,
 39            C: self.C,
 40            u: F::one(),
 41        }
 42    }
 43}
 44
 45#[derive(Debug, Clone, Eq, PartialEq)]
 46pub struct RelaxedR1CS<F: PrimeField> {
 47    pub l: usize, // io len
 48    pub A: SparseMatrix<F>,
 49    pub B: SparseMatrix<F>,
 50    pub C: SparseMatrix<F>,
 51    pub u: F,
 52    pub E: Vec<F>,
 53}
 54impl<F: PrimeField> RelaxedR1CS<F> {
 55    /// check that a RelaxedR1CS structure is satisfied by a z vector. Only for testing.
 56    pub fn check_relation(&self, z: &[F]) -> Result<(), Error> {
 57        let Az = mat_vec_mul_sparse(&self.A, z);
 58        let Bz = mat_vec_mul_sparse(&self.B, z);
 59        let Cz = mat_vec_mul_sparse(&self.C, z);
 60        let uCz = vec_scalar_mul(&Cz, &self.u);
 61        let uCzE = vec_add(&uCz, &self.E);
 62        let AzBz = hadamard(&Az, &Bz);
 63        assert_eq!(AzBz, uCzE);
 64
 65        Ok(())
 66    }
 67}
 68
 69#[cfg(test)]
 70pub mod tests {
 71    use super::*;
 72    use crate::utils::vec::tests::{to_F_matrix, to_F_vec};
 73    use ark_pallas::Fr;
 74
 75    pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
 76        // R1CS for: x^3 + x + 5 = y (example from article
 77        // https://www.vitalik.ca/general/2016/12/10/qap.html )
 78        let A = dense_matrix_to_sparse(to_F_matrix::<F>(vec![
 79            vec![0, 1, 0, 0, 0, 0],
 80            vec![0, 0, 0, 1, 0, 0],
 81            vec![0, 1, 0, 0, 1, 0],
 82            vec![5, 0, 0, 0, 0, 1],
 83        ]));
 84        let B = dense_matrix_to_sparse(to_F_matrix::<F>(vec![
 85            vec![0, 1, 0, 0, 0, 0],
 86            vec![0, 1, 0, 0, 0, 0],
 87            vec![1, 0, 0, 0, 0, 0],
 88            vec![1, 0, 0, 0, 0, 0],
 89        ]));
 90        let C = dense_matrix_to_sparse(to_F_matrix::<F>(vec![
 91            vec![0, 0, 0, 1, 0, 0],
 92            vec![0, 0, 0, 0, 1, 0],
 93            vec![0, 0, 0, 0, 0, 1],
 94            vec![0, 0, 1, 0, 0, 0],
 95        ]));
 96
 97        R1CS::<F> { l: 1, A, B, C }
 98    }
 99
100    pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
101        // z = (1, io, w)
102        to_F_vec(vec![
103            1,
104            input,                             // io
105            input * input * input + input + 5, // x^3 + x + 5
106            input * input,                     // x^2
107            input * input * input,             // x^2 * x
108            input * input * input + input,     // x^3 + x
109        ])
110    }
111
112    #[test]
113    fn test_check_relation() {
114        let r1cs = get_test_r1cs::<Fr>();
115        let z = get_test_z(5);
116        r1cs.check_relation(&z).unwrap();
117        r1cs.relax().check_relation(&z).unwrap();
118    }
119}