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