A client outsources a computation to a cloud server and receives a result. Without verifiable computation, the client must either trust the server or re-do the computation. Why is verification fundamentally cheaper than computation for certain proof systems?
Think about your answer, then reveal below.
Model answer: Verification exploits asymmetry: the server does the computation (potentially very expensive) and produces a proof alongside the result. The proof has special structure (e.g., algebraic or hash-based) that allows the verifier to check correctness by examining a small random sample of the proof or evaluating a few algebraic equations. In SNARKs, the proof is constant-size and verification takes milliseconds regardless of computation complexity. This asymmetry comes from the PCP theorem and its algebraic descendants: every NP statement has a proof that can be verified by reading only O(1) random locations.
The PCP theorem is the theoretical foundation: every NP proof can be written in a format where correctness can be tested by reading a constant number of randomly chosen bits. Practical systems (SNARKs, STARKs) achieve this through arithmetization (encoding computations as polynomial equations) and commitment schemes that let the verifier spot-check the polynomial.
Question 2 Multiple Choice
Blockchain rollups use verifiable computation to process thousands of transactions off-chain and post a single proof on-chain. Why does this improve blockchain scalability?
ARollups compress transaction data to save storage space
BInstead of every blockchain node re-executing thousands of transactions to verify them, a single prover processes the transactions and generates a succinct proof of correct execution. On-chain verification of this proof costs far less computation and storage than re-executing all transactions, allowing the chain to handle orders of magnitude more transactions per second
CRollups move transactions to a faster blockchain
DThe proof replaces the consensus mechanism, eliminating the need for multiple validators
Without rollups, every node on the blockchain must independently execute every transaction — the chain's throughput is limited by the slowest node. With rollups, transactions are batched and executed off-chain by a single prover. A SNARK/STARK proof of correct execution (constant or logarithmic size) is posted on-chain. All nodes verify the proof instead of re-executing. Since verification is orders of magnitude cheaper than execution, the effective throughput multiplies dramatically. Ethereum's layer-2 scaling (zkSync, StarkNet, Polygon zkEVM) uses this approach.
Question 3 True / False
The PCP theorem states that every NP proof can be written in a format checkable by reading O(1) bits. This seems to violate the intuition that checking a proof requires reading the whole proof.
TTrue
FFalse
Answer: True
The PCP theorem does state this — and it IS counterintuitive. The key is that the proof is reformatted into a probabilistically checkable proof (PCP), which is much longer than the original NP witness but has redundancy that allows random spot-checking. The verifier reads O(log n) random bits (for the randomness) and O(1) proof bits (for the check). If the proof is valid, the check always passes. If the proof is invalid, the check fails with constant probability per query, and repetition amplifies this. The PCP theorem was the 2001 Godel Prize and is one of the most important results in theoretical CS.
Question 4 True / False
A verifiable computation system for certified AI inference could allow a client to verify that a server correctly evaluated a neural network on their input, without re-running the network.
TTrue
FFalse
Answer: True
This is an active research area. The client sends an input (possibly encrypted) to the server, which evaluates the neural network and returns the output along with a proof of correct execution. The client verifies the proof in time much less than the network evaluation. Challenges include the enormous circuit sizes of modern neural networks (billions of parameters), the use of floating-point arithmetic (which maps poorly to the finite field arithmetic of SNARKs), and the overhead of proof generation. Current systems can handle small to medium networks, with optimizations for specific architectures (linear layers, ReLU activations) making the approach increasingly practical.
Question 5 Multiple Choice
What is the main difference between a SNARK (Succinct Non-interactive ARgument of Knowledge) and a STARK (Scalable Transparent ARgument of Knowledge)?
ASNARKs are interactive while STARKs are non-interactive
BSNARKs typically require a trusted setup ceremony and use elliptic curve pairings, producing very small proofs (~200 bytes). STARKs require no trusted setup (transparent), use hash functions and polynomial commitments, but produce larger proofs (~100 KB). STARKs are also plausibly post-quantum secure since they avoid elliptic curves
CSTARKs are faster to verify than SNARKs
DSNARKs only work for specific computation types while STARKs are general
The tradeoff is trusted setup and proof size vs. transparency and quantum resistance. SNARKs (like Groth16) achieve the smallest proofs but require a per-circuit trusted setup — a ceremony where randomness is generated and must be destroyed. If the setup randomness leaks, fake proofs can be forged. STARKs eliminate this trust requirement entirely (transparent setup) and use only hash functions (plausibly quantum-safe), but pay with ~500x larger proofs. Universal SNARKs (PLONK, Marlin) offer a middle ground: one trusted setup for all circuits of bounded size.