Proofs of correct computation built only from hash functions.
The idea: The computation's steps are written into a big table, and the table is turned into polynomials that only behave nicely if every step was right. The prover commits to them with Merkle trees, and the verifier asks to see a few random spots. Cheating anywhere would make the polynomials badly irregular, so random spot checks catch it with overwhelming probability. Hashing the commitments replaces the verifier's random questions (Fiat-Shamir), so the proof is just a file that anyone can check.
Why it matters: Used by rollups like Starknet, and likely quantum-safe.
On the map: hash-based, transparent (e.g. Starknet)
STARKs prove that a computation was done correctly using only hash functions[1]: no trusted setup, and plausibly secure against quantum computers. Proofs are larger than SNARKs, tens to hundreds of KB.
Starknet verifies STARK proofs directly on Ethereum. Many other ZK rollups prove with STARKs but wrap the result in a small BN254 SNARK to save gas, which brings back pairing assumptions. Security relies on the hash (often Poseidon or Keccak), the random oracle model (ROM)[2] and, for many parameter choices, a still-unproven form of the FRI proximity-gap conjectures (the strongest form was disproved in 2025)[3].
If any of these breaks, this breaks too.
If this breaks, these break with it.