Commitment Phase

This section describes the prover’s commitment rounds: transcript seeding, witness commitment (Stage 1), after-challenge trace via LogUp (Stage 2), quotient computation (Stage Q), and the evaluation stage.

Transcript Seeding

Before any commitment, the prover initializes the Fiat-Shamir transcript (prove_stark):

1. Create a fresh Challenger().

2. Observe the verifying key’s pre_hash (8 base field elements).

3. Observe the number of AIRs as a single field element.

4. Observe each air_id individually.

The verifier performs identical seeding (verify_stark).

Stage 1: Witness Commitment

The prover commits the main execution trace:

1. Generate witness trace. For each AIR, produce a matrix of \(N\) rows and \(m\) columns, where each column is a witness polynomial \(f_j\) evaluated at the trace domain \(H\) (program-specific; see Part II).

2. Commit via PCS. Extend each column to the LDE domain via coset LDE, build an MMCS Merkle tree, and extract the root commitment \(r_1\) (pcs_commit).

3. Absorb into transcript. The prover observes (in order):

   • Public values for each AIR

   • Flattened preprocessed trace commitments (from the verifying key)

   • Main trace commitment \(r_1\)

   • \(\log_2(\text{degree})\) for each AIR

\[ \mathcal{T}.\text{observe}(\text{pv}_1, \ldots, \text{pv}_k, \; r_{\text{pre}}, \; r_1, \; \log_2 N_1, \ldots) \]

Stage 2: After-Challenge Trace (LogUp)

If any AIR has bus interactions (lookups, permutations), the prover computes auxiliary columns using the FRI LogUp protocol.

1. Grind for LogUp PoW. Compute a proof-of-work witness for the interaction phase.

2. Sample interaction challenges. Draw two extension field challenges:

   • \(\alpha_{\text{lu}} \leftarrow \mathcal{T}.\text{sample\_ext}()\)

   • \(\beta_{\text{lu}} \leftarrow \mathcal{T}.\text{sample\_ext}()\)

3. Compute after-challenge trace. For each AIR with interactions, compute the log-derivative auxiliary columns (compute_after_challenge_trace):

   a. Generate beta powers from \(\beta_{\text{lu}}\) for each interaction.

   b. Evaluate constraint DAG at all rows to get field values needed by the interaction expressions.

   c. Compute denominators for each interaction at each row: $\( d_i = \alpha_{\text{lu}} + m_0 + \beta_{\text{lu}} \cdot m_1 + \cdots + \beta_{\text{lu}}^{|m|} \cdot (\text{bus\_id} + 1) \)\( where \)m_0, m_1, \ldots$ are the interaction message fields.

   d. Batch invert all denominators, then compute chunk sums (weighted by interaction counts).

   e. Running sum \(\phi\): prefix sum of chunk sums. The cumulative sum (exposed value) must equal zero for a valid trace.

4. Observe exposed values (cumulative sums) into the transcript.

5. Commit after-challenge trace via PCS. Flatten FF4 columns to 4 base field columns each. Observe the commitment into the transcript.

Stage Q: Quotient Polynomial

The prover computes and commits the quotient polynomial.

1. Sample \(\alpha\) from the transcript: \(\alpha \leftarrow \mathcal{T}.\text{sample\_ext}()\). This challenge combines all constraint polynomials via random linear combination.

2. Compute quotient chunks for each AIR (compute_quotient_chunks):

   a. Create a disjoint quotient domain of size \(N \cdot d_Q\), where \(d_Q\) is the quotient degree.

   b. Extend all traces (main, preprocessed, after-challenge) to the quotient domain via coset LDE.

   c. Evaluate all constraints at every point of the quotient domain, accumulate with \(\alpha\)-powers using Horner’s method: $\( \text{accumulated}(x) = \sum_{i} \alpha^i \cdot C_i(x) \)$

   d. Divide by the vanishing polynomial: $\( Q(x) = \frac{\text{accumulated}(x)}{Z_H(x)} \)$

   e. Split the quotient evaluations into \(d_Q\) chunks of \(N\) values each, producing \(d_Q\) separate trace matrices.

3. Commit quotient chunks via PCS. Observe the commitment \(r_Q\) into the transcript.

DEEP Proof-of-Work

After the quotient commitment, the prover grinds for a DEEP proof-of-work witness (separate from the LogUp PoW).

Evaluation Stage

1. Sample \(\zeta\) from the transcript: \(\zeta \leftarrow \mathcal{T}.\text{sample\_ext}()\). This is the out-of-domain (OOD) evaluation point.

2. Open all polynomials at \(\zeta\) and \(\zeta \omega\) (the next-row point). For each committed matrix, the prover evaluates its columns at both points using polynomial evaluation from coefficients (pcs_open):

   Round	Matrices	Points
   Preprocessed	Per-AIR constant columns	\(\zeta\), \(\zeta\omega\)
   Cached main	Per-partition trace columns	\(\zeta\), \(\zeta\omega\)
   Common main	Shared trace columns	\(\zeta\), \(\zeta\omega\)
   After-challenge	LogUp auxiliary columns	\(\zeta\), \(\zeta\omega\)
   Quotient	Quotient chunks	\(\zeta\) only

3. Observe opened values into the transcript (done inside pcs_open).

4. Compute FRI reduced polynomial and run the FRI protocol to prove the opened values are consistent with the commitments (prove_fri).