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