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