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