hyperplonk/poly-iop/src/prod_check/mod.rs
poly-iop/src/prod_check/mod.rsRaw
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) + challenge * (f(x) - prod(0,
90/// x) * g(x))` is 0, consists of the following:
91/// - the SubClaim from the SumCheck
92/// - the initial challenge r which is used to build eq(x, r) in ZeroCheck
93/// - The challenge `challenge`
94/// - A final query for `prod(1, ..., 1, 0) = claimed_product`.
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 final_query: (Vec<F>, F),
107 pub challenge: 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 challenge: alpha,
199 })
200 }
201}
202
203#[cfg(test)]
204mod test {
205 use super::ProductCheck;
206 use crate::{errors::PolyIOPErrors, PolyIOP};
207 use arithmetic::VPAuxInfo;
208 use ark_bls12_381::{Bls12_381, Fr};
209 use ark_ec::PairingEngine;
210 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
211 use ark_std::test_rng;
212 use pcs::{prelude::KZGMultilinearPCS, PolynomialCommitmentScheme};
213 use std::{marker::PhantomData, rc::Rc};
214
215 // f and g are guaranteed to have the same product
216 fn test_product_check_helper<E, PCS>(
217 f: &DenseMultilinearExtension<E::Fr>,
218 g: &DenseMultilinearExtension<E::Fr>,
219 pcs_param: &PCS::ProverParam,
220 ) -> Result<(), PolyIOPErrors>
221 where
222 E: PairingEngine,
223 PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
224 {
225 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
226 transcript.append_message(b"testing", b"initializing transcript for testing")?;
227
228 let (proof, prod_x) = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::prove(
229 pcs_param,
230 &Rc::new(f.clone()),
231 &Rc::new(g.clone()),
232 &mut transcript,
233 )?;
234
235 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
236 transcript.append_message(b"testing", b"initializing transcript for testing")?;
237
238 let aux_info = VPAuxInfo {
239 max_degree: 2,
240 num_variables: f.num_vars,
241 phantom: PhantomData::default(),
242 };
243 let subclaim =
244 <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::verify(&proof, &aux_info, &mut transcript)?;
245 assert_eq!(
246 prod_x.evaluate(&subclaim.final_query.0).unwrap(),
247 subclaim.final_query.1,
248 "different product"
249 );
250
251 // bad path
252 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
253 transcript.append_message(b"testing", b"initializing transcript for testing")?;
254
255 let h = f + g;
256 let (bad_proof, prod_x_bad) = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::prove(
257 pcs_param,
258 &Rc::new(f.clone()),
259 &Rc::new(h.clone()),
260 &mut transcript,
261 )?;
262
263 let mut transcript = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::init_transcript();
264 transcript.append_message(b"testing", b"initializing transcript for testing")?;
265 let bad_subclaim = <PolyIOP<E::Fr> as ProductCheck<E, PCS>>::verify(
266 &bad_proof,
267 &aux_info,
268 &mut transcript,
269 )?;
270 assert_ne!(
271 prod_x_bad.evaluate(&bad_subclaim.final_query.0).unwrap(),
272 bad_subclaim.final_query.1,
273 "can't detect wrong proof"
274 );
275
276 Ok(())
277 }
278
279 fn test_product_check(nv: usize) -> Result<(), PolyIOPErrors> {
280 let mut rng = test_rng();
281
282 let f: DenseMultilinearExtension<Fr> = DenseMultilinearExtension::rand(nv, &mut rng);
283 let mut g = f.clone();
284 g.evaluations.reverse();
285
286 let srs = KZGMultilinearPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv + 1)?;
287 let (pcs_param, _) = KZGMultilinearPCS::<Bls12_381>::trim(&srs, nv + 1, Some(nv + 1))?;
288
289 test_product_check_helper::<Bls12_381, KZGMultilinearPCS<Bls12_381>>(&f, &g, &pcs_param)?;
290
291 Ok(())
292 }
293
294 #[test]
295 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
296 test_product_check(1)
297 }
298 #[test]
299 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
300 test_product_check(10)
301 }
302}