sp1_hypercube/prover/zerocheck/
mod.rs

1//! Zerocheck Sumcheck polynomial.
2
3mod fix_last_variable;
4mod sum_as_poly;
5
6use std::fmt::Debug;
7
8pub use fix_last_variable::*;
9use slop_air::Air;
10use slop_algebra::{ExtensionField, Field, UnivariatePolynomial};
11use slop_alloc::{CpuBackend, HasBackend};
12use slop_multilinear::{PaddedMle, Point, VirtualGeq};
13use slop_sumcheck::{
14    ComponentPolyEvalBackend, SumCheckPolyFirstRoundBackend, SumcheckPolyBackend, SumcheckPolyBase,
15};
16use slop_uni_stark::SymbolicAirBuilder;
17pub use sum_as_poly::*;
18
19use crate::{
20    air::MachineAir, ConstraintSumcheckFolder, DebugConstraintBuilder, VerifierConstraintFolder,
21};
22
23/// Zerocheck sumcheck polynomial.
24#[derive(Clone)]
25pub struct ZeroCheckPoly<K, F, EF, A> {
26    /// The data that contains the constraint polynomial.
27    pub air_data: ZerocheckCpuProver<F, EF, A>,
28    /// The random challenge point at which the polynomial is evaluated.
29    pub zeta: Point<EF>,
30    /// The preprocessed trace.
31    pub preprocessed_columns: Option<PaddedMle<K>>,
32    /// The main trace.
33    pub main_columns: PaddedMle<K>,
34    /// The adjustment factor from the constant part of the eq polynomial.
35    pub eq_adjustment: EF,
36    ///  The geq polynomial value.  This will be 0 for all zerocheck polys that are at least one
37    /// non-padded variable.
38    pub geq_value: EF,
39    /// Num padded variables.  These padded variables are the first-most (e.g. the most
40    /// significant) variables.
41    // pub num_padded_vars: usize,
42    /// The padded row adjustment.
43    pub padded_row_adjustment: EF,
44
45    /// A virtual materialization keeping track the geq polynomial which is used to adjust the sums
46    /// for airs in which the zero row doesn't satisfy the constraints.
47    pub virtual_geq: VirtualGeq<K>,
48}
49
50impl<K: Field, F: Field, EF: ExtensionField<F>, AirData> ZeroCheckPoly<K, F, EF, AirData> {
51    /// Creates a new `ZeroCheckPoly`.
52    #[allow(clippy::too_many_arguments)]
53    #[inline]
54    pub fn new(
55        air_data: ZerocheckCpuProver<F, EF, AirData>,
56        zeta: Point<EF>,
57        preprocessed_values: Option<PaddedMle<K>>,
58        main_values: PaddedMle<K>,
59        eq_adjustment: EF,
60        geq_value: EF,
61        padded_row_adjustment: EF,
62        virtual_geq: VirtualGeq<K>,
63    ) -> Self {
64        Self {
65            air_data,
66            zeta,
67            preprocessed_columns: preprocessed_values,
68            main_columns: main_values,
69            eq_adjustment,
70            geq_value,
71            padded_row_adjustment,
72            virtual_geq,
73        }
74    }
75}
76
77impl<K: Field, F: Field, EF, AirData> SumcheckPolyBase for ZeroCheckPoly<K, F, EF, AirData>
78where
79    K: Field,
80{
81    #[inline]
82    fn num_variables(&self) -> u32 {
83        self.main_columns.num_variables()
84    }
85}
86
87impl<K, F, EF, AirData> ComponentPolyEvalBackend<ZeroCheckPoly<K, F, EF, AirData>, EF>
88    for CpuBackend
89where
90    K: Field,
91    F: Field,
92    EF: ExtensionField<F> + ExtensionField<K>,
93    AirData: Sync + Send,
94{
95    fn get_component_poly_evals(poly: &ZeroCheckPoly<K, F, EF, AirData>) -> Vec<EF> {
96        assert!(poly.num_variables() == 0);
97
98        let prep_columns = poly.preprocessed_columns.as_ref();
99        // First get the preprocessed values.
100        let prep_evals = if let Some(preprocessed_values) = prep_columns {
101            preprocessed_values.inner().as_ref().unwrap().guts().as_slice()
102        } else {
103            &[]
104        };
105
106        let main_evals = poly
107            .main_columns
108            .inner()
109            .as_ref()
110            .map(|mle| mle.guts().as_slice().to_vec())
111            .unwrap_or(vec![K::zero(); poly.main_columns.num_polynomials()]);
112
113        // Add the main values.
114        prep_evals.iter().copied().chain(main_evals).map(Into::into).collect::<Vec<_>>()
115    }
116}
117
118impl<F, EF, A: Send + Sync> SumCheckPolyFirstRoundBackend<ZeroCheckPoly<F, F, EF, A>, EF>
119    for CpuBackend
120where
121    F: Field,
122    EF: ExtensionField<F>,
123    A: ZerocheckAir<F, EF>,
124{
125    type NextRoundPoly = ZeroCheckPoly<EF, F, EF, A>;
126
127    #[inline]
128    fn fix_t_variables(
129        poly: ZeroCheckPoly<F, F, EF, A>,
130        alpha: EF,
131        t: usize,
132    ) -> Self::NextRoundPoly {
133        debug_assert!(t == 1);
134        zerocheck_fix_last_variable(poly, alpha)
135    }
136
137    #[inline]
138    fn sum_as_poly_in_last_t_variables(
139        poly: &ZeroCheckPoly<F, F, EF, A>,
140        claim: Option<EF>,
141        t: usize,
142    ) -> UnivariatePolynomial<EF> {
143        debug_assert!(t == 1);
144        debug_assert!(poly.num_variables() > 0);
145        zerocheck_sum_as_poly_in_last_variable::<F, F, EF, A, true>(poly, claim)
146    }
147}
148
149impl<F, EF, A: Send + Sync> SumcheckPolyBackend<ZeroCheckPoly<EF, F, EF, A>, EF> for CpuBackend
150where
151    F: Field,
152    EF: ExtensionField<F>,
153    A: ZerocheckAir<F, EF>,
154{
155    #[inline]
156    fn fix_last_variable(
157        poly: ZeroCheckPoly<EF, F, EF, A>,
158        alpha: EF,
159    ) -> ZeroCheckPoly<EF, F, EF, A> {
160        zerocheck_fix_last_variable(poly, alpha)
161    }
162
163    #[inline]
164    fn sum_as_poly_in_last_variable(
165        poly: &ZeroCheckPoly<EF, F, EF, A>,
166        claim: Option<EF>,
167    ) -> UnivariatePolynomial<EF> {
168        debug_assert!(poly.num_variables() > 0);
169        zerocheck_sum_as_poly_in_last_variable::<EF, F, EF, A, false>(poly, claim)
170    }
171}
172
173impl<K, F, EF, AirData> HasBackend for ZeroCheckPoly<K, F, EF, AirData> {
174    type Backend = CpuBackend;
175
176    #[inline]
177    fn backend(&self) -> &Self::Backend {
178        self.main_columns.backend()
179    }
180}
181
182/// An AIR compatible with the standard zerocheck prover.
183pub trait ZerocheckAir<F: Field, EF: ExtensionField<F>>:
184    Debug
185    + MachineAir<F>
186    + Air<SymbolicAirBuilder<F>>
187    + for<'b> Air<ConstraintSumcheckFolder<'b, F, F, EF>>
188    + for<'b> Air<ConstraintSumcheckFolder<'b, F, EF, EF>>
189    + for<'b> Air<DebugConstraintBuilder<'b, F, EF>>
190    + for<'a> Air<VerifierConstraintFolder<'a, F, EF>>
191{
192}
193
194impl<F: Field, EF: ExtensionField<F>, A> ZerocheckAir<F, EF> for A where
195    A: MachineAir<F>
196        + Debug
197        + Air<SymbolicAirBuilder<F>>
198        + for<'b> Air<ConstraintSumcheckFolder<'b, F, F, EF>>
199        + for<'b> Air<ConstraintSumcheckFolder<'b, F, EF, EF>>
200        + for<'b> Air<DebugConstraintBuilder<'b, F, EF>>
201        + for<'a> Air<VerifierConstraintFolder<'a, F, EF>>
202{
203}
sp1_hypercube/prover/zerocheck/mod.rs

sp1_hypercube/prover/zerocheck/
mod.rs
