1//! Main module for the Product Check protocol
  2
  3use crate::{
  4    errors::PolyIOPErrors,
  5    prod_check::util::{compute_product_poly, prove_zero_check},
  6    zero_check::ZeroCheck,
  7    PolyIOP,
  8};
  9use arithmetic::VPAuxInfo;
 10use ark_ec::PairingEngine;
 11use ark_ff::{One, PrimeField, Zero};
 12use ark_poly::DenseMultilinearExtension;
 13use ark_std::{end_timer, start_timer};
 14use pcs::prelude::PolynomialCommitmentScheme;
 15use std::rc::Rc;
 16use transcript::IOPTranscript;
 17
 18mod util;
 19
 20/// A product-check proves that two n-variate multilinear polynomials `f(x),
 21/// g(x)` satisfy:
 22/// \prod_{x \in {0,1}^n} f(x) = \prod_{x \in {0,1}^n} g(x)
 23///
 24/// A ProductCheck is derived from ZeroCheck.
 25///
 26/// Prover steps:
 27/// 1. build `prod(x0, ..., x_n)` from f and g,
 28///    such that `prod(0, x1, ..., xn)` equals `f/g` over domain {0,1}^n
 29/// 2. push commitments of `prod(x)` to the transcript,
 30///    and `generate_challenge` from current transcript (generate alpha)
 31/// 3. generate the zerocheck proof for the virtual polynomial
 32///    prod(1, x) - prod(x, 0) * prod(x, 1) + alpha * (f(x) - prod(0, x) * g(x))
 33///
 34/// Verifier steps:
 35/// 1. Extract commitments of `prod(x)` from the proof, push
 36/// them to the transcript
 37/// 2. `generate_challenge` from current transcript (generate alpha)
 38/// 3. `verify` to verify the zerocheck proof and generate the subclaim for
 39/// polynomial evaluations
 40pub trait ProductCheck<E, PCS>: ZeroCheck<E::Fr>
 41where
 42    E: PairingEngine,
 43    PCS: PolynomialCommitmentScheme<E>,
 44{
 45    type ProductCheckSubClaim;
 46    type ProductCheckProof;
 47
 48    /// Initialize the system with a transcript
 49    ///
 50    /// This function is optional -- in the case where a ProductCheck is
 51    /// an building block for a more complex protocol, the transcript
 52    /// may be initialized by this complex protocol, and passed to the
 53    /// ProductCheck prover/verifier.
 54    fn init_transcript() -> Self::Transcript;
 55
 56    /// Generate a proof for product check, showing that witness multilinear
 57    /// polynomials f(x), g(x) satisfy `\prod_{x \in {0,1}^n} f(x) =
 58    /// \prod_{x \in {0,1}^n} g(x)`
 59    ///
 60    /// Inputs:
 61    /// - fx: the numerator multilinear polynomial
 62    /// - gx: the denominator multilinear polynomial
 63    /// - transcript: the IOP transcript
 64    /// - pk: PCS committing key
 65    ///
 66    /// Outputs
 67    /// - the product check proof
 68    /// - the product polynomial (used for testing)
 69    ///
 70    /// Cost: O(N)
 71    fn prove(
 72        pcs_param: &PCS::ProverParam,
 73        fx: &Self::MultilinearExtension,
 74        gx: &Self::MultilinearExtension,
 75        transcript: &mut IOPTranscript<E::Fr>,
 76    ) -> Result<(Self::ProductCheckProof, Self::MultilinearExtension), PolyIOPErrors>;
 77
 78    /// Verify that for witness multilinear polynomials f(x), g(x)
 79    /// it holds that `\prod_{x \in {0,1}^n} f(x) = \prod_{x \in {0,1}^n} g(x)`
 80    fn verify(
 81        proof: &Self::ProductCheckProof,
 82        aux_info: &VPAuxInfo<E::Fr>,
 83        transcript: &mut Self::Transcript,
 84    ) -> Result<Self::ProductCheckSubClaim, PolyIOPErrors>;
 85}
 86
 87/// A product check subclaim consists of
 88/// - A zero check IOP subclaim for
 89/// `Q(x) = prod(1, x) - prod(x, 0) * prod(x, 1) + alpha * (f(x) - prod(0,
 90/// x) * g(x)) = 0`
 91/// - The random challenge `alpha`
 92/// - A final query for `prod(1, ..., 1, 0) = 1`.
 93// Note that this final query is in fact a constant that
 94// is independent from the proof. So we should avoid
 95// (de)serialize it.
 96#[derive(Clone, Debug, Default, PartialEq)]
 97pub struct ProductCheckSubClaim<F: PrimeField, ZC: ZeroCheck<F>> {
 98    // the SubClaim from the ZeroCheck
 99    pub zero_check_sub_claim: ZC::ZeroCheckSubClaim,
100    // final query which consists of
101    // - the vector `(1, ..., 1, 0)` (needs to be reversed because Arkwork's MLE uses big-endian
102    //   format for points)
103    // The expected final query evaluation is 1
104    pub final_query: (Vec<F>, F),
105    pub alpha: F,
106}
107
108/// A product check proof consists of
109/// - a zerocheck proof
110/// - a product polynomial commitment
111#[derive(Clone, Debug, Default, PartialEq)]
112pub struct ProductCheckProof<
113    E: PairingEngine,
114    PCS: PolynomialCommitmentScheme<E>,
115    ZC: ZeroCheck<E::Fr>,
116> {
117    pub zero_check_proof: ZC::ZeroCheckProof,
118    pub prod_x_comm: PCS::Commitment,
119}
120
121impl<E, PCS> ProductCheck<E, PCS> for PolyIOP<E::Fr>
122where
123    E: PairingEngine,
124    PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
125{
126    type ProductCheckSubClaim = ProductCheckSubClaim<E::Fr, Self>;
127    type ProductCheckProof = ProductCheckProof<E, PCS, Self>;
128
129    fn init_transcript() -> Self::Transcript {
130        IOPTranscript::<E::Fr>::new(b"Initializing ProductCheck transcript")
131    }
132
133    fn prove(
134        pcs_param: &PCS::ProverParam,
135        fx: &Self::MultilinearExtension,
136        gx: &Self::MultilinearExtension,
137        transcript: &mut IOPTranscript<E::Fr>,
138    ) -> Result<(Self::ProductCheckProof, Self::MultilinearExtension), PolyIOPErrors> {
139        let start = start_timer!(|| "prod_check prove");
140
141        if fx.num_vars != gx.num_vars {
142            return Err(PolyIOPErrors::InvalidParameters(
143                "fx and gx have different number of variables".to_string(),
144            ));
145        }
146
147        // compute the product polynomial
148        let prod_x = compute_product_poly(fx, gx)?;
149
150        // generate challenge
151        let prod_x_comm = PCS::commit(pcs_param, &prod_x)?;
152        transcript.append_serializable_element(b"prod(x)", &prod_x_comm)?;
153        let alpha = transcript.get_and_append_challenge(b"alpha")?;
154
155        // build the zero-check proof
156        let (zero_check_proof, _) = prove_zero_check(fx, gx, &prod_x, &alpha, transcript)?;
157
158        end_timer!(start);
159
160        Ok((
161            ProductCheckProof {
162                zero_check_proof,
163                prod_x_comm,
164            },
165            prod_x,
166        ))
167    }
168
169    fn verify(
170        proof: &Self::ProductCheckProof,
171        aux_info: &VPAuxInfo<E::Fr>,
172        transcript: &mut Self::Transcript,
173    ) -> Result<Self::ProductCheckSubClaim, PolyIOPErrors> {
174        let start = start_timer!(|| "prod_check verify");
175
176        // update transcript and generate challenge
177        transcript.append_serializable_element(b"prod(x)", &proof.prod_x_comm)?;
178        let alpha = transcript.get_and_append_challenge(b"alpha")?;
179
180        // invoke the zero check on the iop_proof
181        // the virtual poly info for Q(x)
182        let zero_check_sub_claim =
183            <Self as ZeroCheck<E::Fr>>::verify(&proof.zero_check_proof, aux_info, transcript)?;
184
185        // the final query is on prod_x, hence has length `num_vars` + 1
186        let mut final_query = vec![E::Fr::one(); aux_info.num_variables + 1];
187        // the point has to be reversed because Arkworks uses big-endian.
188        final_query[0] = E::Fr::zero();
189        let final_eval = E::Fr::one();
190
191        end_timer!(start);
192
193        Ok(ProductCheckSubClaim {
194            zero_check_sub_claim,
195            final_query: (final_query, final_eval),
196            alpha,
197        })
198    }
199}
200
201#[cfg(test)]
202mod test {
203    use super::ProductCheck;
204    use crate::{errors::PolyIOPErrors, PolyIOP};
205    use arithmetic::VPAuxInfo;
206    use ark_bls12_381::{Bls12_381, Fr};
207    use ark_ec::PairingEngine;
208    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
209    use ark_std::test_rng;
210    use pcs::{prelude::KZGMultilinearPCS, PolynomialCommitmentScheme};
211    use std::{marker::PhantomData, rc::Rc};
212
213    // f and g are guaranteed to have the same product
214    fn test_product_check_helper<E, PCS>(
215        f: &DenseMultilinearExtension<E::Fr>,
216        g: &DenseMultilinearExtension<E::Fr>,
217        pcs_param: &PCS::ProverParam,
218    ) -> Result<(), PolyIOPErrors>
219    where
220        E: PairingEngine,
221        PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
222    {
223        let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
224        transcript.append_message(b"testing", b"initializing transcript for testing")?;
225
226        let (proof, prod_x) = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::prove(
227            pcs_param,
228            &Rc::new(f.clone()),
229            &Rc::new(g.clone()),
230            &mut transcript,
231        )?;
232
233        let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
234        transcript.append_message(b"testing", b"initializing transcript for testing")?;
235
236        let aux_info = VPAuxInfo {
237            max_degree: 2,
238            num_variables: f.num_vars,
239            phantom: PhantomData::default(),
240        };
241        let prod_subclaim =
242            <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::verify(&proof, &aux_info, &mut transcript)?;
243        assert_eq!(
244            prod_x.evaluate(&prod_subclaim.final_query.0).unwrap(),
245            prod_subclaim.final_query.1,
246            "different product"
247        );
248
249        // bad path
250        let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
251        transcript.append_message(b"testing", b"initializing transcript for testing")?;
252
253        let h = f + g;
254        let (bad_proof, prod_x_bad) = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::prove(
255            pcs_param,
256            &Rc::new(f.clone()),
257            &Rc::new(h.clone()),
258            &mut transcript,
259        )?;
260
261        let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
262        transcript.append_message(b"testing", b"initializing transcript for testing")?;
263        let bad_subclaim = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::verify(
264            &bad_proof,
265            &aux_info,
266            &mut transcript,
267        )?;
268        assert_ne!(
269            prod_x_bad.evaluate(&bad_subclaim.final_query.0).unwrap(),
270            bad_subclaim.final_query.1,
271            "can't detect wrong proof"
272        );
273
274        Ok(())
275    }
276
277    fn test_product_check(nv: usize) -> Result<(), PolyIOPErrors> {
278        let mut rng = test_rng();
279
280        let f: DenseMultilinearExtension<Fr> = DenseMultilinearExtension::rand(nv, &mut rng);
281        let mut g = f.clone();
282        g.evaluations.reverse();
283
284        let srs = KZGMultilinearPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv + 1)?;
285        let (pcs_param, _) = KZGMultilinearPCS::<Bls12_381>::trim(&srs, nv + 1, Some(nv + 1))?;
286
287        test_product_check_helper::<Bls12_381, KZGMultilinearPCS<Bls12_381>>(&f, &g, &pcs_param)?;
288
289        Ok(())
290    }
291
292    #[test]
293    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
294        test_product_check(1)
295    }
296    #[test]
297    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
298        test_product_check(10)
299    }
300}