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