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