GKR protocol

import gkr
env = gkr.init(verbose=False)

Introduction¶

Building on our exploration of the sum-check protocol, multilinear extensions, and arithmetic circuits, we are now ready to present the GKR protocol in full. Originally introduced by Goldwasser, Kalai, and Rothblum 12, and refined by many authors since, GKR is a cornerstone of modern interactive proofs for verifying circuit computations. This notebook assembles the objects and identities from the previous notebooks and shows how they combine into the protocol itself. We follow Thaler’s presentation 3.

Worked Example¶

We proceed via a complete worked example. It serves two purposes: (i) to summarize the key objects (multilinear extensions, wiring predicates, Thaler’s identity), and (ii) to illustrate the recurring GKR pattern: run sum-check on Thaler’s identity, then apply a folding step that converts a claim about two values into a single claim at a fresh random point.

No example small enough to compute fully by hand can showcase GKR’s asymptotic savings: our toy computation is trivial, while the protocol machinery is comparatively elaborate. The value of the example is conceptual. Later we will discuss complexity and explain why, for large circuits, the verifier’s work in GKR is asymptotically far smaller than re-evaluating the circuit.

Example 1 [setup and arithmetic circuit]. Work over the field $\mathbb{F} = \mathbb{Z}/p\mathbb{Z}$, where $p = 2^{31} - 1$ is the eighth Mersenne prime. Consider the 4-variate polynomial

For instance,

We represent this computation by a constant-input, binary, strictly layered arithmetic circuit $C$ of size 7 and depth $d = 2$:

• Layer 2 (inputs): the four inputs $3,2,4,1$;

• Layer 1: one multiplication gate and one addition gate, computing $3\cdot 2 \equiv 6$ and $4 + 1 \equiv 5$;

• Layer 0 (output): one addition gate computing $6 + 5 \equiv 11$.

In this example, Layer i has size $S_i = 2^i$, hence bit-length $s_i = \lceil \log_2 S_i\rceil = i$ for $i \in \{0,1,2\}$. (For general circuits, $s_i$ need not equal $i$.)

We label the gates in Layer i using bitstrings of length $s_i$ as follows:

• Layer 2 (inputs): $3 \mapsto (0,0), \; 2 \mapsto (0,1), \; 4 \mapsto (1,0), \; 1 \mapsto (1,1)$.

• Layer 1: $\times \mapsto 0, \; + \mapsto 1$.

• Layer 0 (output): $+ \mapsto \emptyset$ (the empty bitstring, also written $()$).

from gkr.ac import ArithmeticCircuit

expression_01 = '(3*2) + (4 + 1)'
gkr_01 = ArithmeticCircuit(expression_01, prime=2**31 - 1)
display(gkr_01.graphviz_circuit_bitstring)

Gate-value functions. For each layer $i \in \{0,\ldots,d\}$, the gate-value function

records the value at each gate. By multilinear interpolation on the Boolean hypercube, each $W_i$ has a unique multilinear extension

Example 1 [gate-value functions]. In our example,

These admit the multilinear extensions (computed explicitly below)

For instance,

matching $W_2(1,1)$.

Wiring predicates. For $i \in \{0,\ldots,d-1\}$, define wiring predicates

encoding the circuit topology. Concretely, $\mathrm{add}_i(\mathbf{c},\mathbf{a},\mathbf{b}) = 1$ iff $\mathbf{c}$ is an addition gate whose two children are $\mathbf{a}$ and $\mathbf{b}$, and $\mathbf{a} \le \mathbf{b}$ (lexicographic order). Similarly for $\mathrm{mult}_i$. Each wiring predicate has a unique multilinear extension

Example 1 [wiring predicates]. In our circuit,

and all other values are zero. The multilinear extensions are:

Gate propagation and Thaler’s identity. The circuit semantics are captured by the layer-wise gate propagation equation: for $i \in \{0,\ldots,d-1\}$ and $\mathbf{z}\in\{0,1\}^{s_i}$,

