1// TODO: some of the struct is generic for Sum Checks and Zero Checks.
  2// If so move them to src/structs.rs
  3
  4use super::SumCheckVerifier;
  5use crate::{
  6    errors::PolyIOPErrors,
  7    structs::{DomainInfo, IOPProverMessage, IOPVerifierState, SubClaim},
  8    transcript::IOPTranscript,
  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 DomainInfo = DomainInfo<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
 24    fn verifier_init(index_info: &Self::DomainInfo) -> 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 at current round, given prover message
 39    ///
 40    /// Normally, this function should perform actual verification. Instead,
 41    /// `verify_round` only samples and stores randomness and perform
 42    /// verifications altogether in `check_and_generate_subclaim` at
 43    /// 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        // Now, verifier should check if the received P(0) + P(1) = expected. The check
 59        // is moved to `check_and_generate_subclaim`, and will be done after the
 60        // last round.
 61
 62        let challenge = transcript.get_and_append_challenge(b"Internal round")?;
 63        self.challenges.push(challenge);
 64        self.polynomials_received
 65            .push(prover_msg.evaluations.to_vec());
 66
 67        // Now, verifier should set `expected` to P(r).
 68        // This operation is also moved to `check_and_generate_subclaim`,
 69        // and will be done after the last round.
 70
 71        if self.round == self.num_vars {
 72            // accept and close
 73            self.finished = true;
 74        } else {
 75            self.round += 1;
 76        }
 77
 78        end_timer!(start);
 79        Ok(challenge)
 80    }
 81
 82    /// verify the sumcheck phase, and generate the subclaim
 83    ///
 84    /// If the asserted sum is correct, then the multilinear polynomial
 85    /// evaluated at `subclaim.point` is `subclaim.expected_evaluation`.
 86    /// Otherwise, it is highly unlikely that those two will be equal.
 87    /// Larger field size guarantees smaller soundness error.
 88    fn check_and_generate_subclaim(
 89        &self,
 90        asserted_sum: &F,
 91    ) -> Result<Self::SubClaim, PolyIOPErrors> {
 92        let start = start_timer!(|| "sum check check and generate subclaim");
 93        if !self.finished {
 94            return Err(PolyIOPErrors::InvalidVerifier(
 95                "Incorrect verifier state: Verifier has not finished.".to_string(),
 96            ));
 97        }
 98
 99        if self.polynomials_received.len() != self.num_vars {
100            return Err(PolyIOPErrors::InvalidVerifier(
101                "insufficient rounds".to_string(),
102            ));
103        }
104
105        #[cfg(feature = "parallel")]
106        let mut expected_vec = self
107            .polynomials_received
108            .clone()
109            .into_par_iter()
110            .zip(self.challenges.clone().into_par_iter())
111            .map(|(evaluations, challenge)| {
112                if evaluations.len() != self.max_degree + 1 {
113                    return Err(PolyIOPErrors::InvalidVerifier(format!(
114                        "incorrect number of evaluations: {} vs {}",
115                        evaluations.len(),
116                        self.max_degree + 1
117                    )));
118                }
119                Ok(interpolate_uni_poly::<F>(&evaluations, challenge))
120            })
121            .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
122
123        #[cfg(not(feature = "parallel"))]
124        let mut expected_vec = self
125            .polynomials_received
126            .clone()
127            .into_iter()
128            .zip(self.challenges.clone().into_iter())
129            .map(|(evaluations, challenge)| {
130                if evaluations.len() != self.max_degree + 1 {
131                    return Err(PolyIOPErrors::InvalidVerifier(format!(
132                        "incorrect number of evaluations: {} vs {}",
133                        evaluations.len(),
134                        self.max_degree + 1
135                    )));
136                }
137                Ok(interpolate_uni_poly::<F>(&evaluations, challenge))
138            })
139            .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
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            if evaluations[0] + evaluations[1] != expected {
150                return Err(PolyIOPErrors::InvalidProof(
151                    "Prover message is not consistent with the claim.".to_string(),
152                ));
153            }
154        }
155        end_timer!(start);
156        Ok(SubClaim {
157            point: self.challenges.to_vec(),
158            // the last expected value (unchecked) will be included in the subclaim
159            expected_evaluation: expected_vec[self.num_vars],
160        })
161    }
162}
163
164/// Interpolate a uni-variate degree-`p_i.len()-1` polynomial and evaluate this
165/// polynomial at `eval_at`.
166pub(crate) fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> F {
167    let start = start_timer!(|| "sum check interpolate uni poly");
168    let mut result = F::zero();
169    let mut i = F::zero();
170    for term in p_i.iter() {
171        let mut term = *term;
172        let mut j = F::zero();
173        for _ in 0..p_i.len() {
174            if j != i {
175                term = term * (eval_at - j) / (i - j)
176            }
177            j += F::one();
178        }
179        i += F::one();
180        result += term;
181    }
182    end_timer!(start);
183    result
184}