machine_cat/
air.rs

1//! The Air trait: the core abstraction for algebraic intermediate representations.
2//!
3//! An [`Air`] defines a set of columns and transition constraints
4//! that must hold at every consecutive row pair of an execution trace.
5//! This is the STARK analog of a plonkish-cat gate, operating on
6//! trace tables rather than individual wires.
7
8use crate::air_expr::AirExpr;
9use crate::column::ColumnCount;
10use crate::error::Error;
11use crate::trace::Trace;
12use field_cat::Field;
13
14/// An Algebraic Intermediate Representation.
15///
16/// Defines the **columns** (trace width) and **transition constraints**
17/// (polynomial expressions that must be zero at every consecutive
18/// row pair) for a provable computation.
19///
20/// Implementations also provide [`generate_trace`](Air::generate_trace)
21/// to compute the execution trace from a given input.
22///
23/// # Categorical interpretation
24///
25/// Each `Air` is a morphism in a category where objects are
26/// trace shapes ([`ColumnCount`]).  Parallel composition of
27/// independent AIRs corresponds to the tensor product (column
28/// concatenation).  This structure is documented here but not
29/// encoded at the type level in v0.1; see the machine-cat
30/// roadmap for future categorical enforcement.
31pub trait Air<F: Field> {
32    /// The type of input this AIR computes over.
33    type Input;
34
35    /// The number of columns in this AIR's trace.
36    fn column_count(&self) -> ColumnCount;
37
38    /// The transition constraints.
39    ///
40    /// Each [`AirExpr`] must evaluate to zero for every consecutive
41    /// row pair `(row[i], row[i+1])` in a valid trace.
42    fn constraints(&self) -> Vec<AirExpr<F>>;
43
44    /// Generate the execution trace from an input.
45    ///
46    /// The returned trace must have [`column_count()`](Air::column_count)
47    /// columns.  The number of rows is determined by the input.
48    ///
49    /// # Errors
50    ///
51    /// Returns an error if the input is invalid or trace generation
52    /// fails.
53    fn generate_trace(&self, input: &Self::Input) -> Result<Trace<F>, Error>;
54}
machine_cat/air.rs

machine_cat/
air.rs
