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}
 56impl<F: PrimeField> RelaxedR1CS<F> {
 57    /// check that a RelaxedR1CS structure is satisfied by a z vector. Only for testing.
 58    pub fn check_relation(&self, z: &[F]) -> Result<(), Error> {
 59        let Az = mat_vec_mul_sparse(&self.A, z);
 60        let Bz = mat_vec_mul_sparse(&self.B, z);
 61        let Cz = mat_vec_mul_sparse(&self.C, z);
 62        let uCz = vec_scalar_mul(&Cz, &self.u);
 63        let uCzE = vec_add(&uCz, &self.E);
 64        let AzBz = hadamard(&Az, &Bz);
 65        if AzBz != uCzE {
 66            return Err(Error::NotSatisfied);
 67        }
 68
 69        Ok(())
 70    }
 71}
 72
 73#[cfg(test)]
 74pub mod tests {
 75    use super::*;
 76    use crate::utils::vec::tests::{to_F_matrix, to_F_vec};
 77    use ark_pallas::Fr;
 78
 79    pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
 80        // R1CS for: x^3 + x + 5 = y (example from article
 81        // https://www.vitalik.ca/general/2016/12/10/qap.html )
 82        let A = to_F_matrix::<F>(vec![
 83            vec![0, 1, 0, 0, 0, 0],
 84            vec![0, 0, 0, 1, 0, 0],
 85            vec![0, 1, 0, 0, 1, 0],
 86            vec![5, 0, 0, 0, 0, 1],
 87        ]);
 88        let B = to_F_matrix::<F>(vec![
 89            vec![0, 1, 0, 0, 0, 0],
 90            vec![0, 1, 0, 0, 0, 0],
 91            vec![1, 0, 0, 0, 0, 0],
 92            vec![1, 0, 0, 0, 0, 0],
 93        ]);
 94        let C = to_F_matrix::<F>(vec![
 95            vec![0, 0, 0, 1, 0, 0],
 96            vec![0, 0, 0, 0, 1, 0],
 97            vec![0, 0, 0, 0, 0, 1],
 98            vec![0, 0, 1, 0, 0, 0],
 99        ]);
100
101        R1CS::<F> { l: 1, A, B, C }
102    }
103
104    pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
105        // z = (1, io, w)
106        to_F_vec(vec![
107            1,
108            input,                             // io
109            input * input * input + input + 5, // x^3 + x + 5
110            input * input,                     // x^2
111            input * input * input,             // x^2 * x
112            input * input * input + input,     // x^3 + x
113        ])
114    }
115
116    #[test]
117    fn test_check_relation() {
118        let r1cs = get_test_r1cs::<Fr>();
119        let z = get_test_z(5);
120        r1cs.check_relation(&z).unwrap();
121        r1cs.relax().check_relation(&z).unwrap();
122    }
123}