Thaler’s identity is the multilinear-extension analogue: for $i \in \{0,\ldots,d-1\}$ and $\mathbf{z}\in\mathbb{F}^{s_i}$,

Example 1 [layer-wise gate propagation and Thaler’s identity]. In our example, (2) expands to

and

What is being verified? The circuit $C$ (including its wiring predicates) is public. The prover’s private information is the collection of intermediate gate values, equivalently the functions $W_i$. In the single-output setting, the prover’s top-level claim is simply that the output gate evaluates to a particular field element (here, 11).

More generally, Layer 0 may contain multiple output gates. We label the $S_0$ outputs by $\{0,1\}^{s_0}$, and the function

encodes all outputs at once. The prover’s claim is that the true output function $W_0$ equals a purported function $W_0^*$ (equivalently, $\widetilde{W}_0=\widetilde{W}_0^*$ as polynomial functions).

The verifier does not check equality at all points. Instead, they sample a uniformly random $\rho_0\in\mathbb{F}^{s_0}$ and check equality at that point:

If $\widetilde{W}_0\neq \widetilde{W}_0^*$, then $\widetilde{W}_0-\widetilde{W}_0^*$ is a nonzero multilinear polynomial function (degree $\le s_0$), so by Schwartz-Zippel,

Thus, a match at a random point gives strong evidence that all output gates are correct.

From Thaler’s identity to GKR. Fix a layer $i$. The verifier does not try to check (2) for all $\mathbf{z}\in\mathbb{F}^{s_i}$. Instead, they sample a random point $\rho_i\in\mathbb{F}^{s_i}$ and ask the prover to justify (2) at $\mathbf{z}=\rho_i$.

Once $\rho_i$ is fixed, the right-hand side of (2) becomes a polynomial function in the $2s_{i+1}$ Boolean variables $(\mathbf{x},\mathbf{y})$. The prover and verifier then run sum-check over these variables. At the end of sum-check, the verifier is left with a small number of claimed values of $\widetilde{W}_{i+1}$; the folding step compresses these into a single new claim about $\widetilde{W}_{i+1}$ at a fresh random point $\rho_{i+1}$.

As in the sum-check notebook, we distinguish circuit-determined objects from prover-asserted objects. We use $(\cdot)^*$ (e.g. $\widetilde{W}_i^*$) for prover claims, which may be false. For clarity, we sometimes use the notation $\;\overset{?}{=}\;$ for an equality that may not hold if P is dishonest. Unadorned symbols refer to the true objects induced by the circuit. For readability, we reuse symbols like the verifier challenges $r_j$ and the prover’s round polynomials $g_j$ across different sum-check invocations; they are “reset” each time a new sum-check begins.

GKR Layer 0. The parties are the verifier V and the prover P. V samples $\rho_0 \leftarrow \mathbb{F}^{s_0}$. Define

the summand in (2) when $i=0$ and $\mathbf{z}=\rho_0$. Thus,

Moreover $\deg g \le 4s_1$: the wiring polynomials have degree $\le 2s_1$, the multilinear extensions $\widetilde{W}_1(\mathbf{x})$ and $\widetilde{W}_1(\mathbf{y})$ have degree $\le s_1$, and the worst case comes from the product term. (In general Layer $i$, the same reasoning gives $\deg g \le 4s_{i+1}$.)

The protocol runs sum-check on (6) (with the prover’s possibly false claim for $\widetilde{W}_0(\rho_0)$ on the left-hand side), with one crucial twist at the final step: instead of having V evaluate $g(r_x,r_y)$ directly, GKR uses claimed values of $\widetilde{W}_1$ and then folds them into a single new claim.

Example 1 [GKR Layer 0]. Here $s_0=0$, so $\mathbb{F}^{s_0}=\{\emptyset\}$ and $\rho_0=\emptyset$. Also $s_1=1$, and from (3) we set

