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