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, 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
 16/// Verifier State
 17pub struct VerifierState<F: PrimeField> {
 18    round: usize,
 19    num_vars: usize,
 20    max_degree: usize,
 21    finished: bool,
 22    /// a list storing the univariate polynomial in evaluation form sent by the
 23    /// prover at each round
 24    polynomials_received: Vec<Vec<F>>,
 25    /// a list storing the randomness sampled by the verifier at each round
 26    challenges: Vec<F>,
 27}
 28
 29impl<F: PrimeField> SumCheckVerifier<F> for VerifierState<F> {
 30    type DomainInfo = DomainInfo<F>;
 31    type ProverMessage = IOPProverMessage<F>;
 32    type Challenge = F;
 33    type Transcript = IOPTranscript<F>;
 34    type SubClaim = SubClaim<F>;
 35
 36    /// initialize the verifier
 37    fn verifier_init(index_info: &Self::DomainInfo) -> Self {
 38        let start = start_timer!(|| "verifier init");
 39        let res = VerifierState {
 40            round: 1,
 41            num_vars: index_info.num_variables,
 42            max_degree: index_info.max_degree,
 43            finished: false,
 44            polynomials_received: Vec::with_capacity(index_info.num_variables),
 45            challenges: Vec::with_capacity(index_info.num_variables),
 46        };
 47        end_timer!(start);
 48        res
 49    }
 50
 51    /// Run verifier at current round, given prover message
 52    ///
 53    /// Normally, this function should perform actual verification. Instead,
 54    /// `verify_round` only samples and stores randomness and perform
 55    /// verifications altogether in `check_and_generate_subclaim` at
 56    /// the last step.
 57    fn verify_round_and_update_state(
 58        &mut self,
 59        prover_msg: &Self::ProverMessage,
 60        transcript: &mut Self::Transcript,
 61    ) -> Result<Self::Challenge, PolyIOPErrors> {
 62        let start = start_timer!(|| format!("verify {}-th round and update state", self.round));
 63
 64        if self.finished {
 65            return Err(PolyIOPErrors::InvalidVerifier(
 66                "Incorrect verifier state: Verifier is already finished.".to_string(),
 67            ));
 68        }
 69
 70        // Now, verifier should check if the received P(0) + P(1) = expected. The check
 71        // is moved to `check_and_generate_subclaim`, and will be done after the
 72        // last round.
 73
 74        let challenge = transcript.get_and_append_challenge(b"Internal round")?;
 75        self.challenges.push(challenge);
 76        self.polynomials_received
 77            .push(prover_msg.evaluations.to_vec());
 78
 79        // Now, verifier should set `expected` to P(r).
 80        // This operation is also moved to `check_and_generate_subclaim`,
 81        // and will be done after the last round.
 82
 83        if self.round == self.num_vars {
 84            // accept and close
 85            self.finished = true;
 86        } else {
 87            self.round += 1;
 88        }
 89
 90        end_timer!(start);
 91        Ok(challenge)
 92    }
 93
 94    /// verify the sumcheck phase, and generate the subclaim
 95    ///
 96    /// If the asserted sum is correct, then the multilinear polynomial
 97    /// evaluated at `subclaim.point` is `subclaim.expected_evaluation`.
 98    /// Otherwise, it is highly unlikely that those two will be equal.
 99    /// Larger field size guarantees smaller soundness error.
100    fn check_and_generate_subclaim(
101        &self,
102        asserted_sum: &F,
103    ) -> Result<Self::SubClaim, PolyIOPErrors> {
104        let start = start_timer!(|| "check_and_generate_subclaim");
105        if !self.finished {
106            return Err(PolyIOPErrors::InvalidVerifier(
107                "Incorrect verifier state: Verifier has not finished.".to_string(),
108            ));
109        }
110
111        if self.polynomials_received.len() != self.num_vars {
112            return Err(PolyIOPErrors::InvalidVerifier(
113                "insufficient rounds".to_string(),
114            ));
115        }
116
117        #[cfg(feature = "parallel")]
118        let mut expected_vec = self
119            .polynomials_received
120            .clone()
121            .into_par_iter()
122            .zip(self.challenges.clone().into_par_iter())
123            .map(|(evaluations, challenge)| {
124                if evaluations.len() != self.max_degree + 1 {
125                    return Err(PolyIOPErrors::InvalidVerifier(format!(
126                        "incorrect number of evaluations: {} vs {}",
127                        evaluations.len(),
128                        self.max_degree + 1
129                    )));
130                }
131                Ok(interpolate_uni_poly::<F>(&evaluations, challenge))
132            })
133            .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
134
135        #[cfg(not(feature = "parallel"))]
136        let mut expected_vec = self
137            .polynomials_received
138            .clone()
139            .into_iter()
140            .zip(self.challenges.clone().into_iter())
141            .map(|(evaluations, challenge)| {
142                if evaluations.len() != self.max_degree + 1 {
143                    return Err(PolyIOPErrors::InvalidVerifier(format!(
144                        "incorrect number of evaluations: {} vs {}",
145                        evaluations.len(),
146                        self.max_degree + 1
147                    )));
148                }
149                Ok(interpolate_uni_poly::<F>(&evaluations, challenge))
150            })
151            .collect::<Result<Vec<_>, PolyIOPErrors>>()?;
152        // insert the asserted_sum to the first position of the expected vector
153        expected_vec.insert(0, *asserted_sum);
154
155        for (evaluations, &expected) in self
156            .polynomials_received
157            .iter()
158            .zip(expected_vec.iter())
159            .take(self.num_vars)
160        {
161            if evaluations[0] + evaluations[1] != expected {
162                return Err(PolyIOPErrors::InvalidProof(
163                    "Prover message is not consistent with the claim.".to_string(),
164                ));
165            }
166        }
167        end_timer!(start);
168        Ok(SubClaim {
169            point: self.challenges.to_vec(),
170            // the last expected value (unchecked) will be included in the subclaim
171            expected_evaluation: expected_vec[self.num_vars],
172        })
173    }
174}
175
176/// interpolate a uni-variate degree-`p_i.len()-1` polynomial and evaluate this
177/// polynomial at `eval_at`.
178pub(crate) fn interpolate_uni_poly<F: PrimeField>(p_i: &[F], eval_at: F) -> F {
179    let start = start_timer!(|| "interpolate_uni_poly");
180    let mut result = F::zero();
181    let mut i = F::zero();
182    for term in p_i.iter() {
183        let mut term = *term;
184        let mut j = F::zero();
185        for _ in 0..p_i.len() {
186            if j != i {
187                term = term * (eval_at - j) / (i - j)
188            }
189            j += F::one();
190        }
191        i += F::one();
192        result += term;
193    }
194    end_timer!(start);
195    result
196}