zk-STARKs vs Bulletproofs vs zk-SNARKs: Transparency, Proof Size, and the Post-Quantum Question

Updated November 10, 2026.

October 27, 2026. NIST publishes the final version of IR 8547, Transition to Post-Quantum Cryptography Standards. It keeps the dates from the 2024 draft: quantum-vulnerable public-key algorithms, RSA and elliptic curves included, are deprecated after 2030 and disallowed after 2035.

Seven months earlier, Google's quantum team cut its estimate of what it takes to break elliptic-curve keys. And it proved the claim with a zero-knowledge proof built on, of all things, elliptic curves.

Most zero-knowledge proof systems in production today sit on that list. Groth16, PLONK with KZG commitments, Bulletproofs. All of them rely on elliptic-curve math that Shor's algorithm breaks.

One family doesn't: zk-STARKs.

This post covers what makes STARKs different, what you give up for it, where Bulletproofs fit, and a table for deciding which one fits which job. If you haven't read the zk-SNARKs deep dive, start there. And for the basics, there's the pillar explainer.

What STARK means

zk-STARK stands for Zero-Knowledge Scalable Transparent ARgument of Knowledge. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev introduced it in a 2018 paper with a title that tells you the whole pitch: Scalable, transparent, and post-quantum secure computational integrity.

Two words carry the weight.

Transparent means no trusted setup. A STARK's randomness is public. There's no toxic waste to generate, guard, or destroy, and no ceremony transcript to audit. Anyone can rebuild the parameters from scratch.

Scalable means proving time grows only a little faster than the computation itself, and verification time grows very slowly, polylogarithmically, with the size of the computation.

One honest caveat on the "zk." Most STARK deployments today are about scaling, not privacy. StarkWare's systems use STARKs to prove that a batch of transactions was processed correctly, and the data is public. The proof system can be zero-knowledge. Whether a given product uses it that way is a question you have to ask.

How a STARK works without a setup

A SNARK gets its small proofs from structured elliptic-curve keys. A STARK gets its integrity from redundancy and random sampling.

1. Record the computation as a table. Every step of the program becomes a row in an execution trace. The rules the program must follow become constraints between rows.
2. Stretch the table with error-correcting codes. The trace is turned into polynomials and evaluated over a much larger domain, using the same Reed-Solomon math that lets a scratched CD still play. This spreads any single cheat across most of the stretched table.
3. Commit with hashes. The prover puts the stretched table into a Merkle tree and publishes the root. Now they're locked in.
4. Spot-check. The verifier asks for a few dozen random positions, checks each one against the Merkle root, and runs a protocol called FRI to confirm the data really is a low-degree polynomial. Fiat-Shamir hashing turns the verifier's random questions into something the prover computes alone, so the proof stays non-interactive.

If you've ever run an audit, you know this move. Sampling forty invoices doesn't prove a ledger is clean, because a fraud on one line hides easily. Now imagine a ledger encoded so that one bad entry corrupts most of the pages. Forty random pages catch it almost every time.

That's the STARK trick. And the only cryptography underneath is a hash function.

The post-quantum argument

Here's why hashes matter.

Shor's algorithm, on a large enough quantum computer, solves the discrete-log problem on elliptic curves. That breaks the assumption under Groth16, under KZG commitments in PLONK, and under the Pedersen commitments in Bulletproofs. The security analysis calls it a structural break: no parameter tweak fixes it. You have to change systems.

Hash functions don't fall to Shor. The best known quantum attacks on them, Grover-style search, give a smaller speedup that you absorb with bigger hash outputs and more query rounds. That's a cost increase, not a collapse.

This isn't just hand-waving. In 2019, Chiesa, Manohar, and Spooner proved that SNARGs built from interactive oracle proofs, the family STARKs belong to, are secure in the quantum random oracle model. And NIST already trusts the same foundation elsewhere: FIPS 205, published August 13, 2024, standardizes SLH-DSA, a signature scheme built entirely from hash functions.

Two precise points, because this is where sloppy claims creep in.

• The quantum risk to a SNARK is forgery. A quantum attacker could make false proofs verify. Groth16 proofs are perfectly zero-knowledge, so old proofs don't suddenly spill their secrets. For a ledger, forgery is the worse outcome anyway. It means undetectable counterfeiting.
• The proof isn't the whole system. A privacy coin or a confidential ledger also uses encryption and signatures, usually elliptic-curve today. Swapping the proof system to a STARK doesn't make the rest post-quantum. Harvest-now-decrypt-later still applies to the encrypted data around the proof.

