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