hyperplonk/poly-iop/src/sum_check/mod.rs
poly-iop/src/sum_check/mod.rsRaw
1//! This module implements the sum check protocol.
2
3use crate::{
4 errors::PolyIOPErrors,
5 structs::{IOPProof, IOPProverState, IOPVerifierState, SubClaim},
6 transcript::IOPTranscript,
7 virtual_poly::{VPAuxInfo, VirtualPolynomial},
8 PolyIOP,
9};
10use ark_ff::PrimeField;
11use ark_std::{end_timer, start_timer};
12
13mod prover;
14mod verifier;
15
16/// Trait for doing sum check protocols.
17pub trait SumCheck<F: PrimeField> {
18 type Proof;
19 type VirtualPolynomial;
20 type VPAuxInfo;
21 type SubClaim;
22 type Transcript;
23
24 /// Extract sum from the proof
25 fn extract_sum(proof: &Self::Proof) -> F;
26
27 /// Initialize the system with a transcript
28 ///
29 /// This function is optional -- in the case where a SumCheck is
30 /// an building block for a more complex protocol, the transcript
31 /// may be initialized by this complex protocol, and passed to the
32 /// SumCheck prover/verifier.
33 fn init_transcript() -> Self::Transcript;
34
35 /// Generate proof of the sum of polynomial over {0,1}^`num_vars`
36 ///
37 /// The polynomial is represented in the form of a VirtualPolynomial.
38 fn prove(
39 poly: &Self::VirtualPolynomial,
40 transcript: &mut Self::Transcript,
41 ) -> Result<Self::Proof, PolyIOPErrors>;
42
43 /// Verify the claimed sum using the proof
44 fn verify(
45 sum: F,
46 proof: &Self::Proof,
47 aux_info: &Self::VPAuxInfo,
48 transcript: &mut Self::Transcript,
49 ) -> Result<Self::SubClaim, PolyIOPErrors>;
50}
51
52/// Trait for sum check protocol prover side APIs.
53pub trait SumCheckProver<F: PrimeField>
54where
55 Self: Sized,
56{
57 type VirtualPolynomial;
58 type ProverMessage;
59
60 /// Initialize the prover state to argue for the sum of the input polynomial
61 /// over {0,1}^`num_vars`.
62 fn prover_init(polynomial: &Self::VirtualPolynomial) -> Result<Self, PolyIOPErrors>;
63
64 /// Receive message from verifier, generate prover message, and proceed to
65 /// next round.
66 ///
67 /// Main algorithm used is from section 3.2 of [XZZPS19](https://eprint.iacr.org/2019/317.pdf#subsection.3.2).
68 fn prove_round_and_update_state(
69 &mut self,
70 challenge: &Option<F>,
71 ) -> Result<Self::ProverMessage, PolyIOPErrors>;
72}
73
74/// Trait for sum check protocol verifier side APIs.
75pub trait SumCheckVerifier<F: PrimeField> {
76 type VPAuxInfo;
77 type ProverMessage;
78 type Challenge;
79 type Transcript;
80 type SubClaim;
81
82 /// Initialize the verifier's state.
83 fn verifier_init(index_info: &Self::VPAuxInfo) -> Self;
84
85 /// Run verifier for the current round, given a prover message.
86 ///
87 /// Note that `verify_round_and_update_state` only samples and stores
88 /// challenges; and update the verifier's state accordingly. The actual
89 /// verifications are deferred (in batch) to `check_and_generate_subclaim`
90 /// at the last step.
91 fn verify_round_and_update_state(
92 &mut self,
93 prover_msg: &Self::ProverMessage,
94 transcript: &mut Self::Transcript,
95 ) -> Result<Self::Challenge, PolyIOPErrors>;
96
97 /// This function verifies the deferred checks in the interactive version of
98 /// the protocol; and generate the subclaim. Returns an error if the
99 /// proof failed to verify.
100 ///
101 /// If the asserted sum is correct, then the multilinear polynomial
102 /// evaluated at `subclaim.point` will be `subclaim.expected_evaluation`.
103 /// Otherwise, it is highly unlikely that those two will be equal.
104 /// Larger field size guarantees smaller soundness error.
105 fn check_and_generate_subclaim(
106 &self,
107 asserted_sum: &F,
108 ) -> Result<Self::SubClaim, PolyIOPErrors>;
109}
110
111impl<F: PrimeField> SumCheck<F> for PolyIOP<F> {
112 type Proof = IOPProof<F>;
113 type VirtualPolynomial = VirtualPolynomial<F>;
114 type VPAuxInfo = VPAuxInfo<F>;
115 type SubClaim = SubClaim<F>;
116 type Transcript = IOPTranscript<F>;
117
118 /// Extract sum from the proof
119 fn extract_sum(proof: &Self::Proof) -> F {
120 let start = start_timer!(|| "extract sum");
121 let res = proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1];
122 end_timer!(start);
123 res
124 }
125
126 /// Initialize the system with a transcript
127 ///
128 /// This function is optional -- in the case where a SumCheck is
129 /// an building block for a more complex protocol, the transcript
130 /// may be initialized by this complex protocol, and passed to the
131 /// SumCheck prover/verifier.
132 fn init_transcript() -> Self::Transcript {
133 let start = start_timer!(|| "init transcript");
134 let res = IOPTranscript::<F>::new(b"Initializing SumCheck transcript");
135 end_timer!(start);
136 res
137 }
138
139 /// Generate proof of the sum of polynomial over {0,1}^`num_vars`
140 ///
141 /// The polynomial is represented in the form of a VirtualPolynomial.
142 fn prove(
143 poly: &Self::VirtualPolynomial,
144 transcript: &mut Self::Transcript,
145 ) -> Result<Self::Proof, PolyIOPErrors> {
146 let start = start_timer!(|| "sum check prove");
147
148 transcript.append_aux_info(&poly.aux_info)?;
149
150 let mut prover_state = IOPProverState::prover_init(poly)?;
151 let mut challenge = None;
152 let mut prover_msgs = Vec::with_capacity(poly.aux_info.num_variables);
153 for _ in 0..poly.aux_info.num_variables {
154 let prover_msg =
155 IOPProverState::prove_round_and_update_state(&mut prover_state, &challenge)?;
156 transcript.append_prover_message(&prover_msg)?;
157 prover_msgs.push(prover_msg);
158 challenge = Some(transcript.get_and_append_challenge(b"Internal round")?);
159 }
160
161 end_timer!(start);
162 Ok(IOPProof {
163 proofs: prover_msgs,
164 })
165 }
166
167 /// Verify the claimed sum using the proof
168 fn verify(
169 claimed_sum: F,
170 proof: &Self::Proof,
171 aux_info: &Self::VPAuxInfo,
172 transcript: &mut Self::Transcript,
173 ) -> Result<Self::SubClaim, PolyIOPErrors> {
174 let start = start_timer!(|| "sum check verify");
175
176 transcript.append_aux_info(aux_info)?;
177 let mut verifier_state = IOPVerifierState::verifier_init(aux_info);
178 for i in 0..aux_info.num_variables {
179 let prover_msg = proof.proofs.get(i).expect("proof is incomplete");
180 transcript.append_prover_message(prover_msg)?;
181 IOPVerifierState::verify_round_and_update_state(
182 &mut verifier_state,
183 prover_msg,
184 transcript,
185 )?;
186 }
187
188 let res = IOPVerifierState::check_and_generate_subclaim(&verifier_state, &claimed_sum);
189
190 end_timer!(start);
191 res
192 }
193}
194
195#[cfg(test)]
196mod test {
197
198 use super::*;
199 use ark_bls12_381::Fr;
200 use ark_ff::UniformRand;
201 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
202 use ark_std::test_rng;
203 use std::rc::Rc;
204
205 fn test_sumcheck(
206 nv: usize,
207 num_multiplicands_range: (usize, usize),
208 num_products: usize,
209 ) -> Result<(), PolyIOPErrors> {
210 let mut rng = test_rng();
211 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
212
213 let (poly, asserted_sum) =
214 VirtualPolynomial::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
215 let proof = <PolyIOP<Fr> as SumCheck<Fr>>::prove(&poly, &mut transcript)?;
216 let poly_info = poly.aux_info.clone();
217 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
218 let subclaim = <PolyIOP<Fr> as SumCheck<Fr>>::verify(
219 asserted_sum,
220 &proof,
221 &poly_info,
222 &mut transcript,
223 )?;
224 assert!(
225 poly.evaluate(&subclaim.point).unwrap() == subclaim.expected_evaluation,
226 "wrong subclaim"
227 );
228 Ok(())
229 }
230
231 fn test_sumcheck_internal(
232 nv: usize,
233 num_multiplicands_range: (usize, usize),
234 num_products: usize,
235 ) -> Result<(), PolyIOPErrors> {
236 let mut rng = test_rng();
237 let (poly, asserted_sum) =
238 VirtualPolynomial::<Fr>::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
239 let poly_info = poly.aux_info.clone();
240 let mut prover_state = IOPProverState::prover_init(&poly)?;
241 let mut verifier_state = IOPVerifierState::verifier_init(&poly_info);
242 let mut challenge = None;
243 let mut transcript = IOPTranscript::new(b"a test transcript");
244 transcript
245 .append_message(b"testing", b"initializing transcript for testing")
246 .unwrap();
247 for _ in 0..poly.aux_info.num_variables {
248 let prover_message =
249 IOPProverState::prove_round_and_update_state(&mut prover_state, &challenge)
250 .unwrap();
251
252 challenge = Some(
253 IOPVerifierState::verify_round_and_update_state(
254 &mut verifier_state,
255 &prover_message,
256 &mut transcript,
257 )
258 .unwrap(),
259 );
260 }
261 let subclaim =
262 IOPVerifierState::check_and_generate_subclaim(&verifier_state, &asserted_sum)
263 .expect("fail to generate subclaim");
264 assert!(
265 poly.evaluate(&subclaim.point).unwrap() == subclaim.expected_evaluation,
266 "wrong subclaim"
267 );
268 Ok(())
269 }
270
271 #[test]
272 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
273 let nv = 1;
274 let num_multiplicands_range = (4, 13);
275 let num_products = 5;
276
277 test_sumcheck(nv, num_multiplicands_range, num_products)?;
278 test_sumcheck_internal(nv, num_multiplicands_range, num_products)
279 }
280 #[test]
281 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
282 let nv = 12;
283 let num_multiplicands_range = (4, 9);
284 let num_products = 5;
285
286 test_sumcheck(nv, num_multiplicands_range, num_products)?;
287 test_sumcheck_internal(nv, num_multiplicands_range, num_products)
288 }
289 #[test]
290 fn zero_polynomial_should_error() {
291 let nv = 0;
292 let num_multiplicands_range = (4, 13);
293 let num_products = 5;
294
295 assert!(test_sumcheck(nv, num_multiplicands_range, num_products).is_err());
296 assert!(test_sumcheck_internal(nv, num_multiplicands_range, num_products).is_err());
297 }
298
299 #[test]
300 fn test_extract_sum() -> Result<(), PolyIOPErrors> {
301 let mut rng = test_rng();
302 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
303 let (poly, asserted_sum) = VirtualPolynomial::<Fr>::rand(8, (3, 4), 3, &mut rng)?;
304
305 let proof = <PolyIOP<Fr> as SumCheck<Fr>>::prove(&poly, &mut transcript)?;
306 assert_eq!(
307 <PolyIOP<Fr> as SumCheck<Fr>>::extract_sum(&proof),
308 asserted_sum
309 );
310 Ok(())
311 }
312
313 #[test]
314 /// Test that the memory usage of shared-reference is linear to number of
315 /// unique MLExtensions instead of total number of multiplicands.
316 fn test_shared_reference() -> Result<(), PolyIOPErrors> {
317 let mut rng = test_rng();
318 let ml_extensions: Vec<_> = (0..5)
319 .map(|_| Rc::new(DenseMultilinearExtension::<Fr>::rand(8, &mut rng)))
320 .collect();
321 let mut poly = VirtualPolynomial::new(8);
322 poly.add_mle_list(
323 vec![
324 ml_extensions[2].clone(),
325 ml_extensions[3].clone(),
326 ml_extensions[0].clone(),
327 ],
328 Fr::rand(&mut rng),
329 )?;
330 poly.add_mle_list(
331 vec![
332 ml_extensions[1].clone(),
333 ml_extensions[4].clone(),
334 ml_extensions[4].clone(),
335 ],
336 Fr::rand(&mut rng),
337 )?;
338 poly.add_mle_list(
339 vec![
340 ml_extensions[3].clone(),
341 ml_extensions[2].clone(),
342 ml_extensions[1].clone(),
343 ],
344 Fr::rand(&mut rng),
345 )?;
346 poly.add_mle_list(
347 vec![ml_extensions[0].clone(), ml_extensions[0].clone()],
348 Fr::rand(&mut rng),
349 )?;
350 poly.add_mle_list(vec![ml_extensions[4].clone()], Fr::rand(&mut rng))?;
351
352 assert_eq!(poly.flattened_ml_extensions.len(), 5);
353
354 // test memory usage for prover
355 let prover = IOPProverState::prover_init(&poly).unwrap();
356 assert_eq!(prover.poly.flattened_ml_extensions.len(), 5);
357 drop(prover);
358
359 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
360 let poly_info = poly.aux_info.clone();
361 let proof = <PolyIOP<Fr> as SumCheck<Fr>>::prove(&poly, &mut transcript)?;
362 let asserted_sum = <PolyIOP<Fr> as SumCheck<Fr>>::extract_sum(&proof);
363
364 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
365 let subclaim = <PolyIOP<Fr> as SumCheck<Fr>>::verify(
366 asserted_sum,
367 &proof,
368 &poly_info,
369 &mut transcript,
370 )?;
371 assert!(
372 poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
373 "wrong subclaim"
374 );
375 Ok(())
376 }
377}