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