zinc_piop/sumcheck/
verifier.rs

1//! Verifier
2
3use crypto_primitives::{FromPrimitiveWithConfig, PrimeField};
4use zinc_poly::{EvaluatablePolynomial, univariate::nat_evaluation::NatEvaluatedPoly};
5use zinc_transcript::traits::{ConstTranscribable, Transcript};
6use zinc_utils::add;
7
8use crate::sumcheck::prover::{NatEvaluatedPolyWithoutConstant, ProverMsg};
9
10use super::SumCheckError;
11
12pub const SQUEEZE_NATIVE_ELEMENTS_NUM: usize = 1;
13
14/// Sumcheck Verifier State.
15pub struct VerifierState<F: PrimeField> {
16    /// The current round number.
17    pub round: usize,
18    /// The number of variables the sumcheck polynomial
19    /// is in.
20    pub nv: usize,
21    /// The degree of the polynomial.
22    pub max_multiplicands: usize,
23    /// `true` if the protocol has finished.
24    pub finished: bool,
25    /// A list storing the univariate polynomial in evaluation form sent by the
26    /// prover at each round so far.
27    pub polynomials_received: Vec<NatEvaluatedPolyWithoutConstant<F>>,
28    /// A list storing the randomness sampled by the verifier at each round so
29    /// far.
30    pub randomness: Vec<F>,
31    /// The field configuration to which
32    /// all the field elements belong to.
33    pub config: F::Config,
34}
35
36impl<F: PrimeField> VerifierState<F> {
37    /// Initialize the verifier state.
38    pub fn new(nvars: usize, degree: usize, config: &F::Config) -> Self {
39        Self {
40            round: 1,
41            nv: nvars,
42            max_multiplicands: degree,
43            finished: false,
44            polynomials_received: Vec::with_capacity(nvars),
45            randomness: Vec::with_capacity(nvars),
46            config: config.clone(),
47        }
48    }
49}
50
51/// Subclaim when verifier is convinced
52#[derive(Clone, Debug)]
53pub struct Subclaim<F> {
54    /// The multi-dimensional point that this multilinear extension is evaluated
55    /// at.
56    pub point: Vec<F>,
57    /// The expected evaluation.
58    pub expected_evaluation: F,
59}
60
61impl<F: FromPrimitiveWithConfig> VerifierState<F> {
62    /// Run verifier at current round, given prover message.
63    ///
64    /// Samples a Fiat-Shamir challenge from the transcript and delegates to
65    /// [`Self::verify_round_with_challenge`]. Returns the sampled challenge.
66    pub fn verify_round(&mut self, prover_msg: &ProverMsg<F>, transcript: &mut impl Transcript) -> F
67    where
68        F::Inner: ConstTranscribable,
69    {
70        let challenge: F = transcript.get_field_challenge(&self.config);
71        self.verify_round_with_challenge(prover_msg, challenge.clone());
72        challenge
73    }
74
75    /// Processes one round of the sumcheck protocol given an explicit
76    /// challenge. Stores the prover's round polynomial and the challenge, then
77    /// advances the round counter. Actual consistency checks are deferred
78    /// to [`Self::check_and_generate_subclaim`].
79    pub fn verify_round_with_challenge(&mut self, prover_msg: &ProverMsg<F>, challenge: F) {
80        if self.finished {
81            panic!("Incorrect verifier state: Verifier is already finished.");
82        }
83
84        // The constant term is omitted from prover messages. The verifier stores the
85        // provided evaluations and will reconstruct the missing value in
86        // `check_and_generate_subclaim`.
87        self.randomness.push(challenge);
88        self.polynomials_received.push(prover_msg.0.clone());
89
90        // Now, verifier should set `expected` to P(r).
91        // This operation is also moved to `check_and_generate_subclaim`,
92        // and will be done after the last round.
93
94        if self.round == self.nv {
95            // accept and close
96            self.finished = true;
97        } else {
98            self.round = add!(self.round, 1);
99        }
100    }
101
102    /// Verify the sumcheck phase, and generate the subclaim.
103    ///
104    /// The verifier reconstructs the missing constant term under the
105    /// assumption that `P(0) + P(1) == expected`. If the asserted sum is
106    /// correct, then the multilinear polynomial evaluated at `subclaim.point`
107    /// is `subclaim.expected_evaluation`.
108    #[allow(clippy::arithmetic_side_effects)]
109    pub fn check_and_generate_subclaim(
110        self,
111        asserted_sum: F,
112    ) -> Result<Subclaim<F>, SumCheckError<F>> {
113        if !self.finished {
114            panic!("Verifier has not finished.");
115        }
116
117        let mut expected = asserted_sum;
118        if self.polynomials_received.len() != self.nv {
119            panic!("insufficient rounds");
120        }
121        for (i, evaluations_without_constant) in self.polynomials_received.iter().enumerate() {
122            let expected_len = if self.max_multiplicands == 0 {
123                0
124            } else {
125                self.max_multiplicands
126            };
127            if evaluations_without_constant.len() != expected_len {
128                return Err(SumCheckError::MaxDegreeExceeded);
129            }
130
131            let constant_term = if self.max_multiplicands == 0 {
132                expected.clone()
133            } else {
134                let p1 = evaluations_without_constant
135                    .first()
136                    .expect("degree > 0 implies the polynomial has an evaluation at 1");
137                expected.clone() - p1.clone()
138            };
139            let mut reconstructed_evaluations =
140                Vec::with_capacity(add!(evaluations_without_constant.len(), 1));
141            reconstructed_evaluations.push(constant_term);
142            reconstructed_evaluations.extend_from_slice(evaluations_without_constant);
143
144            let reconstructed_poly = NatEvaluatedPoly::new(reconstructed_evaluations);
145            expected = reconstructed_poly.evaluate_at_point(&self.randomness[i])?;
146        }
147
148        Ok(Subclaim {
149            point: self.randomness,
150            expected_evaluation: expected,
151        })
152    }
153}
zinc_piop/sumcheck/verifier.rs

zinc_piop/sumcheck/
verifier.rs
