Home > Resources > papers > GKR08-Muggles

Delegating Computation: Interactive Proofs for Muggles (Goldwasser, Kalai, Rothblum 2008)

Last modified: 2026-10-27

DOI: 10.1145/1374376.1374396 · URL: https://doi.org/10.1145/1374376.1374396

Summary

Introduces the GKR protocol: an interactive proof for any language computable by log-space uniform layered arithmetic circuits, in which the prover runs in time polynomial in the circuit size and the verifier in time roughly linear in input size plus polynomial in circuit depth. It proceeds layer by layer, reducing a claim about one layer's outputs to a claim about the next via the sum-check protocol. GKR is the backbone of modern linear-time-prover systems (Hyrax, Libra, Virgo, Expander) and of the sum-check-centric line of ZKPs that is attractive for fast credential presentations on mobile devices. (STOC 2008; journal version JACM 2015.)

Related resources

• Algebraic Methods for Interactive Proof Systems (paper, 1992)
• Doubly-Efficient zkSNARKs Without Trusted Setup (Hyrax) (paper, 2017)
• Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (Xie, Zhang, Zhang, Papamanthou, Song 2019) (paper, 2019)