1use ark_crypto_primitives::sponge::Absorb;
  2use ark_ec::CurveGroup;
  3use ark_ff::PrimeField;
  4use ark_poly::DenseMultilinearExtension;
  5use ark_poly::MultilinearExtension;
  6use ark_serialize::CanonicalDeserialize;
  7use ark_serialize::CanonicalSerialize;
  8use ark_std::rand::Rng;
  9use ark_std::Zero;
 10
 11use super::circuits::LCCCSVar;
 12use super::Witness;
 13use crate::arith::ccs::CCS;
 14use crate::arith::Arith;
 15use crate::commitment::CommitmentScheme;
 16use crate::folding::circuits::CF1;
 17use crate::folding::traits::Inputize;
 18use crate::folding::traits::{CommittedInstanceOps, Dummy};
 19use crate::transcript::AbsorbNonNative;
 20use crate::utils::mle::dense_vec_to_dense_mle;
 21use crate::utils::vec::mat_vec_mul;
 22use crate::Error;
 23
 24/// Linearized Committed CCS instance
 25#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 26pub struct LCCCS<C: CurveGroup> {
 27    // Commitment to witness
 28    pub C: C,
 29    // Relaxation factor of z for folded LCCCS
 30    pub u: C::ScalarField,
 31    // Public input/output
 32    pub x: Vec<C::ScalarField>,
 33    // Random evaluation point for the v_i
 34    pub r_x: Vec<C::ScalarField>,
 35    // Vector of v_i
 36    pub v: Vec<C::ScalarField>,
 37}
 38
 39impl<F: PrimeField> CCS<F> {
 40    pub fn to_lcccs<R: Rng, C, CS: CommitmentScheme<C, H>, const H: bool>(
 41        &self,
 42        rng: &mut R,
 43        cs_params: &CS::ProverParams,
 44        z: &[C::ScalarField],
 45    ) -> Result<(LCCCS<C>, Witness<C::ScalarField>), Error>
 46    where
 47        // enforce that CCS's F is the C::ScalarField
 48        C: CurveGroup<ScalarField = F>,
 49    {
 50        let w: Vec<C::ScalarField> = z[(1 + self.l)..].to_vec();
 51        // if the commitment scheme is set to be hiding, set the random blinding parameter
 52        let r_w = if CS::is_hiding() {
 53            C::ScalarField::rand(rng)
 54        } else {
 55            C::ScalarField::zero()
 56        };
 57        let C = CS::commit(cs_params, &w, &r_w)?;
 58
 59        let r_x: Vec<C::ScalarField> = (0..self.s).map(|_| C::ScalarField::rand(rng)).collect();
 60
 61        let Mzs: Vec<DenseMultilinearExtension<F>> = self
 62            .M
 63            .iter()
 64            .map(|M_j| Ok(dense_vec_to_dense_mle(self.s, &mat_vec_mul(M_j, z)?)))
 65            .collect::<Result<_, Error>>()?;
 66
 67        // compute v_j
 68        let v: Vec<F> = Mzs
 69            .iter()
 70            .map(|Mz| Mz.evaluate(&r_x).ok_or(Error::EvaluationFail))
 71            .collect::<Result<_, Error>>()?;
 72
 73        Ok((
 74            LCCCS::<C> {
 75                C,
 76                u: z[0],
 77                x: z[1..(1 + self.l)].to_vec(),
 78                r_x,
 79                v,
 80            },
 81            Witness::<C::ScalarField> { w, r_w },
 82        ))
 83    }
 84}
 85
 86impl<C: CurveGroup> Dummy<&CCS<CF1<C>>> for LCCCS<C> {
 87    fn dummy(ccs: &CCS<CF1<C>>) -> Self {
 88        Self {
 89            C: C::zero(),
 90            u: CF1::<C>::zero(),
 91            x: vec![CF1::<C>::zero(); ccs.l],
 92            r_x: vec![CF1::<C>::zero(); ccs.s],
 93            v: vec![CF1::<C>::zero(); ccs.t],
 94        }
 95    }
 96}
 97
 98impl<C: CurveGroup> Arith<Witness<CF1<C>>, LCCCS<C>> for CCS<CF1<C>> {
 99    type Evaluation = Vec<CF1<C>>;
100
101    /// Perform the check of the LCCCS instance described at section 4.2,
102    /// notice that this method does not check the commitment correctness
103    fn eval_relation(&self, w: &Witness<CF1<C>>, u: &LCCCS<C>) -> Result<Self::Evaluation, Error> {
104        let z = [&[u.u][..], &u.x, &w.w].concat();
105
106        self.M
107            .iter()
108            .map(|M_j| {
109                let Mz_mle = dense_vec_to_dense_mle(self.s, &mat_vec_mul(M_j, &z)?);
110                Mz_mle.evaluate(&u.r_x).ok_or(Error::EvaluationFail)
111            })
112            .collect()
113    }
114
115    fn check_evaluation(
116        _w: &Witness<CF1<C>>,
117        u: &LCCCS<C>,
118        e: Self::Evaluation,
119    ) -> Result<(), Error> {
120        (u.v == e).then_some(()).ok_or(Error::NotSatisfied)
121    }
122}
123
124impl<C: CurveGroup> Absorb for LCCCS<C>
125where
126    C::ScalarField: Absorb,
127{
128    fn to_sponge_bytes(&self, dest: &mut Vec<u8>) {
129        C::ScalarField::batch_to_sponge_bytes(&self.to_sponge_field_elements_as_vec(), dest);
130    }
131
132    fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
133        // We cannot call `to_native_sponge_field_elements(dest)` directly, as
134        // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
135        // but here `F` is a generic `PrimeField`.
136        self.C
137            .to_native_sponge_field_elements_as_vec()
138            .to_sponge_field_elements(dest);
139        self.u.to_sponge_field_elements(dest);
140        self.x.to_sponge_field_elements(dest);
141        self.r_x.to_sponge_field_elements(dest);
142        self.v.to_sponge_field_elements(dest);
143    }
144}
145
146impl<C: CurveGroup> CommittedInstanceOps<C> for LCCCS<C> {
147    type Var = LCCCSVar<C>;
148
149    fn get_commitments(&self) -> Vec<C> {
150        vec![self.C]
151    }
152
153    fn is_incoming(&self) -> bool {
154        false
155    }
156}
157
158impl<C: CurveGroup> Inputize<C::ScalarField, LCCCSVar<C>> for LCCCS<C> {
159    fn inputize(&self) -> Vec<C::ScalarField> {
160        [
161            &self.C.inputize(),
162            &[self.u][..],
163            &self.x,
164            &self.r_x,
165            &self.v,
166        ]
167        .concat()
168    }
169}
170
171#[cfg(test)]
172pub mod tests {
173    use ark_pallas::{Fr, Projective};
174    use ark_std::test_rng;
175    use ark_std::One;
176    use ark_std::UniformRand;
177    use std::sync::Arc;
178
179    use super::*;
180    use crate::arith::{
181        ccs::tests::{get_test_ccs, get_test_z},
182        r1cs::R1CS,
183        Arith,
184    };
185    use crate::commitment::pedersen::Pedersen;
186    use crate::utils::hypercube::BooleanHypercube;
187    use crate::utils::virtual_polynomial::{build_eq_x_r_vec, VirtualPolynomial};
188
189    // method for testing
190    pub fn compute_Ls<C: CurveGroup>(
191        ccs: &CCS<C::ScalarField>,
192        lcccs: &LCCCS<C>,
193        z: &[C::ScalarField],
194    ) -> Vec<VirtualPolynomial<C::ScalarField>> {
195        let eq_rx = build_eq_x_r_vec(&lcccs.r_x).unwrap();
196        let eq_rx_mle = dense_vec_to_dense_mle(ccs.s, &eq_rx);
197
198        let mut Ls = Vec::with_capacity(ccs.t);
199        for M_j in ccs.M.iter() {
200            let mut L = VirtualPolynomial::<C::ScalarField>::new(ccs.s);
201            let mut Mz = vec![dense_vec_to_dense_mle(ccs.s, &mat_vec_mul(M_j, z).unwrap())];
202            Mz.push(eq_rx_mle.clone());
203            L.add_mle_list(
204                Mz.iter().map(|v| Arc::new(v.clone())),
205                C::ScalarField::one(),
206            )
207            .unwrap();
208            Ls.push(L);
209        }
210        Ls
211    }
212
213    #[test]
214    /// Test linearized CCCS v_j against the L_j(x)
215    fn test_lcccs_v_j() {
216        let mut rng = test_rng();
217
218        let n_rows = 2_u32.pow(5) as usize;
219        let n_cols = 2_u32.pow(5) as usize;
220        let r1cs = R1CS::<Fr>::rand(&mut rng, n_rows, n_cols);
221        let ccs = CCS::from(r1cs);
222        let z: Vec<Fr> = (0..n_cols).map(|_| Fr::rand(&mut rng)).collect();
223
224        let (pedersen_params, _) =
225            Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
226
227        let (lcccs, _) = ccs
228            .to_lcccs::<_, Projective, Pedersen<Projective, false>, false>(
229                &mut rng,
230                &pedersen_params,
231                &z,
232            )
233            .unwrap();
234        // with our test vector coming from R1CS, v should have length 3
235        assert_eq!(lcccs.v.len(), 3);
236
237        let vec_L_j_x = compute_Ls(&ccs, &lcccs, &z);
238        assert_eq!(vec_L_j_x.len(), lcccs.v.len());
239
240        for (v_i, L_j_x) in lcccs.v.into_iter().zip(vec_L_j_x) {
241            let sum_L_j_x = BooleanHypercube::new(ccs.s)
242                .map(|y| L_j_x.evaluate(&y).unwrap())
243                .fold(Fr::zero(), |acc, result| acc + result);
244            assert_eq!(v_i, sum_L_j_x);
245        }
246    }
247
248    /// Given a bad z, check that the v_j should not match with the L_j(x)
249    #[test]
250    fn test_bad_v_j() {
251        let mut rng = test_rng();
252
253        let ccs = get_test_ccs();
254        let z = get_test_z(3);
255        let (w, x) = ccs.split_z(&z);
256        ccs.check_relation(&w, &x).unwrap();
257
258        // Mutate z so that the relation does not hold
259        let mut bad_z = z.clone();
260        bad_z[3] = Fr::zero();
261        let (bad_w, bad_x) = ccs.split_z(&bad_z);
262        assert!(ccs.check_relation(&bad_w, &bad_x).is_err());
263
264        let (pedersen_params, _) =
265            Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
266        // Compute v_j with the right z
267        let (lcccs, _) = ccs
268            .to_lcccs::<_, Projective, Pedersen<Projective>, false>(&mut rng, &pedersen_params, &z)
269            .unwrap();
270        // with our test vector coming from R1CS, v should have length 3
271        assert_eq!(lcccs.v.len(), 3);
272
273        // Bad compute L_j(x) with the bad z
274        let vec_L_j_x = compute_Ls(&ccs, &lcccs, &bad_z);
275        assert_eq!(vec_L_j_x.len(), lcccs.v.len());
276
277        // Make sure that the LCCCS is not satisfied given these L_j(x)
278        // i.e. summing L_j(x) over the hypercube should not give v_j for all j
279        let mut satisfied = true;
280        for (v_i, L_j_x) in lcccs.v.into_iter().zip(vec_L_j_x) {
281            let sum_L_j_x = BooleanHypercube::new(ccs.s)
282                .map(|y| L_j_x.evaluate(&y).unwrap())
283                .fold(Fr::zero(), |acc, result| acc + result);
284            if v_i != sum_L_j_x {
285                satisfied = false;
286            }
287        }
288        assert!(!satisfied);
289    }
290}