September’s ZK call included a presentation of the GKR protocol.
An arithmetic circuit consists of addition and multiplication gates. Public inputs and private inputs are fed into an arithmetic circuit to obtain public outputs. Given the complete set of inputs, an entity can compute the outputs. However, this may not be desirable due to the inclusion of private inputs or the circuit is too computationally demanding. The validity of a computation given the inputs (or a subset of the inputs) and the outputs is circuit satisfiability.
SNARKs such as Plonk and Groth16 are proof systems to handle circuit satisfiability. Additionally, the GKR protocol is another such proof system that predates both Plonk and Groth16. GKR stands for the authors names (Goldwasser, Kalai, and Rothblum) and not an abbreviation of a technical name.
Brief idea of GKR
GKR was developed to address a design assumption of proof systems of the time. The computational abilities of the Prover. GKR focuses on practical Provers.
To achieve this, GKR relies on layered circuits and the sumcheck protocol.
- Layered circuit is a circuit in which operation gates in layer i can only receive inputs from layer i-1.
- Each circuit can be converted into a layered circuit through the introduction of dummy gates (multiplication by 1 or addition by 0).
Roughly, the GKR argument begins at the output layer and applies sumcheck to each layer of the circuit. The function used for sumcheck relies on gate values from the previous layer. However, each gate in layer \ell is the output from two gates in layer \ell+1. To avoid exponential sumcheck arguments, two outputs can be combined into a line.
Some additional remarks
- General criterion of layered circuit design that results in a Prover with \mathsf{polylog} complexity appears to be an open question. Not all circuit design yields a practical Prover.
- Libra adds masking polynomials to introduce a linear time proving zero-knowledge argument using GKR.
- Scroll uses GKR in the zkVM Ceno.
- GKR protocol is used to construct an example in which strong Fiat-Shamir heuristic can be exploited by a malicious user. This is not a weakness of GKR itself, but rather careful design is required.