DEEP Quotient Computation

Out-of-domain quotient accumulation — line equations, conjugate pairs, and periodicity samples.

Overview

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

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 constructs a quotient that is zero if and only if the claim is true:

Q(P) = \frac{f(P) - L(P)}{Z(P)}

where $L$ is the unique line through the claimed evaluation and its conjugate, and $Z$ vanishes at those points.

2. Points Involved

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

P_{\text{ood}} = \left(\frac{1-t^2}{1+t^2}, \; \frac{2t}{1+t^2}\right)

Shifted Point — For columns with mask offset 1:

P_{\text{shifted}} = P_{\text{ood}} \cdot G_{\text{trace}}

Query Points — M31 circle domain points at the queried positions.

3. Line Equation Through Conjugate Pairs

QM31 Conjugation

Recall: $\overline{(m_0, m_1, m_2, m_3)} = (m_0, m_1, -m_2, -m_3)$ — negate entire second CM31, NOT element-wise. See Field Arithmetic for details.

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

a = \bar{v} - v, \quad c = \bar{y_s} - y_s, \quad b = v \cdot c - a \cdot y_s

4. Quotient Contribution

For each column sample:

\Delta Q = \alpha^k \cdot \frac{c \cdot f(q) - (a \cdot q_y + b)}{\text{denom}}

where the denominator depends only on the sample point and query point (pre-computed 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));

5. Accumulation Order

Single-Offset Columns

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)

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.

Total $\alpha$ Count

For the withdrawal circuit (46 trace columns): $44 \times 1 + 2 \times 3 + 8 \times 1 = 58 \text{ contributions}$

For the transfer circuit (57 trace columns): $55 \times 1 + 2 \times 3 + 8 \times 1 = 69 \text{ contributions}$

6. Periodicity Samples: The Deep Cut

This Was Bug #2

Missing periodicity samples shifted all subsequent alpha powers by 2, corrupting every quotient contribution after column 25. The error was only discovered through exhaustive intermediate-value comparison with the Rust prover.

For any column with 2 or more mask offsets, Stwo adds an additional "periodicity" quotient contribution before the regular offset samples.

For our parameters, the periodicity point coincides with the shifted point ( $G_{\text{period}} = \text{identity}$ ), so the periodicity sample uses the offset-1 OOD value at the shifted point.

7. Gas Profile

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

Operation	Per Column	Count	Total
QM31 conjugation	~100	58	~6K
Line coefficients (3 QM31 muls)	~3,600	58	~209K
Alpha scaling (3 QM31 muls)	~3,600	58	~209K
Numerator (2 QM31 muls)	~2,500	58	~145K
Denom multiply + accumulate	~1,300	58	~75K

DEEP Quotient Computation

On this page