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