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