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