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(|(coeffs, 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}