Circle FRI Protocol

Overview

FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) is the core mechanism by which the STARK verifier confirms that committed polynomials have bounded degree. Circle FRI adapts the standard FRI protocol to the circle-group evaluation domain used by Stwo.

This page covers the domain structure, folding operations, pair reconstruction, Merkle verification at each layer, and the specific parameter values used in our verifier.

All FRI logic is implemented in FriVerifier.sol (222 lines).

1. FRI in a Nutshell

The prover claims to have committed a polynomial of degree $< D$ evaluated on a domain of size $N > D$. The verifier checks this by:

1. Folding: Combine pairs of evaluations using a random challenge $\alpha$ to produce a new polynomial of half the degree on a domain of half the size
2. Committing: The prover commits (Merkle tree) to each folded polynomial
3. Repeating: Continue folding until the polynomial is small enough to send explicitly
4. Checking: Verify the final polynomial against the committed constant, and spot-check random queries through all layers

If the original function was far from any low-degree polynomial, the folded function will (with high probability) fail the consistency checks.

2. Circle FRI vs Standard FRI

Standard FRI operates on multiplicative subgroups of a finite field: evaluations at $\omega^i$ are paired as $f(\omega^i)$ and $f(-\omega^i)$, then folded via:

Circle FRI replaces the multiplicative group with the circle group. The first fold is special:

• Circle → Line: Points $(x, y)$ and $(x, -y)$ (conjugate pairs on the circle) are folded using the y-coordinate as the twiddle factor. The result lives on a line domain (just x-coordinates).
• Subsequent folds: Standard FRI on the line domain.

This two-phase structure (one circle fold, then line folds) is unique to Circle STARKs.

3. Our Parameters

The full sequence:

4. The Fold Operation

Both circle and line folds share the same core computation:

function _fold(uint128 fP, uint128 fNegP, uint32 twiddleInv, uint128 alpha)
    internal pure returns (uint128)
{
    uint128 f0 = qm31Add(fP, fNegP);
    uint128 f1 = qm31MulM31(qm31Sub(fP, fNegP), twiddleInv);
    return qm31Add(f0, qm31Mul(alpha, f1));
}

Where:

• fP = evaluation at the "positive" position in the pair
• fNegP = evaluation at the "negative" position (conjugate/negation)
• twiddleInv = inverse of the distinguishing coordinate
• alpha = random folding challenge (QM31)

Mathematically:

Circle Fold Twiddle

For the first layer (circle → line), pairs are $(x, y)$ and $(x, -y)$. The twiddle is:

where $y$ is the y-coordinate of the circle domain point (accessed in bit-reversed order).

Line Fold Twiddle

For inner layers (line → line), pairs are $x$ and $-x$. The twiddle is:

where $x$ is the x-coordinate of the line domain point.

5. Domain Construction

5.1 Circle Domain (First Layer)

The evaluation domain for the committed polynomial is the canonical coset circle domain of log-size LIFTING_LOG_SIZE = 7:

CircleDomain { half_coset: half_odds(LIFTING_LOG_SIZE - 1) }

Where half_odds(n) = Coset(initial: G_{n+2}, step: G_n, log_size: n):

• initial = subgroupGen(LIFTING_LOG_SIZE + 1) = $G^{2^{31-8}} = G^{2^{23}}$
• step = subgroupGen(LIFTING_LOG_SIZE - 1) = $G^{2^{31-6}} = G^{2^{25}}$
• half_size = 2^6 = 64

The full domain has 128 points:

• First 64: initial + i * step for $i = 0, \ldots, 63$
• Last 64: negations of the first 64 (conjugate: $(x, y) \mapsto (x, -y)$)

Points are accessed in bit-reversed order — bit-reverse the index within the domain size before computing the point.

