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]) -> Rc<DenseMultilinearExtension<F>> {
141 let start = start_timer!(|| "zero check build 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 // First, we build array for {1 - r_i}
155 let one_minus_r: Vec<F> = r.iter().map(|ri| F::one() - ri).collect();
156
157 let num_var = r.len();
158 let mut eval = vec![];
159
160 // TODO: optimize the following code
161 // currently, a naive implementation requires num_var * 2^num_var
162 // field multiplications.
163 for i in 0..1 << num_var {
164 let mut current_eval = F::one();
165 let bit_sequence = bit_decompose(i, num_var);
166
167 for (&bit, (ri, one_minus_ri)) in bit_sequence.iter().zip(r.iter().zip(one_minus_r.iter()))
168 {
169 current_eval *= if bit { *ri } else { *one_minus_ri };
170 }
171 eval.push(current_eval);
172 }
173 let mle = DenseMultilinearExtension::from_evaluations_vec(num_var, eval);
174
175 let res = Rc::new(mle);
176 end_timer!(start);
177 res
178}
179
180fn bit_decompose(input: u64, num_var: usize) -> Vec<bool> {
181 let mut res = Vec::with_capacity(num_var);
182 let mut i = input;
183 for _ in 0..num_var {
184 res.push(i & 1 == 1);
185 i >>= 1;
186 }
187 res
188}
189
190#[cfg(test)]
191mod test {
192
193 use super::ZeroCheck;
194 use crate::{errors::PolyIOPErrors, PolyIOP, VirtualPolynomial};
195 use ark_bls12_381::Fr;
196 use ark_std::test_rng;
197
198 fn test_zerocheck(
199 nv: usize,
200 num_multiplicands_range: (usize, usize),
201 num_products: usize,
202 ) -> Result<(), PolyIOPErrors> {
203 let mut rng = test_rng();
204
205 {
206 // good path: zero virtual poly
207 let poly =
208 VirtualPolynomial::rand_zero(nv, num_multiplicands_range, num_products, &mut rng)?;
209
210 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
211 transcript.append_message(b"testing", b"initializing transcript for testing")?;
212 let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
213
214 let poly_info = poly.domain_info.clone();
215 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
216 transcript.append_message(b"testing", b"initializing transcript for testing")?;
217 let subclaim =
218 <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?.0;
219 assert!(
220 poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
221 "wrong subclaim"
222 );
223 }
224
225 {
226 // bad path: random virtual poly whose sum is not zero
227 let (poly, _sum) =
228 VirtualPolynomial::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
229
230 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
231 transcript.append_message(b"testing", b"initializing transcript for testing")?;
232 let proof = <PolyIOP<Fr> as ZeroCheck<Fr>>::prove(&poly, &mut transcript)?;
233
234 let poly_info = poly.domain_info.clone();
235 let mut transcript = <PolyIOP<Fr> as ZeroCheck<Fr>>::init_transcript();
236 transcript.append_message(b"testing", b"initializing transcript for testing")?;
237
238 assert!(
239 <PolyIOP<Fr> as ZeroCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)
240 .is_err()
241 );
242 }
243
244 Ok(())
245 }
246
247 #[test]
248 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
249 let nv = 1;
250 let num_multiplicands_range = (4, 5);
251 let num_products = 1;
252
253 test_zerocheck(nv, num_multiplicands_range, num_products)
254 }
255 #[test]
256 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
257 let nv = 5;
258 let num_multiplicands_range = (4, 9);
259 let num_products = 5;
260
261 test_zerocheck(nv, num_multiplicands_range, num_products)
262 }
263 #[test]
264
265 fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
266 let nv = 0;
267 let num_multiplicands_range = (4, 13);
268 let num_products = 5;
269
270 assert!(test_zerocheck(nv, num_multiplicands_range, num_products).is_err());
271 Ok(())
272 }
273}