The cost: proof size

Nothing's free. STARK proofs are big.

The Ethereum institutional-privacy knowledge base at ethsystems.org puts typical sizes at about 200 bytes for Groth16, about 400 bytes for PLONK over KZG, and roughly 50 to 200 KB for a STARK over FRI. That's two to three orders of magnitude.

Off-chain, nobody cares. A 100 KB file is nothing. On a blockchain, where every byte costs money, it's a real constraint. Two patterns handle it.

Amortize. StarkWare's SHARP prover bundles many programs into one STARK and verifies it on Ethereum. The verification cost gets split across every transaction in the batch. Starknet has run this way since its alpha launched on mainnet in November 2021, and StarkEx powered earlier deployments like dYdX and Immutable X.

Wrap. zkVMs such as RISC Zero and SP1 prove the heavy computation with a STARK, then prove that STARK's verification inside a Groth16 SNARK. The final proof shrinks from hundreds of kilobytes to a few hundred bytes and costs roughly a quarter-million gas to check.

Notice what the wrap does. The last step is Groth16 again. Trusted setup, elliptic curves, quantum exposure. It's a pragmatic choice, and today it's usually the right one. Just know that "built on STARKs" and "post-quantum end to end" aren't the same claim.

Bulletproofs: small range proofs, no setup

Bulletproofs solve a narrower problem very well. The 2017 paper by Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell, published at IEEE Security and Privacy in 2018, targets range proofs: showing a hidden amount sits between 0 and 2⁶⁴ without revealing it. That's how a confidential payment proves nobody created money with a negative output.

What they get right:

• No trusted setup. Like STARKs, they're transparent.
• Short proofs that grow slowly. Proof size grows logarithmically. A 64-bit range proof is 674 bytes, and aggregating eight of them only takes it to 866 bytes.
• Simple assumptions. Just the discrete-log problem on an ordinary elliptic curve. No pairings.

What they don't do:

• Fast verification. Verification time grows linearly with the size of the statement. Fine for a range proof. Painful for a big general computation.
• Beat SNARKs on size. You'll often read that Bulletproofs are smaller and faster than zk-SNARKs. They're not. They're far smaller than the range proofs they replaced. Groth16 is still smaller.
• Survive Shor. They're elliptic-curve based. A quantum attacker could break the binding of the commitments, which means inflation, even though the hidden amounts themselves stay hidden.

The real-world record is solid. Monero switched to Bulletproofs on October 18, 2018. Average transaction size fell from about 18.5 KB to about 3 KB, and fees dropped about 97 percent. It moved to the improved Bulletproofs+ on August 13, 2022. Mimblewimble chains use them too: Grin since its January 2019 launch, and Litecoin's MWEB extension blocks since May 2022.

The inner-product technique behind Bulletproofs also lives on in Halo 2, the setup-free SNARK Zcash adopted in 2022. Good ideas get reused.

Which one when

Sizes come from the ethsystems.org proof-system comparison and the Bulletproofs paper. They vary with the implementation and circuit, so treat them as orders of magnitude, not specs.

What this means for a regulated firm

If you're running a post-quantum migration, and NIST just made that a dated plan rather than a someday project, zero-knowledge systems belong in it.

1. Put proof systems in your cryptographic inventory. Most teams inventory TLS, certificates, and HSM keys. Few list "Groth16 on BN254 inside our tokenization vendor." Ask vendors which proof system they use and which curve.
2. Match the proof to the horizon. A proof checked once at settlement and never relied on again carries little quantum risk. A proof that underwrites the integrity of a ledger for twenty years is a different animal. Forgery there means counterfeit assets nobody can see.
3. Count transparency as a control. With a STARK or Bulletproofs, there's no ceremony to explain to an examiner. The trust model is "SHA-family hashes work" or "discrete log is hard," and your security team already makes those judgments every day.
4. Read past the label. "Built on STARKs" may still end in a Groth16 wrap. "zk-rollup" may hide nothing at all. Ask what's hidden, from whom, and what the final on-chain check depends on.
5. Plan for a swap. Zcash has run three different proof systems since 2016. Your architecture should let you do the same without reissuing everything.

For how these choices show up in practice, see ZK in finance, ZK beyond payments, and the Zcash story.

The question isn't which proof system is best. It's which assumption you're willing to still be standing on in 2035.