1use ark_ff::PrimeField;
  2
  3use crate::utils::vec::*;
  4use crate::Error;
  5use ark_relations::r1cs::ConstraintSystem;
  6
  7#[derive(Debug, Clone, Eq, PartialEq)]
  8pub struct R1CS<F: PrimeField> {
  9    pub l: usize, // io len
 10    pub A: SparseMatrix<F>,
 11    pub B: SparseMatrix<F>,
 12    pub C: SparseMatrix<F>,
 13}
 14
 15impl<F: PrimeField> R1CS<F> {
 16    /// returns a tuple containing (w, x) (witness and public inputs respectively)
 17    pub fn split_z(&self, z: &[F]) -> (Vec<F>, Vec<F>) {
 18        (z[self.l + 1..].to_vec(), z[1..self.l + 1].to_vec())
 19    }
 20
 21    /// check that a R1CS structure is satisfied by a z vector. Only for testing.
 22    pub fn check_relation(&self, z: &[F]) -> Result<(), Error> {
 23        let Az = mat_vec_mul_sparse(&self.A, z)?;
 24        let Bz = mat_vec_mul_sparse(&self.B, z)?;
 25        let Cz = mat_vec_mul_sparse(&self.C, z)?;
 26        let AzBz = hadamard(&Az, &Bz)?;
 27        if AzBz != Cz {
 28            return Err(Error::NotSatisfied);
 29        }
 30
 31        Ok(())
 32    }
 33
 34    /// converts the R1CS instance into a RelaxedR1CS as described in
 35    /// [Nova](https://eprint.iacr.org/2021/370.pdf) section 4.1.
 36    pub fn relax(self) -> RelaxedR1CS<F> {
 37        RelaxedR1CS::<F> {
 38            l: self.l,
 39            E: vec![F::zero(); self.A.n_rows],
 40            A: self.A,
 41            B: self.B,
 42            C: self.C,
 43            u: F::one(),
 44        }
 45    }
 46}
 47
 48#[derive(Debug, Clone, Eq, PartialEq)]
 49pub struct RelaxedR1CS<F: PrimeField> {
 50    pub l: usize, // io len
 51    pub A: SparseMatrix<F>,
 52    pub B: SparseMatrix<F>,
 53    pub C: SparseMatrix<F>,
 54    pub u: F,
 55    pub E: Vec<F>,
 56}
 57
 58impl<F: PrimeField> RelaxedR1CS<F> {
 59    /// check that a RelaxedR1CS structure is satisfied by a z vector. Only for testing.
 60    pub fn check_relation(&self, z: &[F]) -> Result<(), Error> {
 61        let Az = mat_vec_mul_sparse(&self.A, z)?;
 62        let Bz = mat_vec_mul_sparse(&self.B, z)?;
 63        let Cz = mat_vec_mul_sparse(&self.C, z)?;
 64        let uCz = vec_scalar_mul(&Cz, &self.u);
 65        let uCzE = vec_add(&uCz, &self.E)?;
 66        let AzBz = hadamard(&Az, &Bz)?;
 67        if AzBz != uCzE {
 68            return Err(Error::NotSatisfied);
 69        }
 70
 71        Ok(())
 72    }
 73}
 74
 75/// extracts arkworks ConstraintSystem matrices into crate::utils::vec::SparseMatrix format as R1CS
 76/// struct.
 77pub fn extract_r1cs<F: PrimeField>(cs: &ConstraintSystem<F>) -> R1CS<F> {
 78    let m = cs.to_matrices().unwrap();
 79
 80    let n_rows = cs.num_constraints;
 81    let n_cols = cs.num_instance_variables + cs.num_witness_variables; // cs.num_instance_variables already counts the 1
 82
 83    let A = SparseMatrix::<F> {
 84        n_rows,
 85        n_cols,
 86        coeffs: m.a,
 87    };
 88    let B = SparseMatrix::<F> {
 89        n_rows,
 90        n_cols,
 91        coeffs: m.b,
 92    };
 93    let C = SparseMatrix::<F> {
 94        n_rows,
 95        n_cols,
 96        coeffs: m.c,
 97    };
 98
 99    R1CS::<F> {
100        l: cs.num_instance_variables - 1, // -1 to substract the first '1'
101        A,
102        B,
103        C,
104    }
105}
106
107/// extracts the witness and the public inputs from arkworks ConstraintSystem.
108pub fn extract_w_x<F: PrimeField>(cs: &ConstraintSystem<F>) -> (Vec<F>, Vec<F>) {
109    (
110        cs.witness_assignment.clone(),
111        // skip the first element which is '1'
112        cs.instance_assignment[1..].to_vec(),
113    )
114}
115
116#[cfg(test)]
117pub mod tests {
118    use super::*;
119    use crate::utils::vec::tests::{to_F_matrix, to_F_vec};
120
121    use ark_ff::PrimeField;
122    use ark_pallas::Fr;
123
124    pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
125        // R1CS for: x^3 + x + 5 = y (example from article
126        // https://www.vitalik.ca/general/2016/12/10/qap.html )
127        let A = to_F_matrix::<F>(vec![
128            vec![0, 1, 0, 0, 0, 0],
129            vec![0, 0, 0, 1, 0, 0],
130            vec![0, 1, 0, 0, 1, 0],
131            vec![5, 0, 0, 0, 0, 1],
132        ]);
133        let B = to_F_matrix::<F>(vec![
134            vec![0, 1, 0, 0, 0, 0],
135            vec![0, 1, 0, 0, 0, 0],
136            vec![1, 0, 0, 0, 0, 0],
137            vec![1, 0, 0, 0, 0, 0],
138        ]);
139        let C = to_F_matrix::<F>(vec![
140            vec![0, 0, 0, 1, 0, 0],
141            vec![0, 0, 0, 0, 1, 0],
142            vec![0, 0, 0, 0, 0, 1],
143            vec![0, 0, 1, 0, 0, 0],
144        ]);
145
146        R1CS::<F> { l: 1, A, B, C }
147    }
148
149    pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
150        // z = (1, io, w)
151        to_F_vec(vec![
152            1,
153            input,                             // io
154            input * input * input + input + 5, // x^3 + x + 5
155            input * input,                     // x^2
156            input * input * input,             // x^2 * x
157            input * input * input + input,     // x^3 + x
158        ])
159    }
160
161    #[test]
162    fn test_check_relation() {
163        let r1cs = get_test_r1cs::<Fr>();
164        let z = get_test_z(5);
165        r1cs.check_relation(&z).unwrap();
166        r1cs.relax().check_relation(&z).unwrap();
167    }
168}