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    ) -> (LCCCS<C>, Witness<C::ScalarField>) {
 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        (
 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        assert_eq!(self.C, Pedersen::commit(pedersen_params, &w.w, &w.r_w));
 98
 99        // check CCS relation
100        let z: Vec<C::ScalarField> = [vec![self.u], self.x.clone(), w.w.to_vec()].concat();
101        let computed_v = compute_all_sum_Mz_evals(&ccs.M, &z, &self.r_x, ccs.s_prime);
102        assert_eq!(computed_v, self.v);
103        Ok(())
104    }
105}
106
107#[cfg(test)]
108pub mod tests {
109    use super::*;
110    use ark_std::Zero;
111
112    use crate::ccs::tests::{get_test_ccs, get_test_z};
113    use crate::utils::hypercube::BooleanHypercube;
114    use ark_std::test_rng;
115
116    use ark_pallas::{Fr, Projective};
117
118    #[test]
119    /// Test linearized CCCS v_j against the L_j(x)
120    fn test_lcccs_v_j() {
121        let mut rng = test_rng();
122
123        let ccs = get_test_ccs();
124        let z = get_test_z(3);
125        ccs.check_relation(&z.clone()).unwrap();
126
127        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, ccs.n - ccs.l - 1);
128        let (lcccs, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z);
129        // with our test vector comming from R1CS, v should have length 3
130        assert_eq!(lcccs.v.len(), 3);
131
132        let vec_L_j_x = lcccs.compute_Ls(&ccs, &z);
133        assert_eq!(vec_L_j_x.len(), lcccs.v.len());
134
135        for (v_i, L_j_x) in lcccs.v.into_iter().zip(vec_L_j_x) {
136            let sum_L_j_x = BooleanHypercube::new(ccs.s)
137                .map(|y| L_j_x.evaluate(&y).unwrap())
138                .fold(Fr::zero(), |acc, result| acc + result);
139            assert_eq!(v_i, sum_L_j_x);
140        }
141    }
142
143    /// Given a bad z, check that the v_j should not match with the L_j(x)
144    #[test]
145    fn test_bad_v_j() {
146        let mut rng = test_rng();
147
148        let ccs = get_test_ccs();
149        let z = get_test_z(3);
150        ccs.check_relation(&z.clone()).unwrap();
151
152        // Mutate z so that the relation does not hold
153        let mut bad_z = z.clone();
154        bad_z[3] = Fr::zero();
155        assert!(ccs.check_relation(&bad_z.clone()).is_err());
156
157        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, ccs.n - ccs.l - 1);
158        // Compute v_j with the right z
159        let (lcccs, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z);
160        // with our test vector comming from R1CS, v should have length 3
161        assert_eq!(lcccs.v.len(), 3);
162
163        // Bad compute L_j(x) with the bad z
164        let vec_L_j_x = lcccs.compute_Ls(&ccs, &bad_z);
165        assert_eq!(vec_L_j_x.len(), lcccs.v.len());
166
167        // Make sure that the LCCCS is not satisfied given these L_j(x)
168        // i.e. summing L_j(x) over the hypercube should not give v_j for all j
169        let mut satisfied = true;
170        for (v_i, L_j_x) in lcccs.v.into_iter().zip(vec_L_j_x) {
171            let sum_L_j_x = BooleanHypercube::new(ccs.s)
172                .map(|y| L_j_x.evaluate(&y).unwrap())
173                .fold(Fr::zero(), |acc, result| acc + result);
174            if v_i != sum_L_j_x {
175                satisfied = false;
176            }
177        }
178
179        assert!(!satisfied);
180    }
181}