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                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                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`:
166///   \sum_{i=0}^len p_i * (\prod_{j!=i} (eval_at - j)/(i-j) )
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.
170pub(crate) fn interpolate_uni_poly<F: PrimeField>(
171    p_i: &[F],
172    eval_at: F,
173) -> Result<F, PolyIOPErrors> {
174    let start = start_timer!(|| "sum check interpolate uni poly opt");
175
176    let mut res = F::zero();
177
178    // prod = \prod_{j!=i} (eval_at - j)
179    let mut evals = vec![];
180    let len = p_i.len();
181    let mut prod = eval_at;
182    evals.push(eval_at);
183
184    for e in 1..len {
185        let tmp = eval_at - F::from(e as u64);
186        evals.push(tmp);
187        prod *= tmp;
188    }
189
190    for i in 0..len {
191        let divisor = get_divisor(i, len)?;
192        let divisor_f = {
193            if divisor < 0 {
194                -F::from((-divisor) as u128)
195            } else {
196                F::from(divisor as u128)
197            }
198        };
199        res += p_i[i] * prod / (divisor_f * evals[i]);
200    }
201
202    end_timer!(start);
203    Ok(res)
204}
205
206/// Compute \prod_{j!=i)^len (i-j). This function takes O(n^2) number of
207/// primitive operations which is negligible compared to field operations.
208// We know
209//  - factorial(20) ~ 2^61
210//  - factorial(33) ~ 2^123
211// so we will be able to store the result for len<=20 with i64;
212// for len<=33 with i128; and we do not currently support len>33.
213#[inline]
214fn get_divisor(i: usize, len: usize) -> Result<i128, PolyIOPErrors> {
215    if len <= 20 {
216        let mut res = 1i64;
217        for j in 0..len {
218            if j != i {
219                res *= i as i64 - j as i64;
220            }
221        }
222        Ok(res as i128)
223    } else if len <= 33 {
224        let mut res = 1i128;
225        for j in 0..len {
226            if j != i {
227                res *= i as i128 - j as i128;
228            }
229        }
230        Ok(res)
231    } else {
232        Err(PolyIOPErrors::InvalidParameters(
233            "Do not support number variable > 33".to_string(),
234        ))
235    }
236}