2026-03-28T22:40:11Z by Showboat 0.6.1
This walkthrough explains one narrow slice of the AIR API history in Plonky3:
- what PR
#1357/ commit808fb9e2introduced, - how the later window-type split refined that model,
- what the current branch changes in commit
f999f2ce, - where
ref-caststyle views could simplify the code, and - why this branch currently has three substantive regressions.
The approach here is deliberately linear. We start with the historical commits, then move into the current code paths, and only then evaluate the proposed simplification and its failure modes.
git show -s --format='commit %H%nAuthorDate: %aI%nCommitDate: %cI%nSubject: %s' 808fb9e2 7ca1cdff HEAD 45e0ffe4d294816755522dd2cf7c38d6bcd701cecommit 808fb9e282e9c2d4ad5199406caeaae492c55e1d
AuthorDate: 2026-03-05T14:17:17+01:00
CommitDate: 2026-03-05T13:17:17Z
Subject: air: rm `is_transition_window` and add `RowWindow` (#1357)
commit 7ca1cdff34db49b70fce3e581879b6ef92dec6ef
AuthorDate: 2026-03-07T01:37:46+01:00
CommitDate: 2026-03-07T04:37:46+04:00
Subject: refactor: split `AirBuilder::M` into `MainWindow` and `PreprocessedWindow` (#1405)
commit f999f2ce475e91397af9f651813858febd3e38b3
AuthorDate: 2026-03-24T00:31:26+01:00
CommitDate: 2026-03-24T00:31:26+01:00
Subject: air: simplify window access using matrix crate
commit 45e0ffe4d294816755522dd2cf7c38d6bcd701ce
AuthorDate: 2026-03-16T15:04:06+04:00
CommitDate: 2026-03-16T15:04:06+04:00
Subject: chore: release v0.5.1 (#1439)
The key historical change is 808fb9e2, titled air: rm is_transition_window and add RowWindow (#1357).
That commit introduced a new abstraction layer in p3_air:
WindowAccess<T>as a trait for two-row access,RowWindow<'a, T>as the default concrete implementation, and- a new expectation that builders expose current/next rows through this lightweight two-row window instead of through the more general
MatrixAPI.
The intent was pragmatic. AIR evaluation almost always wants "local row" and "next row", not an arbitrary matrix. RowWindow encoded exactly that and stripped away unrelated matrix surface area.
git show 808fb9e2:air/src/air.rs | sed -n '1,170p'use alloc::vec;
use alloc::vec::Vec;
use core::ops::{Add, Mul, Sub};
use p3_field::{Algebra, ExtensionField, Field, PrimeCharacteristicRing};
use p3_matrix::dense::{RowMajorMatrix, RowMajorMatrixView};
use crate::lookup::{Kind, Lookup, LookupEvaluator, LookupInput};
/// Read access to a pair of trace rows (typically current and next).
///
/// Implementors expose two flat slices that constraint evaluators use
/// to express algebraic relations between rows.
pub trait WindowAccess<T> {
/// Full slice of the current row.
fn current_slice(&self) -> &[T];
/// Full slice of the next row.
fn next_slice(&self) -> &[T];
/// Single element from the current row by index.
///
/// Returns `None` if `i` is out of bounds.
#[inline]
fn current(&self, i: usize) -> Option<T>
where
T: Clone,
{
self.current_slice().get(i).cloned()
}
/// Single element from the next row by index.
///
/// Returns `None` if `i` is out of bounds.
#[inline]
fn next(&self, i: usize) -> Option<T>
where
T: Clone,
{
self.next_slice().get(i).cloned()
}
}
/// A lightweight two-row window into a trace matrix.
///
/// Stores two `&[T]` slices — one for the current row and one for
/// the next — without carrying any matrix metadata. This is cheaper
/// than a full `ViewPair` and is the concrete type used by most
/// [`AirBuilder`] implementations for `type M`.
#[derive(Debug, Clone, Copy)]
pub struct RowWindow<'a, T> {
/// The current row.
current: &'a [T],
/// The next row.
next: &'a [T],
}
impl<'a, T> RowWindow<'a, T> {
/// Create a window from a [`RowMajorMatrixView`] that has exactly
/// two rows. The first row becomes `current`, the second `next`.
///
/// # Panics
///
/// Panics if the view does not contain exactly `2 * width` elements.
#[inline]
pub fn from_view(view: &RowMajorMatrixView<'a, T>) -> Self {
let width = view.width;
assert_eq!(
view.values.len(),
2 * width,
"RowWindow::from_view: expected 2 rows (2*{width} elements), got {}",
view.values.len()
);
let (current, next) = view.values.split_at(width);
Self { current, next }
}
/// Create a window from two separate row slices.
///
/// The caller is responsible for providing slices that represent
/// the intended (current, next) pair.
///
/// # Panics
///
/// Panics (in debug builds) if the slices have different lengths.
#[inline]
pub fn from_two_rows(current: &'a [T], next: &'a [T]) -> Self {
debug_assert_eq!(
current.len(),
next.len(),
"RowWindow::from_two_rows: row lengths differ ({} vs {})",
current.len(),
next.len()
);
Self { current, next }
}
}
impl<T> WindowAccess<T> for RowWindow<'_, T> {
#[inline]
fn current_slice(&self) -> &[T] {
self.current
}
#[inline]
fn next_slice(&self) -> &[T] {
self.next
}
}
/// The underlying structure of an AIR.
pub trait BaseAir<F>: Sync {
/// The number of columns (a.k.a. registers) in this AIR.
fn width(&self) -> usize;
/// Return an optional preprocessed trace matrix to be included in the prover's trace.
fn preprocessed_trace(&self) -> Option<RowMajorMatrix<F>> {
None
}
/// Which main trace columns have their next row accessed by this AIR's
/// constraints.
///
/// By default this returns every column index, which will require
/// opening all main columns at both `zeta` and `zeta_next`.
///
/// AIRs that only ever read the current main row (and never access an
/// offset-1 main entry) can override this to return an empty vector to
/// allow the prover and verifier to open only at `zeta`.
///
/// # When to override
///
/// - **Return empty**: single-row AIRs where all constraints are
/// evaluated within one row.
/// - **Keep default** (all columns): AIRs with transition constraints
/// that reference `main.next_slice()`.
/// - **Return a subset**: AIRs where only a few columns need next-row
/// access, enabling future per-column opening optimizations.
///
/// # Correctness
///
/// Must be consistent with [`Air::eval`]. Omitting a column index when
/// the AIR actually reads its next row will cause verification failures
/// or, in the worst case, a soundness gap.
fn main_next_row_columns(&self) -> Vec<usize> {
(0..self.width()).collect()
}
/// Which preprocessed trace columns have their next row accessed by this
/// AIR's constraints.
///
/// By default this returns every preprocessed column index, which will
/// require opening preprocessed columns at both `zeta` and `zeta_next`.
///
/// AIRs that only ever read the current preprocessed row (and never
/// access an offset-1 preprocessed entry) can override this to return an
/// empty vector to allow the prover and verifier to open only at `zeta`.
fn preprocessed_next_row_columns(&self) -> Vec<usize> {
self.preprocessed_trace()
.map(|t| (0..t.width).collect())
.unwrap_or_default()
}
/// Optional hint for the number of constraints in this AIR.
///
/// Normally the prover runs a full symbolic evaluation just to count
/// constraints. Overriding this method lets the prover skip that pass.
///
/// The count must cover every constraint asserted during evaluation,
/// including both transition and boundary constraints. It must **not**
/// include lookup or permutation constraints, which are counted
git show 808fb9e2:uni-stark/src/folder.rs | sed -n '1,120p'use alloc::vec::Vec;
use p3_air::{AirBuilder, ExtensionBuilder, RowWindow};
use p3_field::{Algebra, BasedVectorSpace, PackedField, PrimeCharacteristicRing};
use p3_matrix::dense::RowMajorMatrixView;
use p3_matrix::stack::ViewPair;
use crate::{PackedChallenge, PackedVal, StarkGenericConfig, Val};
/// Batch size for constraint linear-combination chunks in [`finalize_constraints`].
const CONSTRAINT_BATCH: usize = 8;
/// Batched linear combination of packed extension field values with EF coefficients.
///
/// Extension-field analogue of [`PackedField::packed_linear_combination`]. Processes
/// `coeffs` and `values` in chunks of [`CONSTRAINT_BATCH`], then handles the remainder.
#[inline]
fn batched_ext_linear_combination<PE, EF>(coeffs: &[EF], values: &[PE]) -> PE
where
EF: p3_field::Field,
PE: PrimeCharacteristicRing + Algebra<EF> + Copy,
{
debug_assert_eq!(coeffs.len(), values.len());
let len = coeffs.len();
let mut acc = PE::ZERO;
let mut start = 0;
while start + CONSTRAINT_BATCH <= len {
let batch: [PE; CONSTRAINT_BATCH] =
core::array::from_fn(|i| values[start + i] * coeffs[start + i]);
acc += PE::sum_array::<CONSTRAINT_BATCH>(&batch);
start += CONSTRAINT_BATCH;
}
for (&coeff, &val) in coeffs[start..].iter().zip(&values[start..]) {
acc += val * coeff;
}
acc
}
/// Batched linear combination of packed base field values with F coefficients.
///
/// Wraps [`PackedField::packed_linear_combination`] with batched chunking
/// and remainder handling, mirroring [`batched_ext_linear_combination`].
#[inline]
fn batched_base_linear_combination<P: PackedField>(coeffs: &[P::Scalar], values: &[P]) -> P {
debug_assert_eq!(coeffs.len(), values.len());
let len = coeffs.len();
let mut acc = P::ZERO;
let mut start = 0;
while start + CONSTRAINT_BATCH <= len {
acc += P::packed_linear_combination::<CONSTRAINT_BATCH>(
&coeffs[start..start + CONSTRAINT_BATCH],
&values[start..start + CONSTRAINT_BATCH],
);
start += CONSTRAINT_BATCH;
}
for (&coeff, &val) in coeffs[start..].iter().zip(&values[start..]) {
acc += val * coeff;
}
acc
}
/// Packed constraint folder for SIMD-optimized prover evaluation.
///
/// Uses packed types to evaluate constraints on multiple domain points simultaneously.
///
/// Collects constraints during `air.eval()` into separate base/ext vectors, then
/// combines them in [`Self::finalize_constraints`] using decomposed alpha powers and
/// `packed_linear_combination` for efficient SIMD accumulation.
#[derive(Debug)]
pub struct ProverConstraintFolder<'a, SC: StarkGenericConfig> {
/// The [`RowMajorMatrixView`] containing rows on which the constraint polynomial is evaluated.
pub main: RowMajorMatrixView<'a, PackedVal<SC>>,
/// The preprocessed columns as a [`RowMajorMatrixView`].
/// Zero-width when the AIR has no preprocessed trace.
pub preprocessed: RowMajorMatrixView<'a, PackedVal<SC>>,
/// Pre-built window over the preprocessed columns.
pub preprocessed_window: RowWindow<'a, PackedVal<SC>>,
/// Public inputs to the [AIR](`p3_air::Air`) implementation.
pub public_values: &'a [Val<SC>],
/// Evaluations of the Selector polynomial for the first row of the trace
pub is_first_row: PackedVal<SC>,
/// Evaluations of the Selector polynomial for the last row of the trace
pub is_last_row: PackedVal<SC>,
/// Evaluations of the Selector polynomial for rows where transition constraints should be applied
pub is_transition: PackedVal<SC>,
/// Base-field alpha powers, reordered to match base constraint emission order.
/// `base_alpha_powers[d][j]` = d-th basis coefficient of alpha power for j-th base constraint.
pub base_alpha_powers: &'a [Vec<Val<SC>>],
/// Extension-field alpha powers, reordered to match ext constraint emission order.
pub ext_alpha_powers: &'a [SC::Challenge],
/// Collected base-field constraints for this row
pub base_constraints: Vec<PackedVal<SC>>,
/// Collected extension-field constraints for this row
pub ext_constraints: Vec<PackedChallenge<SC>>,
/// Current constraint index being processed (debug-only bookkeeping)
pub constraint_index: usize,
/// Total number of constraints in the AIR (debug-only bookkeeping)
pub constraint_count: usize,
}
/// Handles constraint verification for the verifier in a STARK system.
///
/// Similar to [`ProverConstraintFolder`] but operates on committed values rather than the full trace,
/// using a more efficient accumulation method for verification.
#[derive(Debug)]
pub struct VerifierConstraintFolder<'a, SC: StarkGenericConfig> {
/// Pair of consecutive rows from the committed polynomial evaluations as a [`ViewPair`].
pub main: ViewPair<'a, SC::Challenge>,
/// The preprocessed columns as a [`ViewPair`].
/// Zero-width when the AIR has no preprocessed trace.
pub preprocessed: ViewPair<'a, SC::Challenge>,
/// Pre-built window over the preprocessed columns.
pub preprocessed_window: RowWindow<'a, SC::Challenge>,
/// Public values that are inputs to the computation
pub public_values: &'a [Val<SC>],
/// Evaluations of the Selector polynomial for the first row of the trace
pub is_first_row: SC::Challenge,
/// Evaluations of the Selector polynomial for the last row of the trace
The old model has a few important properties.
First, RowWindow always represents exactly two logical rows. It is not an arbitrary matrix view. Its constructors either split a flat two-row RowMajorMatrixView or accept two row slices directly.
Second, the access pattern is semantic rather than coordinate-based:
current_slice()/next_slice()for whole rows,current(i)/next(i)for individual columns.
Third, the absence of preprocessed columns still fits that model. A builder can hand out a zero-width RowWindow, but it is still a two-row window. That distinction matters later.
git show 808fb9e2:batch-stark/src/verifier.rs | sed -n '70,120p' // - If ZK is not enabled, the prover should not have random commitments.
if (opened_values
.instances
.iter()
.any(|ov| ov.base_opened_values.random.is_some() != SC::Pcs::ZK))
|| (commitments.random.is_some() != SC::Pcs::ZK)
{
return Err(VerificationError::RandomizationError);
}
// Observe the number of instances up front to match the prover's transcript.
let n_instances = airs.len();
challenger.observe_base_as_algebra_element::<Challenge<SC>>(Val::<SC>::from_usize(n_instances));
// Validate opened values shape per instance and observe per-instance binding data.
// Precompute per-instance preprocessed widths and number of quotient chunks.
let mut preprocessed_widths = Vec::with_capacity(airs.len());
// Number of quotient chunks per instance before ZK randomization.
let mut log_num_quotient_chunks = Vec::with_capacity(airs.len());
// The total number of quotient chunks, including ZK randomization.
let mut num_quotient_chunks = Vec::with_capacity(airs.len());
for (i, air) in airs.iter().enumerate() {
let pre_w = common
.preprocessed
.as_ref()
.and_then(|g| g.instances[i].as_ref().map(|m| m.width))
.unwrap_or(0);
preprocessed_widths.push(pre_w);
let layout = AirLayout {
preprocessed_width: pre_w,
main_width: air.width(),
num_public_values: air.num_public_values(),
..Default::default()
};
let log_num_chunks =
info_span!("infer log of constraint degree", air_idx = i).in_scope(|| {
get_log_num_quotient_chunks::<Val<SC>, SC::Challenge, A, LogUpGadget>(
air,
layout,
&all_lookups[i],
config.is_zk(),
&lookup_gadget,
)
});
log_num_quotient_chunks.push(log_num_chunks);
let n_chunks = 1 << (log_num_chunks + config.is_zk());
num_quotient_chunks.push(n_chunks);
}
git show 808fb9e2:lookup/src/folder.rs | sed -n '1,120p'use p3_air::{AirBuilder, ExtensionBuilder, PermutationAirBuilder, RowWindow};
use p3_matrix::dense::RowMajorMatrixView;
use p3_matrix::stack::ViewPair;
use p3_uni_stark::{
PackedChallenge, PackedVal, ProverConstraintFolder, StarkGenericConfig, Val,
VerifierConstraintFolder,
};
pub struct ProverConstraintFolderWithLookups<'a, SC: StarkGenericConfig> {
pub inner: ProverConstraintFolder<'a, SC>,
pub permutation: RowMajorMatrixView<'a, PackedChallenge<SC>>,
pub permutation_challenges: &'a [PackedChallenge<SC>],
pub permutation_values: &'a [PackedChallenge<SC>],
}
impl<'a, SC: StarkGenericConfig> AirBuilder for ProverConstraintFolderWithLookups<'a, SC> {
type F = Val<SC>;
type Expr = PackedVal<SC>;
type Var = PackedVal<SC>;
type PublicVar = Val<SC>;
type M = RowWindow<'a, PackedVal<SC>>;
fn main(&self) -> Self::M {
RowWindow::from_view(&self.inner.main)
}
fn preprocessed(&self) -> &Self::M {
self.inner.preprocessed()
}
#[inline]
fn public_values(&self) -> &[Self::PublicVar] {
self.inner.public_values
}
#[inline]
fn is_first_row(&self) -> Self::Expr {
self.inner.is_first_row
}
#[inline]
fn is_last_row(&self) -> Self::Expr {
self.inner.is_last_row
}
#[inline]
fn is_transition_window(&self, size: usize) -> Self::Expr {
assert!(size <= 2, "only two-row windows are supported, got {size}");
self.inner.is_transition
}
#[inline]
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
self.inner.assert_zero(x);
}
#[inline]
fn assert_zeros<const N: usize, I: Into<Self::Expr>>(&mut self, array: [I; N]) {
self.inner.assert_zeros(array);
}
}
impl<SC: StarkGenericConfig> ExtensionBuilder for ProverConstraintFolderWithLookups<'_, SC> {
type EF = SC::Challenge;
type ExprEF = PackedChallenge<SC>;
type VarEF = PackedChallenge<SC>;
fn assert_zero_ext<I>(&mut self, x: I)
where
I: Into<Self::ExprEF>,
{
self.inner.assert_zero_ext(x);
}
}
impl<'a, SC: StarkGenericConfig> PermutationAirBuilder
for ProverConstraintFolderWithLookups<'a, SC>
{
type RandomVar = PackedChallenge<SC>;
type MP = RowWindow<'a, PackedChallenge<SC>>;
type PermutationVar = PackedChallenge<SC>;
fn permutation(&self) -> Self::MP {
RowWindow::from_view(&self.permutation)
}
fn permutation_randomness(&self) -> &[PackedChallenge<SC>] {
self.permutation_challenges
}
fn permutation_values(&self) -> &[PackedChallenge<SC>] {
self.permutation_values
}
}
pub struct VerifierConstraintFolderWithLookups<'a, SC: StarkGenericConfig> {
pub inner: VerifierConstraintFolder<'a, SC>,
pub permutation: ViewPair<'a, SC::Challenge>,
pub permutation_challenges: &'a [SC::Challenge],
pub permutation_values: &'a [SC::Challenge],
}
impl<'a, SC: StarkGenericConfig> AirBuilder for VerifierConstraintFolderWithLookups<'a, SC> {
type F = Val<SC>;
type Expr = SC::Challenge;
type Var = SC::Challenge;
type PublicVar = Val<SC>;
type M = RowWindow<'a, SC::Challenge>;
fn main(&self) -> Self::M {
RowWindow::from_two_rows(self.inner.main.top.values, self.inner.main.bottom.values)
}
fn preprocessed(&self) -> &Self::M {
self.inner.preprocessed()
}
#[inline]
fn public_values(&self) -> &[Self::PublicVar] {
Those builder and folder snippets show how the contract was used in practice.
- The verifier built a
VerticalPairfrom local/next openings, then immediately converted it into aRowWindowfor the AIR-facing API. - Lookup and prover folders did the same thing for main and preprocessed data.
So the post-#1357 design can be summarized as: store whatever representation is convenient internally, but expose RowWindow at the AIR boundary.
Two days later, commit 7ca1cdff refined the model without abandoning it.
The important change here is not from RowWindow to Matrix. Instead, the single associated type for trace windows was split into two:
MainWindowPreprocessedWindow
That made the API more flexible while keeping the two-row WindowAccess contract intact.
git show 7ca1cdff:air/src/air.rs | sed -n '220,340p'pub trait Air<AB: AirBuilder>: BaseAir<AB::F> {
/// Evaluate all AIR constraints using the provided builder.
///
/// The builder provides both the trace on which the constraints
/// are evaluated on as well as the method of accumulating the
/// constraint evaluations.
///
/// # Arguments
/// - `builder`: Mutable reference to an `AirBuilder` for defining constraints.
fn eval(&self, builder: &mut AB);
}
/// A builder which contains both a trace on which AIR constraints can be evaluated as well as a method of accumulating the AIR constraint evaluations.
///
/// Supports both symbolic cases where the constraints are treated as polynomials and collected into a vector
/// as well cases where the constraints are evaluated on an evaluation trace and combined using randomness.
pub trait AirBuilder: Sized {
/// Underlying field type.
///
/// This should usually implement `Field` but there are a few edge cases (mostly involving `PackedFields`) where
/// it may only implement `PrimeCharacteristicRing`.
type F: PrimeCharacteristicRing + Sync;
/// Serves as the output type for an AIR constraint evaluation.
type Expr: Algebra<Self::F> + Algebra<Self::Var>;
/// The type of the variable appearing in the trace matrix.
///
/// Serves as the input type for an AIR constraint evaluation.
type Var: Into<Self::Expr>
+ Copy
+ Send
+ Sync
+ Add<Self::F, Output = Self::Expr>
+ Add<Self::Var, Output = Self::Expr>
+ Add<Self::Expr, Output = Self::Expr>
+ Sub<Self::F, Output = Self::Expr>
+ Sub<Self::Var, Output = Self::Expr>
+ Sub<Self::Expr, Output = Self::Expr>
+ Mul<Self::F, Output = Self::Expr>
+ Mul<Self::Var, Output = Self::Expr>
+ Mul<Self::Expr, Output = Self::Expr>;
/// Two-row window over the preprocessed trace columns.
type PreprocessedWindow: WindowAccess<Self::Var> + Clone;
/// Two-row window over the main trace columns.
type MainWindow: WindowAccess<Self::Var> + Clone;
/// Variable type for public values.
type PublicVar: Into<Self::Expr> + Copy;
/// Return the current and next row slices of the main (primary) trace.
fn main(&self) -> Self::MainWindow;
/// Return the preprocessed registers as a two-row window.
///
/// When no preprocessed columns exist, this returns a zero-width window.
fn preprocessed(&self) -> &Self::PreprocessedWindow;
/// Expression evaluating to a non-zero value only on the first row.
fn is_first_row(&self) -> Self::Expr;
/// Expression evaluating to a non-zero value only on the last row.
fn is_last_row(&self) -> Self::Expr;
/// Expression evaluating to zero only on the last row.
fn is_transition(&self) -> Self::Expr {
self.is_transition_window(2)
}
/// Expression evaluating to zero only on the last `size - 1` rows.
///
/// # Panics
///
/// Implementations should panic if `size > 2`, since only two-row
/// windows are currently supported.
fn is_transition_window(&self, size: usize) -> Self::Expr;
/// Returns a sub-builder whose constraints are enforced only when `condition` is nonzero.
fn when<I: Into<Self::Expr>>(&mut self, condition: I) -> FilteredAirBuilder<'_, Self> {
FilteredAirBuilder {
inner: self,
condition: condition.into(),
}
}
/// Returns a sub-builder whose constraints are enforced only when `x != y`.
fn when_ne<I1: Into<Self::Expr>, I2: Into<Self::Expr>>(
&mut self,
x: I1,
y: I2,
) -> FilteredAirBuilder<'_, Self> {
self.when(x.into() - y.into())
}
/// Returns a sub-builder whose constraints are enforced only on the first row.
fn when_first_row(&mut self) -> FilteredAirBuilder<'_, Self> {
self.when(self.is_first_row())
}
/// Returns a sub-builder whose constraints are enforced only on the last row.
fn when_last_row(&mut self) -> FilteredAirBuilder<'_, Self> {
self.when(self.is_last_row())
}
/// Returns a sub-builder whose constraints are enforced on all rows except the last.
fn when_transition(&mut self) -> FilteredAirBuilder<'_, Self> {
self.when(self.is_transition())
}
/// Like [`when_transition`](Self::when_transition), but requires a window of `size` rows.
fn when_transition_window(&mut self, size: usize) -> FilteredAirBuilder<'_, Self> {
self.when(self.is_transition_window(size))
}
/// Assert that the given element is zero.
///
/// Where possible, batching multiple assert_zero calls
/// into a single assert_zeros call will improve performance.
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I);
git show 7ca1cdff:lookup/src/lookup_traits.rs | sed -n '40,130p' fn constraint_degree<F: Field>(&self, context: &Lookup<F>) -> usize;
}
/// A builder to generate the lookup traces, given the main trace, public values and permutation challenges.
pub struct LookupTraceBuilder<'a, SC: StarkGenericConfig> {
main: ViewPair<'a, Val<SC>>,
preprocessed: RowWindow<'a, Val<SC>>,
public_values: &'a [Val<SC>],
permutation_challenges: &'a [SC::Challenge],
height: usize,
row: usize,
}
impl<'a, SC: StarkGenericConfig> LookupTraceBuilder<'a, SC> {
pub fn new(
main: ViewPair<'a, Val<SC>>,
preprocessed: ViewPair<'a, Val<SC>>,
public_values: &'a [Val<SC>],
permutation_challenges: &'a [SC::Challenge],
height: usize,
row: usize,
) -> Self {
Self {
main,
preprocessed: RowWindow::from_two_rows(
preprocessed.top.values,
preprocessed.bottom.values,
),
public_values,
permutation_challenges,
height,
row,
}
}
}
impl<'a, SC: StarkGenericConfig> AirBuilder for LookupTraceBuilder<'a, SC> {
type F = Val<SC>;
type Expr = Val<SC>;
type Var = Val<SC>;
type PreprocessedWindow = RowWindow<'a, Val<SC>>;
type MainWindow = RowWindow<'a, Val<SC>>;
type PublicVar = Val<SC>;
#[inline]
fn main(&self) -> Self::MainWindow {
RowWindow::from_two_rows(self.main.top.values, self.main.bottom.values)
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
&self.preprocessed
}
#[inline]
fn is_first_row(&self) -> Self::Expr {
Self::F::from_bool(self.row == 0)
}
#[inline]
fn is_last_row(&self) -> Self::Expr {
Self::F::from_bool(self.row + 1 == self.height)
}
#[inline]
fn is_transition_window(&self, size: usize) -> Self::Expr {
assert!(size <= 2, "only two-row windows are supported, got {size}");
Self::F::from_bool(self.row + 1 < self.height)
}
#[inline]
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
assert!(x.into() == Self::F::ZERO);
}
#[inline]
fn assert_zeros<const N: usize, I: Into<Self::Expr>>(&mut self, array: [I; N]) {
for item in array {
assert!(item.into() == Self::F::ZERO);
}
}
#[inline]
fn public_values(&self) -> &[Self::PublicVar] {
self.public_values
}
}
impl<SC: StarkGenericConfig> ExtensionBuilder for LookupTraceBuilder<'_, SC> {
type EF = SC::Challenge;
type ExprEF = SC::Challenge;
type VarEF = SC::Challenge;
git show 7ca1cdff:uni-stark/src/sub_builder.rs | sed -n '1,110p'//! Helpers for restricting a builder to a subset of trace columns.
//!
//! The uni-STARK builders often need to enforce constraints that refer to only a slice of the main
//! trace. [`SubSliced`] offers a cheap view over a subset of columns, and [`SubAirBuilder`] wires
//! that view into any [`AirBuilder`] implementation so a sub-air can be evaluated independently
//! without copying trace data.
// Code inpsired from SP1 with additional modifications:
// https://github.com/succinctlabs/sp1/blob/main/crates/stark/src/air/sub_builder.rs
use core::marker::PhantomData;
use core::ops::Range;
use p3_air::{AirBuilder, BaseAir, WindowAccess};
/// A column-restricted view over a trace window.
///
/// Wraps an inner window and exposes only the columns within
/// the given range. Lets a sub-AIR see a contiguous subset
/// of the parent trace without copying data.
#[derive(Clone)]
pub struct SubSliced<W, T> {
window: W,
range: Range<usize>,
_marker: PhantomData<T>,
}
impl<W: WindowAccess<T>, T> WindowAccess<T> for SubSliced<W, T> {
#[inline]
fn current_slice(&self) -> &[T] {
&self.window.current_slice()[self.range.clone()]
}
#[inline]
fn next_slice(&self) -> &[T] {
&self.window.next_slice()[self.range.clone()]
}
}
/// Evaluates a sub-AIR against a restricted slice of the parent trace.
///
/// This is useful whenever a standalone component AIR is embedded in a larger system but only owns
/// a few columns. `SubAirBuilder` reuses the parent builder for bookkeeping so witness generation
/// and constraint enforcement stay in sync.
pub struct SubAirBuilder<'a, AB: AirBuilder, SubAir: BaseAir<AB::F>, T> {
/// Mutable reference to the parent builder.
inner: &'a mut AB,
/// Column range (in the parent trace) that the sub-AIR is allowed to see.
column_range: Range<usize>,
/// Marker for the sub-AIR and witness type.
_phantom: core::marker::PhantomData<(SubAir, T)>,
}
impl<'a, AB: AirBuilder, SubAir: BaseAir<AB::F>, T> SubAirBuilder<'a, AB, SubAir, T> {
/// Create a new [`SubAirBuilder`] exposing only `column_range` to the sub-AIR.
///
/// The range must lie entirely inside the parent trace width.
#[must_use]
pub const fn new(inner: &'a mut AB, column_range: Range<usize>) -> Self {
Self {
inner,
column_range,
_phantom: core::marker::PhantomData,
}
}
}
/// Implements `AirBuilder` for `SubAirBuilder`.
impl<AB: AirBuilder, SubAir: BaseAir<AB::F>, F> AirBuilder for SubAirBuilder<'_, AB, SubAir, F> {
type F = AB::F;
type Expr = AB::Expr;
type Var = AB::Var;
type PreprocessedWindow = AB::PreprocessedWindow;
type MainWindow = SubSliced<AB::MainWindow, AB::Var>;
type PublicVar = AB::PublicVar;
fn main(&self) -> Self::MainWindow {
SubSliced {
window: self.inner.main(),
range: self.column_range.clone(),
_marker: PhantomData,
}
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
self.inner.preprocessed()
}
fn is_first_row(&self) -> Self::Expr {
self.inner.is_first_row()
}
fn is_last_row(&self) -> Self::Expr {
self.inner.is_last_row()
}
fn is_transition_window(&self, size: usize) -> Self::Expr {
assert!(size <= 2, "only two-row windows are supported, got {size}");
self.inner.is_transition()
}
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
self.inner.assert_zero(x.into());
}
fn public_values(&self) -> &[Self::PublicVar] {
self.inner.public_values()
}
This intermediate design is worth pausing on because it is the baseline that the current branch is undoing.
At this point the API said:
- builders still expose windows, not matrices;
- main and preprocessed windows may have different concrete types; and
SubAirBuildernarrows the main window through a small wrapper (SubSliced) that itself still implementsWindowAccess.
That design is narrow but coherent. It keeps AIR evaluation code close to its logical model: "I have two rows and maybe a truncated set of columns."
Commit f999f2ce removes WindowAccess and RowWindow entirely and switches the AIR-facing associated types to p3_matrix::Matrix.
That is a materially different abstraction boundary. Instead of exposing a specialized two-row API, the branch exposes a generic matrix API and relies on every caller to treat row 0 as current and row 1 as next.
sed -n '1,170p' air/src/air.rsuse alloc::vec::Vec;
use core::ops::{Add, Mul, Sub};
use p3_field::{Algebra, Dup, ExtensionField, Field, PrimeCharacteristicRing};
use p3_matrix::Matrix;
use p3_matrix::dense::RowMajorMatrix;
/// The underlying structure of an AIR.
pub trait BaseAir<F>: Sync {
/// The number of columns (a.k.a. registers) in this AIR.
fn width(&self) -> usize;
/// Return an optional preprocessed trace matrix to be included in the prover's trace.
fn preprocessed_trace(&self) -> Option<RowMajorMatrix<F>> {
None
}
/// Which main trace columns have their next row accessed by this AIR's
/// constraints.
///
/// By default this returns every column index, which will require
/// opening all main columns at both `zeta` and `zeta_next`.
///
/// AIRs that only ever read the current main row (and never access an
/// offset-1 main entry) can override this to return an empty vector to
/// allow the prover and verifier to open only at `zeta`.
///
/// # When to override
///
/// - **Return empty**: single-row AIRs where all constraints are
/// evaluated within one row.
/// - **Keep default** (all columns): AIRs with transition constraints
/// that reference `main.next_slice()`.
/// - **Return a subset**: AIRs where only a few columns need next-row
/// access, enabling future per-column opening optimizations.
///
/// # Correctness
///
/// Must be consistent with [`Air::eval`]. Omitting a column index when
/// the AIR actually reads its next row will cause verification failures
/// or, in the worst case, a soundness gap.
fn main_next_row_columns(&self) -> Vec<usize> {
(0..self.width()).collect()
}
/// Which preprocessed trace columns have their next row accessed by this
/// AIR's constraints.
///
/// By default this returns every preprocessed column index, which will
/// require opening preprocessed columns at both `zeta` and `zeta_next`.
///
/// AIRs that only ever read the current preprocessed row (and never
/// access an offset-1 preprocessed entry) can override this to return an
/// empty vector to allow the prover and verifier to open only at `zeta`.
fn preprocessed_next_row_columns(&self) -> Vec<usize> {
self.preprocessed_trace()
.map(|t| (0..t.width).collect())
.unwrap_or_default()
}
/// Optional hint for the number of constraints in this AIR.
///
/// Normally the prover runs a full symbolic evaluation just to count
/// constraints. Overriding this method lets the prover skip that pass.
///
/// The count must cover every constraint asserted during evaluation,
/// including both transition and boundary constraints. It must **not**
/// include lookup or permutation constraints, which are counted
/// separately.
///
/// # Correctness
///
/// The returned value **must** exactly match the actual number of
/// constraints. A wrong count will cause the prover to panic or
/// produce an invalid proof.
///
/// Returns `None` by default, which falls back to symbolic evaluation.
fn num_constraints(&self) -> Option<usize> {
None
}
/// Optional hint for the maximum constraint degree in this AIR.
///
/// The constraint degree is the factor by which trace length N
/// scales the constraint polynomial degree.
///
/// For example, a constraint `x * y * z` where x, y, z are trace
/// variables has degree multiple 3.
///
/// Normally the prover runs a full symbolic evaluation to compute this.
/// Overriding this method lets both the prover and verifier skip that
/// pass when only the degree (not the full constraint list) is needed.
///
/// The value must be an upper bound on the degree multiple of every
/// constraint (base and extension). It does not need to be tight, but
/// overestimating wastes prover work (larger quotient domain).
///
/// # Correctness
///
/// The returned value **must** be >= the actual max constraint degree.
/// A value that is too small will cause the prover to produce an
/// invalid proof.
///
/// Returns `None` by default, which falls back to symbolic evaluation.
fn max_constraint_degree(&self) -> Option<usize> {
None
}
/// Return the number of expected public values.
fn num_public_values(&self) -> usize {
0
}
}
/// An algebraic intermediate representation (AIR) definition.
///
/// Contains an evaluation function for computing the constraints of the AIR.
/// This function can be applied to an evaluation trace in which case each
/// constraint will compute a particular value or it can be applied symbolically
/// with each constraint computing a symbolic expression.
pub trait Air<AB: AirBuilder>: BaseAir<AB::F> {
/// Evaluate all AIR constraints using the provided builder.
///
/// The builder provides both the trace on which the constraints
/// are evaluated on as well as the method of accumulating the
/// constraint evaluations.
///
/// # Arguments
/// - `builder`: Mutable reference to an `AirBuilder` for defining constraints.
fn eval(&self, builder: &mut AB);
}
/// A builder which contains both a trace on which AIR constraints can be evaluated as well as a method of accumulating the AIR constraint evaluations.
///
/// Supports both symbolic cases where the constraints are treated as polynomials and collected into a vector
/// as well cases where the constraints are evaluated on an evaluation trace and combined using randomness.
pub trait AirBuilder: Sized {
/// Underlying field type.
///
/// This should usually implement `Field` but there are a few edge cases (mostly involving `PackedFields`) where
/// it may only implement `PrimeCharacteristicRing`.
type F: PrimeCharacteristicRing + Sync;
/// Serves as the output type for an AIR constraint evaluation.
type Expr: Algebra<Self::F> + Algebra<Self::Var>;
/// The type of the variable appearing in the trace matrix.
///
/// Serves as the input type for an AIR constraint evaluation.
type Var: Into<Self::Expr>
+ Copy
+ Send
+ Sync
+ Add<Self::F, Output = Self::Expr>
+ Add<Self::Var, Output = Self::Expr>
+ Add<Self::Expr, Output = Self::Expr>
+ Sub<Self::F, Output = Self::Expr>
+ Sub<Self::Var, Output = Self::Expr>
+ Sub<Self::Expr, Output = Self::Expr>
+ Mul<Self::F, Output = Self::Expr>
+ Mul<Self::Var, Output = Self::Expr>
+ Mul<Self::Expr, Output = Self::Expr>;
/// Two-row window over the preprocessed trace columns.
type PreprocessedWindow: Matrix<Self::Var> + Clone;
/// Two-row window over the main trace columns.
type MainWindow: Matrix<Self::Var> + Clone;
/// Variable type for public values.
type PublicVar: Into<Self::Expr> + Copy;
sed -n '1,120p' uni-stark/src/folder.rsuse alloc::vec::Vec;
use p3_air::{AirBuilder, ExtensionBuilder};
use p3_field::{Algebra, BasedVectorSpace};
use p3_matrix::dense::RowMajorMatrixView;
use p3_matrix::stack::ViewPair;
use crate::{PackedChallenge, PackedVal, StarkGenericConfig, Val};
/// Packed constraint folder for SIMD-optimized prover evaluation.
///
/// Uses packed types to evaluate constraints on multiple domain points simultaneously.
///
/// Collects constraints during `air.eval()` into separate base/ext vectors, then
/// combines them in [`Self::finalize_constraints`] using decomposed alpha powers and
/// `batched_linear_combination` for efficient SIMD accumulation.
#[derive(Debug)]
pub struct ProverConstraintFolder<'a, SC: StarkGenericConfig> {
/// The [`RowMajorMatrixView`] containing rows on which the constraint polynomial is evaluated.
pub main: RowMajorMatrixView<'a, PackedVal<SC>>,
/// The preprocessed columns as a [`RowMajorMatrixView`].
/// Zero-width when the AIR has no preprocessed trace.
pub preprocessed: RowMajorMatrixView<'a, PackedVal<SC>>,
/// Public inputs to the [AIR](`p3_air::Air`) implementation.
pub public_values: &'a [Val<SC>],
/// Evaluations of the first-row selector polynomial.
/// Non-zero only on the first trace row.
pub is_first_row: PackedVal<SC>,
/// Evaluations of the last-row selector polynomial.
/// Non-zero only on the last trace row.
pub is_last_row: PackedVal<SC>,
/// Evaluations of the transition selector polynomial.
/// Zero only on the last trace row.
pub is_transition: PackedVal<SC>,
/// Base-field alpha powers, reordered to match base constraint emission order.
/// `base_alpha_powers[d][j]` = d-th basis coefficient of alpha power for j-th base constraint.
pub base_alpha_powers: &'a [Vec<Val<SC>>],
/// Extension-field alpha powers, reordered to match ext constraint emission order.
pub ext_alpha_powers: &'a [SC::Challenge],
/// Collected base-field constraints for this row
pub base_constraints: Vec<PackedVal<SC>>,
/// Collected extension-field constraints for this row
pub ext_constraints: Vec<PackedChallenge<SC>>,
/// Current constraint index being processed (debug-only bookkeeping)
pub constraint_index: usize,
/// Total number of constraints in the AIR (debug-only bookkeeping)
pub constraint_count: usize,
}
/// Handles constraint verification for the verifier in a STARK system.
///
/// Similar to [`ProverConstraintFolder`] but operates on committed values rather than the full trace,
/// using a more efficient accumulation method for verification.
#[derive(Debug)]
pub struct VerifierConstraintFolder<'a, SC: StarkGenericConfig> {
/// Pair of consecutive rows from the committed polynomial evaluations as a [`ViewPair`].
pub main: ViewPair<'a, SC::Challenge>,
/// The preprocessed columns as a [`ViewPair`].
/// Zero-width when the AIR has no preprocessed trace.
pub preprocessed: ViewPair<'a, SC::Challenge>,
/// Public values that are inputs to the computation
pub public_values: &'a [Val<SC>],
/// Evaluations of the first-row selector polynomial.
/// Non-zero only on the first trace row.
pub is_first_row: SC::Challenge,
/// Evaluations of the last-row selector polynomial.
/// Non-zero only on the last trace row.
pub is_last_row: SC::Challenge,
/// Evaluations of the transition selector polynomial.
/// Zero only on the last trace row.
pub is_transition: SC::Challenge,
/// Single challenge value used for constraint combination
pub alpha: SC::Challenge,
/// Running accumulator for all constraints
pub accumulator: SC::Challenge,
}
impl<SC: StarkGenericConfig> ProverConstraintFolder<'_, SC> {
/// Combine all collected constraints with their pre-computed alpha powers.
///
/// Base constraints use [`Algebra::batched_linear_combination`] per basis dimension,
/// decomposing the extension-field multiply into D base-field SIMD dot products.
/// Extension constraints use the same method with scalar EF coefficients.
///
/// We keep base and extension constraints separate because the base constraints can
/// stay in the base field and use packed SIMD arithmetic. Decomposing EF powers of
/// `alpha` into base-field coordinates turns the base-field fold into a small number
/// of packed dot-products, avoiding repeated cross-field promotions.
#[inline]
pub fn finalize_constraints(&self) -> PackedChallenge<SC> {
debug_assert_eq!(self.constraint_index, self.constraint_count);
let base = &self.base_constraints;
let base_powers = self.base_alpha_powers;
let acc = PackedChallenge::<SC>::from_basis_coefficients_fn(|d| {
PackedVal::<SC>::batched_linear_combination(base, &base_powers[d])
});
acc + PackedChallenge::<SC>::batched_linear_combination(
&self.ext_constraints,
self.ext_alpha_powers,
)
}
}
impl<'a, SC: StarkGenericConfig> AirBuilder for ProverConstraintFolder<'a, SC> {
type F = Val<SC>;
type Expr = PackedVal<SC>;
type Var = PackedVal<SC>;
type PreprocessedWindow = RowMajorMatrixView<'a, PackedVal<SC>>;
type MainWindow = RowMajorMatrixView<'a, PackedVal<SC>>;
type PublicVar = Val<SC>;
#[inline]
fn main(&self) -> Self::MainWindow {
self.main
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
&self.preprocessed
}
sed -n '1,120p' lookup/src/folder.rsuse p3_air::{AirBuilder, ExtensionBuilder, PermutationAirBuilder};
use p3_matrix::dense::RowMajorMatrixView;
use p3_matrix::stack::ViewPair;
use p3_uni_stark::{
PackedChallenge, PackedVal, ProverConstraintFolder, StarkGenericConfig, Val,
VerifierConstraintFolder,
};
pub struct ProverConstraintFolderWithLookups<'a, SC: StarkGenericConfig> {
pub inner: ProverConstraintFolder<'a, SC>,
pub permutation: RowMajorMatrixView<'a, PackedChallenge<SC>>,
pub permutation_challenges: &'a [PackedChallenge<SC>],
pub permutation_values: &'a [PackedChallenge<SC>],
}
impl<'a, SC: StarkGenericConfig> AirBuilder for ProverConstraintFolderWithLookups<'a, SC> {
type F = Val<SC>;
type Expr = PackedVal<SC>;
type Var = PackedVal<SC>;
type PreprocessedWindow = RowMajorMatrixView<'a, PackedVal<SC>>;
type MainWindow = RowMajorMatrixView<'a, PackedVal<SC>>;
type PublicVar = Val<SC>;
fn main(&self) -> Self::MainWindow {
self.inner.main
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
self.inner.preprocessed()
}
#[inline]
fn is_first_row(&self) -> Self::Expr {
self.inner.is_first_row
}
#[inline]
fn is_last_row(&self) -> Self::Expr {
self.inner.is_last_row
}
#[inline]
fn is_transition_window(&self, size: usize) -> Self::Expr {
assert!(size <= 2, "only two-row windows are supported, got {size}");
self.inner.is_transition
}
#[inline]
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
self.inner.assert_zero(x);
}
#[inline]
fn assert_zeros<const N: usize, I: Into<Self::Expr>>(&mut self, array: [I; N]) {
self.inner.assert_zeros(array);
}
#[inline]
fn public_values(&self) -> &[Self::PublicVar] {
self.inner.public_values
}
}
impl<SC: StarkGenericConfig> ExtensionBuilder for ProverConstraintFolderWithLookups<'_, SC> {
type EF = SC::Challenge;
type ExprEF = PackedChallenge<SC>;
type VarEF = PackedChallenge<SC>;
fn assert_zero_ext<I>(&mut self, x: I)
where
I: Into<Self::ExprEF>,
{
self.inner.assert_zero_ext(x);
}
}
impl<'a, SC: StarkGenericConfig> PermutationAirBuilder
for ProverConstraintFolderWithLookups<'a, SC>
{
type RandomVar = PackedChallenge<SC>;
type MP = RowMajorMatrixView<'a, PackedChallenge<SC>>;
type PermutationVar = PackedChallenge<SC>;
fn permutation(&self) -> Self::MP {
self.permutation
}
fn permutation_randomness(&self) -> &[PackedChallenge<SC>] {
self.permutation_challenges
}
fn permutation_values(&self) -> &[PackedChallenge<SC>] {
self.permutation_values
}
}
pub struct VerifierConstraintFolderWithLookups<'a, SC: StarkGenericConfig> {
pub inner: VerifierConstraintFolder<'a, SC>,
pub permutation: ViewPair<'a, SC::Challenge>,
pub permutation_challenges: &'a [SC::Challenge],
pub permutation_values: &'a [SC::Challenge],
}
impl<'a, SC: StarkGenericConfig> AirBuilder for VerifierConstraintFolderWithLookups<'a, SC> {
type F = Val<SC>;
type Expr = SC::Challenge;
type Var = SC::Challenge;
type PublicVar = Val<SC>;
type PreprocessedWindow = ViewPair<'a, SC::Challenge>;
type MainWindow = ViewPair<'a, SC::Challenge>;
fn main(&self) -> Self::MainWindow {
self.inner.main
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
self.inner.preprocessed()
}
sed -n '40,190p' lookup/src/lookup_traits.rs fn constraint_degree<F: Field>(&self, context: &Lookup<F>) -> usize;
}
/// A builder to generate the lookup traces, given the main trace, public values and permutation challenges.
pub struct LookupTraceBuilder<'a, SC: StarkGenericConfig> {
main: ViewPair<'a, Val<SC>>,
preprocessed: ViewPair<'a, Val<SC>>,
public_values: &'a [Val<SC>],
permutation_challenges: &'a [SC::Challenge],
height: usize,
row: usize,
}
impl<'a, SC: StarkGenericConfig> LookupTraceBuilder<'a, SC> {
pub const fn new(
main: ViewPair<'a, Val<SC>>,
preprocessed: ViewPair<'a, Val<SC>>,
public_values: &'a [Val<SC>],
permutation_challenges: &'a [SC::Challenge],
height: usize,
row: usize,
) -> Self {
Self {
main,
preprocessed,
public_values,
permutation_challenges,
height,
row,
}
}
}
impl<'a, SC: StarkGenericConfig> AirBuilder for LookupTraceBuilder<'a, SC> {
type F = Val<SC>;
type Expr = Val<SC>;
type Var = Val<SC>;
type PreprocessedWindow = ViewPair<'a, Val<SC>>;
type MainWindow = ViewPair<'a, Val<SC>>;
type PublicVar = Val<SC>;
#[inline]
fn main(&self) -> Self::MainWindow {
self.main
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
&self.preprocessed
}
#[inline]
fn is_first_row(&self) -> Self::Expr {
Self::F::from_bool(self.row == 0)
}
#[inline]
fn is_last_row(&self) -> Self::Expr {
Self::F::from_bool(self.row + 1 == self.height)
}
#[inline]
fn is_transition_window(&self, size: usize) -> Self::Expr {
assert!(size <= 2, "only two-row windows are supported, got {size}");
Self::F::from_bool(self.row + 1 < self.height)
}
#[inline]
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
assert!(x.into() == Self::F::ZERO);
}
#[inline]
fn assert_zeros<const N: usize, I: Into<Self::Expr>>(&mut self, array: [I; N]) {
for item in array {
assert!(item.into() == Self::F::ZERO);
}
}
#[inline]
fn public_values(&self) -> &[Self::PublicVar] {
self.public_values
}
}
impl<SC: StarkGenericConfig> ExtensionBuilder for LookupTraceBuilder<'_, SC> {
type EF = SC::Challenge;
type ExprEF = SC::Challenge;
type VarEF = SC::Challenge;
fn assert_zero_ext<I: Into<Self::ExprEF>>(&mut self, x: I) {
assert!(x.into() == SC::Challenge::ZERO);
}
}
impl<'a, SC: StarkGenericConfig> PermutationAirBuilder for LookupTraceBuilder<'a, SC> {
type MP = ViewPair<'a, SC::Challenge>;
type RandomVar = SC::Challenge;
type PermutationVar = SC::Challenge;
fn permutation(&self) -> Self::MP {
panic!("we should not be accessing the permutation matrix while building it");
}
fn permutation_randomness(&self) -> &[SC::Challenge] {
self.permutation_challenges
}
fn permutation_values(&self) -> &[SC::Challenge] {
&[]
}
}
/// Evaluates a symbolic expression in the context of an AIR builder.
///
/// Converts `SymbolicExpression<F>` to the builder's expression type `AB::Expr`.
pub fn symbolic_to_expr<AB>(builder: &AB, expr: &SymbolicExpression<AB::F>) -> AB::Expr
where
AB: AirBuilder + PermutationAirBuilder,
{
match expr {
SymbolicExpression::Leaf(leaf) => match leaf {
BaseLeaf::Variable(v) => match v.entry {
BaseEntry::Main { offset } => {
let main = builder.main();
match offset {
0 => main.get(0, v.index).unwrap().into(),
1 => main.get(1, v.index).unwrap().into(),
_ => panic!("Cannot have expressions involving more than two rows."),
}
}
BaseEntry::Periodic => {
panic!("Periodic columns are not supported in lookup resolution")
}
BaseEntry::Public => builder.public_values()[v.index].into(),
BaseEntry::Preprocessed { offset } => {
let prep = builder.preprocessed();
match offset {
0 => prep.get(0, v.index).unwrap().into(),
1 => prep.get(1, v.index).unwrap().into(),
_ => panic!("Cannot have expressions involving more than two rows."),
}
}
},
BaseLeaf::IsFirstRow => {
warn!("IsFirstRow is not normalized");
builder.is_first_row()
}
BaseLeaf::IsLastRow => {
warn!("IsLastRow is not normalized");
builder.is_last_row()
The migration is conceptually simple:
main.current(i)becomesmain.get(0, i).main.next(i)becomesmain.get(1, i).main.current_slice()becomesmain.row_slice(0).unwrap().main.next_slice()becomesmain.row_slice(1).unwrap().
In many local call sites that really is simpler, especially when the underlying representation is already a RowMajorMatrixView or ViewPair.
The tradeoff is that the API loses a semantic guarantee. A Matrix can mean many things; a WindowAccess means exactly two rows with current/next intent.
sed -n '1,140p' matrix/src/stack.rsuse core::ops::Deref;
use crate::Matrix;
use crate::bitrev::BitReversibleMatrix;
use crate::dense::RowMajorMatrixView;
/// A type alias representing a vertical composition of two row-major matrix views.
///
/// `ViewPair` combines two [`RowMajorMatrixView`]'s with the same element type `T`
/// and lifetime `'a` into a single virtual matrix stacked vertically.
///
/// Both views must have the same width; the resulting view has a height equal
/// to the sum of the two original heights.
pub type ViewPair<'a, T> = VerticalPair<RowMajorMatrixView<'a, T>, RowMajorMatrixView<'a, T>>;
/// A matrix composed by stacking two matrices vertically, one on top of the other.
///
/// Both matrices must have the same `width`.
/// The resulting matrix has dimensions:
/// - `width`: The same as the inputs.
/// - `height`: The sum of the `heights` of the input matrices.
///
/// Element access and iteration will first access the rows of the top matrix,
/// followed by the rows of the bottom matrix.
#[derive(Copy, Clone, Debug)]
pub struct VerticalPair<Top, Bottom> {
/// The top matrix in the vertical composition.
pub top: Top,
/// The bottom matrix in the vertical composition.
pub bottom: Bottom,
}
/// A matrix composed by placing two matrices side-by-side horizontally.
///
/// Both matrices must have the same `height`.
/// The resulting matrix has dimensions:
/// - `width`: The sum of the `widths` of the input matrices.
/// - `height`: The same as the inputs.
///
/// Element access and iteration for a given row `i` will first access the elements in the `i`'th row of the left matrix,
/// followed by elements in the `i'`th row of the right matrix.
#[derive(Copy, Clone, Debug)]
pub struct HorizontalPair<Left, Right> {
/// The left matrix in the horizontal composition.
pub left: Left,
/// The right matrix in the horizontal composition.
pub right: Right,
}
impl<Top, Bottom> VerticalPair<Top, Bottom> {
/// Create a new `VerticalPair` by stacking two matrices vertically.
///
/// # Panics
/// Panics if the two matrices do not have the same width (i.e., number of columns),
/// since vertical composition requires column alignment.
///
/// # Returns
/// A `VerticalPair` that represents the combined matrix.
pub fn new<T>(top: Top, bottom: Bottom) -> Self
where
T: Send + Sync + Clone,
Top: Matrix<T>,
Bottom: Matrix<T>,
{
assert_eq!(top.width(), bottom.width());
Self { top, bottom }
}
}
impl<Left, Right> HorizontalPair<Left, Right> {
/// Create a new `HorizontalPair` by joining two matrices side by side.
///
/// # Panics
/// Panics if the two matrices do not have the same height (i.e., number of rows),
/// since horizontal composition requires row alignment.
///
/// # Returns
/// A `HorizontalPair` that represents the combined matrix.
pub fn new<T>(left: Left, right: Right) -> Self
where
T: Send + Sync + Clone,
Left: Matrix<T>,
Right: Matrix<T>,
{
assert_eq!(left.height(), right.height());
Self { left, right }
}
}
impl<T: Send + Sync + Clone, Top: Matrix<T>, Bottom: Matrix<T>> Matrix<T>
for VerticalPair<Top, Bottom>
{
fn width(&self) -> usize {
self.top.width()
}
fn height(&self) -> usize {
self.top.height() + self.bottom.height()
}
unsafe fn get_unchecked(&self, r: usize, c: usize) -> T {
unsafe {
// Safety: The caller must ensure that r < self.height() and c < self.width()
if r < self.top.height() {
self.top.get_unchecked(r, c)
} else {
self.bottom.get_unchecked(r - self.top.height(), c)
}
}
}
unsafe fn row_unchecked(
&self,
r: usize,
) -> impl IntoIterator<Item = T, IntoIter = impl Iterator<Item = T> + Send + Sync> {
unsafe {
// Safety: The caller must ensure that r < self.height()
if r < self.top.height() {
EitherRow::Left(self.top.row_unchecked(r).into_iter())
} else {
EitherRow::Right(self.bottom.row_unchecked(r - self.top.height()).into_iter())
}
}
}
unsafe fn row_subseq_unchecked(
&self,
r: usize,
start: usize,
end: usize,
) -> impl IntoIterator<Item = T, IntoIter = impl Iterator<Item = T> + Send + Sync> {
unsafe {
// Safety: The caller must ensure that r < self.height() and start <= end <= self.width()
if r < self.top.height() {
EitherRow::Left(self.top.row_subseq_unchecked(r, start, end).into_iter())
} else {
EitherRow::Right(
self.bottom
.row_subseq_unchecked(r - self.top.height(), start, end)
.into_iter(),
sed -n '150,210p' matrix/src/lib.rs r: usize,
start: usize,
end: usize,
) -> impl IntoIterator<Item = T, IntoIter = impl Iterator<Item = T> + Send + Sync> {
unsafe {
self.row_unchecked(r)
.into_iter()
.skip(start)
.take(end - start)
}
}
/// Returns the elements of the `r`-th row as something which can be coerced to a slice.
///
/// Returns `None` if `r >= height()`.
#[inline]
fn row_slice(&self, r: usize) -> Option<impl Deref<Target = [T]>> {
(r < self.height()).then(|| unsafe {
// Safety: Clearly `r < self.height()`.
self.row_slice_unchecked(r)
})
}
/// Returns the elements of the `r`-th row as something which can be coerced to a slice.
///
/// For a safe alternative, see [`row_slice`].
///
/// # Safety
/// The caller must ensure that `r < self.height()`.
/// Breaking this assumption is considered undefined behaviour.
#[inline]
unsafe fn row_slice_unchecked(&self, r: usize) -> impl Deref<Target = [T]> {
unsafe { self.row_subslice_unchecked(r, 0, self.width()) }
}
/// Returns a subset of elements of the `r`-th row as something which can be coerced to a slice.
///
/// When `start = 0` and `end = width()`, this is equivalent to [`row_slice_unchecked`].
///
/// For a safe alternative, see [`row_slice`].
///
/// # Safety
/// The caller must ensure that `r < self.height()` and `start <= end <= self.width()`.
/// Breaking any of these assumptions is considered undefined behaviour.
#[inline]
unsafe fn row_subslice_unchecked(
&self,
r: usize,
start: usize,
end: usize,
) -> impl Deref<Target = [T]> {
unsafe {
self.row_subseq_unchecked(r, start, end)
.into_iter()
.collect_vec()
}
}
/// Returns an iterator over all rows in the matrix.
#[inline]
fn rows(&self) -> impl Iterator<Item = impl Iterator<Item = T>> + Send + Sync {
Those matrix snippets explain the new semantics.
ViewPair is just a VerticalPair<RowMajorMatrixView, RowMajorMatrixView>. Its height is the sum of the two inner heights, and row_slice(r) succeeds only when r < height().
That is the root of one of the regressions later on: a pair of zero-height matrices is not a two-row empty window. It is a zero-row matrix.
The user question about ref-cast is a good one, but it applies to a narrower part of the problem than the branch itself.
The ref-cast README shows a pattern for safely casting &T to &U when U is a #[repr(transparent)] wrapper around a single field of type T, including unsized slice-backed view types.
That is relevant for the "typed row view" pattern in the AIRs, where a flat row slice is reinterpreted as a typed columns struct.
curl -Ls --max-time 20 https://raw.githubusercontent.com/dtolnay/ref-cast/master/README.md | sed -n '1,120p'RefCast
=======
[<img alt="github" src="https://img.shields.io/badge/github-dtolnay/ref--cast-8da0cb?style=for-the-badge&labelColor=555555&logo=github" height="20">](https://github.com/dtolnay/ref-cast)
[<img alt="crates.io" src="https://img.shields.io/crates/v/ref-cast.svg?style=for-the-badge&color=fc8d62&logo=rust" height="20">](https://crates.io/crates/ref-cast)
[<img alt="docs.rs" src="https://img.shields.io/badge/docs.rs-ref--cast-66c2a5?style=for-the-badge&labelColor=555555&logo=docs.rs" height="20">](https://docs.rs/ref-cast)
[<img alt="build status" src="https://img.shields.io/github/actions/workflow/status/dtolnay/ref-cast/ci.yml?branch=master&style=for-the-badge" height="20">](https://github.com/dtolnay/ref-cast/actions?query=branch%3Amaster)
Safely cast `&T` to `&U` where the struct `U` contains a single field of
type `T`.
```toml
[dependencies]
ref-cast = "1.0"
```
## Basic example
```rust
use ref_cast::RefCast;
#[derive(RefCast)]
#[repr(transparent)]
struct U(String);
fn main() {
let s = String::new();
// Safely cast from `&String` to `&U`.
let u = U::ref_cast(&s);
}
```
Note that `#[repr(transparent)]` is required in order for the conversion to be
sound. The derive macro will refuse to compile if that is not present.
## Realistic example
Suppose we have a multidimensional array represented in a flat buffer in
row-major order for performance reasons, but we want to expose an indexing
operation that works in column-major order because it is more intuitive in
the context of our application.
```rust
const MAP_WIDTH: usize = 4;
struct Tile(u8);
struct TileMap {
storage: Vec<Tile>,
}
// `tilemap[x][y]` should give us `tilemap.storage[y * MAP_WIDTH + x]`.
```
The signature of the [`Index`] trait in Rust is such that the output is
forced to be borrowed from the type being indexed. So something like the
following is not going to work.
[`Index`]: https://doc.rust-lang.org/std/ops/trait.Index.html
```rust
struct Column<'a> {
tilemap: &'a TileMap,
x: usize,
}
// Does not work! The output of Index must be a reference that is
// borrowed from self. Here the type Column is not a reference.
impl Index<usize> for TileMap {
fn index(&self, x: usize) -> Column {
assert!(x < MAP_WIDTH);
Column { tilemap: self, x }
}
}
impl<'a> Index<usize> for Column<'a> {
fn index(&self, y: usize) -> &Tile {
&self.tilemap.storage[y * MAP_WIDTH + self.x]
}
}
```
Here is a working approach using `RefCast`.
```rust
#[derive(RefCast)]
#[repr(transparent)]
struct Strided([Tile]);
// Implement `tilemap[x][y]` as `tilemap[x..][y * MAP_WIDTH]`.
impl Index<usize> for TileMap {
type Output = Strided;
fn index(&self, x: usize) -> &Self::Output {
assert!(x < MAP_WIDTH);
Strided::ref_cast(&self.storage[x..])
}
}
impl Index<usize> for Strided {
type Output = Tile;
fn index(&self, y: usize) -> &Self::Output {
&self.0[y * MAP_WIDTH]
}
}
```
<br>
#### License
<sup>
Licensed under either of <a href="LICENSE-APACHE">Apache License, Version
2.0</a> or <a href="LICENSE-MIT">MIT license</a> at your option.
</sup>
<br>
<sub>
Unless you explicitly state otherwise, any contribution intentionally submitted
sed -n '120,160p' keccak-air/src/columns.rspub const NUM_KECCAK_COLS: usize = size_of::<KeccakCols<u8>>();
pub(crate) const KECCAK_COL_MAP: KeccakCols<usize> = make_col_map();
const fn make_col_map() -> KeccakCols<usize> {
unsafe { transmute(indices_arr::<NUM_KECCAK_COLS>()) }
}
impl<T> Borrow<KeccakCols<T>> for [T] {
fn borrow(&self) -> &KeccakCols<T> {
debug_assert_eq!(self.len(), NUM_KECCAK_COLS);
let (prefix, shorts, suffix) = unsafe { self.align_to::<KeccakCols<T>>() };
debug_assert!(prefix.is_empty(), "Alignment should match");
debug_assert!(suffix.is_empty(), "Alignment should match");
debug_assert_eq!(shorts.len(), 1);
&shorts[0]
}
}
impl<T> BorrowMut<KeccakCols<T>> for [T] {
fn borrow_mut(&mut self) -> &mut KeccakCols<T> {
debug_assert_eq!(self.len(), NUM_KECCAK_COLS);
let (prefix, shorts, suffix) = unsafe { self.align_to_mut::<KeccakCols<T>>() };
debug_assert!(prefix.is_empty(), "Alignment should match");
debug_assert!(suffix.is_empty(), "Alignment should match");
debug_assert_eq!(shorts.len(), 1);
&mut shorts[0]
}
}
sed -n '258,270p' poseidon1-air/src/air.rs && printf '\n---\n' && sed -n '223,231p' poseidon2-air/src/air.rs && printf '\n---\n' && sed -n '40,48p' keccak-air/src/air.rs #[inline]
fn eval(&self, builder: &mut AB) {
// Read the current row as a flat slice, then reinterpret as columns.
let main = builder.main();
let current_row = main.row_slice(0).unwrap();
let local = (*current_row).borrow();
eval::<_, WIDTH, SBOX_DEGREE, SBOX_REGISTERS, HALF_FULL_ROUNDS, PARTIAL_ROUNDS>(
self, builder, local,
);
}
}
---
{
#[inline]
fn eval(&self, builder: &mut AB) {
let main = builder.main();
let current_row = main.row_slice(0).unwrap();
let local = (*current_row).borrow();
eval::<_, _, WIDTH, SBOX_DEGREE, SBOX_REGISTERS, HALF_FULL_ROUNDS, PARTIAL_ROUNDS>(
self, builder, local,
---
fn eval(&self, builder: &mut AB) {
eval_round_flags(builder);
let main = builder.main();
let current_row = main.row_slice(0).unwrap();
let local: &KeccakCols<AB::Var> = (*current_row).borrow();
let next_row = main.row_slice(1).unwrap();
let next: &KeccakCols<AB::Var> = (*next_row).borrow();
Today those AIRs rely on Borrow impls over [T] and align_to-based reinterpretation of flat row slices into typed structs like KeccakCols<T> or Poseidon1Cols<T, ...>.
A ref-cast style refactor could simplify that layer.
The likely target shape would be something like a transparent wrapper around [T] for a specific row-view type, so that a caller could write a safe FooRow::ref_cast(row_slice) instead of maintaining a manual Borrow impl.
What ref-cast would not replace is the matrix/window plumbing:
- it does not stand in for
ViewPair, - it does not express current-vs-next row semantics, and
- it does not solve the
SubAirBuilderor empty-preprocessed-window contracts.
So the answer is: yes, there is a ref-cast opportunity, but it is in the typed row reinterpretation layer, not in the main abstraction change proposed by this branch.
The first bug is the sharpest one.
The old implementation used SubSliced, which sliced row slices directly with self.range.clone(). A reversed range like 5..3 would fail through ordinary slice bounds checks.
The new implementation delegates to HorizontallyTruncated::new_with_range(). That constructor only checks end <= width. It does not check start <= end.
sed -n '1,120p' uni-stark/src/sub_builder.rs//! Helpers for restricting a builder to a subset of trace columns.
//!
//! The uni-STARK builders often need to enforce constraints that refer to only a slice of the main
//! trace. [`SubAirBuilder`] wires a [`HorizontallyTruncated`] view into any [`AirBuilder`]
//! implementation so a sub-air can be evaluated independently without copying trace data.
// Code inspired by SP1 with additional modifications:
// https://github.com/succinctlabs/sp1/blob/main/crates/stark/src/air/sub_builder.rs
use core::ops::Range;
use p3_air::{AirBuilder, BaseAir};
use p3_matrix::horizontally_truncated::HorizontallyTruncated;
/// Evaluates a sub-AIR against a restricted slice of the parent trace.
///
/// This is useful whenever a standalone component AIR is embedded in a larger system but only owns
/// a few columns. `SubAirBuilder` reuses the parent builder for bookkeeping so witness generation
/// and constraint enforcement stay in sync.
pub struct SubAirBuilder<'a, AB: AirBuilder, SubAir: BaseAir<AB::F>, T> {
/// Mutable reference to the parent builder.
inner: &'a mut AB,
/// Column range (in the parent trace) that the sub-AIR is allowed to see.
column_range: Range<usize>,
/// Marker for the sub-AIR and witness type.
_phantom: core::marker::PhantomData<(SubAir, T)>,
}
impl<'a, AB: AirBuilder, SubAir: BaseAir<AB::F>, T> SubAirBuilder<'a, AB, SubAir, T> {
/// Create a new [`SubAirBuilder`] exposing only `column_range` to the sub-AIR.
///
/// The range must lie entirely inside the parent trace width.
#[must_use]
pub const fn new(inner: &'a mut AB, column_range: Range<usize>) -> Self {
Self {
inner,
column_range,
_phantom: core::marker::PhantomData,
}
}
}
/// Implements `AirBuilder` for `SubAirBuilder`.
impl<AB: AirBuilder, SubAir: BaseAir<AB::F>, F> AirBuilder for SubAirBuilder<'_, AB, SubAir, F> {
type F = AB::F;
type Expr = AB::Expr;
type Var = AB::Var;
type PreprocessedWindow = AB::PreprocessedWindow;
type MainWindow = HorizontallyTruncated<AB::Var, AB::MainWindow>;
type PublicVar = AB::PublicVar;
fn main(&self) -> Self::MainWindow {
HorizontallyTruncated::new_with_range(self.inner.main(), self.column_range.clone())
.expect("SubAirBuilder: column range out of bounds for main trace")
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
self.inner.preprocessed()
}
fn is_first_row(&self) -> Self::Expr {
self.inner.is_first_row()
}
fn is_last_row(&self) -> Self::Expr {
self.inner.is_last_row()
}
fn is_transition_window(&self, size: usize) -> Self::Expr {
assert!(size <= 2, "only two-row windows are supported, got {size}");
self.inner.is_transition()
}
fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
self.inner.assert_zero(x.into());
}
fn public_values(&self) -> &[Self::PublicVar] {
self.inner.public_values()
}
}
sed -n '1,120p' matrix/src/horizontally_truncated.rsuse core::marker::PhantomData;
use core::ops::Range;
use crate::Matrix;
use crate::bitrev::BitReversibleMatrix;
/// A matrix wrapper that exposes a contiguous range of columns from an inner matrix.
///
/// This struct:
/// - wraps another matrix,
/// - restricts access to only the columns within the specified `column_range`.
#[derive(Clone)]
pub struct HorizontallyTruncated<T, Inner> {
/// The underlying full matrix being wrapped.
inner: Inner,
/// The range of columns to expose from the inner matrix.
column_range: Range<usize>,
/// Marker for the element type `T`, not used at runtime.
_phantom: PhantomData<T>,
}
impl<T, Inner: Matrix<T>> HorizontallyTruncated<T, Inner>
where
T: Send + Sync + Clone,
{
/// Construct a new horizontally truncated view of a matrix.
///
/// # Arguments
/// - `inner`: The full inner matrix to be wrapped.
/// - `truncated_width`: The number of columns to expose from the start (must be ≤ `inner.width()`).
///
/// This is equivalent to `new_with_range(inner, 0..truncated_width)`.
///
/// Returns `None` if `truncated_width` is greater than the width of the inner matrix.
pub fn new(inner: Inner, truncated_width: usize) -> Option<Self> {
Self::new_with_range(inner, 0..truncated_width)
}
/// Construct a new view exposing a specific column range of a matrix.
///
/// # Arguments
/// - `inner`: The full inner matrix to be wrapped.
/// - `column_range`: The range of columns to expose (must satisfy `column_range.end <= inner.width()`).
///
/// Returns `None` if the column range extends beyond the width of the inner matrix.
pub fn new_with_range(inner: Inner, column_range: Range<usize>) -> Option<Self> {
(column_range.end <= inner.width()).then(|| Self {
inner,
column_range,
_phantom: PhantomData,
})
}
}
impl<T, Inner> Matrix<T> for HorizontallyTruncated<T, Inner>
where
T: Send + Sync + Clone,
Inner: Matrix<T>,
{
/// Returns the number of columns exposed by the truncated matrix.
#[inline(always)]
fn width(&self) -> usize {
self.column_range.len()
}
/// Returns the number of rows in the matrix (same as the inner matrix).
#[inline(always)]
fn height(&self) -> usize {
self.inner.height()
}
#[inline(always)]
unsafe fn get_unchecked(&self, r: usize, c: usize) -> T {
unsafe {
// Safety: The caller must ensure that `c < self.width()` and `r < self.height()`.
//
// We translate the column index by adding `column_range.start`.
self.inner.get_unchecked(r, self.column_range.start + c)
}
}
unsafe fn row_unchecked(
&self,
r: usize,
) -> impl IntoIterator<Item = T, IntoIter = impl Iterator<Item = T> + Send + Sync> {
unsafe {
// Safety: The caller must ensure that `r < self.height()`.
self.inner
.row_subseq_unchecked(r, self.column_range.start, self.column_range.end)
}
}
unsafe fn row_subseq_unchecked(
&self,
r: usize,
start: usize,
end: usize,
) -> impl IntoIterator<Item = T, IntoIter = impl Iterator<Item = T> + Send + Sync> {
unsafe {
// Safety: The caller must ensure that r < self.height() and start <= end <= self.width().
//
// We translate the column indices by adding `column_range.start`.
self.inner.row_subseq_unchecked(
r,
self.column_range.start + start,
self.column_range.start + end,
)
}
}
unsafe fn row_subslice_unchecked(
&self,
r: usize,
start: usize,
end: usize,
) -> impl core::ops::Deref<Target = [T]> {
unsafe {
// Safety: The caller must ensure that `r < self.height()` and `start <= end <= self.width()`.
//
// We translate the column indices by adding `column_range.start`.
That combination is unsafe in a subtle way.
HorizontallyTruncated implements the Matrix trait, whose unsafe row-subslice methods require start <= end <= self.width(). But the wrapper's own stored column_range can now violate start <= end before any caller ever asks for a row.
Once that invalid state exists, later "safe" APIs like row_slice() may funnel into unsafe row-subslice paths under broken assumptions.
So this is not just a cosmetic validation bug. It weakens an invariant that the previous implementation upheld naturally.
The second bug comes from replacing an empty RowWindow with an empty ViewPair built from RowMajorMatrixView::new(&[], 0).
Under the old model, "no preprocessed columns" still meant "two rows, zero width". Under the new model, it means "zero rows, zero width".
sed -n '440,490p' air/src/check_constraints.rs/// supplies permutation data and lookup inputs.
#[allow(unused)] // Suppresses warnings in release mode where this is dead code.
pub fn check_constraints<F, A>(air: &A, main: &RowMajorMatrix<F>, public_values: &[F])
where
F: Field,
A: for<'a> Air<DebugConstraintBuilder<'a, F>>,
{
let height = main.height();
let preprocessed = air.preprocessed_trace();
for row_index in 0..height {
let row_index_next = (row_index + 1) % height;
// SAFETY: both indices are strictly less than `height`.
let local = unsafe { main.row_slice_unchecked(row_index) };
let next = unsafe { main.row_slice_unchecked(row_index_next) };
// Pair the current and next witness rows into a vertical view.
let main_pair = ViewPair::new(
RowMajorMatrixView::new_row(&*local),
RowMajorMatrixView::new_row(&*next),
);
// Pair the preprocessed rows. When the AIR has no preprocessed
// trace we build a zero-width pair so the builder always has a
// valid (possibly empty) preprocessed matrix.
let (prep_local, prep_next) = preprocessed.as_ref().map_or((None, None), |prep| unsafe {
// SAFETY: same index range as the main trace.
(
Some(prep.row_slice_unchecked(row_index)),
Some(prep.row_slice_unchecked(row_index_next)),
)
});
let preprocessed_pair = match (prep_local.as_ref(), prep_next.as_ref()) {
(Some(l), Some(n)) => ViewPair::new(
RowMajorMatrixView::new_row(&**l),
RowMajorMatrixView::new_row(&**n),
),
_ => ViewPair::new(
RowMajorMatrixView::new(&[], 0),
RowMajorMatrixView::new(&[], 0),
),
};
// Construct the builder with row selectors derived from the position.
let mut builder = DebugConstraintBuilder::new(
row_index,
main_pair,
preprocessed_pair,
public_values,
F::from_bool(row_index == 0),
sed -n '150,230p' lookup/src/debug_util.rs for row in 0..height {
let local_main = instance.main_trace.row_slice(row).unwrap();
let next_main = instance.main_trace.row_slice((row + 1) % height).unwrap();
let main_rows = VerticalPair::new(
RowMajorMatrixView::new_row(&*local_main),
RowMajorMatrixView::new_row(&*next_main),
);
let preprocessed_rows_data = instance.preprocessed_trace.as_ref().map(|prep| {
(
prep.row_slice(row).unwrap(),
prep.row_slice((row + 1) % height).unwrap(),
)
});
let preprocessed_rows = match preprocessed_rows_data.as_ref() {
Some((prep_local, prep_next)) => VerticalPair::new(
RowMajorMatrixView::new_row(&**prep_local),
RowMajorMatrixView::new_row(&**prep_next),
),
None => VerticalPair::new(
RowMajorMatrixView::new(&[], 0),
RowMajorMatrixView::new(&[], 0),
),
};
let builder = MiniLookupBuilder {
main: main_rows,
preprocessed: preprocessed_rows,
public_values: instance.public_values,
permutation_challenges: instance.permutation_challenges,
row,
height,
};
for (tuple_idx, elements) in lookup.element_exprs.iter().enumerate() {
let key = elements
.iter()
.map(|expr| symbolic_to_expr(&builder, expr))
.collect::<Vec<_>>();
let multiplicity = symbolic_to_expr(&builder, &lookup.multiplicities_exprs[tuple_idx]);
multiset.add(
key,
multiplicity,
Location {
instance: instance_idx,
lookup: lookup_idx,
row,
},
);
}
}
}
struct MiniLookupBuilder<'a, F: Field> {
main: ViewPair<'a, F>,
preprocessed: ViewPair<'a, F>,
public_values: &'a [F],
permutation_challenges: &'a [F],
row: usize,
height: usize,
}
impl<'a, F: Field> AirBuilder for MiniLookupBuilder<'a, F> {
type F = F;
type Expr = F;
type Var = F;
type PreprocessedWindow = ViewPair<'a, F>;
type MainWindow = ViewPair<'a, F>;
type PublicVar = F;
fn main(&self) -> Self::MainWindow {
self.main
}
fn preprocessed(&self) -> &Self::PreprocessedWindow {
&self.preprocessed
}
fn is_first_row(&self) -> Self::Expr {
sed -n '40,110p' matrix/src/stack.rs && printf '\n---\n' && sed -n '780,806p' matrix/src/dense.rs/// Element access and iteration for a given row `i` will first access the elements in the `i`'th row of the left matrix,
/// followed by elements in the `i'`th row of the right matrix.
#[derive(Copy, Clone, Debug)]
pub struct HorizontalPair<Left, Right> {
/// The left matrix in the horizontal composition.
pub left: Left,
/// The right matrix in the horizontal composition.
pub right: Right,
}
impl<Top, Bottom> VerticalPair<Top, Bottom> {
/// Create a new `VerticalPair` by stacking two matrices vertically.
///
/// # Panics
/// Panics if the two matrices do not have the same width (i.e., number of columns),
/// since vertical composition requires column alignment.
///
/// # Returns
/// A `VerticalPair` that represents the combined matrix.
pub fn new<T>(top: Top, bottom: Bottom) -> Self
where
T: Send + Sync + Clone,
Top: Matrix<T>,
Bottom: Matrix<T>,
{
assert_eq!(top.width(), bottom.width());
Self { top, bottom }
}
}
impl<Left, Right> HorizontalPair<Left, Right> {
/// Create a new `HorizontalPair` by joining two matrices side by side.
///
/// # Panics
/// Panics if the two matrices do not have the same height (i.e., number of rows),
/// since horizontal composition requires row alignment.
///
/// # Returns
/// A `HorizontalPair` that represents the combined matrix.
pub fn new<T>(left: Left, right: Right) -> Self
where
T: Send + Sync + Clone,
Left: Matrix<T>,
Right: Matrix<T>,
{
assert_eq!(left.height(), right.height());
Self { left, right }
}
}
impl<T: Send + Sync + Clone, Top: Matrix<T>, Bottom: Matrix<T>> Matrix<T>
for VerticalPair<Top, Bottom>
{
fn width(&self) -> usize {
self.top.width()
}
fn height(&self) -> usize {
self.top.height() + self.bottom.height()
}
unsafe fn get_unchecked(&self, r: usize, c: usize) -> T {
unsafe {
// Safety: The caller must ensure that r < self.height() and c < self.width()
if r < self.top.height() {
self.top.get_unchecked(r, c)
} else {
self.bottom.get_unchecked(r - self.top.height(), c)
}
}
}
---
fn test_new_col() {
let matrix = RowMajorMatrix::new_col(vec![1, 2, 3]);
assert_eq!(matrix.width, 1);
assert_eq!(matrix.height(), 3);
}
#[test]
fn test_height_with_zero_width() {
let matrix: DenseMatrix<i32> = RowMajorMatrix::new(vec![], 0);
assert_eq!(matrix.height(), 0);
}
#[test]
fn test_get_methods() {
let matrix = RowMajorMatrix::new(vec![1, 2, 3, 4, 5, 6], 2); // Height = 3, Width = 2
assert_eq!(matrix.get(0, 0), Some(1));
assert_eq!(matrix.get(1, 1), Some(4));
assert_eq!(matrix.get(2, 0), Some(5));
unsafe {
assert_eq!(matrix.get_unchecked(0, 1), 2);
assert_eq!(matrix.get_unchecked(1, 0), 3);
assert_eq!(matrix.get_unchecked(2, 1), 6);
}
assert_eq!(matrix.get(3, 0), None); // Height out of bounds
assert_eq!(matrix.get(0, 2), None); // Width out of bounds
}
This matters because the AIR API still talks about two-row windows, and generic code can reasonably expect row 0 and row 1 to exist even when width is zero.
With the current branch, code that does builder.preprocessed().row_slice(0).unwrap() or builder.preprocessed().get(0, i) on a logically absent preprocessed trace can now panic because the matrix height is 0.
The in-tree tests pass because most call sites either have actual preprocessed data or avoid touching absent preprocessed rows. The contract changed anyway.
The final issue is not an internal correctness bug. It is a compatibility regression.
p3_air reexports its public API from air/src/lib.rs. This branch deletes both WindowAccess and RowWindow from that public surface.
sed -n '1,30p' air/src/lib.rs && printf '\n---\n' && sed -n '132,170p' air/src/air.rs//! APIs for AIRs, and generalizations like PAIRs.
#![no_std]
extern crate alloc;
mod air;
mod check_constraints;
mod named;
pub mod symbolic;
pub mod utils;
mod virtual_column;
pub use air::*;
pub use check_constraints::*;
pub use named::*;
pub use symbolic::*;
pub use virtual_column::*;
---
/// A builder which contains both a trace on which AIR constraints can be evaluated as well as a method of accumulating the AIR constraint evaluations.
///
/// Supports both symbolic cases where the constraints are treated as polynomials and collected into a vector
/// as well cases where the constraints are evaluated on an evaluation trace and combined using randomness.
pub trait AirBuilder: Sized {
/// Underlying field type.
///
/// This should usually implement `Field` but there are a few edge cases (mostly involving `PackedFields`) where
/// it may only implement `PrimeCharacteristicRing`.
type F: PrimeCharacteristicRing + Sync;
/// Serves as the output type for an AIR constraint evaluation.
type Expr: Algebra<Self::F> + Algebra<Self::Var>;
/// The type of the variable appearing in the trace matrix.
///
/// Serves as the input type for an AIR constraint evaluation.
type Var: Into<Self::Expr>
+ Copy
+ Send
+ Sync
+ Add<Self::F, Output = Self::Expr>
+ Add<Self::Var, Output = Self::Expr>
+ Add<Self::Expr, Output = Self::Expr>
+ Sub<Self::F, Output = Self::Expr>
+ Sub<Self::Var, Output = Self::Expr>
+ Sub<Self::Expr, Output = Self::Expr>
+ Mul<Self::F, Output = Self::Expr>
+ Mul<Self::Var, Output = Self::Expr>
+ Mul<Self::Expr, Output = Self::Expr>;
/// Two-row window over the preprocessed trace columns.
type PreprocessedWindow: Matrix<Self::Var> + Clone;
/// Two-row window over the main trace columns.
type MainWindow: Matrix<Self::Var> + Clone;
/// Variable type for public values.
type PublicVar: Into<Self::Expr> + Copy;
git show 7ca1cdff:air/src/air.rs | sed -n '1,120p'use alloc::vec::Vec;
use core::ops::{Add, Mul, Sub};
use p3_field::{Algebra, ExtensionField, Field, PrimeCharacteristicRing};
use p3_matrix::dense::{RowMajorMatrix, RowMajorMatrixView};
/// Read access to a pair of trace rows (typically current and next).
///
/// Implementors expose two flat slices that constraint evaluators use
/// to express algebraic relations between rows.
pub trait WindowAccess<T> {
/// Full slice of the current row.
fn current_slice(&self) -> &[T];
/// Full slice of the next row.
fn next_slice(&self) -> &[T];
/// Single element from the current row by index.
///
/// Returns `None` if `i` is out of bounds.
#[inline]
fn current(&self, i: usize) -> Option<T>
where
T: Clone,
{
self.current_slice().get(i).cloned()
}
/// Single element from the next row by index.
///
/// Returns `None` if `i` is out of bounds.
#[inline]
fn next(&self, i: usize) -> Option<T>
where
T: Clone,
{
self.next_slice().get(i).cloned()
}
}
/// A lightweight two-row window into a trace matrix.
///
/// Stores two `&[T]` slices — one for the current row and one for
/// the next — without carrying any matrix metadata. This is cheaper
/// than a full `ViewPair` and is the concrete type used by most
/// [`AirBuilder`] implementations for `type MainWindow` / `type PreprocessedWindow`.
#[derive(Debug, Clone, Copy)]
pub struct RowWindow<'a, T> {
/// The current row.
current: &'a [T],
/// The next row.
next: &'a [T],
}
impl<'a, T> RowWindow<'a, T> {
/// Create a window from a [`RowMajorMatrixView`] that has exactly
/// two rows. The first row becomes `current`, the second `next`.
///
/// # Panics
///
/// Panics if the view does not contain exactly `2 * width` elements.
#[inline]
pub fn from_view(view: &RowMajorMatrixView<'a, T>) -> Self {
let width = view.width;
assert_eq!(
view.values.len(),
2 * width,
"RowWindow::from_view: expected 2 rows (2*{width} elements), got {}",
view.values.len()
);
let (current, next) = view.values.split_at(width);
Self { current, next }
}
/// Create a window from two separate row slices.
///
/// The caller is responsible for providing slices that represent
/// the intended (current, next) pair.
///
/// # Panics
///
/// Panics (in debug builds) if the slices have different lengths.
#[inline]
pub fn from_two_rows(current: &'a [T], next: &'a [T]) -> Self {
debug_assert_eq!(
current.len(),
next.len(),
"RowWindow::from_two_rows: row lengths differ ({} vs {})",
current.len(),
next.len()
);
Self { current, next }
}
}
impl<T> WindowAccess<T> for RowWindow<'_, T> {
#[inline]
fn current_slice(&self) -> &[T] {
self.current
}
#[inline]
fn next_slice(&self) -> &[T] {
self.next
}
}
/// The underlying structure of an AIR.
pub trait BaseAir<F>: Sync {
/// The number of columns (a.k.a. registers) in this AIR.
fn width(&self) -> usize;
/// Return an optional preprocessed trace matrix to be included in the prover's trace.
fn preprocessed_trace(&self) -> Option<RowMajorMatrix<F>> {
None
}
/// Which main trace columns have their next row accessed by this AIR's
/// constraints.
///
/// By default this returns every column index, which will require
That means any downstream crate that:
- names
RowWindow, - bounds a type against
WindowAccess, or - implements a builder using the old window trait,
will stop compiling on this branch.
That may be acceptable in a coordinated breaking release. It is not an internal cleanup that can be treated as behavior-preserving by default.
The branch is directionally understandable.
It removes a bespoke two-row API and reuses the matrix crate's general access patterns. For many concrete call sites, especially prover/verifier folders already carrying RowMajorMatrixView or ViewPair, the code does get shorter.
But the old design carried three useful guarantees:
- the window abstraction was explicitly two-row,
- empty preprocessed traces still behaved like two rows of width zero, and
- the public AIR API exposed stable names (
WindowAccess,RowWindow) that downstream code could rely on.
This branch currently drops all three at once.
cargo nextest run -E 'test(range_checked_sub_builder) or test(test_mul_fib_pair) or test(test_preprocessed_constraint_positive) or test(test_global_lookup)' >/dev/null 2>&1 && echo 'selected migration tests passed'selected migration tests passed
Those representative tests still pass, which is why the migration can look harmless at first glance.
The remaining problems are edge-contract and compatibility issues:
- invalid truncated ranges,
- zero-row empty preprocessed views masquerading as two-row windows, and
- downstream API breakage.
That is the full picture behind the audit findings.