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