Fri Protocol

FRI Protocol (Circle Variant)

Canonical Theory Sources

• .agents/papers/llm/INDEX.llm.md — unified symbol map and conflict notes
• .agents/papers/llm/Circle_STARKs.llm.md — core circle FRI decomposition/folding soundness
• .agents/papers/llm/Stwo_Whitepaper.llm.md — multi-domain FRI and parameter/security framing

Protocol Structure

Configuration

// crates/stwo/src/core/fri.rs — FriConfig
pub struct FriConfig {
    pub log_blowup_factor: u32,         // Rate = 1/2^B
    pub log_last_layer_degree_bound: u32, // Degree of final polynomial
    pub n_queries: usize,                // Number of query positions
    pub line_fold_step: u32,             // Folding step for inner layers
}

Parameter ranges (enforced in FriConfig::new()):

• log_last_layer_degree_bound: 0..=10
• log_blowup_factor: 1..=16
• line_fold_step: must be > 0

Security: security_bits() = log_blowup_factor * n_queries (plus pow_bits from the PCS config).

Commit Phase

Source: .agents/papers/llm/Circle_STARKs.llm.md (prot:IOP:proximity, prot:IOP:proximity:batch)

1. First layer (circle-to-line fold):

   • Input: polynomial evaluations on a circle domain
   • Operation: J-split fold with random alpha
   • The circle domain collapses to a line domain
   • Constant: CIRCLE_TO_LINE_FOLD_STEP in verifier

2. Inner layers (line folds):

   • Input: evaluations on a line domain
   • Operation: fold by line_fold_step with random alpha per step
   • Each fold halves the domain by fold_step doublings
   • Last inner layer may use a smaller fold_step to land exactly on log_last_layer_degree_bound

3. Last layer:

   • Prover sends the coefficients of the final polynomial
   • Degree must be <= 2^log_last_layer_degree_bound

Verification (Query Phase)

Implementation: crates/stwo/src/core/fri.rs — FriVerifier struct + impl

1. Sample queries: Draw n_queries random positions from the first layer domain
2. Decommit first layer: Verify Merkle openings, fold circle evaluations to line
3. Decommit inner layers: For each layer, verify Merkle openings and fold
4. Verify last layer: Check folded evaluations match the last layer polynomial

Folding Operations

Circle-to-line fold (fold_circle):

Given f(x,y) at point P and conjugate -P:
  f_folded(x) = (f(P) + f(-P))/2 + alpha * (f(P) - f(-P))/(2y)

This is the J-split: even + alpha * odd component.

Line fold (fold_line):

Given g(x) at point x and -x:
  g_folded(2x^2-1) = (g(x) + g(-x))/2 + alpha * (g(x) - g(-x))/(2x)

Implementation:

• Verifier: crates/stwo/src/core/fri.rs — SparseEvaluation::fold_circle(), FriInnerLayerVerifier::verify_and_fold()
• Prover: crates/stwo/src/prover/fri.rs — FriProver
• Backend ops: crates/stwo/src/prover/backend/*/fri.rs

Multi-Step Folding

When line_fold_step > 1, multiple folding rounds are batched into a single FRI layer commitment. The verifier must unfold fold_step times using fold_step many folding alphas (drawn from a single alpha via powers).

Source: .agents/papers/llm/Stwo_Whitepaper.llm.md (prot:cFRI:multi, e:cFRI:multi:folding)

Sparse Evaluation

FRI queries produce a "sparse evaluation" — values at query positions and their conjugate/symmetric positions needed for folding.

// crates/stwo/src/core/fri.rs — SparseEvaluation
// Subset of evaluations at specific query positions, grouped for folding

Error Types

pub enum FriVerificationError {
    InvalidNumFriLayers,           // Wrong number of folding layers
    FirstLayerEvaluationsInvalid,  // Circle fold check failed
    FirstLayerCommitmentInvalid,   // Merkle proof invalid
    InnerLayerEvaluationsInvalid,  // Line fold check failed
    InnerLayerCommitmentInvalid,   // Merkle proof invalid
    LastLayerDegreeInvalid,        // Final polynomial too large
    LastLayerEvaluationsInvalid,   // Final polynomial doesn't match
}

Security Analysis

Source: .agents/papers/llm/Circle_STARKs.llm.md (thm:FRI:soundness:round:by:round) and .agents/papers/llm/Stwo_Whitepaper.llm.md (thm:cFRI:multi:soundness, Section "6. Parameter Rules")

Soundness error has three components:

1. Proximity gap: Depends on rate (rho = 1/2^B), list-decoding radius
2. Folding error: Per-round error from random folding challenges
3. Query error: alpha^s where alpha depends on rate, s = n_queries

Total security bits = pow_bits + log_blowup_factor * n_queries

Default config (PcsConfig::default): 10 + 1*3 = 13 bits. TEST ONLY. Production target: 100+ bits (e.g., pow_bits=26, log_blowup=4, n_queries=20)

Security Invariants

INVARIANT-FRI-1: Every FRI layer commitment must be mixed into the Fiat-Shamir channel BEFORE drawing the folding alpha.

INVARIANT-FRI-2: The last layer polynomial degree must be strictly checked against log_last_layer_degree_bound.

INVARIANT-FRI-3: Query positions must be sampled uniformly after all commitments are mixed.

INVARIANT-FRI-4: Folding operations must use the correct twiddle factors (conjugate y-coordinates for circle fold, x-coordinates for line fold).

INVARIANT-FRI-5: The domain chain must be correct: each folded domain is derived from the previous by the squaring map.

Forbidden Actions

In this domain, agents must NEVER:

• Change FRI parameter range bounds without re-deriving security analysis
• Skip any FRI layer verification step
• Modify the folding operation (alpha mixing) without mathematical proof
• Reorder commitment-then-challenge in the Fiat-Shamir transcript
• Change the last layer degree check to be non-strict