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