STARKs and Transparency: Hash-Based, Post-Quantum-Plausible Proofs Without Trusted Setup

The previous article ended on the trusted-setup question — the ceremony and secret toxic waste that many efficient SNARKs require, and whose compromise silently breaks soundness. STARKs answer that question by removing the setup entirely. A STARK, a scalable transparent argument of knowledge, uses only public randomness and builds its security from hash functions alone, which gives it two properties the pairing-based SNARKs lack: transparency, meaning no trusted ceremony, and a credible claim to post-quantum security. The price is larger proofs. This article explains transparency, the hash-based construction that delivers it, and the size-versus-trust trade-off that decides when a STARK is the right tool.

Transparency: no trusted setup

Transparency means the proof system uses no secret setup — all of its randomness is public, drawn in the open, so there is no structured reference string to generate, no toxic waste to destroy, and no ceremony to run. Every party can see and reproduce the public parameters, and there is no secret whose leakage could let someone forge proofs. This directly eliminates the single most delicate trust assumption of pairing-based SNARKs and the operational machinery — the multi-party ceremonies — built to manage it.

The practical gains are substantial. There is no per-circuit or even one-time ceremony to organize and audit, no risk that a retained secret undermines every proof, and no need to convince skeptical third parties that toxic waste was actually destroyed. For open, adversarial settings — public ledgers, systems with no trusted party to run a ceremony, applications that must be verifiable by anyone with no caveats — transparency is not a minor convenience but a requirement, because a trusted setup is exactly the kind of assumption such settings cannot make.

Transparency also composes cleanly with a scalability goal, which is the other half of the STARK name. A transparent system that is also scalable — prover cost near-linear in the computation, verifier cost only polylogarithmic — gives publicly verifiable proofs of very large computations with no trusted party anywhere in the picture. Achieving both at once is what the hash-based construction is designed to do.

The hash-based construction

A STARK proves a computation by first writing it as an execution trace — a table of the machine's state at every step — and encoding that trace as a polynomial over a finite field. Correct execution corresponds to the trace polynomial satisfying a set of low-degree constraints, so the statement to prove becomes: this polynomial is of low degree and satisfies the constraints. The prover commits to the evaluations of the polynomial using a Merkle tree built with a collision-resistant hash, which lets it later reveal any evaluation with a short authenticated path.

The heart of the system is a proximity test called FRI — a fast Reed-Solomon interactive oracle proof of proximity — which lets the prover convince the verifier that the committed data really is close to a low-degree polynomial rather than arbitrary values, by a recursive folding argument that the verifier checks at a few random points. Combined with the constraint checks, FRI establishes that a valid execution trace exists. The whole protocol is made non-interactive with the Fiat-Shamir transform from the earlier article, deriving the verifier's random challenges from hashes.

The decisive feature is what this construction relies on: hash functions and Reed-Solomon codes, and nothing else — no elliptic curves, no pairings, no number-theoretic assumptions that a quantum computer could break. The stack is an execution trace, a low-degree polynomial encoding, a FRI proximity proof, and Merkle-hash commitments. Because every cryptographic step reduces to the collision resistance of the underlying hash, the security of a STARK rests on the same kind of symmetric assumption that this series argues is the load-bearing quantum-era foundation.

The size and time trade-off

STARKs are scalable in the senses that matter for large computations: the prover runs in quasi-linear time in the size of the computation, and the verifier runs in only polylogarithmic time, checking the proof by sampling a few points. This keeps verification cheap even for enormous statements, which is the same succinctness benefit that motivates SNARKs. Where STARKs differ sharply is proof size: a STARK proof is substantially larger than a pairing-based SNARK's, tens to hundreds of kilobytes against a few hundred bytes.

This is the central trade-off, and it is a genuine exchange rather than a strict improvement. A pairing SNARK like Groth16 gives the smallest possible proof and fastest verification, but requires a trusted setup and is broken by quantum computers. A STARK gives a transparent, setup-free, plausibly post-quantum proof, but that proof is larger and its verification, while polylogarithmic, is heavier in absolute terms. Neither dominates; the choice depends on whether proof size and on-chain cost, or transparency and quantum durability, matter more for the application.

