Field Arithmetic: M31 → CM31 → QM31

Overview

The Circle STARK verifier operates over a three-level algebraic extension tower built on the Mersenne-31 prime. This page covers the mathematical definitions, Solidity implementation details, packing conventions, and test vectors for each level.

All arithmetic is implemented in M31Lib.sol (311 lines).

1. M31 — The Base Field

Definition

This is the largest Mersenne prime that fits in 31 bits. Elements are integers in $[0, p)$.

Why Mersenne-31?

Mersenne primes enable shift-based modular reduction. For any product $x = a \times b$ (at most 62 bits):

Proof: Write $x = h \cdot 2^{31} + \ell$. Then $x = h \cdot (p+1) + \ell = h \cdot p + h + \ell \equiv h + \ell \pmod{p}$.

The result may be $\geq p$, requiring at most one subtraction. This is dramatically cheaper than general modular reduction.

Solidity Implementation

// M31 addition: single add + conditional subtract
function m31Add(uint32 a, uint32 b) internal pure returns (uint32) {
    uint256 sum = uint256(a) + uint256(b);
    if (sum >= P) sum -= P;
    return uint32(sum);
}

// M31 multiplication: Mersenne reduction
function m31Mul(uint32 a, uint32 b) internal pure returns (uint32) {
    uint256 product = uint256(a) * uint256(b);
    uint256 lo = product & P;     // low 31 bits
    uint256 hi = product >> 31;   // high bits
    uint256 r = lo + hi;
    if (r >= P) r -= P;
    return uint32(r);
}

// M31 inversion via Fermat: a^(p-2) mod p
function m31Inv(uint32 a) internal pure returns (uint32) {
    require(a != 0, "M31: division by zero");
    return m31Exp(a, P - 2);
}

Representation

M31 elements are stored as uint32. The maximum valid value is $p - 1 = 2{,}147{,}483{,}646$. Zero is represented as 0, not as $p$.

Test Vectors

2. CM31 — Complex Extension

Definition

Elements are $a + bi$ where $a, b \in \mathbb{F}_p$ and $i^2 = -1$.

This is the Gaussian integers modulo $p$. The polynomial $x^2 + 1$ is irreducible over $\mathbb{F}_p$ because $-1$ is a quadratic non-residue modulo $p$ (since $p \equiv 3 \pmod 4$).

Packing Convention

CM31 is packed into uint64:

• Low 32 bits: real part ($a$)
• High 32 bits: imaginary part ($b$)

function cm31Pack(uint32 real, uint32 imag) internal pure returns (uint64) {
    return uint64(real) | (uint64(imag) << 32);
}

Arithmetic

Multiplication: Standard complex multiplication

4 M31 multiplications + 1 addition + 1 subtraction.

Conjugation: $(a + bi) \mapsto (a - bi)$. Negates only the imaginary part.

Inversion: Uses the norm identity

The denominator $a^2 + b^2$ is an M31 element (guaranteed nonzero for nonzero CM31), inverted via m31Inv.

Negation: $-(a + bi) = (-a) + (-b)i$. Negates both components.

3. QM31 — Quartic Extension (SecureField)

Definition

Elements are $a + bu$ where $a, b \in \mathbb{F}_{p^2}$ (CM31) and $u^2 = 2 + i$.

The constant $R = 2 + i$ is chosen so that $u^2 - R$ is irreducible over $\mathbb{F}_{p^2}$. This means $2 + i$ must be a quadratic non-residue in CM31.

QM31 is Stwo's SecureField — the field used for all random challenges, ensuring they are drawn from a space of size $\sim 2^{124}$.

Packing Convention

QM31 is packed into uint128:

• Low 64 bits: first CM31 component ($a$)
• High 64 bits: second CM31 component ($b$)

Which expands to four M31 values:

