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))
140pub fn build_eq_x_r<F: PrimeField>(
141 r: &[F],
142) -> Result<Rc<DenseMultilinearExtension<F>>, PolyIOPErrors> {
143 let start = start_timer!(|| "zero check build eq_x_r");
144
145 // we build eq(x,r) from its evaluations
146 // we want to evaluate eq(x,r) over x \in {0, 1}^num_vars
147 // for example, with num_vars = 4, x is a binary vector of 4, then
148 // 0 0 0 0 -> (1-r0) * (1-r1) * (1-r2) * (1-r3)
149 // 1 0 0 0 -> r0 * (1-r1) * (1-r2) * (1-r3)
150 // 0 1 0 0 -> (1-r0) * r1 * (1-r2) * (1-r3)
151 // 1 1 0 0 -> r0 * r1 * (1-r2) * (1-r3)
152 // ....
153 // 1 1 1 1 -> r0 * r1 * r2 * r3
154 // we will need 2^num_var evaluations
155
156 let mut eval = Vec::new();
157 build_eq_x_r_helper(r, &mut eval)?;
158
159 let mle = DenseMultilinearExtension::from_evaluations_vec(r.len(), eval);
160
161 let res = Rc::new(mle);
162 end_timer!(start);
163 Ok(res)
164}
165
166/// A helper function to build eq(x, r) recursively.
167/// This function takes `r.len()` steps, and for each step it requires a maximum
168/// `r.len()-1` multiplications.
169fn build_eq_x_r_helper<F: PrimeField>(r: &[F], buf: &mut Vec<F>) -> Result<(), PolyIOPErrors> {
170 if r.is_empty() {
171 return Err(PolyIOPErrors::InvalidParameters(
172 "r length is 0".to_string(),
173 ));
174 } else if r.len() == 1 {
175 // initializing the buffer with [1-r0, r0]
176 buf.push(F::one() - r[0]);
177 buf.push(r[0]);
178 } else {
179 build_eq_x_r_helper(&r[1..], buf)?;
180
181 // suppose in the previous step we have [b1, ..., b_k]
182 // for the current step we will need
183 // if x0 = 0: (1-r0) * [b_1, ..., b_k]
184 // if x0 = 1: r0 * [b1, ..., b_k]
185
186 let mut res = vec![];
187 for &e in buf.iter() {
188 let tmp = e * r[0];
189 res.push(e - tmp);
190 res.push(tmp);
191 }
192 *buf = res;
193 }
194
195 Ok(())
196}
197
198#[cfg(test)]
199mod test {
200
201 use super::{build_eq_x_r, ZeroCheck};
202 use crate::{errors::PolyIOPErrors, PolyIOP, VirtualPolynomial};
203 use ark_bls12_381::Fr;
204 use ark_ff::{PrimeField, UniformRand};
205 use ark_poly::DenseMultilinearExtension;
206 use ark_std::{end_timer, start_timer, test_rng};
207 use std::rc::Rc;
208
209 fn test_zerocheck(
210 nv: usize,
211 num_multiplicands_range: (usize, usize),
212 num_products: usize,
213 ) -> Result<(), PolyIOPErrors> {
214 let mut rng = test_rng();
215
216 {
217 // good path: zero virtual poly
218 let poly =
219 VirtualPolynomial::rand_zero(nv, num_multiplicands_range, num_products, &mut rng)?;
220
221 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
222 transcript.append_message(b"testing", b"initializing transcript for testing")?;
223 let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
224
225 let poly_info = poly.domain_info.clone();
226 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
227 transcript.append_message(b"testing", b"initializing transcript for testing")?;
228 let subclaim =
229 <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?.0;
230 assert!(
231 poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
232 "wrong subclaim"
233 );
234 }
235
236 {
237 // bad path: random virtual poly whose sum is not zero
238 let (poly, _sum) =
239 VirtualPolynomial::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
240
241 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
242 transcript.append_message(b"testing", b"initializing transcript for testing")?;
243 let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
244
245 let poly_info = poly.domain_info.clone();
246 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
247 transcript.append_message(b"testing", b"initializing transcript for testing")?;
248
249 assert!(
250 <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)
251 .is_err()
252 );
253 }
254
255 Ok(())
256 }
257
258 #[test]
259 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
260 let nv = 1;
261 let num_multiplicands_range = (4, 5);
262 let num_products = 1;
263
264 test_zerocheck(nv, num_multiplicands_range, num_products)
265 }
266 #[test]
267 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
268 let nv = 5;
269 let num_multiplicands_range = (4, 9);
270 let num_products = 5;
271
272 test_zerocheck(nv, num_multiplicands_range, num_products)
273 }
274
275 #[test]
276 fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
277 let nv = 0;
278 let num_multiplicands_range = (4, 13);
279 let num_products = 5;
280
281 assert!(test_zerocheck(nv, num_multiplicands_range, num_products).is_err());
282 Ok(())
283 }
284
285 #[test]
286 fn test_eq_xr() {
287 let mut rng = test_rng();
288 for nv in 4..10 {
289 let r: Vec<Fr> = (0..nv).map(|_| Fr::rand(&mut rng)).collect();
290 let eq_x_r = build_eq_x_r(r.as_ref()).unwrap();
291 let eq_x_r2 = build_eq_x_r_for_test(r.as_ref());
292 assert_eq!(eq_x_r, eq_x_r2);
293 }
294 }
295
296 /// Naive method to build eq(x, r).
297 /// Only used for testing purpose.
298 // Evaluate
299 // eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
300 // over r, which is
301 // eq(x,y) = \prod_i=1^num_var (x_i * r_i + (1-x_i)*(1-r_i))
302 fn build_eq_x_r_for_test<F: PrimeField>(r: &[F]) -> Rc<DenseMultilinearExtension<F>> {
303 let start = start_timer!(|| "zero check naive build eq_x_r");
304
305 // we build eq(x,r) from its evaluations
306 // we want to evaluate eq(x,r) over x \in {0, 1}^num_vars
307 // for example, with num_vars = 4, x is a binary vector of 4, then
308 // 0 0 0 0 -> (1-r0) * (1-r1) * (1-r2) * (1-r3)
309 // 1 0 0 0 -> r0 * (1-r1) * (1-r2) * (1-r3)
310 // 0 1 0 0 -> (1-r0) * r1 * (1-r2) * (1-r3)
311 // 1 1 0 0 -> r0 * r1 * (1-r2) * (1-r3)
312 // ....
313 // 1 1 1 1 -> r0 * r1 * r2 * r3
314 // we will need 2^num_var evaluations
315
316 // First, we build array for {1 - r_i}
317 let one_minus_r: Vec<F> = r.iter().map(|ri| F::one() - ri).collect();
318
319 let num_var = r.len();
320 let mut eval = vec![];
321
322 for i in 0..1 << num_var {
323 let mut current_eval = F::one();
324 let bit_sequence = bit_decompose(i, num_var);
325
326 for (&bit, (ri, one_minus_ri)) in
327 bit_sequence.iter().zip(r.iter().zip(one_minus_r.iter()))
328 {
329 current_eval *= if bit { *ri } else { *one_minus_ri };
330 }
331 eval.push(current_eval);
332 }
333
334 let mle = DenseMultilinearExtension::from_evaluations_vec(num_var, eval);
335
336 let res = Rc::new(mle);
337 end_timer!(start);
338 res
339 }
340
341 fn bit_decompose(input: u64, num_var: usize) -> Vec<bool> {
342 let mut res = Vec::with_capacity(num_var);
343 let mut i = input;
344 for _ in 0..num_var {
345 res.push(i & 1 == 1);
346 i >>= 1;
347 }
348 res
349 }
350}