A GKR Tutorial (vitalik.eth.limo)

The post is a hands-on tutorial explaining the GKR (Goldwasser–Kalai–Rothblum) family of protocols and why they power many ultra-fast provers (ZK-EVM, zk-ML, huge batch hash proving). It focuses on proving many parallel executions of the Poseidon2 hash, showing how GKR exploits computations that are large in two dimensions—many low-degree layers and many inputs—to avoid committing to intermediate layers. Instead the prover only commits to inputs and outputs, dramatically cutting the heavy Merkle/KZG commitment cost that makes STARK/SNARK workflows expensive. GKR delivers succinctness (not zero-knowledge by itself), so it’s typically composed with a SNARK/STARK if privacy is required. Technically, GKR reduces claims about sums of a low-degree multivariate polynomial over a hypercube to a single evaluation at a random point via a recursive “sumcheck” using random linear combinations. For degree-4 expressions (e.g., cubic S-boxes like x^3 plus linear weights), each round must supply five evaluations and uses Lagrange weights to map between hypercube halves; the post gives a concrete modular example (mod 89) and code for deg-4 Lagrange weights. The tutorial also explains how Poseidon’s mix of matrix multiplies and S-box rounds fits into GKR by encoding matrix layers as evaluation weights (so the verifier can check without “materializing” the matrix). The result: an efficient prover/verifier flow that scales to batched hashes and neural-network-like layers, explaining why modern high-throughput provers can run in real time on modest hardware.