zinc_piop/sumcheck/
verifier.rs

1//! Verifier
2
3use crypto_primitives::{BaseFieldConfig, ProjectPrimitiveIntegersWithConfig, SetConfig};
4use zinc_poly::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, generic over the field config `C`.
15pub struct VerifierState<C: SetConfig> {
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<C::Element>>,
28    /// A list storing the randomness sampled by the verifier at each round so
29    /// far.
30    pub randomness: Vec<C::Element>,
31    /// The field configuration to which
32    /// all the field elements belong to.
33    pub config: C,
34}
35
36impl<C: SetConfig> VerifierState<C> {
37    /// Initialize the verifier state.
38    pub fn new(nvars: usize, degree: usize, config: &C) -> 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<C: BaseFieldConfig + ProjectPrimitiveIntegersWithConfig> VerifierState<C> {
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(
67        &mut self,
68        prover_msg: &ProverMsg<C::Element>,
69        transcript: &mut impl Transcript,
70    ) -> C::Element
71    where
72        C::Integer: ConstTranscribable,
73    {
74        let challenge: C::Element = transcript.get_field_challenge(&self.config);
75        self.verify_round_with_challenge(prover_msg, challenge.clone());
76        challenge
77    }
78
79    /// Processes one round of the sumcheck protocol given an explicit
80    /// challenge. Stores the prover's round polynomial and the challenge, then
81    /// advances the round counter. Actual consistency checks are deferred
82    /// to [`Self::check_and_generate_subclaim`].
83    pub fn verify_round_with_challenge(
84        &mut self,
85        prover_msg: &ProverMsg<C::Element>,
86        challenge: C::Element,
87    ) {
88        if self.finished {
89            panic!("Incorrect verifier state: Verifier is already finished.");
90        }
91
92        // The constant term is omitted from prover messages. The verifier stores the
93        // provided evaluations and will reconstruct the missing value in
94        // `check_and_generate_subclaim`.
95        self.randomness.push(challenge);
96        self.polynomials_received.push(prover_msg.0.clone());
97
98        // Now, verifier should set `expected` to P(r).
99        // This operation is also moved to `check_and_generate_subclaim`,
100        // and will be done after the last round.
101
102        if self.round == self.nv {
103            // accept and close
104            self.finished = true;
105        } else {
106            self.round = add!(self.round, 1);
107        }
108    }
109
110    /// Verify the sumcheck phase, and generate the subclaim.
111    ///
112    /// The verifier reconstructs the missing constant term under the
113    /// assumption that `P(0) + P(1) == expected`. If the asserted sum is
114    /// correct, then the multilinear polynomial evaluated at `subclaim.point`
115    /// is `subclaim.expected_evaluation`.
116    #[allow(clippy::arithmetic_side_effects)]
117    pub fn check_and_generate_subclaim(
118        self,
119        asserted_sum: C::Element,
120    ) -> Result<Subclaim<C::Element>, SumCheckError<C::Element>> {
121        if !self.finished {
122            panic!("Verifier has not finished.");
123        }
124
125        let mut expected = asserted_sum;
126        if self.polynomials_received.len() != self.nv {
127            panic!("insufficient rounds");
128        }
129        for (i, evaluations_without_constant) in self.polynomials_received.iter().enumerate() {
130            let expected_len = if self.max_multiplicands == 0 {
131                0
132            } else {
133                self.max_multiplicands
134            };
135            if evaluations_without_constant.len() != expected_len {
136                return Err(SumCheckError::MaxDegreeExceeded);
137            }
138
139            let constant_term = if self.max_multiplicands == 0 {
140                expected.clone()
141            } else {
142                let p1 = evaluations_without_constant
143                    .first()
144                    .expect("degree > 0 implies the polynomial has an evaluation at 1");
145                self.config.sub(&expected, p1)
146            };
147            let mut reconstructed_evaluations =
148                Vec::with_capacity(add!(evaluations_without_constant.len(), 1));
149            reconstructed_evaluations.push(constant_term);
150            reconstructed_evaluations.extend_from_slice(evaluations_without_constant);
151
152            let reconstructed_poly = NatEvaluatedPoly::new(reconstructed_evaluations);
153            expected = reconstructed_poly.evaluate_at_point(&self.config, &self.randomness[i])?;
154        }
155
156        Ok(Subclaim {
157            point: self.randomness,
158            expected_evaluation: expected,
159        })
160    }
161}
zinc_piop/sumcheck/verifier.rs

zinc_piop/sumcheck/
verifier.rs
