Multi-AIR (RV32IM)

Multi-AIR (RV32IM)#

The RV32IM Fibonacci program demonstrates the full multi-AIR STARK protocol with LogUp bus interactions, matrices of different heights, and per-height alpha tracking.

Multi-AIR Structure#

Unlike the single-AIR Fibonacci, a multi-AIR proof covers multiple AIRs simultaneously. Each AIR has its own:

  • Trace matrix (possibly different number of rows)

  • Constraint DAG

  • Preprocessed trace (optional)

  • Bus interactions (optional)

All AIRs share a single FRI proof.

Different Heights#

In a multi-AIR proof, trace matrices can have different heights (\(N_a \ne N_b\)). This affects the protocol in several ways:

  1. MMCS: The mixed-matrix commitment scheme (_build_mmcs_tree) builds a single Merkle tree where shorter matrices are injected at higher tree levels.

  2. Per-height alpha tracking: During PCS opening, the \(\alpha\)-power accumulator is maintained separately for each distinct \(\log_2(\text{height})\):

    alpha_pow_per_height: dict[int, FF4]

    This is critical — using a single global accumulator produces incorrect proofs for multi-height cases, even though it works for single-height proofs.

  3. FRI reduced openings: The FRI commit phase receives reduced openings keyed by height. During folding, reduced openings at the current folded height are “rolled in”: \(F_{k+1} \mathrel{+}= \beta_k^2 \cdot \text{ro}_h\).

LogUp Bus Interactions#

Multi-AIR programs use LogUp to enforce consistency between AIRs via shared buses (compute_after_challenge_trace).

Interaction Definition#

Each interaction specifies:

  • Bus ID: which bus this interaction connects to.

  • Message fields: column indices defining the message.

  • Count: the multiplicity (positive for sends, negative for receives).

After-Challenge Computation#

  1. Beta powers: \(\beta^0, \beta^1, \ldots\) generated from the interaction challenge \(\beta_{\text{lu}}\).

  2. Denominators: For each interaction at each row: $\( d = \alpha_{\text{lu}} + m_0 + \beta_{\text{lu}} \cdot m_1 + \cdots + \beta_{\text{lu}}^{|m|} \cdot (\text{bus\_id} + 1) \)$

  3. Reciprocals: Batch invert all denominators.

  4. Chunk sums: Weighted sum of reciprocals by interaction counts.

  5. Running sum \(\phi\): Prefix sum of chunk sums. The final value \(\phi[N-1]\) is the exposed value (cumulative sum).

Cumulative Sum Check#

The sum of exposed values across all AIRs must equal zero:

\[ \sum_{a \in \text{AIRs}} \phi_a[N_a - 1] = 0 \]

This enforces that every bus send has a corresponding receive.

Test Vectors#

The rv32im_fibonacci test vector exercises:

  • Multiple AIRs with different trace heights

  • LogUp interactions across AIRs

  • Per-height alpha tracking in PCS

  • Multi-height MMCS tree construction

The test suite caches the proof to avoid the ~25-minute generation time. Both prover (byte-for-byte match) and verifier tests pass.