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