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