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