hyperplonk/poly-iop/src/sum_check/verifier.rs
poly-iop/src/sum_check/verifier.rsRaw
1//! Verifier subroutines for a SumCheck protocol.
2
3use super::{SumCheckSubClaim, SumCheckVerifier};
4use crate::{
5 errors::PolyIOPErrors,
6 structs::{IOPProverMessage, IOPVerifierState},
7};
8use arithmetic::VPAuxInfo;
9use ark_ff::PrimeField;
10use ark_std::{end_timer, start_timer};
11use transcript::IOPTranscript;
12
13#[cfg(feature = "parallel")]
14use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator};
15
16impl<F: PrimeField> SumCheckVerifier<F> for IOPVerifierState<F> {
17 type VPAuxInfo = VPAuxInfo<F>;
18 type ProverMessage = IOPProverMessage<F>;
19 type Challenge = F;
20 type Transcript = IOPTranscript<F>;
21 type SumCheckSubClaim = SumCheckSubClaim<F>;
22
23 /// Initialize the verifier's state.
24 fn verifier_init(index_info: &Self::VPAuxInfo) -> Self {
25 let start = start_timer!(|| "sum check verifier init");
26 let res = Self {
27 round: 1,
28 num_vars: index_info.num_variables,
29 max_degree: index_info.max_degree,
30 finished: false,
31 polynomials_received: Vec::with_capacity(index_info.num_variables),
32 challenges: Vec::with_capacity(index_info.num_variables),
33 };
34 end_timer!(start);
35 res
36 }
37
38 /// Run verifier for the current round, given a prover message.
39 ///
40 /// Note that `verify_round_and_update_state` only samples and stores
41 /// challenges; and update the verifier's state accordingly. The actual
42 /// verifications are deferred (in batch) to `check_and_generate_subclaim`
43 /// at the last step.
44 fn verify_round_and_update_state(
45 &mut self,
46 prover_msg: &Self::ProverMessage,
47 transcript: &mut Self::Transcript,
48 ) -> Result<Self::Challenge, PolyIOPErrors> {
49 let start =
50 start_timer!(|| format!("sum check verify {}-th round and update state", self.round));
51
52 if self.finished {
53 return Err(PolyIOPErrors::InvalidVerifier(
54 "Incorrect verifier state: Verifier is already finished.".to_string(),
55 ));
56 }
57
58 // In an interactive protocol, the verifier should
59 //
60 // 1. check if the received 'P(0) + P(1) = expected`.
61 // 2. set `expected` to P(r)`
62 //
63 // When we turn the protocol to a non-interactive one, it is sufficient to defer
64 // such checks to `check_and_generate_subclaim` after the last round.
65
66 let challenge = transcript.get_and_append_challenge(b"Internal round")?;
67 self.challenges.push(challenge);
68 self.polynomials_received
69 .push(prover_msg.evaluations.to_vec());
70
71 if self.round == self.num_vars {
72 // accept and close
73 self.finished = true;
74 } else {
75 // proceed to the next round
76 self.round += 1;
77 }
78
79 end_timer!(start);
80 Ok(challenge)
81 }
82
83 /// This function verifies the deferred checks in the interactive version of
84 /// the protocol; and generate the subclaim. Returns an error if the
85 /// proof failed to verify.
86 ///
87 /// If the asserted sum is correct, then the multilinear polynomial
88 /// evaluated at `subclaim.point` will be `subclaim.expected_evaluation`.
89 /// Otherwise, it is highly unlikely that those two will be equal.
90 /// Larger field size guarantees smaller soundness error.
91 fn check_and_generate_subclaim(
92 &self,
93 asserted_sum: &F,
94 ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors> {
95 let start = start_timer!(|| "sum check check and generate subclaim");
96 if !self.finished {
97 return Err(PolyIOPErrors::InvalidVerifier(
98 "Incorrect verifier state: Verifier has not finished.".to_string(),
99 ));
100 }
101
102 if self.polynomials_received.len() != self.num_vars {
103 return Err(PolyIOPErrors::InvalidVerifier(
104 "insufficient rounds".to_string(),
105 ));
106 }
107
108 println!(
109 "eval len {} max degree {}",
110 self.polynomials_received[0].len(),
111 self.max_degree + 1
112 );
113
114 // the deferred check during the interactive phase:
115 // 2. set `expected` to P(r)`
116 #[cfg(feature = "parallel")]
117 let mut expected_vec = self
118 .polynomials_received
119 .clone()
120 .into_par_iter()
121 .zip(self.challenges.clone().into_par_iter())
122 .map(|(evaluations, challenge)| {
123 if evaluations.len() != self.max_degree + 1 {
124 return Err(PolyIOPErrors::InvalidVerifier(format!(
125 "incorrect number of evaluations: {} vs {}",
126 evaluations.len(),
127 self.max_degree + 1
128 )));
129 }
130 interpolate_uni_poly::<F>(&evaluations, challenge)
131 })
132 .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
133
134 #[cfg(not(feature = "parallel"))]
135 let mut expected_vec = self
136 .polynomials_received
137 .clone()
138 .into_iter()
139 .zip(self.challenges.clone().into_iter())
140 .map(|(evaluations, challenge)| {
141 if evaluations.len() != self.max_degree + 1 {
142 return Err(PolyIOPErrors::InvalidVerifier(format!(
143 "incorrect number of evaluations: {} vs {}",
144 evaluations.len(),
145 self.max_degree + 1
146 )));
147 }
148 interpolate_uni_poly::<F>(&evaluations, challenge)
149 })
150 .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
151
152 // insert the asserted_sum to the first position of the expected vector
153 expected_vec.insert(0, *asserted_sum);
154
155 for (evaluations, &expected) in self
156 .polynomials_received
157 .iter()
158 .zip(expected_vec.iter())
159 .take(self.num_vars)
160 {
161 // the deferred check during the interactive phase:
162 // 1. check if the received 'P(0) + P(1) = expected`.
163 if evaluations[0] + evaluations[1] != expected {
164 return Err(PolyIOPErrors::InvalidProof(
165 "Prover message is not consistent with the claim.".to_string(),
166 ));
167 }
168 }
169 end_timer!(start);
170 Ok(SumCheckSubClaim {
171 point: self.challenges.clone(),
172 // the last expected value (not checked within this function) will be included in the
173 // subclaim
174 expected_evaluation: expected_vec[self.num_vars],
175 })
176 }
177}
178
179/// Interpolate a uni-variate degree-`p_i.len()-1` polynomial and evaluate this
180/// polynomial at `eval_at`:
181///
182/// \sum_{i=0}^len p_i * (\prod_{j!=i} (eval_at - j)/(i-j) )
183///
184/// This implementation is linear in number of inputs in terms of field
185/// operations. It also has a quadratic term in primitive operations which is
186/// negligible compared to field operations.
187fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> Result<F, PolyIOPErrors> {
188 let start = start_timer!(|| "sum check interpolate uni poly opt");
189
190 let len = p_i.len();
191 let mut evals = vec![];
192 let mut prod = eval_at;
193 evals.push(eval_at);
194
195 // `prod = \prod_{j} (eval_at - j)`
196 for e in 1..len {
197 let tmp = eval_at - F::from(e as u64);
198 evals.push(tmp);
199 prod *= tmp;
200 }
201 let mut res = F::zero();
202 // we want to compute \prod (j!=i) (i-j) for a given i
203 //
204 // we start from the last step, which is
205 // denom[len-1] = (len-1) * (len-2) *... * 2 * 1
206 // the step before that is
207 // denom[len-2] = (len-2) * (len-3) * ... * 2 * 1 * -1
208 // and the step before that is
209 // denom[len-3] = (len-3) * (len-4) * ... * 2 * 1 * -1 * -2
210 //
211 // i.e., for any i, the one before this will be derived from
212 // denom[i-1] = denom[i] * (len-i) / i
213 //
214 // that is, we only need to store
215 // - the last denom for i = len-1, and
216 // - the ratio between current step and fhe last step, which is the product of
217 // (len-i) / i from all previous steps and we store this product as a fraction
218 // number to reduce field divisions.
219
220 // We know
221 // - 2^61 < factorial(20) < 2^62
222 // - 2^122 < factorial(33) < 2^123
223 // so we will be able to compute the ratio
224 // - for len <= 20 with i64
225 // - for len <= 33 with i128
226 // - for len > 33 with BigInt
227 if p_i.len() <= 20 {
228 let last_denominator = F::from(u64_factorial(len - 1));
229 let mut ratio_numerator = 1i64;
230 let mut ratio_denominator = 1u64;
231
232 for i in (0..len).rev() {
233 let ratio_numerator_f = if ratio_numerator < 0 {
234 -F::from((-ratio_numerator) as u64)
235 } else {
236 F::from(ratio_numerator as u64)
237 };
238
239 res += p_i[i] * prod * F::from(ratio_denominator)
240 / (last_denominator * ratio_numerator_f * evals[i]);
241
242 // compute denom for the next step is current_denom * (len-i)/i
243 if i != 0 {
244 ratio_numerator *= -(len as i64 - i as i64);
245 ratio_denominator *= i as u64;
246 }
247 }
248 } else if p_i.len() <= 33 {
249 let last_denominator = F::from(u128_factorial(len - 1));
250 let mut ratio_numerator = 1i128;
251 let mut ratio_denominator = 1u128;
252
253 for i in (0..len).rev() {
254 let ratio_numerator_f = if ratio_numerator < 0 {
255 -F::from((-ratio_numerator) as u128)
256 } else {
257 F::from(ratio_numerator as u128)
258 };
259
260 res += p_i[i] * prod * F::from(ratio_denominator)
261 / (last_denominator * ratio_numerator_f * evals[i]);
262
263 // compute denom for the next step is current_denom * (len-i)/i
264 if i != 0 {
265 ratio_numerator *= -(len as i128 - i as i128);
266 ratio_denominator *= i as u128;
267 }
268 }
269 } else {
270 let mut denom_up = field_factorial::<F>(len - 1);
271 let mut denom_down = F::one();
272
273 for i in (0..len).rev() {
274 res += p_i[i] * prod * denom_down / (denom_up * evals[i]);
275
276 // compute denom for the next step is current_denom * (len-i)/i
277 if i != 0 {
278 denom_up *= -F::from((len - i) as u64);
279 denom_down *= F::from(i as u64);
280 }
281 }
282 }
283 end_timer!(start);
284 Ok(res)
285}
286
287/// compute the factorial(a) = 1 * 2 * ... * a
288#[inline]
289fn field_factorial<F: PrimeField>(a: usize) -> F {
290 let mut res = F::one();
291 for i in 2..=a {
292 res *= F::from(i as u64);
293 }
294 res
295}
296
297/// compute the factorial(a) = 1 * 2 * ... * a
298#[inline]
299fn u128_factorial(a: usize) -> u128 {
300 let mut res = 1u128;
301 for i in 2..=a {
302 res *= i as u128;
303 }
304 res
305}
306
307/// compute the factorial(a) = 1 * 2 * ... * a
308#[inline]
309fn u64_factorial(a: usize) -> u64 {
310 let mut res = 1u64;
311 for i in 2..=a {
312 res *= i as u64;
313 }
314 res
315}
316
317#[cfg(test)]
318mod test {
319 use super::interpolate_uni_poly;
320 use crate::errors::PolyIOPErrors;
321 use ark_bls12_381::Fr;
322 use ark_poly::{univariate::DensePolynomial, Polynomial, UVPolynomial};
323 use ark_std::{vec::Vec, UniformRand};
324
325 #[test]
326 fn test_interpolation() -> Result<(), PolyIOPErrors> {
327 let mut prng = ark_std::test_rng();
328
329 // test a polynomial with 20 known points, i.e., with degree 19
330 let poly = DensePolynomial::<Fr>::rand(20 - 1, &mut prng);
331 let evals = (0..20)
332 .map(|i| poly.evaluate(&Fr::from(i)))
333 .collect::<Vec<Fr>>();
334 let query = Fr::rand(&mut prng);
335
336 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
337
338 // test a polynomial with 33 known points, i.e., with degree 32
339 let poly = DensePolynomial::<Fr>::rand(33 - 1, &mut prng);
340 let evals = (0..33)
341 .map(|i| poly.evaluate(&Fr::from(i)))
342 .collect::<Vec<Fr>>();
343 let query = Fr::rand(&mut prng);
344
345 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
346
347 // test a polynomial with 64 known points, i.e., with degree 63
348 let poly = DensePolynomial::<Fr>::rand(64 - 1, &mut prng);
349 let evals = (0..64)
350 .map(|i| poly.evaluate(&Fr::from(i)))
351 .collect::<Vec<Fr>>();
352 let query = Fr::rand(&mut prng);
353
354 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
355
356 Ok(())
357 }
358}