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 // the deferred check during the interactive phase:
109 // 2. set `expected` to P(r)`
110 #[cfg(feature = "parallel")]
111 let mut expected_vec = self
112 .polynomials_received
113 .clone()
114 .into_par_iter()
115 .zip(self.challenges.clone().into_par_iter())
116 .map(|(evaluations, challenge)| {
117 if evaluations.len() != self.max_degree + 1 {
118 return Err(PolyIOPErrors::InvalidVerifier(format!(
119 "incorrect number of evaluations: {} vs {}",
120 evaluations.len(),
121 self.max_degree + 1
122 )));
123 }
124 interpolate_uni_poly::<F>(&evaluations, challenge)
125 })
126 .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
127
128 #[cfg(not(feature = "parallel"))]
129 let mut expected_vec = self
130 .polynomials_received
131 .clone()
132 .into_iter()
133 .zip(self.challenges.clone().into_iter())
134 .map(|(evaluations, challenge)| {
135 if evaluations.len() != self.max_degree + 1 {
136 return Err(PolyIOPErrors::InvalidVerifier(format!(
137 "incorrect number of evaluations: {} vs {}",
138 evaluations.len(),
139 self.max_degree + 1
140 )));
141 }
142 interpolate_uni_poly::<F>(&evaluations, challenge)
143 })
144 .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
145
146 // insert the asserted_sum to the first position of the expected vector
147 expected_vec.insert(0, *asserted_sum);
148
149 for (evaluations, &expected) in self
150 .polynomials_received
151 .iter()
152 .zip(expected_vec.iter())
153 .take(self.num_vars)
154 {
155 // the deferred check during the interactive phase:
156 // 1. check if the received 'P(0) + P(1) = expected`.
157 if evaluations[0] + evaluations[1] != expected {
158 return Err(PolyIOPErrors::InvalidProof(
159 "Prover message is not consistent with the claim.".to_string(),
160 ));
161 }
162 }
163 end_timer!(start);
164 Ok(SumCheckSubClaim {
165 point: self.challenges.clone(),
166 // the last expected value (not checked within this function) will be included in the
167 // subclaim
168 expected_evaluation: expected_vec[self.num_vars],
169 })
170 }
171}
172
173/// Interpolate a uni-variate degree-`p_i.len()-1` polynomial and evaluate this
174/// polynomial at `eval_at`:
175///
176/// \sum_{i=0}^len p_i * (\prod_{j!=i} (eval_at - j)/(i-j) )
177///
178/// This implementation is linear in number of inputs in terms of field
179/// operations. It also has a quadratic term in primitive operations which is
180/// negligible compared to field operations.
181fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> Result<F, PolyIOPErrors> {
182 let start = start_timer!(|| "sum check interpolate uni poly opt");
183
184 let len = p_i.len();
185 let mut evals = vec![];
186 let mut prod = eval_at;
187 evals.push(eval_at);
188
189 // `prod = \prod_{j} (eval_at - j)`
190 for e in 1..len {
191 let tmp = eval_at - F::from(e as u64);
192 evals.push(tmp);
193 prod *= tmp;
194 }
195 let mut res = F::zero();
196 // we want to compute \prod (j!=i) (i-j) for a given i
197 //
198 // we start from the last step, which is
199 // denom[len-1] = (len-1) * (len-2) *... * 2 * 1
200 // the step before that is
201 // denom[len-2] = (len-2) * (len-3) * ... * 2 * 1 * -1
202 // and the step before that is
203 // denom[len-3] = (len-3) * (len-4) * ... * 2 * 1 * -1 * -2
204 //
205 // i.e., for any i, the one before this will be derived from
206 // denom[i-1] = denom[i] * (len-i) / i
207 //
208 // that is, we only need to store
209 // - the last denom for i = len-1, and
210 // - the ratio between current step and fhe last step, which is the product of
211 // (len-i) / i from all previous steps and we store this product as a fraction
212 // number to reduce field divisions.
213
214 // We know
215 // - 2^61 < factorial(20) < 2^62
216 // - 2^122 < factorial(33) < 2^123
217 // so we will be able to compute the ratio
218 // - for len <= 20 with i64
219 // - for len <= 33 with i128
220 // - for len > 33 with BigInt
221 if p_i.len() <= 20 {
222 let last_denominator = F::from(u64_factorial(len - 1));
223 let mut ratio_numerator = 1i64;
224 let mut ratio_denominator = 1u64;
225
226 for i in (0..len).rev() {
227 let ratio_numerator_f = if ratio_numerator < 0 {
228 -F::from((-ratio_numerator) as u64)
229 } else {
230 F::from(ratio_numerator as u64)
231 };
232
233 res += p_i[i] * prod * F::from(ratio_denominator)
234 / (last_denominator * ratio_numerator_f * evals[i]);
235
236 // compute denom for the next step is current_denom * (len-i)/i
237 if i != 0 {
238 ratio_numerator *= -(len as i64 - i as i64);
239 ratio_denominator *= i as u64;
240 }
241 }
242 } else if p_i.len() <= 33 {
243 let last_denominator = F::from(u128_factorial(len - 1));
244 let mut ratio_numerator = 1i128;
245 let mut ratio_denominator = 1u128;
246
247 for i in (0..len).rev() {
248 let ratio_numerator_f = if ratio_numerator < 0 {
249 -F::from((-ratio_numerator) as u128)
250 } else {
251 F::from(ratio_numerator as u128)
252 };
253
254 res += p_i[i] * prod * F::from(ratio_denominator)
255 / (last_denominator * ratio_numerator_f * evals[i]);
256
257 // compute denom for the next step is current_denom * (len-i)/i
258 if i != 0 {
259 ratio_numerator *= -(len as i128 - i as i128);
260 ratio_denominator *= i as u128;
261 }
262 }
263 } else {
264 let mut denom_up = field_factorial::<F>(len - 1);
265 let mut denom_down = F::one();
266
267 for i in (0..len).rev() {
268 res += p_i[i] * prod * denom_down / (denom_up * evals[i]);
269
270 // compute denom for the next step is current_denom * (len-i)/i
271 if i != 0 {
272 denom_up *= -F::from((len - i) as u64);
273 denom_down *= F::from(i as u64);
274 }
275 }
276 }
277 end_timer!(start);
278 Ok(res)
279}
280
281/// compute the factorial(a) = 1 * 2 * ... * a
282#[inline]
283fn field_factorial<F: PrimeField>(a: usize) -> F {
284 let mut res = F::one();
285 for i in 2..=a {
286 res *= F::from(i as u64);
287 }
288 res
289}
290
291/// compute the factorial(a) = 1 * 2 * ... * a
292#[inline]
293fn u128_factorial(a: usize) -> u128 {
294 let mut res = 1u128;
295 for i in 2..=a {
296 res *= i as u128;
297 }
298 res
299}
300
301/// compute the factorial(a) = 1 * 2 * ... * a
302#[inline]
303fn u64_factorial(a: usize) -> u64 {
304 let mut res = 1u64;
305 for i in 2..=a {
306 res *= i as u64;
307 }
308 res
309}
310
311#[cfg(test)]
312mod test {
313 use super::interpolate_uni_poly;
314 use crate::errors::PolyIOPErrors;
315 use ark_bls12_381::Fr;
316 use ark_poly::{univariate::DensePolynomial, Polynomial, UVPolynomial};
317 use ark_std::{vec::Vec, UniformRand};
318
319 #[test]
320 fn test_interpolation() -> Result<(), PolyIOPErrors> {
321 let mut prng = ark_std::test_rng();
322
323 // test a polynomial with 20 known points, i.e., with degree 19
324 let poly = DensePolynomial::<Fr>::rand(20 - 1, &mut prng);
325 let evals = (0..20)
326 .map(|i| poly.evaluate(&Fr::from(i)))
327 .collect::<Vec<Fr>>();
328 let query = Fr::rand(&mut prng);
329
330 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
331
332 // test a polynomial with 33 known points, i.e., with degree 32
333 let poly = DensePolynomial::<Fr>::rand(33 - 1, &mut prng);
334 let evals = (0..33)
335 .map(|i| poly.evaluate(&Fr::from(i)))
336 .collect::<Vec<Fr>>();
337 let query = Fr::rand(&mut prng);
338
339 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
340
341 // test a polynomial with 64 known points, i.e., with degree 63
342 let poly = DensePolynomial::<Fr>::rand(64 - 1, &mut prng);
343 let evals = (0..64)
344 .map(|i| poly.evaluate(&Fr::from(i)))
345 .collect::<Vec<Fr>>();
346 let query = Fr::rand(&mut prng);
347
348 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
349
350 Ok(())
351 }
352}