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.

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

2. Circle FRI vs Standard FRI

Standard FRI operates on multiplicative subgroups. 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) are folded using the y-coordinate as the twiddle factor. Result lives on a line domain.
• Subsequent folds: Standard FRI on the line domain.

3. Our Parameters

The full sequence:

4. The Fold Operation

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));
}

Circle Fold Twiddle

For the first layer, pairs are $(x, y)$ and $(x, -y)$. Twiddle: $t^{-1} = 1/y$.

Line Fold Twiddle

For inner layers, pairs are $x$ and $-x$. Twiddle: $t^{-1} = 1/x$.

5. Domain Construction

Circle Domain (First Layer)

The evaluation domain is the canonical coset circle domain of log-size LIFTING_LOG_SIZE = 7. It has 128 points: 64 "positive" points and their conjugates.

Points are accessed in bit-reversed order.

6. Pair Reconstruction

At each FRI layer, the verifier needs evaluations at pairs of conjugate positions:

1. If both positions are queried — use them directly
2. If only one position is queried — the partner comes from the FRI witness array
3. After reconstruction, both siblings are verified against the layer's Merkle tree

7. Last Layer Verification

After all folds, the verifier receives the last-layer polynomial explicitly. For each query position, it evaluates the polynomial at the corresponding domain point using Horner's method and checks against the folded evaluation.

8. Gas Impact

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

The dominant cost is Merkle verification across all FRI layers.