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::pairing::Pairing;
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::ScalarField>
56where
57 E: Pairing,
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::ScalarField>,
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::ScalarField>,
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: Pairing,
140 PCS: PolynomialCommitmentScheme<E>,
141 ZC: ZeroCheck<E::ScalarField>,
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::ScalarField>
149where
150 E: Pairing,
151 PCS: PolynomialCommitmentScheme<E, Polynomial = Arc<DenseMultilinearExtension<E::ScalarField>>>,
152{
153 type ProductCheckSubClaim = ProductCheckSubClaim<E::ScalarField, Self>;
154 type ProductCheckProof = ProductCheckProof<E, PCS, Self>;
155
156 fn init_transcript() -> Self::Transcript {
157 IOPTranscript::<E::ScalarField>::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::ScalarField>,
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::ScalarField>,
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 = <Self as ZeroCheck<E::ScalarField>>::verify(
236 &proof.zero_check_proof,
237 aux_info,
238 transcript,
239 )?;
240
241 // the final query is on prod_x
242 let mut final_query = vec![E::ScalarField::one(); aux_info.num_variables];
243 // the point has to be reversed because Arkworks uses big-endian.
244 final_query[0] = E::ScalarField::zero();
245 let final_eval = E::ScalarField::one();
246
247 end_timer!(start);
248
249 Ok(ProductCheckSubClaim {
250 zero_check_sub_claim,
251 final_query: (final_query, final_eval),
252 alpha,
253 })
254 }
255}
256
257#[cfg(test)]
258mod test {
259 use super::ProductCheck;
260 use crate::{
261 pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme},
262 poly_iop::{errors::PolyIOPErrors, PolyIOP},
263 };
264 use arithmetic::VPAuxInfo;
265 use ark_bls12_381::{Bls12_381, Fr};
266 use ark_ec::pairing::Pairing;
267 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
268 use ark_std::test_rng;
269 use std::{marker::PhantomData, sync::Arc};
270
271 fn check_frac_poly<E>(
272 frac_poly: &Arc<DenseMultilinearExtension<E::ScalarField>>,
273 fs: &[Arc<DenseMultilinearExtension<E::ScalarField>>],
274 gs: &[Arc<DenseMultilinearExtension<E::ScalarField>>],
275 ) where
276 E: Pairing,
277 {
278 let mut flag = true;
279 let num_vars = frac_poly.num_vars;
280 for i in 0..1 << num_vars {
281 let nom = fs
282 .iter()
283 .fold(E::ScalarField::from(1u8), |acc, f| acc * f.evaluations[i]);
284 let denom = gs
285 .iter()
286 .fold(E::ScalarField::from(1u8), |acc, g| acc * g.evaluations[i]);
287 if denom * frac_poly.evaluations[i] != nom {
288 flag = false;
289 break;
290 }
291 }
292 assert!(flag);
293 }
294 // fs and gs are guaranteed to have the same product
295 // fs and hs doesn't have the same product
296 fn test_product_check_helper<E, PCS>(
297 fs: &[Arc<DenseMultilinearExtension<E::ScalarField>>],
298 gs: &[Arc<DenseMultilinearExtension<E::ScalarField>>],
299 hs: &[Arc<DenseMultilinearExtension<E::ScalarField>>],
300 pcs_param: &PCS::ProverParam,
301 ) -> Result<(), PolyIOPErrors>
302 where
303 E: Pairing,
304 PCS: PolynomialCommitmentScheme<
305 E,
306 Polynomial = Arc<DenseMultilinearExtension<E::ScalarField>>,
307 >,
308 {
309 let mut transcript = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::init_transcript();
310 transcript.append_message(b"testing", b"initializing transcript for testing")?;
311
312 let (proof, prod_x, frac_poly) = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::prove(
313 pcs_param,
314 fs,
315 gs,
316 &mut transcript,
317 )?;
318
319 let mut transcript = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::init_transcript();
320 transcript.append_message(b"testing", b"initializing transcript for testing")?;
321
322 // what's aux_info for?
323 let aux_info = VPAuxInfo {
324 max_degree: fs.len() + 1,
325 num_variables: fs[0].num_vars,
326 phantom: PhantomData::default(),
327 };
328 let prod_subclaim = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::verify(
329 &proof,
330 &aux_info,
331 &mut transcript,
332 )?;
333 assert_eq!(
334 prod_x.evaluate(&prod_subclaim.final_query.0).unwrap(),
335 prod_subclaim.final_query.1,
336 "different product"
337 );
338 check_frac_poly::<E>(&frac_poly, fs, gs);
339
340 // bad path
341 let mut transcript = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::init_transcript();
342 transcript.append_message(b"testing", b"initializing transcript for testing")?;
343
344 let (bad_proof, prod_x_bad, frac_poly) = <PolyIOP<E::ScalarField> as ProductCheck<
345 E,
346 PCS,
347 >>::prove(
348 pcs_param, fs, hs, &mut transcript
349 )?;
350
351 let mut transcript = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::init_transcript();
352 transcript.append_message(b"testing", b"initializing transcript for testing")?;
353 let bad_subclaim = <PolyIOP<E::ScalarField> as ProductCheck<E, PCS>>::verify(
354 &bad_proof,
355 &aux_info,
356 &mut transcript,
357 )?;
358 assert_ne!(
359 prod_x_bad.evaluate(&bad_subclaim.final_query.0).unwrap(),
360 bad_subclaim.final_query.1,
361 "can't detect wrong proof"
362 );
363 // the frac_poly should still be computed correctly
364 check_frac_poly::<E>(&frac_poly, fs, hs);
365
366 Ok(())
367 }
368
369 fn test_product_check(nv: usize) -> Result<(), PolyIOPErrors> {
370 let mut rng = test_rng();
371
372 let f1: DenseMultilinearExtension<Fr> = DenseMultilinearExtension::rand(nv, &mut rng);
373 let mut g1 = f1.clone();
374 g1.evaluations.reverse();
375 let f2: DenseMultilinearExtension<Fr> = DenseMultilinearExtension::rand(nv, &mut rng);
376 let mut g2 = f2.clone();
377 g2.evaluations.reverse();
378 let fs = vec![Arc::new(f1), Arc::new(f2)];
379 let gs = vec![Arc::new(g2), Arc::new(g1)];
380 let mut hs = vec![];
381 for _ in 0..fs.len() {
382 hs.push(Arc::new(DenseMultilinearExtension::rand(
383 fs[0].num_vars,
384 &mut rng,
385 )));
386 }
387
388 let srs = MultilinearKzgPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv)?;
389 let (pcs_param, _) = MultilinearKzgPCS::<Bls12_381>::trim(&srs, None, Some(nv))?;
390
391 test_product_check_helper::<Bls12_381, MultilinearKzgPCS<Bls12_381>>(
392 &fs, &gs, &hs, &pcs_param,
393 )?;
394
395 Ok(())
396 }
397
398 #[test]
399 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
400 test_product_check(1)
401 }
402 #[test]
403 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
404 test_product_check(10)
405 }
406}