hyperplonk/poly-iop/src/zero_check/mod.rs
poly-iop/src/zero_check/mod.rsRaw
1use ark_ff::PrimeField;
2use ark_poly::DenseMultilinearExtension;
3use ark_std::{end_timer, start_timer};
4use std::rc::Rc;
5
6use crate::{
7 errors::PolyIOPErrors,
8 structs::{DomainInfo, IOPProof, SubClaim},
9 sum_check::SumCheck,
10 transcript::IOPTranscript,
11 virtual_poly::VirtualPolynomial,
12 PolyIOP,
13};
14
15pub trait ZeroCheck<F: PrimeField> {
16 type Proof;
17 type PolyList;
18 type DomainInfo;
19 type SubClaim;
20 type Transcript;
21
22 /// Initialize the system with a transcript
23 ///
24 /// This function is optional -- in the case where a ZeroCheck is
25 /// an building block for a more complex protocol, the transcript
26 /// may be initialized by this complex protocol, and passed to the
27 /// ZeroCheck prover/verifier.
28 fn init_transcript() -> Self::Transcript;
29
30 /// initialize the prover to argue for the sum of polynomial over
31 /// {0,1}^`num_vars` is zero.
32 fn prove(
33 poly: &Self::PolyList,
34 transcript: &mut Self::Transcript,
35 ) -> Result<Self::Proof, PolyIOPErrors>;
36
37 /// verify the claimed sum using the proof
38 fn verify(
39 proof: &Self::Proof,
40 domain_info: &Self::DomainInfo,
41 transcript: &mut Self::Transcript,
42 ) -> Result<Self::SubClaim, PolyIOPErrors>;
43}
44
45impl<F: PrimeField> ZeroCheck<F> for PolyIOP<F> {
46 type Proof = IOPProof<F>;
47 type PolyList = VirtualPolynomial<F>;
48 type DomainInfo = DomainInfo<F>;
49
50 /// A ZeroCheck SubClaim consists of
51 /// - the SubClaim from the ZeroCheck
52 /// - the initial challenge r which is used to build eq(x, r)
53 type SubClaim = (SubClaim<F>, Vec<F>);
54 type Transcript = IOPTranscript<F>;
55
56 /// Initialize the system with a transcript
57 ///
58 /// This function is optional -- in the case where a ZeroCheck is
59 /// an building block for a more complex protocol, the transcript
60 /// may be initialized by this complex protocol, and passed to the
61 /// ZeroCheck prover/verifier.
62 fn init_transcript() -> Self::Transcript {
63 IOPTranscript::<F>::new(b"Initializing ZeroCheck transcript")
64 }
65
66 /// initialize the prover to argue for the sum of polynomial over
67 /// {0,1}^`num_vars` is zero.
68 fn prove(
69 poly: &Self::PolyList,
70 transcript: &mut Self::Transcript,
71 ) -> Result<Self::Proof, PolyIOPErrors> {
72 let start = start_timer!(|| "zero check prove");
73
74 let length = poly.domain_info.num_variables;
75 let r = transcript.get_and_append_challenge_vectors(b"vector r", length)?;
76 let f_hat = build_f_hat(poly, r.as_ref())?;
77 let res = <Self as SumCheck<F>>::prove(&f_hat, transcript);
78
79 end_timer!(start);
80 res
81 }
82
83 /// Verify the claimed sum using the proof.
84 /// the initial challenge `r` is also returned.
85 /// The caller needs to makes sure that `\hat f = f * eq(x, r)`
86 fn verify(
87 proof: &Self::Proof,
88 fx_domain_info: &Self::DomainInfo,
89 transcript: &mut Self::Transcript,
90 ) -> Result<Self::SubClaim, PolyIOPErrors> {
91 let start = start_timer!(|| "zero check verify");
92
93 // check that the sum is zero
94 if proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1] != F::zero() {
95 return Err(PolyIOPErrors::InvalidProof(format!(
96 "zero check: sum {} is not zero",
97 proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1]
98 )));
99 }
100
101 // generate `r` and pass it to the caller for correctness check
102 let length = fx_domain_info.num_variables;
103 let r = transcript.get_and_append_challenge_vectors(b"vector r", length)?;
104
105 // hat_fx's max degree is increased by eq(x, r).degree() which is 1
106 let mut hat_fx_domain_info = fx_domain_info.clone();
107 hat_fx_domain_info.max_degree += 1;
108 let subclaim =
109 <Self as SumCheck<F>>::verify(F::zero(), proof, &hat_fx_domain_info, transcript)?;
110
111 end_timer!(start);
112 Ok((subclaim, r))
113 }
114}
115
116// Input poly f(x) and a random vector r, output
117// \hat f(x) = \sum_{x_i \in eval_x} f(x_i) eq(x, r)
118// where
119// eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
120fn build_f_hat<F: PrimeField>(
121 poly: &VirtualPolynomial<F>,
122 r: &[F],
123) -> Result<VirtualPolynomial<F>, PolyIOPErrors> {
124 let start = start_timer!(|| "zero check build hat f");
125
126 assert_eq!(poly.domain_info.num_variables, r.len());
127
128 let eq_x_r = build_eq_x_r(r)?;
129 let mut res = poly.clone();
130 res.mul_by_mle(eq_x_r, F::one())?;
131
132 end_timer!(start);
133 Ok(res)
134}
135
136// Evaluate
137// eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
138// over r, which is
139// eq(x,y) = \prod_i=1^num_var (x_i * r_i + (1-x_i)*(1-r_i))
140fn build_eq_x_r<F: PrimeField>(r: &[F]) -> Result<Rc<DenseMultilinearExtension<F>>, PolyIOPErrors> {
141 let start = start_timer!(|| "zero check build eq_x_r");
142
143 // we build eq(x,r) from its evaluations
144 // we want to evaluate eq(x,r) over x \in {0, 1}^num_vars
145 // for example, with num_vars = 4, x is a binary vector of 4, then
146 // 0 0 0 0 -> (1-r0) * (1-r1) * (1-r2) * (1-r3)
147 // 1 0 0 0 -> r0 * (1-r1) * (1-r2) * (1-r3)
148 // 0 1 0 0 -> (1-r0) * r1 * (1-r2) * (1-r3)
149 // 1 1 0 0 -> r0 * r1 * (1-r2) * (1-r3)
150 // ....
151 // 1 1 1 1 -> r0 * r1 * r2 * r3
152 // we will need 2^num_var evaluations
153
154 let mut eval = Vec::new();
155 build_eq_x_r_helper(r, &mut eval)?;
156
157 let mle = DenseMultilinearExtension::from_evaluations_vec(r.len(), eval);
158
159 let res = Rc::new(mle);
160 end_timer!(start);
161 Ok(res)
162}
163
164/// A helper function to build eq(x, r) recursively.
165/// This function takes `r.len()` steps, and for each step it requires a maximum
166/// `r.len()-1` multiplications.
167fn build_eq_x_r_helper<F: PrimeField>(r: &[F], buf: &mut Vec<F>) -> Result<(), PolyIOPErrors> {
168 if r.is_empty() {
169 return Err(PolyIOPErrors::InvalidParameters(
170 "r length is 0".to_string(),
171 ));
172 } else if r.len() == 1 {
173 // initializing the buffer with [1-r0, r0]
174 buf.push(F::one() - r[0]);
175 buf.push(r[0]);
176 } else {
177 build_eq_x_r_helper(&r[1..], buf)?;
178
179 // suppose in the previous step we have [b1, ..., b_k]
180 // for the current step we will need
181 // if x0 = 0: (1-r0) * [b_1, ..., b_k]
182 // if x0 = 1: r0 * [b1, ..., b_k]
183
184 let mut res = vec![];
185 for &e in buf.iter() {
186 let tmp = e * r[0];
187 res.push(e - tmp);
188 res.push(tmp);
189 }
190 *buf = res;
191 }
192
193 Ok(())
194}
195
196#[cfg(test)]
197mod test {
198
199 use super::{build_eq_x_r, ZeroCheck};
200 use crate::{errors::PolyIOPErrors, PolyIOP, VirtualPolynomial};
201 use ark_bls12_381::Fr;
202 use ark_ff::{PrimeField, UniformRand};
203 use ark_poly::DenseMultilinearExtension;
204 use ark_std::{end_timer, start_timer, test_rng};
205 use std::rc::Rc;
206
207 fn test_zerocheck(
208 nv: usize,
209 num_multiplicands_range: (usize, usize),
210 num_products: usize,
211 ) -> Result<(), PolyIOPErrors> {
212 let mut rng = test_rng();
213
214 {
215 // good path: zero virtual poly
216 let poly =
217 VirtualPolynomial::rand_zero(nv, num_multiplicands_range, num_products, &mut rng)?;
218
219 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
220 transcript.append_message(b"testing", b"initializing transcript for testing")?;
221 let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
222
223 let poly_info = poly.domain_info.clone();
224 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
225 transcript.append_message(b"testing", b"initializing transcript for testing")?;
226 let subclaim =
227 <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?.0;
228 assert!(
229 poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
230 "wrong subclaim"
231 );
232 }
233
234 {
235 // bad path: random virtual poly whose sum is not zero
236 let (poly, _sum) =
237 VirtualPolynomial::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
238
239 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
240 transcript.append_message(b"testing", b"initializing transcript for testing")?;
241 let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
242
243 let poly_info = poly.domain_info.clone();
244 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
245 transcript.append_message(b"testing", b"initializing transcript for testing")?;
246
247 assert!(
248 <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)
249 .is_err()
250 );
251 }
252
253 Ok(())
254 }
255
256 #[test]
257 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
258 let nv = 1;
259 let num_multiplicands_range = (4, 5);
260 let num_products = 1;
261
262 test_zerocheck(nv, num_multiplicands_range, num_products)
263 }
264 #[test]
265 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
266 let nv = 5;
267 let num_multiplicands_range = (4, 9);
268 let num_products = 5;
269
270 test_zerocheck(nv, num_multiplicands_range, num_products)
271 }
272
273 #[test]
274 fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
275 let nv = 0;
276 let num_multiplicands_range = (4, 13);
277 let num_products = 5;
278
279 assert!(test_zerocheck(nv, num_multiplicands_range, num_products).is_err());
280 Ok(())
281 }
282
283 #[test]
284 fn test_eq_xr() {
285 let mut rng = test_rng();
286 for nv in 4..10 {
287 let r: Vec<Fr> = (0..nv).map(|_| Fr::rand(&mut rng)).collect();
288 let eq_x_r = build_eq_x_r(r.as_ref()).unwrap();
289 let eq_x_r2 = build_eq_x_r_for_test(r.as_ref());
290 assert_eq!(eq_x_r, eq_x_r2);
291 }
292 }
293
294 /// Naive method to build eq(x, r).
295 /// Only used for testing purpose.
296 // Evaluate
297 // eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
298 // over r, which is
299 // eq(x,y) = \prod_i=1^num_var (x_i * r_i + (1-x_i)*(1-r_i))
300 fn build_eq_x_r_for_test<F: PrimeField>(r: &[F]) -> Rc<DenseMultilinearExtension<F>> {
301 let start = start_timer!(|| "zero check naive build eq_x_r");
302
303 // we build eq(x,r) from its evaluations
304 // we want to evaluate eq(x,r) over x \in {0, 1}^num_vars
305 // for example, with num_vars = 4, x is a binary vector of 4, then
306 // 0 0 0 0 -> (1-r0) * (1-r1) * (1-r2) * (1-r3)
307 // 1 0 0 0 -> r0 * (1-r1) * (1-r2) * (1-r3)
308 // 0 1 0 0 -> (1-r0) * r1 * (1-r2) * (1-r3)
309 // 1 1 0 0 -> r0 * r1 * (1-r2) * (1-r3)
310 // ....
311 // 1 1 1 1 -> r0 * r1 * r2 * r3
312 // we will need 2^num_var evaluations
313
314 // First, we build array for {1 - r_i}
315 let one_minus_r: Vec<F> = r.iter().map(|ri| F::one() - ri).collect();
316
317 let num_var = r.len();
318 let mut eval = vec![];
319
320 for i in 0..1 << num_var {
321 let mut current_eval = F::one();
322 let bit_sequence = bit_decompose(i, num_var);
323
324 for (&bit, (ri, one_minus_ri)) in
325 bit_sequence.iter().zip(r.iter().zip(one_minus_r.iter()))
326 {
327 current_eval *= if bit { *ri } else { *one_minus_ri };
328 }
329 eval.push(current_eval);
330 }
331
332 let mle = DenseMultilinearExtension::from_evaluations_vec(num_var, eval);
333
334 let res = Rc::new(mle);
335 end_timer!(start);
336 res
337 }
338
339 fn bit_decompose(input: u64, num_var: usize) -> Vec<bool> {
340 let mut res = Vec::with_capacity(num_var);
341 let mut i = input;
342 for _ in 0..num_var {
343 res.push(i & 1 == 1);
344 i >>= 1;
345 }
346 res
347 }
348}