hyperplonk/subroutines/src/poly_iop/sum_check/verifier.rs
subroutines/src/poly_iop/sum_check/verifier.rsRaw
1//! Verifier subroutines for a SumCheck protocol.
2
3use super::{SumCheckSubClaim, SumCheckVerifier};
4use crate::poly_iop::{
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.
181/// TODO: The quadratic term can be removed by precomputing the lagrange
182/// coefficients.
183fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> Result<F, PolyIOPErrors> {
184 let start = start_timer!(|| "sum check interpolate uni poly opt");
185
186 let len = p_i.len();
187 let mut evals = vec![];
188 let mut prod = eval_at;
189 evals.push(eval_at);
190
191 // `prod = \prod_{j} (eval_at - j)`
192 for e in 1..len {
193 let tmp = eval_at - F::from(e as u64);
194 evals.push(tmp);
195 prod *= tmp;
196 }
197 let mut res = F::zero();
198 // we want to compute \prod (j!=i) (i-j) for a given i
199 //
200 // we start from the last step, which is
201 // denom[len-1] = (len-1) * (len-2) *... * 2 * 1
202 // the step before that is
203 // denom[len-2] = (len-2) * (len-3) * ... * 2 * 1 * -1
204 // and the step before that is
205 // denom[len-3] = (len-3) * (len-4) * ... * 2 * 1 * -1 * -2
206 //
207 // i.e., for any i, the one before this will be derived from
208 // denom[i-1] = denom[i] * (len-i) / i
209 //
210 // that is, we only need to store
211 // - the last denom for i = len-1, and
212 // - the ratio between current step and fhe last step, which is the product of
213 // (len-i) / i from all previous steps and we store this product as a fraction
214 // number to reduce field divisions.
215
216 // We know
217 // - 2^61 < factorial(20) < 2^62
218 // - 2^122 < factorial(33) < 2^123
219 // so we will be able to compute the ratio
220 // - for len <= 20 with i64
221 // - for len <= 33 with i128
222 // - for len > 33 with BigInt
223 if p_i.len() <= 20 {
224 let last_denominator = F::from(u64_factorial(len - 1));
225 let mut ratio_numerator = 1i64;
226 let mut ratio_denominator = 1u64;
227
228 for i in (0..len).rev() {
229 let ratio_numerator_f = if ratio_numerator < 0 {
230 -F::from((-ratio_numerator) as u64)
231 } else {
232 F::from(ratio_numerator as u64)
233 };
234
235 res += p_i[i] * prod * F::from(ratio_denominator)
236 / (last_denominator * ratio_numerator_f * evals[i]);
237
238 // compute denom for the next step is current_denom * (len-i)/i
239 if i != 0 {
240 ratio_numerator *= -(len as i64 - i as i64);
241 ratio_denominator *= i as u64;
242 }
243 }
244 } else if p_i.len() <= 33 {
245 let last_denominator = F::from(u128_factorial(len - 1));
246 let mut ratio_numerator = 1i128;
247 let mut ratio_denominator = 1u128;
248
249 for i in (0..len).rev() {
250 let ratio_numerator_f = if ratio_numerator < 0 {
251 -F::from((-ratio_numerator) as u128)
252 } else {
253 F::from(ratio_numerator as u128)
254 };
255
256 res += p_i[i] * prod * F::from(ratio_denominator)
257 / (last_denominator * ratio_numerator_f * evals[i]);
258
259 // compute denom for the next step is current_denom * (len-i)/i
260 if i != 0 {
261 ratio_numerator *= -(len as i128 - i as i128);
262 ratio_denominator *= i as u128;
263 }
264 }
265 } else {
266 let mut denom_up = field_factorial::<F>(len - 1);
267 let mut denom_down = F::one();
268
269 for i in (0..len).rev() {
270 res += p_i[i] * prod * denom_down / (denom_up * evals[i]);
271
272 // compute denom for the next step is current_denom * (len-i)/i
273 if i != 0 {
274 denom_up *= -F::from((len - i) as u64);
275 denom_down *= F::from(i as u64);
276 }
277 }
278 }
279 end_timer!(start);
280 Ok(res)
281}
282
283/// compute the factorial(a) = 1 * 2 * ... * a
284#[inline]
285fn field_factorial<F: PrimeField>(a: usize) -> F {
286 let mut res = F::one();
287 for i in 2..=a {
288 res *= F::from(i as u64);
289 }
290 res
291}
292
293/// compute the factorial(a) = 1 * 2 * ... * a
294#[inline]
295fn u128_factorial(a: usize) -> u128 {
296 let mut res = 1u128;
297 for i in 2..=a {
298 res *= i as u128;
299 }
300 res
301}
302
303/// compute the factorial(a) = 1 * 2 * ... * a
304#[inline]
305fn u64_factorial(a: usize) -> u64 {
306 let mut res = 1u64;
307 for i in 2..=a {
308 res *= i as u64;
309 }
310 res
311}
312
313#[cfg(test)]
314mod test {
315 use super::interpolate_uni_poly;
316 use crate::poly_iop::errors::PolyIOPErrors;
317 use ark_bls12_381::Fr;
318 use ark_poly::{univariate::DensePolynomial, Polynomial, UVPolynomial};
319 use ark_std::{vec::Vec, UniformRand};
320
321 #[test]
322 fn test_interpolation() -> Result<(), PolyIOPErrors> {
323 let mut prng = ark_std::test_rng();
324
325 // test a polynomial with 20 known points, i.e., with degree 19
326 let poly = DensePolynomial::<Fr>::rand(20 - 1, &mut prng);
327 let evals = (0..20)
328 .map(|i| poly.evaluate(&Fr::from(i)))
329 .collect::<Vec<Fr>>();
330 let query = Fr::rand(&mut prng);
331
332 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
333
334 // test a polynomial with 33 known points, i.e., with degree 32
335 let poly = DensePolynomial::<Fr>::rand(33 - 1, &mut prng);
336 let evals = (0..33)
337 .map(|i| poly.evaluate(&Fr::from(i)))
338 .collect::<Vec<Fr>>();
339 let query = Fr::rand(&mut prng);
340
341 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
342
343 // test a polynomial with 64 known points, i.e., with degree 63
344 let poly = DensePolynomial::<Fr>::rand(64 - 1, &mut prng);
345 let evals = (0..64)
346 .map(|i| poly.evaluate(&Fr::from(i)))
347 .collect::<Vec<Fr>>();
348 let query = Fr::rand(&mut prng);
349
350 assert_eq!(poly.evaluate(&query), interpolate_uni_poly(&evals, query)?);
351
352 Ok(())
353 }
354}