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