DEEP Quotient Computation

Overview

The DEEP (Domain Extension for Eliminating Pretenders) technique is how the verifier connects the committed polynomial evaluations (at queried domain points) with the out-of-domain (OOD) evaluations (at a random challenge point). It is the most mathematically intricate component of the verifier and the source of both critical bugs found during the port.

All DEEP quotient logic is in OodQuotients.sol (221 lines).

1. Purpose

The prover claims that a committed polynomial $f$ satisfies $f(P_{\text{ood}}) = v$ for some out-of-domain point $P_{\text{ood}}$. The verifier cannot evaluate $f$ at $P_{\text{ood}}$ directly (it only has Merkle commitments). Instead, it constructs a quotient that is zero if and only if the claim is true:

where $L$ is the unique line passing through the claimed evaluation and its conjugate, and $Z$ vanishes at those points. If $f(P_{\text{ood}}) = v$, then $Q$ is a polynomial of degree $\deg(f) - 1$. If the claim is false, $Q$ has a pole and the FRI check will (with high probability) fail.

2. Points Involved

Three types of evaluation points appear:

OOD Point $P_{\text{ood}}$

Generated via stereographic projection from a random QM31 challenge $t$:

This point lies on the QM31 circle (not the M31 circle), ensuring it is "outside" the evaluation domain with overwhelming probability.

Shifted Point $P_{\text{shifted}}$

For columns with mask offset 1 (reading the next row), the evaluation is at:

where $G_{\text{trace}}$ is the subgroup generator of order $2^{\text{LOG\_TRACE\_SIZE}} = 2^6$. Circle point multiplication:

with all arithmetic in QM31.

Periodicity Point $P_{\text{period}}$

For columns with 2+ mask offsets, Stwo adds a periodicity sample at:

For our parameters, $G_{\text{period}} = \text{identity}$, so $P_{\text{period}} = P_{\text{shifted}}$. See Section 6 for the derivation.

Query Points $q = (q_x, q_y)$

These are M31 circle domain points at the queried positions. They lie on the M31 circle (not QM31), accessed in bit-reversed order from the lifting domain.

3. Line Equation Through Conjugate Pairs

The key insight in DEEP quotients for circle STARKs is that we work with line equations through conjugate pairs. Given a sample $(P_s, v)$ where $P_s$ is a QM31 circle point and $v$ is the claimed evaluation:

The conjugate pair is $(\bar{P_s}, \bar{v})$ where $\bar{\cdot}$ denotes QM31 complex conjugation.

The unique line $\ell(x, y) = a \cdot y + b$ passing through both $(P_s, v)$ and $(\bar{P_s}, \bar{v})$ has coefficients:

4. Quotient Contribution

For each column sample, the quotient contribution is:

where:

• $\alpha^k$ is the current power of the random coefficient (one power per contribution)
• $f(q)$ is the queried M31 trace value at the query point
• The numerator checks whether $f(q)$ lies on the line through the claimed evaluations
• The denominator is the line denominator evaluated at the query point

Line Denominator

The denominator isolates the vanishing behavior at the sample point:

where superscripts denote CM31 real/imaginary parts of the QM31 coordinates. This is a CM31 value.

The denominator depends only on the sample point and the query point, not on the column values. For the OOD point and shifted point, we pre-compute their inverses once per query:

ctx.denomOodsInv = cm31Inv(_lineDenom(pts.oodsX, pts.oodsY, ctx.qx, ctx.qy));
ctx.denomShiftedInv = cm31Inv(_lineDenom(pts.shiftedX, pts.shiftedY, ctx.qx, ctx.qy));

These are reused across all columns that share the same evaluation point.

Numerator Computation

function _computeNumerator(uint128 c, uint128 a, uint128 b, uint32 fVal, uint32 qy)
    internal pure returns (uint128)
{
    uint128 fQ = qm31FromM31(fVal, 0, 0, 0);
    uint128 qyQ = qm31FromM31(qy, 0, 0, 0);
    return qm31Sub(
        qm31Mul(c, fQ),
        qm31Add(qm31Mul(a, qyQ), b)
    );
}

