A GKR Tutorial

This post is a tutorial explaining GKR, the family of interactive protocols it describes as behind the extreme speed of many recent ZK proving systems, such as ZK-EVM provers and zk-ML systems. GKR works by running a computation backwards layer by layer, using sumchecks to turn an obligation about one layer into an obligation about the previous layer, and it commits only to the inputs and outputs rather than to every intermediate layer. The author notes that a Merkle-tree commitment to an erasure coding requires hashing 4 to 16 bytes per byte committed, which GKR avoids except at the start and end. The post focuses on a GKR implementation for proving Poseidon2 hashes, with examples computed modulo 89, and notes that real systems use a 32-bit prime field such as KoalaBear.