• Bits [0..31]: $m_0$ (real part of $a$)
• Bits [32..63]: $m_1$ (imaginary part of $a$)
• Bits [64..95]: $m_2$ (real part of $b$)
• Bits [96..127]: $m_3$ (imaginary part of $b$)

function qm31FromM31(uint32 a, uint32 b, uint32 c, uint32 d) internal pure returns (uint128) {
    return qm31Pack(cm31Pack(a, b), cm31Pack(c, d));
}

Arithmetic

Multiplication: In $\mathbb{F}_{p^2}[u]/(u^2 - R)$:

This requires 4 CM31 multiplications + 1 CM31 multiplication by $R$ + 2 CM31 additions.

Since $R = 2 + i$ is a small constant, the multiplication by $R$ is:

which is 4 M31 multiplications + 2 M31 additions + 1 M31 subtraction — slightly cheaper than a general CM31 multiply.

Inversion: Analogous to CM31:

The denominator $a^2 - R \cdot b^2$ is a CM31 element, inverted via cm31Inv.

Complex Conjugation

Stwo defines complex conjugation for QM31 as:

impl ComplexConjugate for QM31 {
    fn complex_conjugate(&self) -> Self {
        Self(self.0, -self.1)  // Negate ENTIRE second CM31
    }
}

For $q = (m_0, m_1, m_2, m_3)$:

The correct Solidity implementation:

function _conjQ(uint128 q) internal pure returns (uint128) {
    return M31Lib.qm31Pack(
        M31Lib.qm31First(q),          // Keep first CM31 unchanged
        M31Lib.cm31Neg(M31Lib.qm31Second(q))  // Negate ENTIRE second CM31
    );
}

Note: cm31Neg (negate both real and imaginary) is used, not cm31Conj (negate only imaginary). This is the algebraic conjugation in the extension $\mathbb{F}_{p^2}[u]/(u^2 - R)$: it maps $u \mapsto -u$, which negates the coefficient of $u$ as a whole CM31 element.

Why This Matters

The complex conjugate appears in every DEEP quotient line equation:

If $\bar{v}$ is computed incorrectly, the line coefficients $a$ and $c$ are wrong. This propagates through the numerator and corrupts the quotient. Since each quotient is accumulated with a power of $\alpha$, a single wrong quotient eventually corrupts the entire FRI input.

The bug was subtle because:

• For QM31 elements with $m_1 = 0$ or $m_2 = 0$, both implementations agree
• The first several columns' quotients appeared correct
• The error only became visible after accumulating enough wrong contributions

4. Circle Point Arithmetic

Definition

Points $(x, y)$ on the unit circle $x^2 + y^2 = 1$ over $\mathbb{F}_p$.

Group Operation

$(x_1, y_1) \circ (x_2, y_2) = (x_1 x_2 - y_1 y_2, \; x_1 y_2 + y_1 x_2)$

This is complex multiplication restricted to the unit circle. The identity is $(1, 0)$.

Generator

$G = (2, 1268011823)$ with $|G| = 2^{31} = p + 1$.

The generator order equals $p + 1$ (not $p - 1$ as in multiplicative groups). This is a fundamental difference from standard STARK domains.

Scalar Multiplication

To compute $G^k$, we use binary square-and-multiply:

function circleMul(uint32 x, uint32 y, uint256 scalar)
    internal pure returns (uint32 rx, uint32 ry)
{
    rx = 1; ry = 0;  // Identity
    while (scalar > 0) {
        if (scalar & 1 == 1) {
            (rx, ry) = circleAdd(rx, ry, x, y);
        }
        (x, y) = circleAdd(x, y, x, y);
        scalar >>= 1;
    }
}

Doubling (x-coordinate only)

For FRI line domains, we only need the x-coordinate after doubling:

This avoids computing the y-coordinate entirely.

5. Gas Costs

Approximate gas costs for each operation (measured via forge test):

QM31 multiplication is the dominant cost in the verifier — it appears in every quotient accumulation and every FRI fold.