Note that fVal and qy are M31 values promoted to QM31 for the computation. The result is QM31.

Final Assembly

function _addQ(
    uint128 acc, uint128 alphaPow,
    uint32 queriedVal, uint128 sampleVal, uint128 samplePtY,
    uint32 qy, uint64 denomInv
) internal pure returns (uint128) {
    // Line coefficients
    uint128 a = qm31Sub(_conjQ(sampleVal), sampleVal);
    uint128 c = qm31Sub(_conjQ(samplePtY), samplePtY);
    uint128 b = qm31Sub(qm31Mul(sampleVal, c), qm31Mul(a, samplePtY));

    // Scale by alphaPow
    a = qm31Mul(alphaPow, a);
    b = qm31Mul(alphaPow, b);
    c = qm31Mul(alphaPow, c);

    // Numerator: c * f(q) - (a * qy + b)
    uint128 num = _computeNumerator(c, a, b, queriedVal, qy);

    // num * denomInv (CM31 inverse promoted to QM31)
    uint128 diQ = qm31Pack(denomInv, cm31Pack(0, 0));
    return qm31Add(acc, qm31Mul(num, diQ));
}

5. Accumulation Order

The verifier processes columns in strict order, accumulating quotient contributions with increasing powers of $\alpha$:

Single-Offset Columns

For the withdrawal circuit, 44 of 46 trace columns are single-offset. For the transfer circuit, 55 of 57 trace columns are single-offset.

One contribution per column, consuming one $\alpha$ power:

acc += α^k * quotient(col_value, ood_value, ood_point)
k += 1

Shifted Columns (columns 25 and 29)

These column indices are now constructor parameters (MULTI_MASK_COL_0, MULTI_MASK_COL_1) rather than hardcoded values, allowing the same verifier code to support both the withdrawal circuit (46 columns) and the transfer circuit (57 columns). Both circuits use columns 25 and 29 as the shifted columns.

Three contributions per column, consuming three $\alpha$ powers:

acc += α^k   * quotient(col_value, shifted_ood_value, shifted_point)   // periodicity
acc += α^(k+1) * quotient(col_value, ood_value_offset0, ood_point)     // offset 0
acc += α^(k+2) * quotient(col_value, ood_value_offset1, shifted_point) // offset 1
k += 3

Composition Columns (8 columns)

One contribution per column at the OOD point:

acc += α^k * quotient(comp_value, comp_ood_value, ood_point)
k += 1

Total $\alpha$ Count

For the withdrawal circuit (46 trace columns):

For the transfer circuit (57 trace columns):

The final accumulator is the FRI input for that query.

6. Periodicity Samples: The Deep Cut

What Are Periodicity Samples?

In Stwo's build_samples_with_randomness_and_periodicity, for any column with 2 or more mask offsets, an additional "periodicity" quotient contribution is prepended before the regular offset samples.

The periodicity sample represents the constraint that the polynomial must be periodic with respect to the column's evaluation domain. For columns with only one mask offset, no periodicity sample is needed.

Periodicity Point Derivation

The periodicity point is:

where G_period = CanonicCoset(lifting_log_size).step().repeated_double(column_extended_log_size).

For our parameters:

• lifting_log_size = 7
• column_extended_log_size = 7 (= trace_log_size + log_blowup_factor = 6 + 1)
• CanonicCoset(7).step() = subgroupGen(7) → index $= 2^{31-7} = 2^{24}$
• After 7 doublings: index $= 2^{24} \times 2^7 = 2^{31}$
• $G^{2^{31}} =$ identity (since $|G| = 2^{31}$)

Therefore: $G_{\text{period}} = \text{identity} = (1, 0)$