To see how cheating is forced to “thread the needle”, suppose P falsely claims that $\widetilde{W}_0(\rho_0)$ equals 10 (the truth is 11). The sum-check claim is

which is true iff the left-hand side equals 11. Since P insists on $\widetilde{W}_0^*(\rho_0) = 10$, they must lie consistently, and later they will still need luck to avoid detection.

Sum-check Round 0.0. Define

so that, as $\widetilde{W}_0$ and $g_0$ are ground-truth polynomial functions, $\widetilde{W}_0(\rho_0)=g_0(0)+g_0(1)$. P sends $g_0^*$, and V checks:

1. $\deg g_0^* \le 4s_1 = 4$,

2. $\widetilde{W}_0^*(\rho_0)=g_0^*(0)+g_0^*(1)$.

If both pass, V samples $r_0\leftarrow\mathbb{F}$ and sends it to P.

In truth, $g_0(u_0)=(1-u_0)(11-u_0)$, but V does not know this. To satisfy the checks while forcing $g_0^*(0)+g_0^*(1)=10$, P can pick (for example)

since

Suppose V chooses $r_0=17$.

Sum-check Round 0.1. Define $g_1(u_1):=g(r_0,u_1)$, so $g_0(r_0)=g_1(0)+g_1(1)$. P sends $g_1^*$, and V checks:

1. $\deg g_1^* \le 4$,

2. $g_0^*(r_0)=g_1^*(0)+g_1^*(1)$.

If both pass, V samples $r_1\leftarrow\mathbb{F}$ and sends it to P.

Since $r_0=17$, the truth is

but P can instead claim

which satisfies

Suppose V chooses $r_1=42$.

Sum-check final check (where GKR diverges). In standalone sum-check, V would check $g_1^*(r_1)\overset{?}{=}g(r_0,r_1)$, but in GKR V does not directly evaluate $g(r_0,r_1)$.

Instead, define

and P supplies claimed values $z_0^*,z_1^*$ asserted to equal $z_0,z_1$.

In our example, the ground truth is

and also

whereas

so standalone sum-check would reject. GKR postpones this evaluation and moves to folding.

At this point, V has reduced a claim about $\widetilde{W}_0$ to two claimed values of $\widetilde{W}_1$. Recursing naïvely would cause a blow-up. Folding avoids this by compressing two claims into one.

GKR folding at Layer 0. At the end of the Layer 0 sum-check, V is left to verify

where

are the verifier challenge vectors from the $2s_1$ rounds. P supplies claimed values

Together, (5), (7), and (8) amount to the “bridging” equation

Since the circuit is public, V can evaluate $\widetilde{\mathrm{add}}_0$ and $\widetilde{\mathrm{mult}}_0$ at any point, so V checks (9) and rejects if it fails.

Now fold the two claims in (8) into a single claim. Define the affine line $\ell:\mathbb{F}\to\mathbb{F}^{s_1}$ by

and define the associated univariate polynomial function $q_1 : \mathbb{F} \to \mathbb{F}$ by

By construction, $q_1(0)=\widetilde{W}_1(r_x)$ and $q_1(1)=\widetilde{W}_1(r_y)$.

P sends a univariate polynomial function $q_1^*$, purported to equal $q_1$. V checks:

1. $\deg q_1^* \le s_1$,

2. $q_1^*(0)=z_0^*$ and $q_1^*(1)=z_1^*$.

If these checks pass, V samples $\tau_1\leftarrow\mathbb{F}$ and sets

In an honest execution, $q^*_1$ is the true $q_1$, and hence $q_1^*(\tau_1)$ is equal to $\widetilde{W}_1(\rho_1)$. Thus the two claims in (8) have been reduced to a single claim about $\widetilde{W}_1$ at the random point $\rho_1$. The protocol then proceeds to Layer 1.

Example 1 [GKR folding at Layer 0]. In this example, $r_x=r_0$ and $r_y=r_1$. P supplies $z_0^*,z_1^*$, and V checks

