1use ark_ec::CurveGroup;
  2use ark_poly::DenseMultilinearExtension;
  3use ark_std::One;
  4use std::sync::Arc;
  5
  6use ark_std::{rand::Rng, UniformRand};
  7
  8use super::cccs::Witness;
  9use super::utils::{compute_all_sum_Mz_evals, compute_sum_Mz};
 10use crate::ccs::CCS;
 11use crate::commitment::{
 12    pedersen::{Params as PedersenParams, Pedersen},
 13    CommitmentProver,
 14};
 15use crate::utils::mle::{matrix_to_mle, vec_to_mle};
 16use crate::utils::virtual_polynomial::VirtualPolynomial;
 17use crate::Error;
 18
 19/// Linearized Committed CCS instance
 20#[derive(Debug, Clone, Eq, PartialEq)]
 21pub struct LCCCS<C: CurveGroup> {
 22    // Commitment to witness
 23    pub C: C,
 24    // Relaxation factor of z for folded LCCCS
 25    pub u: C::ScalarField,
 26    // Public input/output
 27    pub x: Vec<C::ScalarField>,
 28    // Random evaluation point for the v_i
 29    pub r_x: Vec<C::ScalarField>,
 30    // Vector of v_i
 31    pub v: Vec<C::ScalarField>,
 32}
 33
 34impl<C: CurveGroup> CCS<C> {
 35    /// Compute v_j values of the linearized committed CCS form
 36    /// Given `r`, compute:  \sum_{y \in {0,1}^s'} M_j(r, y) * z(y)
 37    fn compute_v_j(&self, z: &[C::ScalarField], r: &[C::ScalarField]) -> Vec<C::ScalarField> {
 38        compute_all_sum_Mz_evals(&self.M, &z.to_vec(), r, self.s_prime)
 39    }
 40
 41    pub fn to_lcccs<R: Rng>(
 42        &self,
 43        rng: &mut R,
 44        pedersen_params: &PedersenParams<C>,
 45        z: &[C::ScalarField],
 46    ) -> Result<(LCCCS<C>, Witness<C::ScalarField>), Error> {
 47        let w: Vec<C::ScalarField> = z[(1 + self.l)..].to_vec();
 48        let r_w = C::ScalarField::rand(rng);
 49        let C = Pedersen::commit(pedersen_params, &w, &r_w)?;
 50
 51        let r_x: Vec<C::ScalarField> = (0..self.s).map(|_| C::ScalarField::rand(rng)).collect();
 52        let v = self.compute_v_j(z, &r_x);
 53
 54        Ok((
 55            LCCCS::<C> {
 56                C,
 57                u: C::ScalarField::one(),
 58                x: z[1..(1 + self.l)].to_vec(),
 59                r_x,
 60                v,
 61            },
 62            Witness::<C::ScalarField> { w, r_w },
 63        ))
 64    }
 65}
 66
 67impl<C: CurveGroup> LCCCS<C> {
 68    /// Compute all L_j(x) polynomials
 69    pub fn compute_Ls(
 70        &self,
 71        ccs: &CCS<C>,
 72        z: &Vec<C::ScalarField>,
 73    ) -> Vec<VirtualPolynomial<C::ScalarField>> {
 74        let z_mle = vec_to_mle(ccs.s_prime, z);
 75        // Convert all matrices to MLE
 76        let M_x_y_mle: Vec<DenseMultilinearExtension<C::ScalarField>> =
 77            ccs.M.clone().into_iter().map(matrix_to_mle).collect();
 78
 79        let mut vec_L_j_x = Vec::with_capacity(ccs.t);
 80        for M_j in M_x_y_mle {
 81            let sum_Mz = compute_sum_Mz(M_j, &z_mle, ccs.s_prime);
 82            let sum_Mz_virtual =
 83                VirtualPolynomial::new_from_mle(&Arc::new(sum_Mz.clone()), C::ScalarField::one());
 84            let L_j_x = sum_Mz_virtual.build_f_hat(&self.r_x).unwrap();
 85            vec_L_j_x.push(L_j_x);
 86        }
 87
 88        vec_L_j_x
 89    }
 90
 91    /// Perform the check of the LCCCS instance described at section 4.2
 92    pub fn check_relation(
 93        &self,
 94        pedersen_params: &PedersenParams<C>,
 95        ccs: &CCS<C>,
 96        w: &Witness<C::ScalarField>,
 97    ) -> Result<(), Error> {
 98        // check that C is the commitment of w. Notice that this is not verifying a Pedersen
 99        // opening, but checking that the Commmitment comes from committing to the witness.
100        if self.C != Pedersen::commit(pedersen_params, &w.w, &w.r_w)? {
101            return Err(Error::NotSatisfied);
102        }
103
104        // check CCS relation
105        let z: Vec<C::ScalarField> = [vec![self.u], self.x.clone(), w.w.to_vec()].concat();
106        let computed_v = compute_all_sum_Mz_evals(&ccs.M, &z, &self.r_x, ccs.s_prime);
107        if computed_v != self.v {
108            return Err(Error::NotSatisfied);
109        }
110        Ok(())
111    }
112}
113
114#[cfg(test)]
115pub mod tests {
116    use super::*;
117    use ark_std::Zero;
118
119    use crate::ccs::tests::{get_test_ccs, get_test_z};
120    use crate::utils::hypercube::BooleanHypercube;
121    use ark_std::test_rng;
122
123    use ark_pallas::{Fr, Projective};
124
125    #[test]
126    /// Test linearized CCCS v_j against the L_j(x)
127    fn test_lcccs_v_j() {
128        let mut rng = test_rng();
129
130        let ccs = get_test_ccs();
131        let z = get_test_z(3);
132        ccs.check_relation(&z.clone()).unwrap();
133
134        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, ccs.n - ccs.l - 1);
135        let (lcccs, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z).unwrap();
136        // with our test vector comming from R1CS, v should have length 3
137        assert_eq!(lcccs.v.len(), 3);
138
139        let vec_L_j_x = lcccs.compute_Ls(&ccs, &z);
140        assert_eq!(vec_L_j_x.len(), lcccs.v.len());
141
142        for (v_i, L_j_x) in lcccs.v.into_iter().zip(vec_L_j_x) {
143            let sum_L_j_x = BooleanHypercube::new(ccs.s)
144                .map(|y| L_j_x.evaluate(&y).unwrap())
145                .fold(Fr::zero(), |acc, result| acc + result);
146            assert_eq!(v_i, sum_L_j_x);
147        }
148    }
149
150    /// Given a bad z, check that the v_j should not match with the L_j(x)
151    #[test]
152    fn test_bad_v_j() {
153        let mut rng = test_rng();
154
155        let ccs = get_test_ccs();
156        let z = get_test_z(3);
157        ccs.check_relation(&z.clone()).unwrap();
158
159        // Mutate z so that the relation does not hold
160        let mut bad_z = z.clone();
161        bad_z[3] = Fr::zero();
162        assert!(ccs.check_relation(&bad_z.clone()).is_err());
163
164        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, ccs.n - ccs.l - 1);
165        // Compute v_j with the right z
166        let (lcccs, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z).unwrap();
167        // with our test vector comming from R1CS, v should have length 3
168        assert_eq!(lcccs.v.len(), 3);
169
170        // Bad compute L_j(x) with the bad z
171        let vec_L_j_x = lcccs.compute_Ls(&ccs, &bad_z);
172        assert_eq!(vec_L_j_x.len(), lcccs.v.len());
173
174        // Make sure that the LCCCS is not satisfied given these L_j(x)
175        // i.e. summing L_j(x) over the hypercube should not give v_j for all j
176        let mut satisfied = true;
177        for (v_i, L_j_x) in lcccs.v.into_iter().zip(vec_L_j_x) {
178            let sum_L_j_x = BooleanHypercube::new(ccs.s)
179                .map(|y| L_j_x.evaluate(&y).unwrap())
180                .fold(Fr::zero(), |acc, result| acc + result);
181            if v_i != sum_L_j_x {
182                satisfied = false;
183            }
184        }
185
186        assert!(!satisfied);
187    }
188}