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 proof

FRI 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 signatures

Each 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

SystemTrusted setupPQ secureProof sizeVerify
STARK (Sahyadri)NoneYes (hash-based)631-735 KB (batch)35 ms
STARK (Sahyadri chain)NoneYes~200 KB1.5 ms
Groth16Trusted per circuitNo (pairings)~200 B~5 ms
PLONKUniversal trusted setupNo (pairings)~500 B~5 ms
BulletproofsNoneNo (EC-based)~1-2 KB~10 ms
KZGTrusted per ceremonyNo~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

OperationTimeSpaceNotes
STARK proof generationO(T_compute · log T_compute)O(T_compute)Dominated by polynomial evaluation
STARK proof verificationO(log T_compute · queries)O(log T_compute)FRI verify dominates
STARK proof sizeO(log T_compute · queries)—Logarithmic in computation size
Recursive compositionO(1) per linkO(1)Constant cost independent of depth
FRI folding (per round)O(|D|)O(|D|)|D| is the domain size, halves each round
Merkle commitmentO(|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.