Define $\ell$ as in (10) and $q_1$ as in (11). Here $\ell(t)=(1-t)r_0+tr_1$ and $q_1(t)=\widetilde{W}_1(\ell(t))=6-\ell(t)$. P sends $q_1^*$ and V checks the endpoint constraints (and $\deg q_1^*\le 1$). Then V samples $\tau_1\leftarrow\mathbb{F}$ and defines $\rho_1=\ell(\tau_1)$ as in (12). In an honest execution, $q_1^*(\tau_1)$ equals $\widetilde{W}_1(\rho_1)$, and by Thaler’s identity this equals

With the concrete values above, $(r_0,r_1)=(17,42)$ and $g_1^*(r_1)=44016$. To satisfy (13), P must choose $z_0^*,z_1^*$ with

Since $\big[(1-17)\cdot 42\big]^{-1}\equiv 405848844\bmod p$, one possible choice is

Then P can define $q_1^*(t):=(1-t)z_0^*+t z_1^*$, which automatically satisfies the endpoint checks.

Suppose V chooses $\tau_1=3$. Then $\rho_1=\ell(3)=92$, and the truth is $q_1(3)=\widetilde{W}_1(92)=6-92=-86$, whereas

Thus in the next sum-check (Layer 1), P is forced to justify the false claim

The true value of the right-hand side is 2147483561. V does not know this, but after the Layer 1 sum-check the inconsistency is detected with high probability.

GKR Layer i ($1 \le i \le d-2$). At the start of Layer $i$, V holds a point $\rho_i\in\mathbb{F}^{s_i}$ and a claimed value $q_i^*(\tau_i)\in\mathbb{F}$, which (if P is honest) equals $\widetilde{W}_i(\rho_i)$. V and P run sum-check to justify Thaler’s identity at $\mathbf{z}=\rho_i$.

Define

a polynomial function on $\mathbb{F}^{s_{i+1}}\times\mathbb{F}^{s_{i+1}}$. Sum-check is applied to

Let $m:=2s_{i+1}$, and identify $(\mathbf{x},\mathbf{y})$ with $v=(v_0,\ldots,v_{m-1})\in\mathbb{F}^m$, where $\mathbf{x}=(v_0,\ldots,v_{s_{i+1}-1})$ and $\mathbf{y}=(v_{s_{i+1}},\ldots,v_{m-1})$. The sum-check routine has $m$ rounds, with verifier challenges $r=(r_0,\ldots,r_{m-1})\in\mathbb{F}^m$. Write $r_x=(r_0,\ldots,r_{s_{i+1}-1})\in\mathbb{F}^{s_{i+1}}$ and $r_y=(r_{s_{i+1}},\ldots,r_{m-1})\in\mathbb{F}^{s_{i+1}}$. As usual, the prover sends round polynomials $g_j^*$, and the verifier checks the degree bound and consistency equations. After the final challenge $r_{m-1}$, sum-check reduces consistency to $g_{m-1}^*(r_{m-1}) = g(r_0,\ldots,r_{m-1}) = g(r_x,r_y)$.

Expanding $g(r_x,r_y)$ yields

where $z_x:=\widetilde{W}_{i+1}(r_x)$ and $z_y:=\widetilde{W}_{i+1}(r_y)$.

GKR folding at Layer i. P supplies claimed values $z_x^*,z_y^*\in\mathbb{F}$. V checks the bridging equation

rejecting if it fails. To fold the two claims into one, define

and

Then $q_{i+1}(0)=\widetilde{W}_{i+1}(r_x)$ and $q_{i+1}(1)=\widetilde{W}_{i+1}(r_y)$. P sends $q_{i+1}^*$, and V checks:

1. $\deg q_{i+1}^* \le s_{i+1}$,

2. $q_{i+1}^*(0)=z_x^*$ and $q_{i+1}^*(1)=z_y^*$.

If these pass, V samples $\tau_{i+1}\leftarrow\mathbb{F}$ and defines

