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