STARK
Scalable Transparent ARguments of Knowledge. A proof-system class with three properties: no trusted setup, sublinear verification, and hash-based soundness. Sahyadri uses FRI-based STARKs over binary fields as its primary proof primitive.
1. Formal Definition
A STARK is a pair of probabilistic polynomial-time algorithms (Prove, Verify) for a relation R ⊆ 1* × 1*, satisfying four properties. Each property is essential; removing any one produces a weaker system that is no longer a STARK.
Definition 1.1 (STARK)
A STARK for a relation R is (Prove, Verify) where:
Prove(statement x, witness w) → π if (x, w) ∈ R
Verify(statement x, proof π) → {⊤, ⊥}
satisfying:
Completeness:
∀(x, w) ∈ R: Pr[Verify(x, Prove(x, w)) = ⊤] = 1 - negl(λ)
Soundness:
∀x ∉ L_R, ∀π*: Pr[Verify(x, π*) = ⊤] ≤ 2^(-λ) + negl(λ)
Transparency:
Prove and Verify share no secret setup. No trusted party. No
common reference string. Randomness is derived from public
hash functions via Fiat-Shamir.
Scalable verification:
T_verify(π) = poly(λ) · polylog(T_compute)
|π| = poly(λ) · polylog(T_compute)
where T_compute is the time to compute the relation directly,
λ is the security parameter (typically 100-128).The four properties define the class. Different STARK instantiations make different choices for field, hash function, polynomial commitment scheme, and Fiat-Shamir transform. These choices determine proof size, verify time, and quantum security — but they do not change what a STARK is.
2. The IOP Foundation
STARKs are constructed from Interactive Oracle Proofs (IOPs). An IOP is an interactive protocol where the prover sends oracle functions (typically polynomials) rather than explicit strings, and the verifier can query those oracles at points of its choosing.
IOP structure:
Prover P and verifier V exchange messages:
P → V: oracle f_1
V → P: random challenge r_1
P → V: oracle f_2
V → P: random challenge r_2
...
V → P: random challenge r_k
P → V: query responses
Verifier queries f_i at specific points and decides accept/reject.
IOP → STARK:
Fiat-Shamir transform replaces V's randomness with hash outputs:
r_i = H(state ‖ transcript_i)
The hash is modeled as a random oracle, giving the IOP
non-interactive soundness in the random oracle model.The soundness error of the IOP is ε = q / |F| where q is the number of queries and F is the field. For Goldilocks, |F| = 2^64 - 2^32 + 1, so ~64 bits per query. With 100 queries, the soundness error is ~2^-6400 — far beyond any plausible attack, which is why query counts can be lower than a naive analysis suggests.
3. FRI — The Polynomial Commitment
FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) is the PCS that most STARK implementations use. It reduces the polynomial commitment problem to Merkle commitment of a Reed-Solomon codeword.
FRI problem statement:
Given: commitment to a function f: D → F (as Merkle root of
codeword evaluations)
Prove: f is close to a polynomial of degree < d
FRI protocol:
1. Prover sends commitment to f
2. Verifier sends random challenge α_1
3. Prover computes f_1(x) = f(x) + α_1 · f(-x), sends commitment
4. Verifier sends α_2
5. Prover computes f_2 from f_1, sends commitment
... repeat log(d) times
Final: verifier queries a few points and checks consistency
Soundness:
If f is δ-far from degree-d polynomial, then with probability
≥ 1 - |D|/|F|, the FRI test rejects.
Proof size:
O(log(d) · log(|D|)) Merkle path inclusions
For typical parameters: 30-80 KB base proofFRI is what makes STARKs "scalable." A naive polynomial commitment would require the verifier to check all evaluations of the polynomial, which is the same as re-executing the computation. FRI reduces this to a logarithmic number of Merkle path checks.
4. Sahyadri's Instantiation
Sahyadri uses a specific STARK instantiation. Each parameter was chosen to satisfy a concrete protocol requirement.
Sahyadri STARK instantiation:
Field: Goldilocks (2^64 - 2^32 + 1)
Hash (FRI): Poseidon2 W8, rate 4, digest 4
Hash (content): SHA3-256
PCS: FRI with log_blowup = 2, 100 queries,
16-bit query PoW
Fiat-Shamir: Poseidon2 over Goldilocks
Signatures: ML-DSA-65 (Dilithium3, NIST Level 3)
Recursion: Binary-field AIRs via Plonky3
Proof parameters:
Base proof size: 631-735 KB (for N = 2..8 signatures)
Chain proof size: ~350 KB (extrapolated, at 4444 leaves; measured ~430 KB at 65,536 leaves)
Verify time: 35 ms (base), 1.5 ms (chain)
Soundness error: ≤ 2^-80 per proof (100 queries, 100-bit target)
Quantum security: ~128-bit for hashing, NIST Level 3 for signaturesEach parameter choice has a rationale. Goldilocks fits in 64-bit arithmetic, so Poseidon2 over it runs in native CPU registers — no big-integer library. Poseidon2 has ~300 AIR constraints per permutation, versus ~30,000 for SHA3-256 — a 100× reduction that makes in-circuit hashing feasible. The 100-query FRI with 16-bit query PoW achieves roughly 80-bit security, which is the standard target for consumer-facing protocols.
5. Execution Trace
A STARK proves that a computation was executed correctly. The computation is expressed as an execution trace — a matrix where rows are time steps and columns are state variables.
Example: simple counter
Program: counter ← counter + 1
Initial value: 0
Steps: 8
Execution trace (2 columns, 8 rows):
step | counter | step_num
─────┼─────────┼─────────
0 | 0 | 0
1 | 1 | 1
2 | 2 | 2
3 | 3 | 3
4 | 4 | 4
5 | 5 | 5
6 | 6 | 6
7 | 7 | 7
AIR constraints:
C1: counter[r+1] = counter[r] + 1 (transition)
C2: step_num[r+1] = step_num[r] + 1 (transition)
C3: counter[0] = 0 (boundary)
C4: step_num[0] = 0 (boundary)
C5: step_num[7] = 7 (boundary)
If all constraints hold at all rows, the trace represents a valid
execution of the program. The STARK proves exactly this.The AIR (Algebraic Intermediate Representation) defines the constraints. The STARK proves that a specific trace satisfies the constraints — which implies that the computation terminated correctly. The verifier does not re-execute the computation; it verifies that the trace is consistent with the constraint system.
6. Recursion
STARKs are recursively composable. A STARK can prove the statement "there exists a proof π such that Verify(x, π) = ⊤." This is what enables proof aggregation.
Recursion definition:
Define Verify-AIR as the constraint system that encodes the
STARK verifier itself. Then:
π_rec = Prove(
statement: "Verify-AIR(vk, public_inputs, π_child) accepts",
witness: π_child
)
where vk is the verification key, π_child is the proof being verified.
Cost of recursion:
|π_rec| ≈ |π_child| + constant
T_verify(π_rec) ≈ T_verify(π_child)
The proof does not grow with depth. A chain of n aggregated proofs
produces a root proof of size O(1) in n.This is what makes O(1) chain proofs possible. Each aggregation step takes two child proofs and produces a parent proof. The parent proof's size and verify time are independent of how many child proofs it covers — because the recursion is at the commitment level, not at the AIR level.
The cost of recursion. A recursively composed proof is larger than a base proof. Base batch proofs are 631-735 KB; aggregated chain proofs are ~200 KB serialized. The reduction happens because the chain aggregation does not recursively prove the content of the batch proofs — it proves only that specific hashes were committed. This is what makes the ~3× size reduction possible.
7. What a STARK Does Not Provide
A STARK proves one thing: the computation encoded in the AIR was executed correctly. It does not prove anything else. This boundary is frequently overlooked.
A STARK does NOT prove:
1. That the AIR correctly encodes the intended computation.
If the AIR is wrong, the STARK proves the wrong thing.
2. That the input to the computation was well-formed.
A STARK can prove "given input X, output is Y" without
proving that X itself is valid.
3. That the constraint system is sound.
Some programs cannot be encoded as polynomial constraints.
Encoding mistakes produce STARKs that prove nothing.
4. That the verifier's parameters are correct.
If the FRI parameters are too weak, a STARK can be forged.
Parameter selection is a protocol-level decision, not a
proof-system property.
5. Zero-knowledge (by default).
Standard STARKs are not zero-knowledge — they reveal the
execution trace. ZK-STARKs add masking polynomials to hide
witness values.
6. Post-quantum security (automatically).
Only if the hash function and field are quantum-safe.
STARKs instantiated over hash functions are post-quantum;
STARKs that commit to elliptic-curve points are not.Sahyadri's STARK usage specifically addresses each of these:
- AIR correctness is verified by the formal specification in
crypto/plonky3/src/. The AIRs are tested against the native implementations — a STARK proof must be accepted only if the native code also accepts. - Input well-formedness is checked by the transaction validation layer before the STARK is produced. Malformed transactions are rejected at the mempool.
- Parameter selection uses the standard 100-query FRI configuration. This is the strongest setting used in production systems; weaker settings are not used anywhere in the codebase.
- Zero-knowledge is not claimed. Sahyadri's STARKs are transparent, not zero-knowledge. Verification reveals the proof and therefore the input-output relationship. Applications that need privacy must add ZK-masking or use a different construction.
- Post-quantum security is structural. No elliptic curves appear in the STARK path. All hashing is Poseidon2 or SHA3-256; all signature verification is ML-DSA-65. The stack is post-quantum because every primitive in it is post-quantum — not because "STARK is post-quantum" as a class property.
8. STARK vs Other Proof Systems
| System | Trusted setup | PQ secure | Proof size | Verify |
|---|---|---|---|---|
| STARK (Sahyadri) | None | Yes (hash-based) | 631-735 KB (batch) | 35 ms |
| STARK (Sahyadri chain) | None | Yes | ~200 KB | 1.5 ms |
| Groth16 | Trusted per circuit | No (pairings) | ~200 B | ~5 ms |
| PLONK | Universal trusted setup | No (pairings) | ~500 B | ~5 ms |
| Bulletproofs | None | No (EC-based) | ~1-2 KB | ~10 ms |
| KZG | Trusted per ceremony | No | ~48 B | ~2 ms |
STARKs are not the smallest proofs. Groth16 and KZG are orders of magnitude smaller. STARKs are the only class that combines transparency, post-quantum security, and recursive composition without a trusted setup. For Sahyadri's requirements — no trusted parties, quantum resistance from genesis, O(1) recursion at scale — this combination is mandatory, not optional.
9. Where STARKs Appear in Sahyadri
Four distinct proof types appear in the live codebase. Each has its own AIR definition, its own constraint count, and its own role.
Proof type AIR constraints Verify cost Dilithium-3 signature ~30,000/signature 35 ms (batch of 2..8) Location: crypto/plonky3/src/dilithium_stark/ Purpose: Verify ML-DSA-65 signatures in-circuit AIR: Matrix-vector multiplication, NTT, rejection sampling SMT state proof ~5,000/path <1 ms Location: crypto/plonky3/src/smt_stark/ Purpose: Verify Merkle path against SMT root AIR: Poseidon2 permutations, path bit checks Poseidon2 hash proof ~300/permutation ~1 ms Location: crypto/plonky3/src/poseidon2_stark/ Purpose: Verify hash outputs in-circuit AIR: Poseidon2 round function Chain aggregation ~5,000/link 1.5 ms at 4444 links Location: crypto/plonky3/src/smt_stark/chain_blob.rs Purpose: Link chain proof to parent proof AIR: Hash check, commitment verification
10. Path A vs Path B — Soundness Disclosure
The current STARK aggregation uses Path B soundness. This is a protocol-level choice, not a STARK property. It is documented here because it affects what claims are valid.
Path A (full adversarial soundness):
Approach: Verify the entire Merkle path in-circuit.
Effect: A malicious prover cannot lie about inclusion.
Cost: ~19 min (legacy in-circuit Path A). A'2 bus-delegated Merkle: 4-level measured 0.28 s, 4444-level target in progress.
Status: Non-viable.
Path B (public-value binding, current):
Approach: Verify only the sumcheck + fold chain in-circuit. Merkle
verified natively outside the proof, during child-proof
generation.
Effect: Sound against honest-prover attacks. Forgery requires
breaking Fiat-Shamir.
Cost: ~298 ms per composition.
Status: Testnet-grade. Implemented and running.
A'2 (delegated Merkle, under research):
Approach: Split a compact MerkleVerifierAir off the main circuit.
Batch-verify 8 Merkle paths per proof.
Target: ~5-10× constraint reduction.
Status: Not started. 2-3 week research spike.A STARK is only as strong as the AIR it proves. Path B's AIRs prove a weaker statement than Path A's — this is why Path B is faster, and why Path B is not sufficient for a full mainnet audit that demands adversarial soundness. The trade-off is documented, not hidden.
11. Relationship with Plonky3
STARK is the proof-system class. Plonky3 is the Rust framework implementing a specific instantiation of that class. They are not the same thing, and the distinction matters for evaluating claims about the protocol.
STARK Plonky3 Proof-system class Rust framework Mathematical definition Implementation (Prove, Verify) pair Library of primitives Multiple instantiations One specific instantiation Abstract, no code Concrete, all code Not a software artifact A specific software artifact What Plonky3 provides: - Field arithmetic (Goldilocks, BabyBear, Mersenne31) - Hash functions (Poseidon2, Keccak, BLAKE3) - FRI commitment scheme - AIR abstraction - Recursion primitives What Sahyadri provides on top of Plonky3: - AIR definitions for Dilithium-3, SMT, Poseidon2, chain aggregation - Chain commitment protocol - Aggregation strategy (binary tree, N-to-1) - Mining-aware proving scheduler - Path A vs Path B choice
When this documentation says "Sahyadri uses STARKs," it means: Sahyadri defines AIRs for its specific computations using Plonky3's field, hash, and FRI primitives, and produces proofs with Plonky3's prover. It does not mean Sahyadri uses a turnkey STARK library — because no such thing exists at this level of customization.
12. Complexity
| Operation | Time | Space | Notes |
|---|---|---|---|
| STARK proof generation | O(T_compute · log T_compute) | O(T_compute) | Dominated by polynomial evaluation |
| STARK proof verification | O(log T_compute · queries) | O(log T_compute) | FRI verify dominates |
| STARK proof size | O(log T_compute · queries) | — | Logarithmic in computation size |
| Recursive composition | O(1) per link | O(1) | Constant cost independent of depth |
| FRI folding (per round) | O(|D|) | O(|D|) | |D| is the domain size, halves each round |
| Merkle commitment | O(|D|) | O(|D|) | One hash per codeword element |
13. Security Analysis
The security of a STARK rests on two assumptions. Both are stated formally. Neither requires trusting any party.
Assumption 13.1 (Hash collision resistance)
For a hash function H used in the Merkle commitment:
Pr[A finds x ≠ y : H(x) = H(y)] ≤ 2^(-λ_coll)
For Poseidon2 over Goldilocks with 256-bit output:
λ_coll ≈ 128 (classical)
λ_coll ≈ 64 (quantum, Grover for collision)
Assumption 13.2 (FRI soundness)
The FRI protocol with q queries, log_blowup = 2, and 16-bit
query PoW provides soundness error:
ε_sound ≤ (proximity_gap) + 2^(-q · log(|F|))
For q = 100, |F| = 2^64:
ε_sound ≈ 2^-80 + negl(λ) (with query PoW providing
additional 16-bit work factor)Both assumptions are hash-based. No elliptic-curve assumption appears anywhere. A quantum adversary gains only a quadratic speedup against hash preimage search (Grover) — the security parameter is halved, not broken. For a 256-bit commitment, quantum security is ~128-bit, which remains infeasible.
14. Limitations
What Sahyadri's STARK implementation does not do, stated plainly:
Not provided by Sahyadri's STARKs:
1. Zero-knowledge.
Standard STARKs reveal the execution trace. Sahyadri's STARKs
are transparent, not private. Applications that need privacy
must add masking or use a different construction.
2. Smallest proofs.
Groth16 and KZG produce 200-500 byte proofs. Sahyadri's STARK
base proofs are 631-735 KB — roughly 3× larger than the ~200 KB chain proof. This is the cost of
transparency and post-quantum security.
3. Fastest verification.
Groth16 verifies in ~5 ms. Sahyadri's base STARKs verify in
35 ms. The chain proof (1.5 ms) is faster, but base proofs are
not the smallest or fastest in the field.
4. Full adversarial soundness (currently).
Path B soundness is implemented. Path A soundness would require
3800× more compute and is not viable. The trade-off is
documented in proof-aggregation.
5. Protection against AIR bugs.
If an AIR definition is wrong, the STARK proves the wrong thing.
AIR correctness must be verified by testing against native
implementations — the STARK system itself cannot detect this.15. Summary
STARK is a proof-system class defined by four properties: completeness, soundness, transparency, and scalability. Sahyadri uses a specific instantiation — FRI-based proofs over Goldilocks with Poseidon2 hashing and ML-DSA-65 signatures — implemented via Plonky3.
Four proof types appear in the codebase: batch signature proofs (631-735 KB), SMT state proofs (~2 KB), Poseidon2 hash proofs (~1 KB), and chain proofs (~200 KB). Each has its own AIR definition; none is a Plonky3 out-of-the-box construction.
The chain proof is ~200 KB serialized (growing sublinearly with tree depth, O(log N)) and verifies in 1.5 ms at any chain length. This is possible because the chain aggregation does not recursively prove signature validity — it proves that a commitment chain is consistent. The reduction from 631 KB (base proof) to ~200 KB (chain proof, serialized) is a consequence of this design choice, not a STARK parameter optimization.
Path B soundness is currently used — sound against honest-prover attacks, not against adversarial witness generation. Path A would close this gap at 3800× compute cost. The trade-off is documented, not hidden. No trusted setup, no elliptic curves, no claim beyond what the AIRs prove.