1use ark_ec::CurveGroup;
  2use ark_ff::PrimeField;
  3use ark_std::One;
  4use ark_std::Zero;
  5use std::sync::Arc;
  6
  7use ark_std::rand::Rng;
  8
  9use super::Witness;
 10use crate::ccs::CCS;
 11use crate::commitment::CommitmentScheme;
 12use crate::utils::mle::dense_vec_to_dense_mle;
 13use crate::utils::vec::mat_vec_mul;
 14use crate::utils::virtual_polynomial::{build_eq_x_r_vec, VirtualPolynomial};
 15use crate::Error;
 16
 17/// Committed CCS instance
 18#[derive(Debug, Clone)]
 19pub struct CCCS<C: CurveGroup> {
 20    // Commitment to witness
 21    pub C: C,
 22    // Public input/output
 23    pub x: Vec<C::ScalarField>,
 24}
 25
 26impl<F: PrimeField> CCS<F> {
 27    pub fn to_cccs<R: Rng, C: CurveGroup, CS: CommitmentScheme<C>>(
 28        &self,
 29        rng: &mut R,
 30        cs_params: &CS::ProverParams,
 31        z: &[C::ScalarField],
 32    ) -> Result<(CCCS<C>, Witness<C::ScalarField>), Error>
 33    where
 34        // enforce that CCS's F is the C::ScalarField
 35        C: CurveGroup<ScalarField = F>,
 36    {
 37        let w: Vec<C::ScalarField> = z[(1 + self.l)..].to_vec();
 38
 39        // if the commitment scheme is set to be hiding, set the random blinding parameter
 40        let r_w = if CS::is_hiding() {
 41            C::ScalarField::rand(rng)
 42        } else {
 43            C::ScalarField::zero()
 44        };
 45        let C = CS::commit(cs_params, &w, &r_w)?;
 46
 47        Ok((
 48            CCCS::<C> {
 49                C,
 50                x: z[1..(1 + self.l)].to_vec(),
 51            },
 52            Witness::<C::ScalarField> { w, r_w },
 53        ))
 54    }
 55
 56    /// Computes q(x) = \sum^q c_i * \prod_{j \in S_i} ( \sum_{y \in {0,1}^s'} M_j(x, y) * z(y) )
 57    /// polynomial over x
 58    pub fn compute_q(&self, z: &[F]) -> Result<VirtualPolynomial<F>, Error> {
 59        let mut q_x = VirtualPolynomial::<F>::new(self.s);
 60        for i in 0..self.q {
 61            let mut Q_k = vec![];
 62            for &j in self.S[i].iter() {
 63                Q_k.push(dense_vec_to_dense_mle(self.s, &mat_vec_mul(&self.M[j], z)?));
 64            }
 65            q_x.add_mle_list(Q_k.iter().map(|v| Arc::new(v.clone())), self.c[i])?;
 66        }
 67        Ok(q_x)
 68    }
 69
 70    /// Computes Q(x) = eq(beta, x) * q(x)
 71    ///               = eq(beta, x) * \sum^q c_i * \prod_{j \in S_i} ( \sum_{y \in {0,1}^s'} M_j(x, y) * z(y) )
 72    /// polynomial over x
 73    pub fn compute_Q(&self, z: &[F], beta: &[F]) -> Result<VirtualPolynomial<F>, Error> {
 74        let eq_beta = build_eq_x_r_vec(beta)?;
 75        let eq_beta_mle = dense_vec_to_dense_mle(self.s, &eq_beta);
 76
 77        let mut Q = VirtualPolynomial::<F>::new(self.s);
 78        for i in 0..self.q {
 79            let mut Q_k = vec![];
 80            for &j in self.S[i].iter() {
 81                Q_k.push(dense_vec_to_dense_mle(self.s, &mat_vec_mul(&self.M[j], z)?));
 82            }
 83            Q_k.push(eq_beta_mle.clone());
 84            Q.add_mle_list(Q_k.iter().map(|v| Arc::new(v.clone())), self.c[i])?;
 85        }
 86        Ok(Q)
 87    }
 88}
 89
 90impl<C: CurveGroup> CCCS<C> {
 91    pub fn dummy(l: usize) -> CCCS<C>
 92    where
 93        C::ScalarField: PrimeField,
 94    {
 95        CCCS::<C> {
 96            C: C::zero(),
 97            x: vec![C::ScalarField::zero(); l],
 98        }
 99    }
100
101    /// Perform the check of the CCCS instance described at section 4.1,
102    /// notice that this method does not check the commitment correctness
103    pub fn check_relation(
104        &self,
105        ccs: &CCS<C::ScalarField>,
106        w: &Witness<C::ScalarField>,
107    ) -> Result<(), Error> {
108        // check CCCS relation
109        let z: Vec<C::ScalarField> =
110            [vec![C::ScalarField::one()], self.x.clone(), w.w.to_vec()].concat();
111
112        // A CCCS relation is satisfied if the q(x) multivariate polynomial evaluates to zero in
113        // the hypercube, evaluating over the whole boolean hypercube for a normal-sized instance
114        // would take too much, this checks the CCS relation of the CCCS.
115        ccs.check_relation(&z)?;
116
117        Ok(())
118    }
119}
120
121#[cfg(test)]
122pub mod tests {
123    use ark_pallas::Fr;
124    use ark_std::test_rng;
125    use ark_std::UniformRand;
126
127    use super::*;
128    use crate::ccs::tests::{get_test_ccs, get_test_z};
129    use crate::utils::hypercube::BooleanHypercube;
130
131    /// Do some sanity checks on q(x). It's a multivariable polynomial and it should evaluate to zero inside the
132    /// hypercube, but to not-zero outside the hypercube.
133    #[test]
134    fn test_compute_q() {
135        let mut rng = test_rng();
136
137        let ccs = get_test_ccs::<Fr>();
138        let z = get_test_z(3);
139
140        let q = ccs.compute_q(&z).unwrap();
141
142        // Evaluate inside the hypercube
143        for x in BooleanHypercube::new(ccs.s) {
144            assert_eq!(Fr::zero(), q.evaluate(&x).unwrap());
145        }
146
147        // Evaluate outside the hypercube
148        let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
149        assert_ne!(Fr::zero(), q.evaluate(&beta).unwrap());
150    }
151
152    /// Perform some sanity checks on Q(x).
153    #[test]
154    fn test_compute_Q() {
155        let mut rng = test_rng();
156
157        let ccs: CCS<Fr> = get_test_ccs();
158        let z = get_test_z(3);
159        ccs.check_relation(&z).unwrap();
160
161        let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
162
163        // Compute Q(x) = eq(beta, x) * q(x).
164        let Q = ccs.compute_Q(&z, &beta).unwrap();
165
166        // Let's consider the multilinear polynomial G(x) = \sum_{y \in {0, 1}^s} eq(x, y) q(y)
167        // which interpolates the multivariate polynomial q(x) inside the hypercube.
168        //
169        // Observe that summing Q(x) inside the hypercube, directly computes G(\beta).
170        //
171        // Now, G(x) is multilinear and agrees with q(x) inside the hypercube. Since q(x) vanishes inside the
172        // hypercube, this means that G(x) also vanishes in the hypercube. Since G(x) is multilinear and vanishes
173        // inside the hypercube, this makes it the zero polynomial.
174        //
175        // Hence, evaluating G(x) at a random beta should give zero.
176
177        // Now sum Q(x) evaluations in the hypercube and expect it to be 0
178        let r = BooleanHypercube::new(ccs.s)
179            .map(|x| Q.evaluate(&x).unwrap())
180            .fold(Fr::zero(), |acc, result| acc + result);
181        assert_eq!(r, Fr::zero());
182    }
183
184    /// The polynomial G(x) (see above) interpolates q(x) inside the hypercube.
185    /// Summing Q(x) over the hypercube is equivalent to evaluating G(x) at some point.
186    /// This test makes sure that G(x) agrees with q(x) inside the hypercube, but not outside
187    #[test]
188    fn test_Q_against_q() {
189        let mut rng = test_rng();
190
191        let ccs: CCS<Fr> = get_test_ccs();
192        let z = get_test_z(3);
193        ccs.check_relation(&z).unwrap();
194
195        // Now test that if we create Q(x) with eq(d,y) where d is inside the hypercube, \sum Q(x) should be G(d) which
196        // should be equal to q(d), since G(x) interpolates q(x) inside the hypercube
197        let q = ccs.compute_q(&z).unwrap();
198        for d in BooleanHypercube::new(ccs.s) {
199            let Q_at_d = ccs.compute_Q(&z, &d).unwrap();
200
201            // Get G(d) by summing over Q_d(x) over the hypercube
202            let G_at_d = BooleanHypercube::new(ccs.s)
203                .map(|x| Q_at_d.evaluate(&x).unwrap())
204                .fold(Fr::zero(), |acc, result| acc + result);
205            assert_eq!(G_at_d, q.evaluate(&d).unwrap());
206        }
207
208        // Now test that they should disagree outside of the hypercube
209        let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
210        let Q_at_r = ccs.compute_Q(&z, &r).unwrap();
211
212        // Get G(d) by summing over Q_d(x) over the hypercube
213        let G_at_r = BooleanHypercube::new(ccs.s)
214            .map(|x| Q_at_r.evaluate(&x).unwrap())
215            .fold(Fr::zero(), |acc, result| acc + result);
216        assert_ne!(G_at_r, q.evaluate(&r).unwrap());
217    }
218}