hyperplonk/subroutines/src/poly_iop/prod_check/mod.rs
subroutines/src/poly_iop/prod_check/mod.rsRaw
1// Copyright (c) 2023 Espresso Systems (espressosys.com)
2// This file is part of the HyperPlonk library.
3
4// You should have received a copy of the MIT License
5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
6
7//! Main module for the Product Check protocol
8
9use crate::{
10 pcs::PolynomialCommitmentScheme,
11 poly_iop::{
12 errors::PolyIOPErrors,
13 prod_check::util::{compute_frac_poly, compute_product_poly, prove_zero_check},
14 zero_check::ZeroCheck,
15 PolyIOP,
16 },
17};
18use arithmetic::VPAuxInfo;
19use ark_ec::PairingEngine;
20use ark_ff::{One, PrimeField, Zero};
21use ark_poly::DenseMultilinearExtension;
22use ark_std::{end_timer, start_timer};
23use std::sync::Arc;
24use transcript::IOPTranscript;
25
26mod util;
27
28/// A product-check proves that two lists of n-variate multilinear polynomials
29/// `(f1, f2, ..., fk)` and `(g1, ..., gk)` satisfy:
30/// \prod_{x \in {0,1}^n} f1(x) * ... * fk(x) = \prod_{x \in {0,1}^n} g1(x) *
31/// ... * gk(x)
32///
33/// A ProductCheck is derived from ZeroCheck.
34///
35/// Prover steps:
36/// 1. build MLE `frac(x)` s.t. `frac(x) = f1(x) * ... * fk(x) / (g1(x) * ... *
37/// gk(x))` for all x \in {0,1}^n 2. build `prod(x)` from `frac(x)`, where
38/// `prod(x)` equals to `v(1,x)` in the paper 2. push commitments of `frac(x)`
39/// and `prod(x)` to the transcript, and `generate_challenge` from current
40/// transcript (generate alpha) 3. generate the zerocheck proof for the virtual
41/// polynomial Q(x): prod(x) - p1(x) * p2(x)
42/// + alpha * frac(x) * g1(x) * ... * gk(x)
43/// - alpha * f1(x) * ... * fk(x)
44/// where p1(x) = (1-x1) * frac(x2, ..., xn, 0)
45/// + x1 * prod(x2, ..., xn, 0),
46/// and p2(x) = (1-x1) * frac(x2, ..., xn, 1)
47/// + x1 * prod(x2, ..., xn, 1)
48///
49/// Verifier steps:
50/// 1. Extract commitments of `frac(x)` and `prod(x)` from the proof, push
51/// them to the transcript
52/// 2. `generate_challenge` from current transcript (generate alpha)
53/// 3. `verify` to verify the zerocheck proof and generate the subclaim for
54/// polynomial evaluations
55pub trait ProductCheck<E, PCS>: ZeroCheck<E::Fr>
56where
57 E: PairingEngine,
58 PCS: PolynomialCommitmentScheme<E>,
59{
60 type ProductCheckSubClaim;
61 type ProductCheckProof;
62
63 /// Initialize the system with a transcript
64 ///
65 /// This function is optional -- in the case where a ProductCheck is
66 /// an building block for a more complex protocol, the transcript
67 /// may be initialized by this complex protocol, and passed to the
68 /// ProductCheck prover/verifier.
69 fn init_transcript() -> Self::Transcript;
70
71 /// Proves that two lists of n-variate multilinear polynomials `(f1, f2,
72 /// ..., fk)` and `(g1, ..., gk)` satisfy:
73 /// \prod_{x \in {0,1}^n} f1(x) * ... * fk(x)
74 /// = \prod_{x \in {0,1}^n} g1(x) * ... * gk(x)
75 ///
76 /// Inputs:
77 /// - fxs: the list of numerator multilinear polynomial
78 /// - gxs: the list of denominator multilinear polynomial
79 /// - transcript: the IOP transcript
80 /// - pk: PCS committing key
81 ///
82 /// Outputs
83 /// - the product check proof
84 /// - the product polynomial (used for testing)
85 /// - the fractional polynomial (used for testing)
86 ///
87 /// Cost: O(N)
88 #[allow(clippy::type_complexity)]
89 fn prove(
90 pcs_param: &PCS::ProverParam,
91 fxs: &[Self::MultilinearExtension],
92 gxs: &[Self::MultilinearExtension],
93 transcript: &mut IOPTranscript<E::Fr>,
94 ) -> Result<
95 (
96 Self::ProductCheckProof,
97 Self::MultilinearExtension,
98 Self::MultilinearExtension,
99 ),
100 PolyIOPErrors,
101 >;
102
103 /// Verify that for witness multilinear polynomials (f1, ..., fk, g1, ...,
104 /// gk) it holds that
105 /// `\prod_{x \in {0,1}^n} f1(x) * ... * fk(x)
106 /// = \prod_{x \in {0,1}^n} g1(x) * ... * gk(x)`
107 fn verify(
108 proof: &Self::ProductCheckProof,
109 aux_info: &VPAuxInfo<E::Fr>,
110 transcript: &mut Self::Transcript,
111 ) -> Result<Self::ProductCheckSubClaim, PolyIOPErrors>;
112}
113
114/// A product check subclaim consists of
115/// - A zero check IOP subclaim for the virtual polynomial
116/// - The random challenge `alpha`
117/// - A final query for `prod(1, ..., 1, 0) = 1`.
118// Note that this final query is in fact a constant that
119// is independent from the proof. So we should avoid
120// (de)serialize it.
121#[derive(Clone, Debug, Default, PartialEq)]
122pub struct ProductCheckSubClaim<F: PrimeField, ZC: ZeroCheck<F>> {
123 // the SubClaim from the ZeroCheck
124 pub zero_check_sub_claim: ZC::ZeroCheckSubClaim,
125 // final query which consists of
126 // - the vector `(1, ..., 1, 0)` (needs to be reversed because Arkwork's MLE uses big-endian
127 // format for points)
128 // The expected final query evaluation is 1
129 pub final_query: (Vec<F>, F),
130 pub alpha: F,
131}
132
133/// A product check proof consists of
134/// - a zerocheck proof
135/// - a product polynomial commitment
136/// - a polynomial commitment for the fractional polynomial
137#[derive(Clone, Debug, Default, PartialEq)]
138pub struct ProductCheckProof<
139 E: PairingEngine,
140 PCS: PolynomialCommitmentScheme<E>,
141 ZC: ZeroCheck<E::Fr>,
142> {
143 pub zero_check_proof: ZC::ZeroCheckProof,
144 pub prod_x_comm: PCS::Commitment,
145 pub frac_comm: PCS::Commitment,
146}
147
148impl<E, PCS> ProductCheck<E, PCS> for PolyIOP<E::Fr>
149where
150 E: PairingEngine,
151 PCS: PolynomialCommitmentScheme<E, Polynomial = Arc<DenseMultilinearExtension<E::Fr>>>,
152{
153 type ProductCheckSubClaim = ProductCheckSubClaim<E::Fr, Self>;
154 type ProductCheckProof = ProductCheckProof<E, PCS, Self>;
155
156 fn init_transcript() -> Self::Transcript {
157 IOPTranscript::<E::Fr>::new(b"Initializing ProductCheck transcript")
158 }
159
160 fn prove(
161 pcs_param: &PCS::ProverParam,
162 fxs: &[Self::MultilinearExtension],
163 gxs: &[Self::MultilinearExtension],
164 transcript: &mut IOPTranscript<E::Fr>,
165 ) -> Result<
166 (
167 Self::ProductCheckProof,
168 Self::MultilinearExtension,
169 Self::MultilinearExtension,
170 ),
171 PolyIOPErrors,
172 > {
173 let start = start_timer!(|| "prod_check prove");
174
175 if fxs.is_empty() {
176 return Err(PolyIOPErrors::InvalidParameters("fxs is empty".to_string()));
177 }
178 if fxs.len() != gxs.len() {
179 return Err(PolyIOPErrors::InvalidParameters(
180 "fxs and gxs have different number of polynomials".to_string(),
181 ));
182 }
183 for poly in fxs.iter().chain(gxs.iter()) {
184 if poly.num_vars != fxs[0].num_vars {
185 return Err(PolyIOPErrors::InvalidParameters(
186 "fx and gx have different number of variables".to_string(),
187 ));
188 }
189 }
190
191 // compute the fractional polynomial frac_p s.t.
192 // frac_p(x) = f1(x) * ... * fk(x) / (g1(x) * ... * gk(x))
193 let frac_poly = compute_frac_poly(fxs, gxs)?;
194 // compute the product polynomial
195 let prod_x = compute_product_poly(&frac_poly)?;
196
197 // generate challenge
198 let frac_comm = PCS::commit(pcs_param, &frac_poly)?;
199 let prod_x_comm = PCS::commit(pcs_param, &prod_x)?;
200 transcript.append_serializable_element(b"frac(x)", &frac_comm)?;
201 transcript.append_serializable_element(b"prod(x)", &prod_x_comm)?;
202 let alpha = transcript.get_and_append_challenge(b"alpha")?;
203
204 // build the zero-check proof
205 let (zero_check_proof, _) =
206 prove_zero_check(fxs, gxs, &frac_poly, &prod_x, &alpha, transcript)?;
207
208 end_timer!(start);
209
210 Ok((
211 ProductCheckProof {
212 zero_check_proof,
213 prod_x_comm,
214 frac_comm,
215 },
216 prod_x,
217 frac_poly,
218 ))
219 }
220
221 fn verify(
222 proof: &Self::ProductCheckProof,
223 aux_info: &VPAuxInfo<E::Fr>,
224 transcript: &mut Self::Transcript,
225 ) -> Result<Self::ProductCheckSubClaim, PolyIOPErrors> {
226 let start = start_timer!(|| "prod_check verify");
227
228 // update transcript and generate challenge
229 transcript.append_serializable_element(b"frac(x)", &proof.frac_comm)?;
230 transcript.append_serializable_element(b"prod(x)", &proof.prod_x_comm)?;
231 let alpha = transcript.get_and_append_challenge(b"alpha")?;
232
233 // invoke the zero check on the iop_proof
234 // the virtual poly info for Q(x)
235 let zero_check_sub_claim =
236 <Self as ZeroCheck<E::Fr>>::verify(&proof.zero_check_proof, aux_info, transcript)?;
237
238 // the final query is on prod_x
239 let mut final_query = vec![E::Fr::one(); aux_info.num_variables];
240 // the point has to be reversed because Arkworks uses big-endian.
241 final_query[0] = E::Fr::zero();
242 let final_eval = E::Fr::one();
243
244 end_timer!(start);
245
246 Ok(ProductCheckSubClaim {
247 zero_check_sub_claim,
248 final_query: (final_query, final_eval),
249 alpha,
250 })
251 }
252}
253
254#[cfg(test)]
255mod test {
256 use super::ProductCheck;
257 use crate::{
258 pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme},
259 poly_iop::{errors::PolyIOPErrors, PolyIOP},
260 };
261 use arithmetic::VPAuxInfo;
262 use ark_bls12_381::{Bls12_381, Fr};
263 use ark_ec::PairingEngine;
264 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
265 use ark_std::test_rng;
266 use std::{marker::PhantomData, sync::Arc};
267
268 fn check_frac_poly<E>(
269 frac_poly: &Arc<DenseMultilinearExtension<E::Fr>>,
270 fs: &[Arc<DenseMultilinearExtension<E::Fr>>],
271 gs: &[Arc<DenseMultilinearExtension<E::Fr>>],
272 ) where
273 E: PairingEngine,
274 {
275 let mut flag = true;
276 let num_vars = frac_poly.num_vars;
277 for i in 0..1 << num_vars {
278 let nom = fs
279 .iter()
280 .fold(E::Fr::from(1u8), |acc, f| acc * f.evaluations[i]);
281 let denom = gs
282 .iter()
283 .fold(E::Fr::from(1u8), |acc, g| acc * g.evaluations[i]);
284 if denom * frac_poly.evaluations[i] != nom {
285 flag = false;
286 break;
287 }
288 }
289 assert_eq!(flag, true);
290 }
291 // fs and gs are guaranteed to have the same product
292 // fs and hs doesn't have the same product
293 fn test_product_check_helper<E, PCS>(
294 fs: &[Arc<DenseMultilinearExtension<E::Fr>>],
295 gs: &[Arc<DenseMultilinearExtension<E::Fr>>],
296 hs: &[Arc<DenseMultilinearExtension<E::Fr>>],
297 pcs_param: &PCS::ProverParam,
298 ) -> Result<(), PolyIOPErrors>
299 where
300 E: PairingEngine,
301 PCS: PolynomialCommitmentScheme<E, Polynomial = Arc<DenseMultilinearExtension<E::Fr>>>,
302 {
303 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
304 transcript.append_message(b"testing", b"initializing transcript for testing")?;
305
306 let (proof, prod_x, frac_poly) =
307 <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::prove(pcs_param, fs, gs, &mut transcript)?;
308
309 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
310 transcript.append_message(b"testing", b"initializing transcript for testing")?;
311
312 // what's aux_info for?
313 let aux_info = VPAuxInfo {
314 max_degree: fs.len() + 1,
315 num_variables: fs[0].num_vars,
316 phantom: PhantomData::default(),
317 };
318 let prod_subclaim =
319 <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::verify(&proof, &aux_info, &mut transcript)?;
320 assert_eq!(
321 prod_x.evaluate(&prod_subclaim.final_query.0).unwrap(),
322 prod_subclaim.final_query.1,
323 "different product"
324 );
325 check_frac_poly::<E>(&frac_poly, fs, gs);
326
327 // bad path
328 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
329 transcript.append_message(b"testing", b"initializing transcript for testing")?;
330
331 let (bad_proof, prod_x_bad, frac_poly) =
332 <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::prove(pcs_param, fs, hs, &mut transcript)?;
333
334 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
335 transcript.append_message(b"testing", b"initializing transcript for testing")?;
336 let bad_subclaim = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::verify(
337 &bad_proof,
338 &aux_info,
339 &mut transcript,
340 )?;
341 assert_ne!(
342 prod_x_bad.evaluate(&bad_subclaim.final_query.0).unwrap(),
343 bad_subclaim.final_query.1,
344 "can't detect wrong proof"
345 );
346 // the frac_poly should still be computed correctly
347 check_frac_poly::<E>(&frac_poly, fs, hs);
348
349 Ok(())
350 }
351
352 fn test_product_check(nv: usize) -> Result<(), PolyIOPErrors> {
353 let mut rng = test_rng();
354
355 let f1: DenseMultilinearExtension<Fr> = DenseMultilinearExtension::rand(nv, &mut rng);
356 let mut g1 = f1.clone();
357 g1.evaluations.reverse();
358 let f2: DenseMultilinearExtension<Fr> = DenseMultilinearExtension::rand(nv, &mut rng);
359 let mut g2 = f2.clone();
360 g2.evaluations.reverse();
361 let fs = vec![Arc::new(f1), Arc::new(f2)];
362 let gs = vec![Arc::new(g2), Arc::new(g1)];
363 let mut hs = vec![];
364 for _ in 0..fs.len() {
365 hs.push(Arc::new(DenseMultilinearExtension::rand(
366 fs[0].num_vars,
367 &mut rng,
368 )));
369 }
370
371 let srs = MultilinearKzgPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv)?;
372 let (pcs_param, _) = MultilinearKzgPCS::<Bls12_381>::trim(&srs, None, Some(nv))?;
373
374 test_product_check_helper::<Bls12_381, MultilinearKzgPCS<Bls12_381>>(
375 &fs, &gs, &hs, &pcs_param,
376 )?;
377
378 Ok(())
379 }
380
381 #[test]
382 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
383 test_product_check(1)
384 }
385 #[test]
386 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
387 test_product_check(10)
388 }
389}