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 PolyIOP,
7};
8use arithmetic::{VPAuxInfo, VirtualPolynomial};
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 SumCheckProof;
24 type Transcript;
25 type SumCheckSubClaim;
26
27 /// Extract sum from the proof
28 fn extract_sum(proof: &Self::SumCheckProof) -> 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::SumCheckProof, PolyIOPErrors>;
45
46 /// Verify the claimed sum using the proof
47 fn verify(
48 sum: F,
49 proof: &Self::SumCheckProof,
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, Eq)]
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 SumCheckProof = 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::SumCheckProof) -> 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::SumCheckProof, 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 // pushing the last challenge point to the state
176 if let Some(p) = challenge {
177 prover_state.challenges.push(p)
178 };
179
180 end_timer!(start);
181 Ok(IOPProof {
182 point: prover_state.challenges,
183 proofs: prover_msgs,
184 })
185 }
186
187 /// Verify the claimed sum using the proof
188 fn verify(
189 claimed_sum: F,
190 proof: &Self::SumCheckProof,
191 aux_info: &Self::VPAuxInfo,
192 transcript: &mut Self::Transcript,
193 ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors> {
194 let start = start_timer!(|| "sum check verify");
195
196 transcript.append_serializable_element(b"aux info", aux_info)?;
197 let mut verifier_state = IOPVerifierState::verifier_init(aux_info);
198 for i in 0..aux_info.num_variables {
199 let prover_msg = proof.proofs.get(i).expect("proof is incomplete");
200 transcript.append_serializable_element(b"prover msg", prover_msg)?;
201 IOPVerifierState::verify_round_and_update_state(
202 &mut verifier_state,
203 prover_msg,
204 transcript,
205 )?;
206 }
207
208 let res = IOPVerifierState::check_and_generate_subclaim(&verifier_state, &claimed_sum);
209
210 end_timer!(start);
211 res
212 }
213}
214
215#[cfg(test)]
216mod test {
217
218 use super::*;
219 use ark_bls12_381::Fr;
220 use ark_ff::UniformRand;
221 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
222 use ark_std::test_rng;
223 use std::rc::Rc;
224
225 fn test_sumcheck(
226 nv: usize,
227 num_multiplicands_range: (usize, usize),
228 num_products: usize,
229 ) -> Result<(), PolyIOPErrors> {
230 let mut rng = test_rng();
231 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
232
233 let (poly, asserted_sum) =
234 VirtualPolynomial::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
235 let proof = <PolyIOP<Fr> as SumCheck<Fr>>::prove(&poly, &mut transcript)?;
236 let poly_info = poly.aux_info.clone();
237 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
238 let subclaim = <PolyIOP<Fr> as SumCheck<Fr>>::verify(
239 asserted_sum,
240 &proof,
241 &poly_info,
242 &mut transcript,
243 )?;
244 assert!(
245 poly.evaluate(&subclaim.point).unwrap() == subclaim.expected_evaluation,
246 "wrong subclaim"
247 );
248 Ok(())
249 }
250
251 fn test_sumcheck_internal(
252 nv: usize,
253 num_multiplicands_range: (usize, usize),
254 num_products: usize,
255 ) -> Result<(), PolyIOPErrors> {
256 let mut rng = test_rng();
257 let (poly, asserted_sum) =
258 VirtualPolynomial::<Fr>::rand(nv, num_multiplicands_range, num_products, &mut rng)?;
259 let poly_info = poly.aux_info.clone();
260 let mut prover_state = IOPProverState::prover_init(&poly)?;
261 let mut verifier_state = IOPVerifierState::verifier_init(&poly_info);
262 let mut challenge = None;
263 let mut transcript = IOPTranscript::new(b"a test transcript");
264 transcript
265 .append_message(b"testing", b"initializing transcript for testing")
266 .unwrap();
267 for _ in 0..poly.aux_info.num_variables {
268 let prover_message =
269 IOPProverState::prove_round_and_update_state(&mut prover_state, &challenge)
270 .unwrap();
271
272 challenge = Some(
273 IOPVerifierState::verify_round_and_update_state(
274 &mut verifier_state,
275 &prover_message,
276 &mut transcript,
277 )
278 .unwrap(),
279 );
280 }
281 let subclaim =
282 IOPVerifierState::check_and_generate_subclaim(&verifier_state, &asserted_sum)
283 .expect("fail to generate subclaim");
284 assert!(
285 poly.evaluate(&subclaim.point).unwrap() == subclaim.expected_evaluation,
286 "wrong subclaim"
287 );
288 Ok(())
289 }
290
291 #[test]
292 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
293 let nv = 1;
294 let num_multiplicands_range = (4, 13);
295 let num_products = 5;
296
297 test_sumcheck(nv, num_multiplicands_range, num_products)?;
298 test_sumcheck_internal(nv, num_multiplicands_range, num_products)
299 }
300 #[test]
301 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
302 let nv = 12;
303 let num_multiplicands_range = (4, 9);
304 let num_products = 5;
305
306 test_sumcheck(nv, num_multiplicands_range, num_products)?;
307 test_sumcheck_internal(nv, num_multiplicands_range, num_products)
308 }
309 #[test]
310 fn zero_polynomial_should_error() {
311 let nv = 0;
312 let num_multiplicands_range = (4, 13);
313 let num_products = 5;
314
315 assert!(test_sumcheck(nv, num_multiplicands_range, num_products).is_err());
316 assert!(test_sumcheck_internal(nv, num_multiplicands_range, num_products).is_err());
317 }
318
319 #[test]
320 fn test_extract_sum() -> Result<(), PolyIOPErrors> {
321 let mut rng = test_rng();
322 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
323 let (poly, asserted_sum) = VirtualPolynomial::<Fr>::rand(8, (3, 4), 3, &mut rng)?;
324
325 let proof = <PolyIOP<Fr> as SumCheck<Fr>>::prove(&poly, &mut transcript)?;
326 assert_eq!(
327 <PolyIOP<Fr> as SumCheck<Fr>>::extract_sum(&proof),
328 asserted_sum
329 );
330 Ok(())
331 }
332
333 #[test]
334 /// Test that the memory usage of shared-reference is linear to number of
335 /// unique MLExtensions instead of total number of multiplicands.
336 fn test_shared_reference() -> Result<(), PolyIOPErrors> {
337 let mut rng = test_rng();
338 let ml_extensions: Vec<_> = (0..5)
339 .map(|_| Rc::new(DenseMultilinearExtension::<Fr>::rand(8, &mut rng)))
340 .collect();
341 let mut poly = VirtualPolynomial::new(8);
342 poly.add_mle_list(
343 vec![
344 ml_extensions[2].clone(),
345 ml_extensions[3].clone(),
346 ml_extensions[0].clone(),
347 ],
348 Fr::rand(&mut rng),
349 )?;
350 poly.add_mle_list(
351 vec![
352 ml_extensions[1].clone(),
353 ml_extensions[4].clone(),
354 ml_extensions[4].clone(),
355 ],
356 Fr::rand(&mut rng),
357 )?;
358 poly.add_mle_list(
359 vec![
360 ml_extensions[3].clone(),
361 ml_extensions[2].clone(),
362 ml_extensions[1].clone(),
363 ],
364 Fr::rand(&mut rng),
365 )?;
366 poly.add_mle_list(
367 vec![ml_extensions[0].clone(), ml_extensions[0].clone()],
368 Fr::rand(&mut rng),
369 )?;
370 poly.add_mle_list(vec![ml_extensions[4].clone()], Fr::rand(&mut rng))?;
371
372 assert_eq!(poly.flattened_ml_extensions.len(), 5);
373
374 // test memory usage for prover
375 let prover = IOPProverState::<Fr>::prover_init(&poly).unwrap();
376 assert_eq!(prover.poly.flattened_ml_extensions.len(), 5);
377 drop(prover);
378
379 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
380 let poly_info = poly.aux_info.clone();
381 let proof = <PolyIOP<Fr> as SumCheck<Fr>>::prove(&poly, &mut transcript)?;
382 let asserted_sum = <PolyIOP<Fr> as SumCheck<Fr>>::extract_sum(&proof);
383
384 let mut transcript = <PolyIOP<Fr> as SumCheck<Fr>>::init_transcript();
385 let subclaim = <PolyIOP<Fr> as SumCheck<Fr>>::verify(
386 asserted_sum,
387 &proof,
388 &poly_info,
389 &mut transcript,
390 )?;
391 assert!(
392 poly.evaluate(&subclaim.point)? == subclaim.expected_evaluation,
393 "wrong subclaim"
394 );
395 Ok(())
396 }
397}