hyperplonk/poly-iop/src/zero_check/mod.rs
poly-iop/src/zero_check/mod.rsRaw
1mod prover;
2mod verifier;
3
4use ark_ff::PrimeField;
5use ark_poly::DenseMultilinearExtension;
6pub use prover::ProverState;
7use std::rc::Rc;
8pub use verifier::VerifierState;
9
10use crate::{
11 errors::PolyIOPErrors,
12 structs::{DomainInfo, IOPProof, SubClaim},
13 sum_check::SumCheck,
14 transcript::IOPTranscript,
15 virtual_poly::VirtualPolynomial,
16 PolyIOP,
17};
18
19pub trait ZeroCheck<F: PrimeField> {
20 type Proof;
21 type PolyList;
22 type DomainInfo;
23 type SubClaim;
24 type Transcript;
25
26 /// Initialize the system with a transcript
27 ///
28 /// This function is optional -- in the case where a ZeroCheck is
29 /// an building block for a more complex protocol, the transcript
30 /// may be initialized by this complex protocol, and passed to the
31 /// ZeroCheck prover/verifier.
32 fn init_transcript() -> Self::Transcript;
33
34 fn prove(
35 poly: &Self::PolyList,
36 transcript: &mut Self::Transcript,
37 ) -> Result<Self::Proof, PolyIOPErrors>;
38
39 /// verify the claimed sum using the proof
40 fn verify(
41 proof: &Self::Proof,
42 domain_info: &Self::DomainInfo,
43 transcript: &mut Self::Transcript,
44 ) -> Result<Self::SubClaim, PolyIOPErrors>;
45}
46
47impl<F: PrimeField> ZeroCheck<F> for PolyIOP<F> {
48 type Proof = IOPProof<F>;
49 type PolyList = VirtualPolynomial<F>;
50 type DomainInfo = DomainInfo<F>;
51 type SubClaim = SubClaim<F>;
52 type Transcript = IOPTranscript<F>;
53
54 /// Initialize the system with a transcript
55 ///
56 /// This function is optional -- in the case where a ZeroCheck is
57 /// an building block for a more complex protocol, the transcript
58 /// may be initialized by this complex protocol, and passed to the
59 /// ZeroCheck prover/verifier.
60 fn init_transcript() -> Self::Transcript {
61 IOPTranscript::<F>::new(b"Initializing ZeroCheck transcript")
62 }
63
64 fn prove(
65 poly: &Self::PolyList,
66 transcript: &mut Self::Transcript,
67 ) -> Result<Self::Proof, PolyIOPErrors> {
68 let length = poly.domain_info.num_variables;
69 let r = transcript.get_and_append_challenge_vectors(b"vector r", length)?;
70 let f_hat = build_f_hat(poly, r.as_ref());
71 <Self as SumCheck<F>>::prove(&f_hat, transcript)
72 }
73
74 /// Verify the claimed sum using the proof.
75 /// Caller needs to makes sure that `\hat f = f * eq(x, r)`
76 fn verify(
77 proof: &Self::Proof,
78 domain_info: &Self::DomainInfo,
79 transcript: &mut Self::Transcript,
80 ) -> Result<Self::SubClaim, PolyIOPErrors> {
81 println!(
82 "sum: {}",
83 proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1]
84 );
85
86 <Self as SumCheck<F>>::verify(F::zero(), proof, domain_info, transcript)
87 }
88}
89
90// Input poly f(x) and a random vector r, output
91// \hat f(x) = \sum_{x_i \in eval_x} f(x_i) eq(x, r)
92// where
93// eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
94fn build_f_hat<F: PrimeField>(poly: &VirtualPolynomial<F>, r: &[F]) -> VirtualPolynomial<F> {
95 assert_eq!(poly.domain_info.num_variables, r.len());
96 let mut res = poly.clone();
97 let eq_x_r = build_eq_x_r(r);
98 res.add_product([eq_x_r; 1], F::one());
99 // // First, we build array for {1 - r_i}
100 // let one_minus_r: Vec<F> = r.iter().map(|ri| F::one() - ri).collect();
101
102 // let mut eval = vec![];
103 // // let eq_x_r = build_eq_x_r(r);
104 // let num_var = r.len();
105 // let mut res = VirtualPolynomial::new(num_var);
106 // // res.add_product([eq_x_r; 1], F::one());
107
108 // for i in 0..1 << num_var {
109 // let bit_sequence = bit_decompose(i, num_var);
110 // let bit_points: Vec<F> = bit_sequence.iter().map(|&x| F::from(x as
111 // u64)).collect(); let mut eq_eval = F::one();
112 // for (&bit, (ri, one_minus_ri)) in
113 // bit_sequence.iter().zip(r.iter().zip(one_minus_r.iter())) {
114 // if bit {
115 // eq_eval *= ri;
116 // } else {
117 // eq_eval *= one_minus_ri;
118 // }
119 // }
120 // eval.push(eq_eval * poly.evaluate(&bit_points))
121 // }
122 // let hat_f = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
123 // num_var, eval,
124 // ));
125 // res.add_product([hat_f; 1], F::one());
126 res
127}
128
129// Evaluate
130// eq(x,y) = \prod_i=1^num_var (x_i * y_i + (1-x_i)*(1-y_i))
131// over r, which is
132// eq(x,y) = \prod_i=1^num_var (x_i * r_i + (1-x_i)*(1-r_i))
133fn build_eq_x_r<F: PrimeField>(r: &[F]) -> Rc<DenseMultilinearExtension<F>> {
134 // we build eq(x,r) from its evaluations
135 // we want to evaluate eq(x,r) over x \in {0, 1}^num_vars
136 // for example, with num_vars = 4, x is a binary vector of 4, then
137 // 0 0 0 0 -> (1-r0) * (1-r1) * (1-r2) * (1-r3)
138 // 1 0 0 0 -> r0 * (1-r1) * (1-r2) * (1-r3)
139 // 0 1 0 0 -> (1-r0) * r1 * (1-r2) * (1-r3)
140 // 1 1 0 0 -> r0 * r1 * (1-r2) * (1-r3)
141 // ....
142 // 1 1 1 1 -> r0 * r1 * r2 * r3
143 // we will need 2^num_var evaluations
144
145 // First, we build array for {1 - r_i}
146 let one_minus_r: Vec<F> = r.iter().map(|ri| F::one() - ri).collect();
147
148 let num_var = r.len();
149 let mut eval = vec![];
150
151 // TODO: optimize the following code
152 // currently, a naive implementation requires num_var * 2^num_var
153 // field multiplications.
154 for i in 0..1 << num_var {
155 let mut current_eval = F::one();
156 let bit_sequence = bit_decompose(i, num_var);
157
158 for (&bit, (ri, one_minus_ri)) in bit_sequence.iter().zip(r.iter().zip(one_minus_r.iter()))
159 {
160 if bit {
161 current_eval *= *ri;
162 } else {
163 current_eval *= *one_minus_ri;
164 }
165 }
166 eval.push(current_eval);
167 }
168 let res = Rc::new(DenseMultilinearExtension::from_evaluations_vec(
169 num_var, eval,
170 ));
171
172 res
173}
174
175fn bit_decompose(input: u64, num_var: usize) -> Vec<bool> {
176 let mut res = Vec::with_capacity(num_var);
177 let mut i = input;
178 for _ in 0..num_var {
179 res.push(i & 1 == 1);
180 i >>= 1;
181 }
182 res
183}
184
185#[cfg(test)]
186mod test {
187
188 use super::ZeroCheck;
189 use crate::{virtual_poly::test::random_zero_list_of_products, PolyIOP, VirtualPolynomial};
190 use ark_bls12_381::Fr;
191 use ark_ff::UniformRand;
192 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
193 use ark_std::test_rng;
194 use std::rc::Rc;
195
196 fn test_polynomial(nv: usize, num_multiplicands_range: (usize, usize), num_products: usize) {
197 let mut rng = test_rng();
198 let mut transcript = PolyIOP::init_transcript();
199 transcript
200 .append_message(b"testing", b"initializing transcript for testing")
201 .unwrap();
202 let poly = random_zero_list_of_products::<Fr, _>(
203 nv,
204 num_multiplicands_range,
205 num_products,
206 &mut rng,
207 );
208 // println!("{:?}", poly);
209
210 let proof = PolyIOP::prove(&poly, &mut transcript).expect("fail to prove");
211 println!(
212 "{}",
213 proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1]
214 );
215
216 let poly_info = poly.domain_info.clone();
217 let mut transcript = PolyIOP::init_transcript();
218 transcript
219 .append_message(b"testing", b"initializing transcript for testing")
220 .unwrap();
221 let subclaim =
222 PolyIOP::verify(&proof, &poly_info, &mut transcript).expect("fail to verify");
223 assert!(
224 poly.evaluate(&subclaim.point) == subclaim.expected_evaluation,
225 "wrong subclaim"
226 );
227 }
228
229 #[test]
230 fn test_trivial_polynomial() {
231 let nv = 1;
232 let num_multiplicands_range = (4, 5);
233 let num_products = 1;
234
235 test_polynomial(nv, num_multiplicands_range, num_products);
236 }
237 #[test]
238 fn test_normal_polynomial() {
239 let nv = 16;
240 let num_multiplicands_range = (4, 9);
241 let num_products = 5;
242
243 test_polynomial(nv, num_multiplicands_range, num_products);
244 }
245 #[test]
246 #[should_panic]
247 fn zero_polynomial_should_error() {
248 let nv = 0;
249 let num_multiplicands_range = (4, 13);
250 let num_products = 5;
251
252 test_polynomial(nv, num_multiplicands_range, num_products);
253 }
254
255 #[test]
256 /// Test that the memory usage of shared-reference is linear to number of
257 /// unique MLExtensions instead of total number of multiplicands.
258 fn test_shared_reference() {
259 let mut rng = test_rng();
260 let ml_extensions: Vec<_> = (0..5)
261 .map(|_| Rc::new(DenseMultilinearExtension::<Fr>::rand(8, &mut rng)))
262 .collect();
263 let mut poly = VirtualPolynomial::new(8);
264 poly.add_product(
265 vec![
266 ml_extensions[2].clone(),
267 ml_extensions[3].clone(),
268 ml_extensions[0].clone(),
269 ],
270 Fr::rand(&mut rng),
271 );
272 poly.add_product(
273 vec![
274 ml_extensions[1].clone(),
275 ml_extensions[4].clone(),
276 ml_extensions[4].clone(),
277 ],
278 Fr::rand(&mut rng),
279 );
280 poly.add_product(
281 vec![
282 ml_extensions[3].clone(),
283 ml_extensions[2].clone(),
284 ml_extensions[1].clone(),
285 ],
286 Fr::rand(&mut rng),
287 );
288 poly.add_product(
289 vec![ml_extensions[0].clone(), ml_extensions[0].clone()],
290 Fr::rand(&mut rng),
291 );
292 poly.add_product(vec![ml_extensions[4].clone()], Fr::rand(&mut rng));
293
294 assert_eq!(poly.flattened_ml_extensions.len(), 5);
295
296 let mut transcript = PolyIOP::init_transcript();
297
298 transcript
299 .append_message(b"testing", b"initializing transcript for testing")
300 .unwrap();
301 let poly_info = poly.domain_info.clone();
302 let proof = PolyIOP::prove(&poly, &mut transcript).expect("fail to prove");
303
304 let mut transcript = PolyIOP::init_transcript();
305
306 transcript
307 .append_message(b"testing", b"initializing transcript for testing")
308 .unwrap();
309 let subclaim =
310 PolyIOP::verify(&proof, &poly_info, &mut transcript).expect("fail to verify");
311 assert!(
312 poly.evaluate(&subclaim.point) == subclaim.expected_evaluation,
313 "wrong subclaim"
314 );
315 }
316}