Today, let’s talk about GKR. I won’t go too deep into the details here. The goal is to keep this article relatively “light”, and I’ll link to some resources if you want to dive deeper.
The GKR protocol, introduced by Goldwasser, Kalai, and Rothblum in 2008, is an interactive proof system for verifying the correctness of computations represented as arithmetic circuits.
It builds on the Sumcheck protocol, using it as a key tool to efficiently verify layered circuits (circuits where each layer depends on the one below).
Suppose you have a computation that takes a large input and applies several layers of arithmetic operations to produce an output. Re-running the entire computation just to verify the output would be expensive.
But what if the verifier could efficiently check the result without redoing all the work or blindly trusting the prover? Sounds familiar, right? That’s the Sumcheck spirit.
GKR assumes an arithmetic circuit structured into d layers.
To keep things consistent, we’ll label the top layer (the output) as layer 0, and increase the index as we go down to the input layer, which is layer d. Each gate in layer i performs an arithmetic operation (either addition or multiplication) on the outputs of two gates in layer i + 1.
I made a simple circuit as an example:
graph BT
subgraph "layer 2 (input)"
a
b
c
d
end
subgraph layer 1
l1_0
l1_1
l1_2
l1_3
end
subgraph "layer 0 (output)"
l0_0
l0_1
end
add
mul
a --> l1_0
a --> l1_1
b --> l1_0
b --> l1_2
c --> l1_1
c --> l1_2
d --> l1_3
d --> l1_3
l1_0 --> l0_0
l1_1 --> l0_0
l1_2 --> l0_1
l1_3 --> l0_1
a("L2 (00): 7")
b("L2 (01): 5")
c("L2 (10): 3")
d("L2 (11): 6")
l1_0("L1 (00): 12 = 7 + 5")
l1_1("L1 (01): 21 = 7 * 3")
l1_2("L1 (10): 15 = 5 * 3")
l1_3("L1 (11): 12 = 6 + 6")
l0_0("L0 (0): 33 = 12 + 21")
l0_1("L0 (1): 79 = (12 * 15) % 101")
style add fill:blue,color:#fff
style l1_0 fill:blue,color:#fff
style l1_3 fill:blue,color:#fff
style l0_0 fill:blue,color:#fff
style mul fill:green,color:#fff
style l1_1 fill:green,color:#fff
style l1_2 fill:green,color:#fff
style l0_1 fill:green,color:#fff
Layer 2 is our input layer [7, 5, 3, 6], and the circuit outputs [33, 79] (operations are in $\mathbb{F}_{101}$).
Since we’re working with multivariate polynomials, we use binary encodings for gate indices over the boolean hypercube (ex: 00, 01,…). That’s why I indicated (00), (01), …
The relationships between layer 2 and layer 1 gates can be written as:
$$ L_1(00) = L_2(00)+L_2(01) \\ L_1(01) = L_2(00)*L_2(10) \\ L_1(10) = L_2(01)*L_2(10) \\ L_1(11) = L_2(11)+L_2(11) $$
But these aren’t in a form we can use directly with Sumcheck. To apply Sumcheck, we need to express each layer as a polynomial relation involving a sum over the boolean cube.
Something like:
$$ L_1=\displaystyle\sum_{b \in {\{0,1\}}^2}L_2(b) $$
We’ll define selectors that activate only when a gate applies a specific operation.