p3_sumcheck/lib.rs
1//! Sumcheck protocol implementation for multilinear polynomial verification.
2//!
3//! # The Sumcheck Protocol
4//!
5//! The sumcheck protocol verifies a claimed sum of the form:
6//!
7//! ```text
8//! sum_{x in {0,1}^l} g(x) = t
9//! ```
10//!
11//! Without it, the verifier would need to evaluate `g` at all `2^l` hypercube points.
12//! The protocol reduces this to a single evaluation at a random point, using `l` rounds.
13//!
14//! In each round, the prover sends a low-degree univariate polynomial:
15//!
16//! ```text
17//! h_i(X) = sum_{x_{i+1}, ..., x_l in {0,1}} g(r_1, ..., r_{i-1}, X, x_{i+1}, ..., x_l)
18//! ```
19//!
20//! The verifier checks `h_i(0) + h_i(1) == claimed_sum`.
21//! Then samples a random challenge `r_i` and updates the claim to `h_i(r_i)`.
22//!
23//! After `l` rounds, the verifier holds `(r_1, ..., r_l)` and queries `g` directly.
24
25#![no_std]
26
27extern crate alloc;
28
29pub mod commit;
30pub mod constraints;
31pub mod data;
32pub mod error;
33pub mod lagrange;
34pub mod layout;
35pub mod product_polynomial;
36pub mod strategy;
37pub mod svo;
38pub mod table;
39#[cfg(any(test, feature = "test-util"))]
40pub mod test_util;
41#[cfg(test)]
42mod tests;
43pub mod zk;
44
45pub use data::{SumcheckData, verify_final_sumcheck_rounds};
46pub use error::SumcheckError;
47pub(crate) use lagrange::extrapolate_01inf;
48use p3_field::Field;
49pub use table::{OpeningProtocol, PointSchedule, TableShape, TableSpec};
50
51/// A claimed evaluation together with layout-specific auxiliary data.
52#[derive(Debug, Clone)]
53pub struct Claim<F: Field, P, Data> {
54 /// Point representation used to evaluate or later reconstruct this claim.
55 pub(crate) point: P,
56 /// Claimed value at `point`.
57 pub(crate) eval: F,
58 /// Extra strategy-specific prover or verifier metadata.
59 pub(crate) data: Data,
60}
61
62impl<F: Field, P, Data> Claim<F, P, Data> {
63 /// Returns the claimed value.
64 pub const fn eval(&self) -> F {
65 self.eval
66 }
67
68 /// Returns the point representation attached to this claim.
69 pub const fn point(&self) -> &P {
70 &self.point
71 }
72}