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