And: $P_{\text{period}} = P_{\text{shifted}} \cdot (1, 0) = P_{\text{shifted}}$

Consequence

The periodicity point coincides with the shifted point. This means:

• Same y-coordinate for the line equation
• Same line denominator inverse

The periodicity sample uses the offset-1 OOD value (peeked ahead from the trace OOD array) at the shifted point.

Initial Wrong Assumption

7. The OOD Value Array

The trace OOD values are stored in a flat array, indexed sequentially:

Total: 41 trace OOD values (37 single + 2×2 shifted).

For shifted columns, the code "peeks ahead" to read the offset-1 value for the periodicity sample before advancing the index:

uint128 shiftedVal = p.traceOodValues[s.tOodIdx + 1]; // peek: offset-1
// ... use shiftedVal for periodicity sample ...
s.acc = _addQ(..., p.traceOodValues[s.tOodIdx++], ...); // offset-0, advance
s.acc = _addQ(..., p.traceOodValues[s.tOodIdx++], ...); // offset-1, advance

8. Complete Accumulation Flow

For each query position $q_i$:

1. Compute query context:
   - Bit-reverse position → domain index
   - Look up circle domain point (qx, qy)
   - Compute denomOodsInv = cm31Inv(lineDenom(ood, q))
   - Compute denomShiftedInv = cm31Inv(lineDenom(shifted, q))

2. Initialize: acc = 0, alphaPow = 1, tOodIdx = 0

3. For each trace column (0..TRACE_WIDTH-1):
   qVal = queriedTrace[col][qi]

   If col == MULTI_MASK_COL_0 or col == MULTI_MASK_COL_1:
     // Periodicity sample
     shiftedVal = traceOodValues[tOodIdx + 1]
     acc += addQ(alphaPow, qVal, shiftedVal, shiftedY, qy, denomShiftedInv)
     alphaPow *= randomCoeff

     // Offset-0 sample
     acc += addQ(alphaPow, qVal, traceOodValues[tOodIdx++], oodsY, qy, denomOodsInv)
     alphaPow *= randomCoeff

     // Offset-1 sample
     acc += addQ(alphaPow, qVal, traceOodValues[tOodIdx++], shiftedY, qy, denomShiftedInv)
     alphaPow *= randomCoeff
   Else:
     acc += addQ(alphaPow, qVal, traceOodValues[tOodIdx++], oodsY, qy, denomOodsInv)
     alphaPow *= randomCoeff

4. For each composition column (0..7):
   acc += addQ(alphaPow, queriedComp[col][qi], compOodValues[col], oodsY, qy, denomOodsInv)
   alphaPow *= randomCoeff

5. Return acc as FRI answer for query qi

9. Debugging Strategy

The quotient computation is the hardest component to debug because errors are non-local: a wrong value at one column affects all subsequent columns through the alpha accumulation.

Our debugging strategy:

1. Rust transcript: Added logging to the Rust verifier's quotient computation at every column, outputting intermediate values $(a, b, c, \text{num}, \text{denom})$
2. Column-by-column comparison: Hardcoded Rust values in Solidity tests, comparing at each column boundary
3. Bisection: When the accumulator diverged, bisected to find the first differing column
4. Root cause analysis: Traced the divergence to specific arithmetic operations

For Bug #1 (conjugation), the first divergence appeared at column 0's $c$ coefficient — the line coefficient computed from $\bar{y_{\text{ood}}} - y_{\text{ood}}$, which directly uses the conjugate.

For Bug #2 (periodicity), all columns before 25 matched perfectly. Column 25 introduced an unexpected third contribution, shifting the alpha counter for all subsequent columns.

10. Gas Profile

DEEP quotient computation accounts for ~29% of total verification gas (~5M out of ~20M):

The per-query overhead (2 CM31 inversions) is modest; the bulk of the cost is the 58 column-wise QM31 multiplications across 3 queries = 174 iterations.