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 std::{fmt::Debug, rc::Rc};
13use transcript::IOPTranscript;
14
15mod prover;
16mod verifier;
17
18/// Trait for doing sum check protocols.
19pub trait SumCheck<F: PrimeField> {
20 type VirtualPolynomial;
21 type VPAuxInfo;
22 type MultilinearExtension;
23
24 type SumCheckProof: Clone + Debug + Default + PartialEq;
25 type Transcript;
26 type SumCheckSubClaim: Clone + Debug + Default + PartialEq;
27
28 /// Extract sum from the proof
29 fn extract_sum(proof: &Self::SumCheckProof) -> F;
30
31 /// Initialize the system with a transcript
32 ///
33 /// This function is optional -- in the case where a SumCheck is
34 /// an building block for a more complex protocol, the transcript
35 /// may be initialized by this complex protocol, and passed to the
36 /// SumCheck prover/verifier.
37 fn init_transcript() -> Self::Transcript;
38
39 /// Generate proof of the sum of polynomial over {0,1}^`num_vars`
40 ///
41 /// The polynomial is represented in the form of a VirtualPolynomial.
42 fn prove(
43 poly: &Self::VirtualPolynomial,
44 transcript: &mut Self::Transcript,
45 ) -> Result<Self::SumCheckProof, PolyIOPErrors>;
46
47 /// Verify the claimed sum using the proof
48 fn verify(
49 sum: F,
50 proof: &Self::SumCheckProof,
51 aux_info: &Self::VPAuxInfo,
52 transcript: &mut Self::Transcript,
53 ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors>;
54}
55
56/// Trait for sum check protocol prover side APIs.
57pub trait SumCheckProver<F: PrimeField>
58where
59 Self: Sized,
60{
61 type VirtualPolynomial;
62 type ProverMessage;
63
64 /// Initialize the prover state to argue for the sum of the input polynomial
65 /// over {0,1}^`num_vars`.
66 fn prover_init(polynomial: &Self::VirtualPolynomial) -> Result<Self, PolyIOPErrors>;
67
68 /// Receive message from verifier, generate prover message, and proceed to
69 /// next round.
70 ///
71 /// Main algorithm used is from section 3.2 of [XZZPS19](https://eprint.iacr.org/2019/317.pdf#subsection.3.2).
72 fn prove_round_and_update_state(
73 &mut self,
74 challenge: &Option<F>,
75 ) -> Result<Self::ProverMessage, PolyIOPErrors>;
76}
77
78/// Trait for sum check protocol verifier side APIs.
79pub trait SumCheckVerifier<F: PrimeField> {
80 type VPAuxInfo;
81 type ProverMessage;
82 type Challenge;
83 type Transcript;
84 type SumCheckSubClaim;
85
86 /// Initialize the verifier's state.
87 fn verifier_init(index_info: &Self::VPAuxInfo) -> Self;
88
89 /// Run verifier for the current round, given a prover message.
90 ///
91 /// Note that `verify_round_and_update_state` only samples and stores
92 /// challenges; and update the verifier's state accordingly. The actual
93 /// verifications are deferred (in batch) to `check_and_generate_subclaim`
94 /// at the last step.
95 fn verify_round_and_update_state(
96 &mut self,
97 prover_msg: &Self::ProverMessage,
98 transcript: &mut Self::Transcript,
99 ) -> Result<Self::Challenge, PolyIOPErrors>;
100
101 /// This function verifies the deferred checks in the interactive version of
102 /// the protocol; and generate the subclaim. Returns an error if the
103 /// proof failed to verify.
104 ///
105 /// If the asserted sum is correct, then the multilinear polynomial
106 /// evaluated at `subclaim.point` will be `subclaim.expected_evaluation`.
107 /// Otherwise, it is highly unlikely that those two will be equal.
108 /// Larger field size guarantees smaller soundness error.
109 fn check_and_generate_subclaim(
110 &self,
111 asserted_sum: &F,
112 ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors>;
113}
114
115/// A SumCheckSubClaim is a claim generated by the verifier at the end of
116/// verification when it is convinced.
117#[derive(Clone, Debug, Default, PartialEq, Eq)]
118pub struct SumCheckSubClaim<F: PrimeField> {
119 /// the multi-dimensional point that this multilinear extension is evaluated
120 /// to
121 pub point: Vec<F>,
122 /// the expected evaluation
123 pub expected_evaluation: F,
124}
125
126impl<F: PrimeField> SumCheck<F> for PolyIOP<F> {
127 type SumCheckProof = IOPProof<F>;
128 type VirtualPolynomial = VirtualPolynomial<F>;
129 type VPAuxInfo = VPAuxInfo<F>;
130 type MultilinearExtension = Rc<DenseMultilinearExtension<F>>;
131 type SumCheckSubClaim = SumCheckSubClaim<F>;
132 type Transcript = IOPTranscript<F>;
133
134 /// Extract sum from the proof
135 fn extract_sum(proof: &Self::SumCheckProof) -> F {
136 let start = start_timer!(|| "extract sum");
137 let res = proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1];
138 end_timer!(start);
139 res
140 }
141
142 /// Initialize the system with a transcript
143 ///
144 /// This function is optional -- in the case where a SumCheck is
145 /// an building block for a more complex protocol, the transcript
146 /// may be initialized by this complex protocol, and passed to the
147 /// SumCheck prover/verifier.
148 fn init_transcript() -> Self::Transcript {
149 let start = start_timer!(|| "init transcript");
150 let res = IOPTranscript::<F>::new(b"Initializing SumCheck transcript");
151 end_timer!(start);
152 res
153 }
154
155 /// Generate proof of the sum of polynomial over {0,1}^`num_vars`
156 ///
157 /// The polynomial is represented in the form of a VirtualPolynomial.
158 fn prove(
159 poly: &Self::VirtualPolynomial,
160 transcript: &mut Self::Transcript,
161 ) -> Result<Self::SumCheckProof, PolyIOPErrors> {
162 let start = start_timer!(|| "sum check prove");
163
164 transcript.append_serializable_element(b"aux info", &poly.aux_info)?;
165
166 let mut prover_state = IOPProverState::prover_init(poly)?;
167 let mut challenge = None;
168 let mut prover_msgs = Vec::with_capacity(poly.aux_info.num_variables);
169 for _ in 0..poly.aux_info.num_variables {
170 let prover_msg =
171 IOPProverState::prove_round_and_update_state(&mut prover_state, &challenge)?;
172 transcript.append_serializable_element(b"prover msg", &prover_msg)?;
173 prover_msgs.push(prover_msg);
174 challenge = Some(transcript.get_and_append_challenge(b"Internal round")?);
175 }
176 // pushing the last challenge point to the state
177 if let Some(p) = challenge {
178 prover_state.challenges.push(p)
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}