# Zk Stark Foundations

> STWO-specific STARK architecture and protocol flow. Provides implementation locations, security parameter configuration, proof flow mapping, and invariants. Use when working on proof system code, reviewing constraint logic, modifying FRI parameters, or auditing soundness.

- Skill: `starkware-libs/zk-stark-foundations` (Agent Skill)
- Install (CLI): `npx skillmds@latest add starkware-libs/zk-stark-foundations`
- Raw SKILL.md: https://api.skillmd.com/api/skills/starkware-libs/zk-stark-foundations/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Security
- Author: starkware-libs (https://skillmd.com/u/starkware-libs)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/starkware-libs/zk-stark-foundations

---


# ZK-STARK Foundations for STWO

## Canonical Theory Sources

- `.agents/papers/llm/INDEX.llm.md` — notation harmonization and source map
- `.agents/papers/llm/Circle_STARKs.llm.md` — core circle STARK AIR/FRI theory
- `.agents/papers/llm/Stwo_Whitepaper.llm.md` — STWO protocol layering and parameterization

## STWO Protocol Architecture

### AIR Constraints

Constraint polynomial identities over the trace
(`Circle_STARKs.llm.md` -> `e:overall:identity`):

```
P_i(s_i, p_1, ..., p_w, p_1 o T, ..., p_w o T) = 0   over H
```

**Implementation**: `crates/constraint-framework/src/lib.rs` — `EvalAtRow` trait

### FRI Low-Degree Test

Circle FRI variant operating over circle group domains
(`Circle_STARKs.llm.md` -> `prot:IOP:proximity`):
- **Verifier**: `crates/stwo/src/core/fri.rs` — `FriVerifier`
- **Prover**: `crates/stwo/src/prover/fri.rs` — `FriProver`

### Polynomial Commitment Scheme

FRI-based PCS with Merkle-committed evaluations and DEEP quotient openings:
- **Verifier**: `crates/stwo/src/core/pcs/`
- **Prover**: `crates/stwo/src/prover/pcs/`

### DEEP-ALI (Algebraic Linking)

OODS point sampling + DEEP quotient `(p(x) - p(z)) / (x - z)` + FRI.
Links committed evaluations to constraint identity
(`Circle_STARKs.llm.md` -> `prop:deep:quotients`, `thm:AIR:soundness`).
- **Quotients**: `crates/stwo/src/core/pcs/quotients.rs`
- **Verifier**: `crates/stwo/src/core/verifier.rs` — `verify()`

### Proof of Work (Grinding)

Pre-query PoW nonce adding `pow_bits` of security.
- `crates/stwo/src/core/proof_of_work.rs` (verifier)
- `crates/stwo/src/prover/backend/*/grind.rs` (prover)

## Security Parameters

| Parameter | Symbol | Config Field | Security Impact |
|-----------|--------|-------------|-----------------|
| Blowup factor | 2^B | `fri_config.log_blowup_factor` | Rate = 1/2^B. Higher = more secure but slower |
| FRI queries | s | `fri_config.n_queries` | Each query adds `log_blowup_factor` security bits |
| Grinding bits | g | `pcs_config.pow_bits` | Adds `g` bits of security |
| Last layer degree | - | `fri_config.log_last_layer_degree_bound` | Degree bound for the final FRI layer |
| Total security | - | `pcs_config.security_bits()` | = pow_bits + log_blowup_factor * n_queries |

**WARNING**: Default PcsConfig has only ~13 bits of security (test config).
Production must use appropriate parameters. See DIVERGENCE-007.

## STARK Proof Flow

```
1. Trace Generation      → Witness polynomials p_1,...,p_w
2. Trace Commitment       → Merkle commit evaluations on domain D
3. Constraint Evaluation  → Composition polynomial from random combination
4. Composition Commitment → Merkle commit composition evaluations
5. OODS Challenge         → Random point z on circle
6. DEEP Quotients         → (p(x) - p(z)) / vanishing(x,z) for each poly
7. FRI                    → Prove quotients are low-degree
8. Proof of Work          → Find grinding nonce
9. Query Phase            → Verify folding chain at random positions
```

**Implementation entry points**:
- Prover: `crates/stwo/src/prover/mod.rs` — `prove()`
- Verifier: `crates/stwo/src/core/verifier.rs` — `verify()`

## Security Invariants

INVARIANT-ZK-1: The composition polynomial identity must hold over the
entire trace domain H. A single violated constraint at any row breaks soundness.

INVARIANT-ZK-2: The OODS point must be sampled uniformly from the circle
group over the secure field, excluding the commitment domain.

INVARIANT-ZK-3: FRI folding challenges must be drawn from the Fiat-Shamir
transcript AFTER mixing in the previous layer's commitment.

INVARIANT-ZK-4: The Merkle tree commitment must be binding — the hash
function must be collision-resistant.

INVARIANT-ZK-5: The proof-of-work nonce must be verified by the verifier
before accepting the proof.

## Forbidden Actions

In this domain, agents must NEVER:
- Reduce security parameters without explicit human approval and documented justification
- Skip the OODS sampling step or use a deterministic point
- Reorder the Fiat-Shamir transcript (commitment → challenge ordering is critical)
- Remove or weaken any FRI verification check
- Accept a proof without verifying all layers including the last layer