GKR

Paper

Delegating Computation: Interactive Proofs for Muggles
Authors: Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum
Date: 2008

• An Interactive Proof (IP)
• can be turned into a zkSNARK with PCS and Fiat-Shamir
• designed to delegate computation for arbitrary computation rather than the specific Sum-Check Protocol computation

Overview

• reduces the evaluation of the circuit to only the inputs
• uses layered arithmetic circuits as the intermediate representation in the protocol
• main idea: write the output $y$ as the sum-check equations of input $x$, i.e. $y=\sum f(x)$
• The Sum-Check Protocol is applied once per layer of the circuit
• The verifier needs to evaluate the circuit at its multilinear extension at a random point
• Prover is not required to make any commitments as long as all inputs are public
  • Pro:
    • Information-theoretic (statistical) security since there is no cryptography in the protocol
    • Security comes from the non-predictability of the verifier challenge
  • Con:
    • No commitment scheme so it’s hard to keep the circuit size small
    • Uses a lot of untrusted advice
      • i.e. instead of computing division in the circuit, Prover provides the quotient and remainder and the circuit checks that they are correct with a multiplication and an addition
• If there is a private input, then it needs to be committed

Layered Circuit

Circuit is decomposed into layers where the gates in a layer are only connected to gates in adjacent layers.

Layer $0$: output layer
Layer $d$: input layer

Any circuit can be transformed into a layered circuit with a maximum blowup factor of $d$ in circuit size.

Protocol

$C$: layered arithmetic circuit of fan-in two
$d$: circuit depth
$x\in {\mathbb{F}}^n$: inputs
$S_i$: number of gates at layer $i$ of $C$
$k_i=lo{g}_2(S_i)$

Round 0

1. Prover send a function $D$ claimed to equal to the circuit output $W_0$ to Verifier
2. Verifier picks a random $r_0\in {\mathbb{F}}^{k_0}$ to compute $\tilde{D}(r_0)=m_0$.

Protocol Main Objective

The remaining protocol is to verify $m_0\stackrel{?}{=}\widetilde{W_0}(r_0)$

Round $i=0,\dots ,d-1$

1. Define the $(2k_{i+1})$-variate polynomial:

$$\begin{array}{rl}{f}_{r_i}^i(b,c):=\widetilde{ad{d}_i}(r_i,b,c)({\tilde{W}}_{i+1}(b)& +{\tilde{W}}_{i+1}(c))+\widetilde{mul{t}_i}(r_i,b,c)({\tilde{W}}_{i+1}(b){\tilde{W}}_{i+1}(c))\\ & \\ \text{where the }\text{wiring predicate: }ad{d}_i()& =1⟺(r_i,b,c)\text{ connects to add gate}\\ mul{t}_i()& =1⟺(r_i,b,c)\text{ connects to mult gate}\end{array}$$

1. Prover claims $\sum _{b,c\in \{0,1{\}}^{k_{i+1}}}{f}_{r_i}^{(i)}(b,c)=m_i$
2. Prover and Verifier apply the sum-check protocol to verify the claim, up till the last step
3. During the last step of the sum-check protocol:
   1. Prover sends a univariate polynomial $q$ of degree at most $k_{i+1}$, claim $q\stackrel{?}{=}\widetilde{W_{i+1}}$
   2. Verifier continue the sum-check protocol and perform final step where: $\widetilde{W_{i+1}}(b^{\star })=q(0)$, $\widetilde{W_{i+1}}(c^{\star })=q(1)$
   3. Verifier pick random $r^{\star }\in \mathbb{F}$ and set $r_{i+1}=l(r^{\star })$ and $m_{i+1}\leftarrow q(r_{i+1})$

Round $d$

1. Verifier checks $m_d\stackrel{?}{=}\widetilde{W_d}(r_d)$

Security

Soundness

• follows sum-check protocol and is based on Schwartz-Zippel Lemma (i.e. no cryptographic assumptions)

Cost

Prover Time

• original: $O(N^3)$
• optimized to $O(N)$ in subsequent works

Proof Size

• $O(DlogN)$
  • linear in the depth $D$ of the circuit, and log in the width of the circuit

Verifier Time

• $O(DlogN)$ + input size + time to evaluate $add$ and $mult$
  • i.e. the Verifier can run in time sublinear in N (circuit size)
  • structured circuits (common scenario): $O(DlogN)$
    • e.g. matrix multiplication, data-parallel circuits where they only depend on the public circuit description but not the values within the circuit
  • with preprocessing: $O(DlogN)$
  • worst case: $O(N)$

Proof Size and Verifier Time for SNARKs for Verifiable Computation

In verifiable computation, the Verifier can (at least in principle) perform the computation locally in linear time. Thus for (non-ZK)SNARKs used for verifiable computation, it is meaningless for the verifier to use a SNARK that requires linear Verifier time. In this case, the SNARK needs to be in sublinear verifier time and proof size.

In GKR, the circuit is stored succinctly in the proof. This allows the Verifier to read the circuit in sub-linear time.

Improvements

Prover Time Optimization

• CMT12: improved to $O(NlogN)$ by using multilinear extensions instead of low-degree extensions
• vRAM / ZGKPP: $O(NlogN)$ for circuits with many non-connected but different copies
• Giraffe / WBSTWW17: $O(N)$ for data-parallel circuits
• Libra19 / XZZ19: $O(N)$

Generalization

• original GKR only support layered circuits
• Virgo++ / ZLWZSXZ21 generalize GKR to arbitrary arithmetic general circuits with the same prover costs

Others

• Tha13 - Proposition 2: GKR for binary tree
• BTVW14: multi-provers, a sum-check-based polynomial IOP (precursor of Spartan), mildly disguised

GKR-based (zk)SNARKs

GKR can be combined with a PCS and FIat-Shamir to create a (zk)SNARK:

• vSQL17 (sumcheck / GKR + multivariate KZG)
• Hyrax18
• zkvSQL18
• Libra19 (sumcheck / GKR + multivariate KZG)
• Virgo20
• Virgo++ / Virgo21

GKR-based Lookup Arguments

• Lasso24
• GKRLogUp23 Improving logarithmic derivative lookups using GKR

Resources

• Proofs, Arguments and Zero Knowledge by Justin Thaler, Chapter 4.6
• A Note on the GKR Protocol by Justin Thaler
• Explore Expander Bootcamp: GKR and Sumcheck Protocol