function circleDomainAt(uint32 liftingLogSize, uint256 i)
    internal pure returns (uint32 px, uint32 py)
{
    uint256 halfSize = 1 << (liftingLogSize - 1);
    uint256 initialIdx = subgroupGenIndex(liftingLogSize + 1);
    uint256 stepIdx = subgroupGenIndex(liftingLogSize - 1);

    if (i < halfSize) {
        uint256 pointIdx = reduceIndex(initialIdx + i * stepIdx);
        (px, py) = indexToPoint(pointIdx);
    } else {
        uint256 pointIdx = reduceIndex(initialIdx + (i - halfSize) * stepIdx);
        pointIdx = negIndex(pointIdx);
        (px, py) = indexToPoint(pointIdx);
    }
}

5.2 Line Domains (Inner Layers)

After the circle-to-line fold, subsequent layers operate on line domains — sets of x-coordinates on the circle.

For inner layer $k$ (0-indexed):

Domain = half_odds(LIFTING_LOG_SIZE - 1).repeated_double(k)

After $k$ doublings:

• initial = subgroupGen(LIFTING_LOG_SIZE + 1 - k)
• step = subgroupGen(LIFTING_LOG_SIZE - 1 - k)
• log_size = LIFTING_LOG_SIZE - 1 - k

function friLineDomainAt(uint32 layerIdx, uint32 liftingLogSize, uint256 i)
    internal pure returns (uint32 x)
{
    uint256 initialIdx = subgroupGenIndex(liftingLogSize + 1 - layerIdx);
    uint256 stepIdx = subgroupGenIndex(liftingLogSize - 1 - layerIdx);
    uint256 pointIdx = reduceIndex(initialIdx + i * stepIdx);
    (x, ) = indexToPoint(pointIdx);  // Only need x-coordinate
}

5.3 Last Layer Domain

The last layer domain is constructed the same way as inner layer domains, but after all N_FRI_INNER_LAYERS doublings:

function friLastLayerDomainAt(uint32 liftingLogSize, uint32 nInnerLayers, uint256 i)
    internal pure returns (uint32 x)
{
    uint256 initialIdx = subgroupGenIndex(liftingLogSize + 1 - nInnerLayers);
    uint256 stepIdx = subgroupGenIndex(liftingLogSize - 1 - nInnerLayers);
    uint256 pointIdx = reduceIndex(initialIdx + i * stepIdx);
    (x, ) = indexToPoint(pointIdx);
}

6. Pair Reconstruction

At each FRI layer, the verifier needs evaluations at pairs of conjugate positions. Some positions are queried directly; their partners may or may not also be queried.

Three cases arise:

Case 1: Both Siblings Queried

If positions $2k$ and $2k+1$ are both in the query set, use their evaluations directly.

Case 2: Only Even Position Queried

Position $2k$ is queried, $2k+1$ is not. The evaluation at $2k+1$ comes from the FRI witness array.

Case 3: Only Odd Position Queried

Position $2k+1$ is queried, $2k$ is not. The evaluation at $2k$ comes from the FRI witness array.

if (both siblings present) {
    evalEven = queryEvals[i];
    evalOdd = queryEvals[i + 1];
    i += 2;
} else if (query is even) {
    evalEven = queryEvals[i];
    evalOdd = witnessEvals[wIdx++];
    i += 1;
} else {  // query is odd
    evalEven = witnessEvals[wIdx++];
    evalOdd = queryEvals[i];
    i += 1;
}

After reconstruction, both sibling evaluations are verified against the Merkle tree for that layer.

7. Merkle Verification per Layer

Each FRI layer's evaluations are committed in a Merkle tree. After pair reconstruction, the verifier:

1. Hashes both siblings as QM31 leaves
2. Records their positions
3. Verifies the Merkle decommitment against the layer's committed root

The committed tree height equals the layer's domain log size:

• First layer: LIFTING_LOG_SIZE = 7
• Inner layer $k$: LIFTING_LOG_SIZE - 1 - k

8. Last Layer Verification

After all folds, the verifier receives the last-layer polynomial coefficients explicitly. For each remaining query position, it:

