GKR: An Introduction

GKR is a protocol for circuit evaluation, specifically for layered circuits. We will be covering the protocol as presented in Thaler's Proofs, Arguments and Zero-Knowledge, which is slightly simpler than the one presented in the original GKR paper.

In this note, we will present the GKR protocol "by re-discovery". That is, we will present 2 intermediary protocols that build on each other, and culminate into GKR. Specifically, we will start with the most naive version, GKR**, improve on it to get GKR*, and once again improve on it to get GKR. The hope is that first learning GKR** and GKR* makes understanding why and how GKR works much easier.

The circuit

All 3 protocols will be proving the evaluation of the following circuit.

The circuit has 3 layers, where layer 0 is the output layer, and layer 2 is the input layer. \(S_i\) denotes the number of nodes in layer \(i\): \(S_0 = 2\), \(S_1 = 4\), \(S_2 = 8\). It will also be useful to have a variable \(k_i\) to hold the logarithm of \(S_i\): \(k_0 = 1\), \(k_1 = 2\), \(k_2 = 3\). Finally, the values that each layer takes is represented by a function \(W_i: \{0, 1\}^{k_i} \rightarrow \mathbb{F}\). That is, each layer's \(j^{\mathrm{th}}\) value is mapped to from the bit decomposition of \(j\). For example, consider how \(W_2\) is defined:

• \(W_2(0, 0, 0) = y_0\)
• \(W_2(0, 0, 1) = y_1\)
• \(W_2(0, 1, 0) = y_2\)
• …
• \(W_2(1, 1, 1) = y_7\)

Lastly, \(W_i\) is defined in terms of \(W_{i+1}\), except for the input layer:

\[ W_i(x) = \sum_{b, c \in \{0, 1\}^{k_{i+1}}} add_{i+1}(x, b, c) (W_{i+1}(b) + W_{i+1}(c)) + mul_{i+1}(x, b, c) (W_{i+1}(b) \times W_{i+1}(c)), \]

where

