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