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_poly::Polynomial;
20use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial};
21use ark_std::{end_timer, start_timer};
22use espresso_subroutines::poly_iop::prelude::PolyIOPErrors;
23
24#[cfg(feature = "parallel")]
25use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator};
26
27impl<C: CurveGroup> SumCheckVerifier<C> for IOPVerifierState<C> {
28 type VPAuxInfo = VPAuxInfo<C::ScalarField>;
29 type ProverMessage = IOPProverMessage<C::ScalarField>;
30 type Challenge = C::ScalarField;
31 type SumCheckSubClaim = SumCheckSubClaim<C::ScalarField>;
32
33 /// Initialize the verifier's state.
34 fn verifier_init(index_info: &Self::VPAuxInfo) -> Self {
35 let start = start_timer!(|| "sum check verifier init");
36 let res = Self {
37 round: 1,
38 num_vars: index_info.num_variables,
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.push(prover_msg.coeffs.to_vec());
71
72 if self.round == self.num_vars {
73 // accept and close
74 self.finished = true;
75 } else {
76 // proceed to the next round
77 self.round += 1;
78 }
79
80 end_timer!(start);
81 Ok(challenge)
82 }
83
84 fn check_and_generate_subclaim(
85 &self,
86 asserted_sum: &C::ScalarField,
87 ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors> {
88 let start = start_timer!(|| "sum check check and generate subclaim");
89 if !self.finished {
90 return Err(PolyIOPErrors::InvalidVerifier(
91 "Incorrect verifier state: Verifier has not finished.".to_string(),
92 ));
93 }
94
95 if self.polynomials_received.len() != self.num_vars {
96 return Err(PolyIOPErrors::InvalidVerifier(
97 "insufficient rounds".to_string(),
98 ));
99 }
100
101 // the deferred check during the interactive phase:
102 // 2. set `expected` to P(r)`
103 #[cfg(feature = "parallel")]
104 let mut expected_vec = self
105 .polynomials_received
106 .clone()
107 .into_par_iter()
108 .zip(self.challenges.clone().into_par_iter())
109 .map(|(coeffs, challenge)| {
110 // Removed check on number of evaluations here since verifier receives polynomial in coeffs form
111 let prover_poly = DensePolynomial::from_coefficients_slice(&coeffs);
112 Ok(prover_poly.evaluate(&challenge))
113 })
114 .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
115
116 #[cfg(not(feature = "parallel"))]
117 let mut expected_vec = self
118 .polynomials_received
119 .clone()
120 .into_iter()
121 .zip(self.challenges.clone().into_iter())
122 .map(|(evaluations, challenge)| {
123 // Removed check on number of evaluations here since verifier receives polynomial in coeffs form
124 let prover_poly = DensePolynomial::from_coefficients_slice(&coeffs);
125 Ok(prover_poly.evaluate(&challenge))
126 })
127 .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
128
129 // insert the asserted_sum to the first position of the expected vector
130 expected_vec.insert(0, *asserted_sum);
131
132 for (coeffs, &expected) in self
133 .polynomials_received
134 .iter()
135 .zip(expected_vec.iter())
136 .take(self.num_vars)
137 {
138 let poly = DensePolynomial::from_coefficients_slice(coeffs);
139 let eval_at_one: C::ScalarField = poly.iter().sum();
140 let eval_at_zero: C::ScalarField = poly.coeffs[0];
141 let eval = eval_at_one + eval_at_zero;
142
143 println!("evaluations: {:?}, expected: {:?}", eval, expected);
144 // the deferred check during the interactive phase:
145 // 1. check if the received 'P(0) + P(1) = expected`.
146 if eval != expected {
147 return Err(PolyIOPErrors::InvalidProof(
148 "Prover message is not consistent with the claim.".to_string(),
149 ));
150 }
151 }
152 end_timer!(start);
153 Ok(SumCheckSubClaim {
154 point: self.challenges.clone(),
155 // the last expected value (not checked within this function) will be included in the
156 // subclaim
157 expected_evaluation: expected_vec[self.num_vars],
158 })
159 }
160}
161
162/// Interpolate a uni-variate degree-`p_i.len()-1` polynomial and evaluate this
163/// polynomial at `eval_at`:
164///
165/// \sum_{i=0}^len p_i * (\prod_{j!=i} (eval_at - j)/(i-j) )
166///
167/// This implementation is linear in number of inputs in terms of field
168/// operations. It also has a quadratic term in primitive operations which is
169/// negligible compared to field operations.
170/// TODO: The quadratic term can be removed by precomputing the lagrange
171/// coefficients.
172pub fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> Result<F, PolyIOPErrors> {
173 let start = start_timer!(|| "sum check interpolate uni poly opt");
174
175 let len = p_i.len();
176 let mut evals = vec![];
177 let mut prod = eval_at;
178 evals.push(eval_at);
179
180 // `prod = \prod_{j} (eval_at - j)`
181 for e in 1..len {
182 let tmp = eval_at - F::from(e as u64);
183 evals.push(tmp);
184 prod *= tmp;
185 }
186 let mut res = F::zero();
187 // we want to compute \prod (j!=i) (i-j) for a given i
188 //
189 // we start from the last step, which is
190 // denom[len-1] = (len-1) * (len-2) *... * 2 * 1
191 // the step before that is
192 // denom[len-2] = (len-2) * (len-3) * ... * 2 * 1 * -1
193 // and the step before that is
194 // denom[len-3] = (len-3) * (len-4) * ... * 2 * 1 * -1 * -2
195 //
196 // i.e., for any i, the one before this will be derived from
197 // denom[i-1] = denom[i] * (len-i) / i
198 //
199 // that is, we only need to store
200 // - the last denom for i = len-1, and
201 // - the ratio between current step and fhe last step, which is the product of
202 // (len-i) / i from all previous steps and we store this product as a fraction
203 // number to reduce field divisions.
204
205 // We know
206 // - 2^61 < factorial(20) < 2^62
207 // - 2^122 < factorial(33) < 2^123
208 // so we will be able to compute the ratio
209 // - for len <= 20 with i64
210 // - for len <= 33 with i128
211 // - for len > 33 with BigInt
212 if p_i.len() <= 20 {
213 let last_denominator = F::from(u64_factorial(len - 1));
214 let mut ratio_numerator = 1i64;
215 let mut ratio_denominator = 1u64;
216
217 for i in (0..len).rev() {
218 let ratio_numerator_f = if ratio_numerator < 0 {
219 -F::from((-ratio_numerator) as u64)
220 } else {
221 F::from(ratio_numerator as u64)
222 };
223
224 res += p_i[i] * prod * F::from(ratio_denominator)
225 / (last_denominator * ratio_numerator_f * evals[i]);
226
227 // compute denom for the next step is current_denom * (len-i)/i
228 if i != 0 {
229 ratio_numerator *= -(len as i64 - i as i64);
230 ratio_denominator *= i as u64;
231 }
232 }
233 } else if p_i.len() <= 33 {
234 let last_denominator = F::from(u128_factorial(len - 1));
235 let mut ratio_numerator = 1i128;
236 let mut ratio_denominator = 1u128;
237
238 for i in (0..len).rev() {
239 let ratio_numerator_f = if ratio_numerator < 0 {
240 -F::from((-ratio_numerator) as u128)
241 } else {
242 F::from(ratio_numerator as u128)
243 };
244
245 res += p_i[i] * prod * F::from(ratio_denominator)
246 / (last_denominator * ratio_numerator_f * evals[i]);
247
248 // compute denom for the next step is current_denom * (len-i)/i
249 if i != 0 {
250 ratio_numerator *= -(len as i128 - i as i128);
251 ratio_denominator *= i as u128;
252 }
253 }
254 } else {
255 let mut denom_up = field_factorial::<F>(len - 1);
256 let mut denom_down = F::one();
257
258 for i in (0..len).rev() {
259 res += p_i[i] * prod * denom_down / (denom_up * evals[i]);
260
261 // compute denom for the next step is current_denom * (len-i)/i
262 if i != 0 {
263 denom_up *= -F::from((len - i) as u64);
264 denom_down *= F::from(i as u64);
265 }
266 }
267 }
268 end_timer!(start);
269 Ok(res)
270}
271
272/// compute the factorial(a) = 1 * 2 * ... * a
273#[inline]
274fn field_factorial<F: PrimeField>(a: usize) -> F {
275 let mut res = F::one();
276 for i in 2..=a {
277 res *= F::from(i as u64);
278 }
279 res
280}
281
282/// compute the factorial(a) = 1 * 2 * ... * a
283#[inline]
284fn u128_factorial(a: usize) -> u128 {
285 let mut res = 1u128;
286 for i in 2..=a {
287 res *= i as u128;
288 }
289 res
290}
291
292/// compute the factorial(a) = 1 * 2 * ... * a
293#[inline]
294fn u64_factorial(a: usize) -> u64 {
295 let mut res = 1u64;
296 for i in 2..=a {
297 res *= i as u64;
298 }
299 res
300}