1use ark_ff::PrimeField;
  2use ark_std::log2;
  3
  4use crate::utils::vec::{hadamard, mat_vec_mul, vec_add, vec_scalar_mul, SparseMatrix};
  5use crate::Error;
  6
  7pub mod r1cs;
  8use r1cs::R1CS;
  9
 10/// CCS represents the Customizable Constraint Systems structure defined in
 11/// the [CCS paper](https://eprint.iacr.org/2023/552)
 12#[derive(Debug, Clone, Eq, PartialEq)]
 13pub struct CCS<F: PrimeField> {
 14    /// m: number of rows in M_i (such that M_i \in F^{m, n})
 15    pub m: usize,
 16    /// n = |z|, number of cols in M_i
 17    pub n: usize,
 18    /// l = |io|, size of public input/output
 19    pub l: usize,
 20    /// t = |M|, number of matrices
 21    pub t: usize,
 22    /// q = |c| = |S|, number of multisets
 23    pub q: usize,
 24    /// d: max degree in each variable
 25    pub d: usize,
 26    /// s = log(m), dimension of x
 27    pub s: usize,
 28    /// s_prime = log(n), dimension of y
 29    pub s_prime: usize,
 30
 31    /// vector of matrices
 32    pub M: Vec<SparseMatrix<F>>,
 33    /// vector of multisets
 34    pub S: Vec<Vec<usize>>,
 35    /// vector of coefficients
 36    pub c: Vec<F>,
 37}
 38
 39impl<F: PrimeField> CCS<F> {
 40    /// check that a CCS structure is satisfied by a z vector. Only for testing.
 41    pub fn check_relation(&self, z: &[F]) -> Result<(), Error> {
 42        let mut result = vec![F::zero(); self.m];
 43
 44        for i in 0..self.q {
 45            // extract the needed M_j matrices out of S_i
 46            let vec_M_j: Vec<&SparseMatrix<F>> = self.S[i].iter().map(|j| &self.M[*j]).collect();
 47
 48            // complete the hadamard chain
 49            let mut hadamard_result = vec![F::one(); self.m];
 50            for M_j in vec_M_j.into_iter() {
 51                hadamard_result = hadamard(&hadamard_result, &mat_vec_mul(M_j, z)?)?;
 52            }
 53
 54            // multiply by the coefficient of this step
 55            let c_M_j_z = vec_scalar_mul(&hadamard_result, &self.c[i]);
 56
 57            // add it to the final vector
 58            result = vec_add(&result, &c_M_j_z)?;
 59        }
 60
 61        // make sure the final vector is all zeroes
 62        for e in result {
 63            if !e.is_zero() {
 64                return Err(Error::NotSatisfied);
 65            }
 66        }
 67
 68        Ok(())
 69    }
 70}
 71
 72impl<F: PrimeField> CCS<F> {
 73    pub fn from_r1cs(r1cs: R1CS<F>) -> Self {
 74        let m = r1cs.A.n_rows;
 75        let n = r1cs.A.n_cols;
 76        CCS {
 77            m,
 78            n,
 79            l: r1cs.l,
 80            s: log2(m) as usize,
 81            s_prime: log2(n) as usize,
 82            t: 3,
 83            q: 2,
 84            d: 2,
 85
 86            S: vec![vec![0, 1], vec![2]],
 87            c: vec![F::one(), F::one().neg()],
 88            M: vec![r1cs.A, r1cs.B, r1cs.C],
 89        }
 90    }
 91
 92    pub fn to_r1cs(self) -> R1CS<F> {
 93        R1CS::<F> {
 94            l: self.l,
 95            A: self.M[0].clone(),
 96            B: self.M[1].clone(),
 97            C: self.M[2].clone(),
 98        }
 99    }
100}
101
102#[cfg(test)]
103pub mod tests {
104    use super::*;
105    use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z as r1cs_get_test_z};
106    use ark_ff::PrimeField;
107    use ark_pallas::Fr;
108
109    pub fn get_test_ccs<F: PrimeField>() -> CCS<F> {
110        let r1cs = get_test_r1cs::<F>();
111        CCS::<F>::from_r1cs(r1cs)
112    }
113    pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
114        r1cs_get_test_z(input)
115    }
116
117    /// Test that a basic CCS relation can be satisfied
118    #[test]
119    fn test_ccs_relation() {
120        let ccs = get_test_ccs::<Fr>();
121        let z = get_test_z(3);
122
123        ccs.check_relation(&z).unwrap();
124    }
125}