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