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