The quantum-durability point deserves emphasis because it connects to the whole post-quantum theme. A STARK's security rests on hash collision resistance, which a quantum adversary attacks only with the mild, well-understood speedup of generic search — mitigated by a modest increase in hash output size. A pairing SNARK's security rests on problems a quantum computer solves outright. So among proof systems, the transparent hash-based ones are the natural post-quantum choice, and a verifiable-computation deployment meant to endure has the same harvest-and-endurance reasons to prefer them that the rest of the migration has to prefer lattice and hash primitives.

When to choose a STARK, and the AI stakes

The decision follows from what the application cannot compromise on. If proof size or on-chain verification cost is the binding constraint and a trusted setup is acceptable, a pairing SNARK's tiny proof wins. If transparency is required — no trusted party to run a ceremony, no assumption that a secret was destroyed — or if the proofs must remain sound in a post-quantum world, a STARK is the right choice despite its larger proofs, which can often be amortized or compressed by proving many statements together. The two are complementary tools, and some systems even compose them, using a STARK to prove a batch and a small SNARK to compress the final proof.

For the post-quantum thesis of this series, STARKs are the proof-system embodiment of the same argument made everywhere else: the primitives that endure into the quantum era are the ones resting on symmetric and hash assumptions, not on the number-theoretic problems a quantum computer breaks. A verifiable-computation stack that must last should treat its proof system with the same harvest-now-decrypt-later discipline as its encryption — preferring the transparent, hash-based option when durability matters, rather than deploying a pairing-based proof whose soundness has an expiration date.

For AI, the application is durable verifiable inference. A proof that a model produced an output — an audit trail for an autonomous agent's decision, a guarantee to a user that the promised model was actually run — may need to remain verifiable for years, and it may need to be checkable by anyone with no trusted setup in the loop. Those requirements point squarely at transparent, post-quantum proofs. STARKs make verifiable AI something that can be deployed in open, adversarial, long-lived settings without a ceremony and without a quantum expiration date, which is exactly the setting a trustworthy agent ecosystem needs. The larger proofs are the price, and for high-stakes, long-lived verifiable inference it is usually the right price to pay.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

durable_proofs:
  transparency: required   # no trusted setup
  post_quantum: required   # hash-based security
  system: stark
  assumption: hash_collision_resistance
  trade_off:
    proof_size: larger
    setup_and_quantum: eliminated
  batching: amortize_large_proofs

Glossary

STARK

A scalable transparent argument of knowledge: a hash-based, setup-free, plausibly post-quantum proof system.

Transparency

The property of using only public randomness, so there is no trusted setup or secret to protect.

Execution trace

A table of a computation's state at each step, encoded as a polynomial that a STARK proves is low-degree and constraint-satisfying.

FRI

A fast Reed-Solomon proximity test that proves committed data is close to a low-degree polynomial, the core of a STARK.

Merkle commitment

A hash-tree commitment to many values allowing short authenticated openings of any one, used for transparent commitments.

Post-quantum plausibility

A STARK's security reduces to hash collision resistance, which quantum computers only mildly weaken, unlike the pairings SNARKs use.

References

1. Ben-Sasson, Bentov, Horesh, Riabzev, Scalable, Transparent, and Post-Quantum Secure Computational Integrity / STARKs (IACR ePrint 2018/046)
2. Ben-Sasson, Bentov, Horesh, Riabzev, Fast Reed-Solomon Interactive Oracle Proofs of Proximity / FRI (ICALP 2018)
3. Merkle, A Digital Signature Based on a Conventional Encryption Function (CRYPTO 1987)
4. Ben-Sasson, Chiesa, Spooner, Interactive Oracle Proofs (TCC 2016)
5. Thaler, Proofs, Arguments, and Zero-Knowledge (monograph, 2022)