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