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