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