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