1//! Verifier subroutines for a SumCheck protocol.
  2
  3use super::SumCheckVerifier;
  4use crate::{
  5    errors::PolyIOPErrors,
  6    structs::{IOPProverMessage, IOPVerifierState, SubClaim},
  7    transcript::IOPTranscript,
  8    virtual_poly::VPAuxInfo,
  9};
 10use ark_ff::PrimeField;
 11use ark_std::{end_timer, start_timer};
 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 SubClaim = SubClaim<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::SubClaim, 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(SubClaim {
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.
181fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> Result<F, PolyIOPErrors> {
182    let start = start_timer!(|| "sum check interpolate uni poly opt");
183
184    let mut res = F::zero();
185
186    // compute
187    //  - prod = \prod (eval_at - j)
188    //  - evals = [eval_at - j]
189    let mut evals = vec![];
190    let len = p_i.len();
191    let mut prod = eval_at;
192    evals.push(eval_at);
193
194    for e in 1..len {
195        let tmp = eval_at - F::from(e as u64);
196        evals.push(tmp);
197        prod *= tmp;
198    }
199
200    for i in 0..len {
201        // res += p_i * prod / (divisor * (eval_at - j))
202        let divisor = get_divisor(i, len)?;
203        let divisor_f = {
204            if divisor < 0 {
205                -F::from((-divisor) as u128)
206            } else {
207                F::from(divisor as u128)
208            }
209        };
210        res += p_i[i] * prod / (divisor_f * evals[i]);
211    }
212
213    end_timer!(start);
214    Ok(res)
215}
216
217/// Compute \prod_{j!=i)^len (i-j). This function takes O(n^2) number of
218/// primitive operations which is negligible compared to field operations.
219// We know
220//  - factorial(20) ~ 2^61
221//  - factorial(33) ~ 2^123
222// so we will be able to store the result for len<=20 with i64;
223// for len<=33 with i128; and we do not currently support len>33.
224#[inline]
225fn get_divisor(i: usize, len: usize) -> Result<i128, PolyIOPErrors> {
226    if len <= 20 {
227        let mut res = 1i64;
228        for j in 0..len {
229            if j != i {
230                res *= i as i64 - j as i64;
231            }
232        }
233        Ok(res as i128)
234    } else if len <= 33 {
235        let mut res = 1i128;
236        for j in 0..len {
237            if j != i {
238                res *= i as i128 - j as i128;
239            }
240        }
241        Ok(res)
242    } else {
243        Err(PolyIOPErrors::InvalidParameters(
244            "Do not support number variable > 33".to_string(),
245        ))
246    }
247}