A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Verifiable computation allows a weak client to delegate computation to a powerful (but untrusted) server and efficiently verify that the result is correct, with verification cost much less than performing the computation. This requires succinct proofs of correctness — proofs whose size and verification time are sublinear (ideally polylogarithmic or constant) in the computation size. Key constructions include interactive proofs (GKR protocol), probabilistically checkable proofs (PCPs), and succinct non-interactive arguments (SNARGs/SNARKs). Applications span cloud computing, blockchain scalability (rollups), and certified AI inference.
Verifiable computation addresses a trust problem: when you outsource a computation to an untrusted party, how do you know the result is correct? Re-doing the computation yourself defeats the purpose of delegation. Verifiable computation provides a better answer: the server performs the computation and produces a proof of correctness that the client can check in time much less than the computation itself. If the proof verifies, the client is convinced the result is correct — even if the server is malicious, lazy, or buggy.
The theoretical foundation is the PCP (Probabilistically Checkable Proof) theorem, which shows that every NP statement has a proof format where correctness can be tested by reading only a constant number of randomly chosen bits. This remarkable result — which won the 2001 Godel Prize — means that exponentially long proofs can be verified by sampling, with the probability of missing an error decreasing exponentially with the number of samples. Modern proof systems translate this theoretical possibility into practical constructions using arithmetization: encoding the computation as a set of polynomial equations over a finite field. The prover commits to the polynomial, and the verifier spot-checks by evaluating at random points.
SNARKs (Succinct Non-interactive Arguments of Knowledge) are the most compact proof systems: the proof is constant-size (a few hundred bytes for Groth16) and verification takes milliseconds, regardless of computation complexity. The "argument" (vs. "proof") indicates that soundness is computational — an all-powerful prover could forge proofs, but no polynomial-time prover can. Most SNARKs require a trusted setup: a one-time ceremony generating structured parameters. If the ceremony's randomness is compromised, fake proofs become possible. STARKs (Scalable Transparent Arguments of Knowledge) avoid this by using hash-based commitments — no trusted setup, plausibly quantum-safe — but with larger proofs (around 100 KB).
The most impactful application today is blockchain scalability. Ethereum processes ~15 transactions per second on its base layer. ZK-rollups (zkSync, StarkNet, Polygon zkEVM) batch thousands of transactions, execute them off-chain, and post a single SNARK/STARK proof on-chain. Every Ethereum node verifies this tiny proof instead of re-executing thousands of transactions, multiplying effective throughput by orders of magnitude. Beyond blockchain, verifiable computation enables certified cloud computing (verify that AWS computed your function correctly), verifiable AI inference (prove that a specific neural network produced a specific output for a specific input), and privacy-preserving compliance (prove your data satisfies regulatory requirements without revealing the data). The field is advancing rapidly, with proof generation times dropping from hours to seconds for practical circuit sizes, making deployment in production systems increasingly viable.