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