1. Bit-reverses the position within the last domain size
2. Computes the domain point x-coordinate
3. Evaluates the polynomial at that point (Horner's method)
4. Checks equality with the folded evaluation

function verifyLastLayer(
    uint256[] memory queryPositions,
    uint128[] memory queryEvals,
    uint128[] memory lastLayerPoly,
    uint32 liftingLogSize,
    uint32 nInnerLayers
) internal pure {
    uint32 lastDomainLogSize = liftingLogSize - 1 - nInnerLayers;
    for (uint256 i = 0; i < queryPositions.length; i++) {
        uint256 brIdx = bitReverseIndex(queryPositions[i], lastDomainLogSize);
        uint32 x = friLastLayerDomainAt(liftingLogSize, nInnerLayers, brIdx);
        require(queryEvals[i] == _evalPoly(lastLayerPoly, x), "FRI: last layer mismatch");
    }
}

Polynomial evaluation uses Horner's method over QM31, with an M31 evaluation point:

function _evalPoly(uint128[] memory coeffs, uint32 x) internal pure returns (uint128) {
    if (coeffs.length == 0) return 0;
    uint128 result = coeffs[coeffs.length - 1];
    for (uint256 i = coeffs.length - 1; i > 0; i--) {
        result = qm31Add(qm31MulM31(result, x), coeffs[i - 1]);
    }
    return result;
}

9. Bit Reversal

Bit reversal is used throughout FRI to map query positions to domain points. The circle and line domains are stored in bit-reversed order for efficient folding.

For an index $i$ in a domain of log-size $n$, the bit-reversed index reverses the lower $n$ bits:

function bitReverseIndex(uint256 i, uint32 logSize) internal pure returns (uint256) {
    if (logSize == 0) return i;
    uint256 reversed = _reverseBits256(i);
    return reversed >> (256 - uint256(logSize));
}

The full 256-bit reversal uses progressive swapping of bit groups (1, 2, 4, 8, 16, 32, 64, 128 bits), then extracts the top logSize bits.

10. Worked Example

Consider a simplified Circle FRI with 3 queries on a domain of size 8 ($\log = 3$).

Setup: Query positions (after sorting): $[1, 3, 5]$

First layer (Circle → Line, domain log 3):

• Position pairs: $(0,1)$, $(2,3)$, $(4,5)$
• Query 1 is at position 1 (odd) → need witness for position 0
• Queries 3 and 5 are at positions 3 and 5 (odd) → need witnesses for 2 and 4
• Bit-reverse each pair start within domain log 3:
  • Pair $(0,1)$: bit-reverse $0$ in 3 bits → $0$, lookup circleDomainAt(3, 0) → get $y$, twiddle = $1/y$
  • Pair $(2,3)$: bit-reverse $2$ in 3 bits → $2$, lookup circleDomainAt(3, 2) → get $y'$, twiddle = $1/y'$
  • Pair $(4,5)$: bit-reverse $4$ in 3 bits → $1$, lookup circleDomainAt(3, 1) → get $y''$, twiddle = $1/y''$
• Fold each pair: $\text{fold}(f_{\text{even}}, f_{\text{odd}}, t^{-1}, \alpha_1)$
• Folded positions: $[0, 1, 2]$ (each pair maps to its index ÷ 2)

Inner layer 0 (Line → Line, domain log 2):

• Folded positions $[0, 1, 2]$
• Pairs: $(0,1)$ — both present! And position 2, whose partner is position 3 (from witness)
• Bit-reverse and compute line domain twiddles
• Fold → positions $[0, 1]$

Inner layer 1 (Line → Line, domain log 1):

• Positions $[0, 1]$ — a complete pair
• Fold → position $[0]$

Last layer: Evaluate the constant polynomial at domain point, check against folded value.

11. Gas Impact

FRI verification dominates the overall gas cost (~41% of total ~20M gas). The main contributors:

The dominant cost is Merkle verification across all FRI layers — each layer requires a separate tree walk.