\[ add_{i+1}(x, b, c) = \left\{ \begin{array}{l} 1, & \text{if } W_i(x) = W_{i+1}(b) + W_{i+1}(c) \\ 0, & \text{otherwise, } \end{array} \right. \]

and

\[ mul_{i+1}(x, b, c) = \left\{ \begin{array}{l} 1, & \text{if } W_i(x) = W_{i+1}(b) \times W_{i+1}(c) \\ 0, & \text{otherwise. } \end{array} \right. \]

For example, in our circuit, \(add_1(0, (0, 0), (0, 1)) = 1\) (referring to the top-left node getting its input from the first 2 nodes on the next layer), and \(mul_1(1, (1, 0), (1, 1)) = 1\) (referring to the top-right node getting its input from the first 2 nodes on the next layer).

Lastly, we will assume that polynomials \(\tilde{D}_i\) sent from the prover to the verifier are stored in evaluation form over the domain \(\{0, 1\}^{k_i}\). For example, to send the polynomial \(\tilde{D}_0\), the prover sends 2 values: \(\tilde{D}_0(0)\) and \(\tilde{D}_0(1)\). Similarly, to send the polynomial \(\tilde{D}_1\), the prover sends 4 values: \(\tilde{D}_1(0, 0)\) and \(\tilde{D}_1(0, 1)\), \(\tilde{D}_1(1, 0)\) and \(\tilde{D}_1(1, 1)\).

Preliminaries

The protocol will make use of \(\tilde{W}_i\), the multilinear extension of \(W_i\), instead of \(W_i\) itself. If you are not familiar with what the multilinear extension of a function is, please refer to Thaler's Proofs, Arguments and Zero-Knowledge, section 3.5. That is, from now on, we sort of forget about the circuit itself (and its layers \(W_i\)), and think in terms of the corresponding layer polynomials \(\tilde{W_i}\) instead.

The circuit \(C\) and inputs \(\tilde{W}_2\) are public, meaning that both the verifier and prover know them. The goal of the prover will be to convince the verifier that it evaluated \(C\) with \(\tilde{W}_2\) properly.

Hence, the zero-knowledge property is not a goal. The verifier technically is allowed to see everything. The purpose of the protocol is solely to speed up the verifier by making it not evaluate the entire circuit.

GKR**

We start by presenting GKR**, the simplest of our 3 protocols. In line with the verifier speed goal, we will try to have the verifier evaluate each \(\tilde{D}_i\) polynomial at most once. This is because polynomial evaluation can be expensive, so we want to limit how many times the verifier runs polynomial evaluation.

GKR**: high-level description

In this section, we will go over the protocol from a high-level view in order to give an intuition for what the protocol is doing before we dive into the details in the next section.

At the beginning of the protocol, the prover evaluates the circuit. In other words, it computes the polynomials \(\tilde{W}_1\) and \(\tilde{W}_0\), and sends them to the verifier.

It is key to understand that since the verifier doesn't trust the prover, it doesn't know yet that the polynomials received correspond to the evaluation of the circuit \(C\) using \(W_2\) as input. We will reserve the use of \(\tilde{W}_1\) and \(\tilde{W}_0\) to refer to the layer polynomials that result from correctly evaluating the circuit. Hence, from the perspective of the verifier, we will use \(\tilde{D}_1\) and \(\tilde{D}_0\) to refer to the polynomials received by the prover.

The purpose of the protocol will be to convince the verifier that \(\tilde{D}_1 = \tilde{W}_1\) and \(\tilde{D}_0 = \tilde{W}_0\). Or, in plain English, that the polynomials received by the prover correspond to the correct evaluation of the circuit. Note that for the input layer, we use \(\tilde{W}_2\) directly (as opposed to \(\tilde{D}_2\)), since the verifier has access to the circuit inputs, and hence knows what the true inputs are without needing to rely on the prover.

The key is to remember that \(\tilde{W}_0\) is defined in terms of \(\tilde{W}_1\), and \(\tilde{W}_1\) in terms of \(\tilde{W}_2\), as described in the first section. Hence, the verifier will perform the following steps:

1. Show that \(\tilde{D}_1 = \tilde{W}_1\) by checking that

\[ \tilde{D}_1(x) = \sum_{b, c \in \{0, 1\}^3} \tilde{add_1}(x, b, c) (\tilde{W}_2(b) + \tilde{W}_2(c)) + \tilde{mul_1}(x, b, c) (\tilde{W}_2(b) \times \tilde{W}_2(c)) \]

In the next section, we'll explore how to actually run this check. For now, the critical thing to understand is that after the check passed, the verifier is convinced that \(\tilde{D}_1(x)\) is indeed the same as \(\tilde{W}_1(x)\). This is because the right-hand side of the equation is the literal definition of \(\tilde{W}_1(x)\). Hence, after this check has passed, we can start using \(\tilde{W}_1(x)\) instead of \(\tilde{D}_1(x)\).

2. Show that \(\tilde{D}_0 = \tilde{W}_0\) by checking that

\[ \tilde{D}_0(x) = \sum_{b, c \in \{0, 1\}^2} \tilde{add_0}(x, b, c) (\tilde{W}_1(b) + \tilde{W}_1(c)) + \tilde{mul_0}(x, b, c) (\tilde{W}_1(b) \times \tilde{W}_1(c)) \]

Notice that the verifier does indeed know the polynomial \(\tilde{W}_1(x)\) due to the previous check having passed. So it is now able to run this check as well (which as you might have noticed, uses \(\tilde{W}_1\) instead of \(\tilde{D}_1\)). Hence, by the same argument, after this check passes, the verifier will be convinced that \(\tilde{D}_0 = \tilde{W}_0\). Since \(\tilde{W}_0\) is the polynomial for the output layer of the circuit, we're done! The verifier can retrieve the 2 circuit outputs at \(\tilde{W}_0(0)\) and \(\tilde{W}_0(1)\).

Note that since polynomials are sent in evaluation form (as described in the Preliminaries section), the verifier directly received \(\tilde{W}_0(0)\) and \(\tilde{W}_0(1)\) from the prover, and so retrieving these 2 values doesn't require running a polynomial evaluation algorithm.

GKR**: the core check

In this section, we will deep dive into how the checks from the previous section are actually performed.

\[ \tilde{D}_i(x) = \sum_{b, c \in \{0, 1\}^{k_{i+1}}} \tilde{add_i}(x, b, c) [\tilde{W}_{i+1}(b) + \tilde{W}_{i+1}(c)] + \tilde{mul_i}(x, b, c) [\tilde{W}_{i+1}(b) \times \tilde{W}_{i+1}(c)] \]

The first thing to realize is that this is a polynomial equality test between the polynomial on the left-hand side, and the one on the right-hand side. If you are not familiar with how to do that, we recommend to watch this video, or to review Thaler's Proofs, Arguments and Zero-Knowledge, section 2.1 (referred to as "Reed-Solomon Fingerprinting"). In short, to quickly test if two polynomials are equal, we evaluate it at a random point.

Hence, the verifier draws a random \(\lambda_i \in \mathbb{F}^{k_i}\), and evaluates both sides at this point.

\[ \tilde{D}_i(\lambda_i) = \sum_{b, c \in \{0, 1\}^{k_{i+1}}} \tilde{add_i}(\lambda_i, b, c) [\tilde{D}_{i+1}(b) + \tilde{D}_{i+1}(c)] + \tilde{mul_i}(\lambda_i, b, c) [\tilde{D}_{i+1}(b) \times \tilde{D}_{i+1}(c)] \]

However, we run into a problem. The verifier can evaluate the left-hand side (remember: it is allowed to evaluate each \(\tilde{D}_i\) once), but cannot evaluate the right-hand side without evaluating \(\tilde{D}_{i+1}\) multiple times (\(2 \times 2^{k_{i+1}}\) times to be exact).

Fortunately, we can use the sum-check algorithm here! Recall that sum-check can be used to evaluate expressions of the form

\[ H = \sum_{x \in \{0, 1\}^k} g(x) \]

In our case,

• \(H = \tilde{D}_i(\lambda_i)\),
• \(x = (b, c)\), and
• \(g((b, c)) = \tilde{add_i}(\lambda_i, b, c) [\tilde{D}_{i+1}(b) + \tilde{D}_{i+1}(c)] + \tilde{mul_i}(\lambda_i, b, c) [\tilde{D}_{i+1}(b) \times \tilde{D}_{i+1}(c)]\).

So the prover and verifier run the sum-check algorithm. For each of the \(2 \times k_{i+1}\) steps of sum-check, the verifier will draw a random variable from \(\mathbb{F}\). Let us denote the first \(k_{i+1}\) of them \(\gamma_b \in \mathbb{F}^{k_{i+1}}\), and the subsequent \(k_{i+1}\) of them \(\gamma_c \in \mathbb{F}^{k_{i+1}}\).

When the prover and verifier get to the last step, the verifier will need to evaluate \(\tilde{D}_{i+1}(\gamma_b)\) and \(\tilde{D}_{i+1}(\gamma_c)\) as part of the evaluation of \(g\). But this violates our rule, since \(\tilde{D}_{i+1}\) would be evaluated twice by the verifier! Fortunately, there's a neat trick we can use which lets the verifier only evaluate \(\tilde{D}_{i+1}\) once. We will defer to Thaler's Proofs, Arguments and Zero-Knowledge, section 4.5.2 for the explanation of why the trick works, and just use it directly here.

A line \(l_{i+1}: \mathbb{F} \rightarrow \mathbb{F}^{k_{i+1}}\) is defined, such that \(l_{i+1}(0) = \gamma_b\) and \(l_{i+1}(1) = \gamma_c\). The prover sends a polynomial \(q_{i+1}: \mathbb{F} \rightarrow \mathbb{F}^{k_{i+1}}\) that is claimed to be equal to \(\tilde{D}_{i+1} \circ l_{i+1}\). Hence, the verifier runs a polynomial equality test on \(q_{i+1} = \tilde{D}_{i+1} \circ l_{i+1}\): it draws a random \(\gamma_{i+1}^* \in \mathbb{F}\), and checks that

\[ q(\gamma_{i+1}^*) = \tilde{D}_{i+1}(l_{i+1}(\gamma_{i+1}^*)) \]

Note that this is the only evaluation of \(\tilde{D}_{i+1}\) that the verifier is allowed to do. And here's where the trick shines. Assuming that the check passed, then the verifier can evaluate \(q_{i+1}(0)\) to get \(\tilde{D}_{i+1}(b)\), and \(q_{i+1}(1)\) to get \(\tilde{D}_{i+1}(c)\). Note that the verifier is allowed to evaluate \(q_{i+1}\) multiple times, since \(q_{i+1}\) is effectively a collection of \(k_{i+1}\) small univariate polynomials that are much faster to evaluate than \(\tilde{D}_{i+1}\).

And so the verifier is able to complete the last step of the sum-check protocol (since it can evaluate \(g((\gamma_b, \gamma_c))\). Zooming back out, this completes our original intent of checking

\[ \tilde{D}_i(x) = \sum_{b, c \in \{0, 1\}^{k_{i+1}}} \tilde{add_i}(x, b, c) [\tilde{W}_{i+1}(b) + \tilde{W}_{i+1}(c)] + \tilde{mul_i}(x, b, c) [\tilde{W}_{i+1}(b) \times \tilde{W}_{i+1}(c)] .\]

GKR**: the protocol

So far, we've seen the entire protocol, piece by piece. In this section, we put it all together.

1. The honest prover evaluates the circuit, in effect computing the polynomials \(\tilde{W}_1\) and \(\tilde{W}_0\). It sends both polynomials to the verifier, which receives them as \(\tilde{D}_1\) and \(\tilde{D}_0\), respectively.
2. The verifier draws a random \(\lambda_1 \in \mathbb{F}^2\) and checks

\[ \tilde{D}_1(\lambda_1) = \sum_{b, c \in \{0, 1\}^3} \tilde{add_2}(\lambda_1, b, c) [\tilde{W}_2(b) + \tilde{W}_2(c)] + \tilde{mul_2}(\lambda_1, b, c) [\tilde{W}_2(b) \times \tilde{W}_2(c)] \]

using the sum-check algorithm, and using the trick described in the previous section to only evaluate \(\tilde{W}_2\) once at \(l_2(\gamma_2^*)\). This convinces the verifier that \(\tilde{D}_1 = \tilde{W}_1\).

3. The verifier draws a random \(\lambda_0 \in \mathbb{F}\) and checks

\[ \tilde{D}_0(\lambda_0) = \sum_{b, c \in \{0, 1\}^2} \tilde{add_1}(\lambda_0, b, c) [\tilde{D}_1(b) + \tilde{D}_1(c)] + \tilde{mul_1}(\lambda_0, b, c) [\tilde{D}_1(b) \times \tilde{D}_1(c)] \]

using the sum-check algorithm, and using the trick described in the previous section to only evaluate \(\tilde{D}_1\) once at \(l_1(\gamma_1^*)\). This convinces the verifier that \(\tilde{D}_0 = \tilde{W}_0\), and completes the protocol.

GKR**: the problem

GKR** doesn't actually achieve our goal of evaluating each \(\tilde{D}_i\) polynomial once! While each "layer check" indeed only evaluates its polynomials once, \(\tilde{D}_1\) is evaluated twice: once during step 2 (at \(\lambda_1\)), and once during step 3 (at \(l_1(\gamma_1^*)\)). In general, the verifier will evaluate each inner layer twice; that is, every layer that is not the input or output layer.

So while GKR** is sound, we could improve the performance of the verifier by actually having it only evaluate each \(\tilde{D}_i\) polynomial once.

GKR*

GKR* improves on GKR** by achieving the desired property of the verifier only needing to evaluate the layer polynomials \(\tilde{D}_i\) once.

Let's take a closer look at both evaluations of \(\tilde{D}_1\) in GKR**.

1. \(\tilde{D}_1(\lambda_1)\) for a random \(\lambda_1\) drawn by the verifier in step 2, and
2. \(\tilde{D}_1(l_1(\gamma_1^*))\) in step 3, where \(\gamma_1^*\) is a random value drawn by the verifier, and \(l_1\) is the line between \(\gamma_b\) and \(\gamma_c\), such that \(l(0) = \gamma_b\) and \(l(1) = \gamma_c\).

The key observation to make is that \(\lambda_1\) is a random value freely drawn by the verifier, whereas \(l_1(\gamma_1^*)\) is constrained, since you need to run the sum-check algorithm in step 3 all the way to the end in order to know \(l_1\) and, by extension, \(l_1(\gamma_1^*)\). So somehow, if we could run step 3 before step 2, we could first run step 3's sum-check, get \(l_1(\gamma_1^*)\), and reuse \(l_1(\gamma_1^*)\) in step 2 (instead of \(\lambda_1\)). This way, the verifier would only evaluate \(\tilde{D}_1(l_1(\gamma_1^*))\), and be able to reuse that evaluation for both steps!

It turns out this is easy to achieve: simply run the algorithm in reverse order! Start from the output layer \(\tilde{D}_0\), and make your way to the input layer \(\tilde{W}_2\).

GKR*: the protocol

1. The honest prover evaluates the circuit, in effect computing the polynomials \(\tilde{W}_1\) and \(\tilde{W}_0\). It sends both polynomials to the verifier, which receives them as \(\tilde{D}_1\) and \(\tilde{D}_0\), respectively.

2. The verifier draws a random \(\lambda_0 \in \mathbb{F}\) and checks

\[ \tilde{D}_0(\lambda_0) = \sum_{b, c \in \{0, 1\}^2} \tilde{add_1}(\lambda_0, b, c) [\tilde{D}_1(b) + \tilde{D}_1(c)] + \tilde{mul_1}(\lambda_0, b, c) [\tilde{D}_1(b) \times \tilde{D}_1(c)] \]

using the sum-check algorithm, and evaluating \(\tilde{D}_1\) only at \(l_1(\gamma_1^*)\).

3. The verifier reuses the \(\tilde{D}_1(l_1(\gamma_1^*))\) evaluation, and checks

\[ \tilde{D}_1(l_1(\gamma_1^*)) = \sum_{b, c \in \{0, 1\}^3} \tilde{add_2}(\lambda_1, b, c) [\tilde{W}_2(b) + \tilde{W}_2(c)] + \tilde{mul_2}(\lambda_1, b, c) [\tilde{W}_2(b) \times \tilde{W}_2(c)] \]

using the sum-check algorithm, and evaluating \(\tilde{W}_2\) only at \(l_2(\gamma_2^*)\).

GKR*: Recap

We actually did it this time! In GKR*, the verifier actually only evaluates each layer polynomial once. And GKR* is sound, using the same reasoning made in GKR**, since exactly the same checks are performed by the verifier, except in reverse order.

GKR

We're now ready to tackle the actual GKR protocol! It improves on GKR* by allowing the verifier evaluate only the input layer \(\tilde{W}_0\) and output layer \(\tilde{W}_2\). That is, the inner layer \(\tilde{W}_1\) doesn't need to be evaluated explicitly by the verifier. This might sound like a marginal gain, but it's huge. While our simple circuit only has one inner layer, real-world circuits have many more. And most importantly, the number of layers to be evaluated by the verifier is constant.

At a first glance, it's reasonable to wonder how that is even possible. After all, isn't the protocol ultimately based on running polynomial equality for each layer? How can you run polynomial equality on the inner layers without even evaluating the polynomial at one point? This is what we'll be exploring in this section.

Note: Since the prover no longer sends the inner layer polynomials \(\tilde{D}_i\), we will stop using "\(\tilde{D}\)" for the inner layers - we will instead use \(\tilde{W}\) directly

GKR: an in-depth look

The core improvement of GKR is that the prover doesn't need to send any inner layer polynomial; it is sufficient to only send the \(q_i = \tilde{W}_i \circ l_i\) polynomials. Let's see how that is possible by tracing what the verifier is doing, and how it reasons through the data it is receiving from the prover.

1. The honest prover evaluates the circuit, and sends the output layer polynomial \(\tilde{D}_0\).
2. Run sum-check on
   \[ C_0 = \sum_{b, c \in \{0, 1\}^2} \tilde{add_1}(\lambda_0, b, c) [\tilde{W}_1(b) + \tilde{W}_1(c)] + \tilde{mul_1}(\lambda_0, b, c) [\tilde{W}_1(b) \times \tilde{W}_1(c)] \]

• At the last step, after the verifier has drawn all the random variables for \(\gamma_b\) and \(\gamma_c\), define \(l_1\), the line such that \(l_1(0) = \gamma_b\) and \(l_1(1) = \gamma_c\).
• The verifier receives univariate polynomial \(q_1 \overset{?}{=} \tilde{W}_1 \circ l_1\). It will only be able to check that equality later; for now, it just uses \(q_1\) as is.
• To complete the last step of sum-check, the verifier uses \(q_1(0)\) as a stand-in for \(\tilde{W}_1(\gamma_b)\), and \(q_1(1)\) as a stand-in for \(\tilde{W}_1(\gamma_c)\).
• We denote the value resulting from this sum-check as \(C_0\). The verifier simply holds on to that value for later.

Peeking forward, this step is designed such that when the verifier will later confirm that \(q_1 = \tilde{W}_1 \circ l_1\), then

\[q_1(0) = \tilde{W}_1(l_1(0)) = \tilde{W}_1(\gamma_b),\] and
\[q_1(1) = \tilde{W}_1(l_1(1)) = \tilde{W}_1(\gamma_c),\]
which in turn means that \(C_0 = \tilde{W}_0(\lambda_0)\), due to how the sum-check is defined. But we're getting ahead of ourselves!

3. The verifier draws \(\gamma_1^* \in \mathbb{F}\), and the verifier and prover run sum-check on
   \[ C_1 = \sum_{b, c \in \{0, 1\}^3} \tilde{add_2}(l_1(\gamma_1^*), b, c) [\tilde{W}_2(b) + \tilde{W}_2(c)] + \tilde{mul_2}(l_1(\gamma_1^*), b, c) [\tilde{W}_2(b) \times \tilde{W}_2(c)] \]

• At the last step, after the verifier has drawn all the random variables for \(\gamma_b\) and \(\gamma_c\), define \(l_2\), the line such that \(l_2(0) = \gamma_b\) and \(l_2(1) = \gamma_c\).
• The verifier receives univariate polynomial \(q_2 \overset{?}{=} \tilde{W}_2 \circ l_2\). It will only be able to check that equality later; for now, it just uses \(q_2\) as is.
• To complete the last step of sum-check, the verifier uses \(q_2(0)\) as a stand-in for \(\tilde{W}_2(\gamma_b)\), and \(q_2(1)\) as a stand-in for \(\tilde{W}_2(\gamma_c)\).
• We denote the value resulting from this sum-check as \(C_1\). The verifier simply holds on to that value for later.

Similarly, this sum-check instance was designed such that when the verifier is able to confirm that \(q_2 = \tilde{W}_2 \circ l_2\), then \(C_1 = \tilde{W}_1(l(\gamma_1^*))\).

4. The verifier runs the check \(\tilde{W}_2(l_2(\gamma_2^*)) = q_2(\gamma_2^*)\).

• Remember that \(\tilde{W}_2\) is the input layer polynomial, and is public. This is the only time in the protocol that the verifier will evaluate it.
• Note that since \(\gamma_2^*\) is random, this check is a polynomial equality check between \(q_2\) and \(\tilde{W}_2 \circ l_2\).
• The verifier is now convinced that \(q_2 = \tilde{W}_2 \circ l_2\).

5. Going back to step 3, now that we know that \(q_2 = \tilde{W}_2 \circ l_2\), we then also know that \(C_1 = \tilde{W}_1(l(\gamma_1^*)) = \tilde{W}_1 \circ l_1(\gamma_1^*)\).

• This enables the verifier to use \(C_1\) to run an equality check between \(q_1\) and \(\tilde{W}_1 \circ l_1\)!
• The verifier checks \(q_1(\gamma_1^*) = C_1\).
• The verifier is now convinced that \(q_1 = \tilde{W}_1 \circ l_1\).

6. Going back to step 1, now that we know that \(q_1 = \tilde{W}_1 \circ l_1\), we then also know that \(C_0 = \tilde{W}_0(\lambda_0)\).

• This enables the verifier to finally check \(\tilde{D}_0 = \tilde{W}_0\).
• The verifier checks \(\tilde{D}_0(\lambda_0) = C_0\).
• The verifier is convinced that \(\tilde{D}_0 = \tilde{W}_0\).

And that completes the protocol! The verifier is convinced that the prover correctly evaluated the circuit, and that the outputs that it received indeed correspond to the outputs of circuit evaluation.

This is a very beautiful protocol. Ultimately, GKR was able to improve on GKR* by realizing that the carefully constructed sum-check problems allow you to forgo running an expensive polynomial evaluation step on the layer polynomials themselves at every step, if only you're willing to wait until the very end for everything to click together.