AIR Cryptographer Expertise

Expert-level knowledge for designing, implementing, and auditing Algebraic Intermediate Representations (AIRs) in zero-knowledge proof systems.

Core Mindset

Soundness-first thinking: Every constraint review starts with "how could a cheater slip through?" Think adversarially. Construct counterexample traces by hand. Exploit polynomial identity loopholes.

Algebraic precision: Constraints define solution spaces over finite fields. A missing constraint isn't just a bug—it's extra degrees of freedom for a malicious prover.

Finite Field Foundations

Essential intuitions:

• •Characteristics and inverses: Every non-zero element has a multiplicative inverse. No zero divisors.
• •Roots of unity: Multiplicative subgroups of order 2^k enable FFT-friendly evaluation domains.
• •Extension fields: When you need more algebraic structure (e.g., M31 → QM31 for Stwo).
• •Frobenius endomorphism: The map x → x^p is field-linear; crucial for extension field arithmetic.

Polynomial Mechanics

Interpolation: Given n points, unique polynomial of degree < n passes through them. Lagrange basis makes this explicit.

Vanishing polynomials: Z_H(x) = ∏(x - h) for h ∈ H vanishes exactly on domain H. This is the foundation of constraint enforcement.

Degree behavior:

• •Multiplication: deg(f·g) = deg(f) + deg(g)
• •Composition: deg(f∘g) = deg(f) · deg(g)
• •Low-degree testing verifies a function is "close to" a low-degree polynomial

Evaluation domains: Multiplicative cosets for separation. Blowup factor determines security margin between trace degree and domain size.

Trace Design Principles

Column Classification

Critical rule: Every column must be constrained. An unconstrained column is a free variable for the prover.

Row Semantics

Define precisely what each row represents:

• •CPU cycle / instruction
• •Memory operation
• •Padding (must be distinguishable!)

Row types require selectors. Selectors must be:

• •Boolean: s(s-1) = 0
• •Mutually exclusive: Σ s_i = 1 (or coverage proof)
• •Actually constrained (not just documented)

Minimal vs Redundant Columns

Start minimal. Add auxiliary columns only when:

• •Degree reduction is necessary
• •Soundness requires explicit intermediate values
• •Verification cost dominates

Constraint Categories

Transition Constraints (Local)

Express correct step relation between row i and row i+1:

next_pc = pc + instruction_size  (when not branching)
next_register[k] = f(current_state, opcode)

Danger: Writing a relation instead of a function. Multiple valid next-states = unsound.

Boundary Constraints

Pin specific rows to specific values:

• •Initial: Row 0 state matches expected start
• •Final: Last row satisfies termination condition
• •I/O: Public inputs/outputs bound at known positions

Danger: "Final row" must be uniquely defined. Variable-length traces need explicit halt handling.

Booleanity and Range Constraints

For boolean b: b(b-1) = 0

For k-bit value x with bits b0...b{k-1}:

x = Σ b_i · 2^i
b_i(b_i - 1) = 0  for all i

Danger: Forgetting booleanity constraints on decomposition bits.

Selector Discipline

Selectors gate which constraints apply to which rows.

Checklist:

• • Each selector is boolean
• • Exactly one selector active per row (or explicit coverage)
• • No "ghost mode" where all selectors = 0
• • Selector itself is constrained (not free)

Classic bug: All selectors zero makes all gated constraints vacuously true.

Global Consistency Arguments

Permutation / Multiset Equality

Prove two multisets are equal via grand product:

∏(α - a_i) = ∏(α - b_i)

Checklist:

• •Initial product = 1 (boundary constraint)
• •Final products equal (boundary constraint)
• •Challenge α bound to transcript after commitments
• •Duplicates handled correctly

Danger: Product hitting zero, missing boundary constraints, challenge reuse.

Lookup Arguments

Prove all values in column A appear in table T.

Checklist:

• •Table is committed/fixed
• •Compression is collision-resistant (sufficient randomness)
• •Repeated lookups soundly counted

Danger: Weak compression allows out-of-table values.

Memory Consistency

Memory operations form a log: (address, timestamp, value, is_write)

Patterns:

• •Sort by address, then by timestamp
• •Consecutive same-address ops: read sees last write
• •Permutation links memory log to CPU trace

Danger:

• •Address aliasing across different trace sections
• •Timestamp not proven monotonic
• •Read-before-write not enforced

Quotient and Composition

Constraint polynomial C(x) should vanish on trace domain H.

Quotient: Q(x) = C(x) / Z_H(x)

If C doesn't vanish on H, Q has poles → not low-degree → FRI rejects.

Row-Set Control

Constraints apply to different row sets:

• •All rows: divide by Z_H(x)
• •All but last: divide by Z_H(x) / (x - ω^{n-1})
• •First only: multiply by Lagrange selector for row 0
• •Last only: multiply by Lagrange selector for row n-1

Danger: Constraint meant for "all rows" accidentally only enforced on subset due to incorrect vanishing factor.

Degree Accounting

Track degree of every constraint:

Base constraint degree: d
After selector multiplication: d + deg(selector)
After boundary polynomial: d + deg(boundary)

Composition polynomial degree must stay below domain size with sufficient margin (blowup factor).

Fiat-Shamir Hygiene

Transcript must bind:

• •All commitments (trace, lookup tables, etc.)
• •Public inputs
• •Trace length / domain parameters
• •Any prover messages

Challenge separation: Different arguments need independent challenges. Reusing challenges creates algebraic vulnerabilities.

Danger: Challenge derived before commitment → prover can adapt witness.

Adversarial Witness Exercises

Before declaring an AIR sound, try to break it:

1. •All selectors = 0: Do constraints still enforce anything?
2. •Corrupt one column: Can it drift without detection?
3. •Attack last row: Dump inconsistency into wrap-around?
4. •Duplicate/omit memory events: Does global check catch it?
5. •Force product to zero: Exploit grand product boundary?
6. •Exploit gating: Make "if flag then X" vacuous by leaving flag unconstrained?

If you find a counterexample trace, you found a bug.

Common Vulnerability Patterns

Performance-Aware Design

Understand tradeoffs without being an engineer:

Rules of thumb:

• •Auxiliary columns to reduce degree often worth it
• •Local constraints cheaper than global arguments
• •Precomputation tables vs dynamic checks: depends on table size

Review Deliverables

When reviewing an AIR, produce:

1. •Column inventory: Name, meaning, range, where constrained
2. •Constraint map: Each semantic claim → which constraint enforces it
3. •Degree table: Every constraint's degree contribution
4. •Adversarial tests: Attempted counterexamples
5. •Risk ranking: Critical / High / Medium findings
6. •Proposed fixes: Concrete constraint additions/modifications

See references/review-checklist.md for the complete systematic review sheet.