In an honest execution, $q_{i+1}^*(\tau_{i+1})$ equals $\widetilde{W}_{i+1}(\rho_{i+1})$. The protocol proceeds to the next layer until reaching $d-1$.

GKR Layer d - 1 (final layer). Layer $d-1$ is handled differently because its child gates lie in the input layer $d$. Here the recursion bottoms out: $\widetilde{W}_d$ is fully determined by the public inputs, so the verifier can evaluate $\widetilde{W}_d$ directly.

As before, at the start of Layer d - 1, V holds $\rho_{d-1}\in\mathbb{F}^{s_{d-1}}$ and a claimed value $q_{d-1}^*(\tau_{d-1})$ (honestly $\widetilde{W}_{d-1}(\rho_{d-1})$). The parties run sum-check on Thaler’s identity at layer $d-1$, producing challenge vectors $r_x,r_y\in\mathbb{F}^{s_d}$ and reducing to a final check of the form $g_{2s_d-1}^*(r_{2s_d-1}) \overset{?}{=} g(r_x,r_y)$. Unlike earlier layers, V now computes $z_x=\widetilde{W}_d(r_x)$ and $z_y=\widetilde{W}_d(r_y)$ directly from the public inputs, and checks the corresponding bridging equation. If it holds, V accepts; otherwise V rejects.

This completes the description of the GKR protocol.

Example 1 [GKR Layer d - 1]. In our example $d=2$, so the final nontrivial layer is $d-1=1$. The input layer has size $S_2=4$ and hence $s_2=2$. At the end of Layer 0, V holds $\rho_1\in\mathbb{F}^{s_1}=\mathbb{F}$ and a claimed value $q_1^*(\tau_1)$, which (if P is honest) equals $\widetilde{W}_1(\rho_1)$. Sum-check at Layer 1 runs for $2s_2=4$ rounds. At the end, V needs to check $g_3^*(r_3)\overset{?}{=}g(r_0,r_1,r_2,r_3)$. Crucially, since this is the input layer, V can evaluate $\widetilde{W}_2$ directly:

and therefore V can compute the right-hand side $g(r_0,r_1,r_2,r_3)$ explicitly and reject if it disagrees with $g_3^*(r_3)$.

Sum-check for Layer 1. Here $s_2 = 2$, so the sum-check protocol runs for $2s_2 = 4$ rounds. Recall that the layer-1 claim being justified is the (possibly false) value $q_1^*(\tau_1)$, which in an honest execution equals $\widetilde{W}_1(\rho_1)$; see the setup in the preceding discussion (in particular, the explicit identity in (14) above).

Sum-check Round 1.0. Define

For the true $g_0$ and $g$, we have $g_0(0)+g_0(1)=\sum g(\cdot)$, so the sum-check consistency condition for the prover’s first message is

The prover P sends a polynomial $g_0^*$, claiming it is the same as $g_0$. V checks:

1. $\deg g_0^* \le 4s_2 = 8$,

2. $q_1^*(\tau_1) = g_0^*(0) + g_0^*(1)$.

If either check fails, V rejects. Otherwise, V samples

and sends it to P.

With our specific values ($\rho_1 = 92$), the true polynomial is

However, since P is pursuing the false claim from earlier, P must send some different polynomial $g_0^*$ that still passes the two checks above. Suppose P chooses

Then the degree bound holds, and in $\mathbb{Z}/p\mathbb{Z}$ we have

So far, P’s messages are consistent and V does not reject. Suppose V’s random challenge is

Sum-check Round 1.1. Define

so that, as these are the true polynomials,

P sends $g_1^*$ (claiming it is the same as $g_1$). V checks:

1. $\deg g_1^* \le 8$,

2. $g_0^*(r_0) = g_1^*(0) + g_1^*(1)$.

If the checks pass, V samples

and sends it to P.

With our specific values ($r_0 = 99$), the true polynomial is

Suppose P instead claims

V verifies the degree bound and the consistency equation by checking (in $\mathbb{Z}/p\mathbb{Z}$)