Encoding Layers in GKR

At this point, we have all the puzzle pieces needed to describe the GKR protocol -- layered arithmetic circuits, multilinear extensions, and sumcheck. This section talks about how we can tie all of these concepts together to verify claims on the output of an arithmetic circuit.

Grounding Example

We start with an example layered arithmetic circuit. Throughout this tutorial, we will provide this concrete example while simultaneously providing the generic steps of GKR.

Note some differences from the way this circuit is labeled as opposed to the example in the statement encoding section. Over here, we let the output be a nonzero value for the sake of the example (we explain how to transform any circuit with nonzero output to a circuit with zero output in a future section). Additionally, note that the gate labels start from $0$ in each layer, as opposed to the labels being unique throughout the entire circuit in the previous example. Because our gates ${\mathrm{add}}_{i,j,k}$ and ${\mathrm{mul}}_{i,j,k}$ are unique per triplet of layers $(i,j,k)$, we can start from $0$ in labeling the gates at the start of each layer.

In this example, $\mathcal{P}$ claims that the output of the following circuit is $45.$ Note that beyond the values in the input, and the actual structure of the circuit (what we refer to as the circuit description), $\mathcal{V}$ does not need any more information to verify the output of the circuit by computation:

This is because every node in every layer ${\mathcal{L}}_i$ with $i<d$ can be computed as the result of gates applied to nodes in previous layers.

At a high level, for the rest of this section we focus on encoding layers in two ways: as an MLE of its own, and using its relationship to other layers (via gates). We can equate these two encodings because they are of the same thing (the values in a single layer). With that, we have an equation we can perform a sumcheck over.

Encoding Layer Nodes as an MLE

We start by encoding the input layer in our example, and then show how this extends to the general case. More concretely, we want an MLE ${\tilde{V}}_j(x)$ such that ${\tilde{V}}_j(x)={\mathrm{val}}_j(x).$ Although it might not be immediately evident, because we eventually want to invoke the sumcheck protocol, it is useful to consider the inputs $x$ as bit-strings rather than integral values.

Example

Therefore, for example, we want ${\tilde{V}}_3(0,1)=3$ because ${\mathrm{val}}_3(1)=3$ and the bit-string $01$ represents $1$. Another way of restating our problem statement of encoding the input layer as some MLE ${\tilde{V}}_3(x_1,x_2)$ is to say "when $x=z$, output ${\mathrm{val}}_3(z).$

Here we can leverage the power of the $\widetilde{\mathrm{eq}}$ MLE: $${\tilde{V}}_3(x_1,x_2)=\sum _{b_1,b_2}\widetilde{\mathrm{eq}}(x_1,x_2;b_1,b_2)\cdot V_3(b_1,b_2),$$ or in other words: $${\tilde{V}}_3(x_1,x_2)=5(1-x_1)(1-x_2)+3(1-x_1)x_2+2x_1(1-x_2)+5x_1{x}_2.$$ You can independently verify that at each of the node input label values, $\tilde{V}(x)$ outputs the correct value.

General

Note that we conveniently defined the node labels to start from $0$ and naturally enumerate the nodes in each layer in our definition of ${\tilde{V}}_3(x_1,x_2)$ above. This allows us to generally extend the function $f(x)={\mathrm{val}}_i(x)$ which represents the nodes of layer $i$ into the following MLE: $${\tilde{V}}_i(x)=\sum _{z\in \{0,1{\}}^{s_i}}\widetilde{\mathrm{eq}}(x;z){\mathrm{val}}_i(z)$$ where $s_i$ is the $\log$ number of nodes in layer $i$.

Encoding Layers using their Relationship to other Layers

Another note we made when presenting the above diagram was that the only information that $\mathcal{V}$ needs to know immediately is the values of the input itself and the structure of the circuit. This is because the values of the future layers are determined by nodes in previous layers and the gates that connect them. Let's formalize this statement below.

Example

In the running example, let's fill in the layer ${\mathcal{L}}_2:$

We were able to fill this in because: $$\begin{array}{rlr}{\mathrm{val}}_2(0)& =& {\mathrm{val}}_3(1)+{\mathrm{val}}_3(2)\\ {\mathrm{val}}_2(1)& =& {\mathrm{val}}_3(0)\cdot {\mathrm{val}}_3(2)\\ {\mathrm{val}}_2(2)& =& {\mathrm{val}}_3(1)\cdot {\mathrm{val}}_3(3)\end{array}$$

So, while one way to write the MLE representing ${\mathcal{L}}_2$, as explained in the previous section, is $${\tilde{V}}_2(x_1,x_2)=5(1-x_1)(1-x_2)+10(1-x_1)x_2+15x_1(1-x_2),$$ we can also represent it by its relationship to the nodes in ${\mathcal{L}}_3:$ $$\begin{array}{rlr}{\tilde{V}}_2(x_1,x_2)& =& \widetilde{\mathrm{eq}}(x_1,x_2;0,0)({\tilde{V}}_3(0,1)+{\tilde{V}}_3(1,0))\\ & +& \widetilde{\mathrm{eq}}(x_1,x_2;0,1)({\tilde{V}}_3(0,0)\cdot {\tilde{V}}_3(1,0))\\ & +& \widetilde{\mathrm{eq}}(x_1,x_2;1,0)({\tilde{V}}_3(0,1)\cdot {\tilde{V}}_3(1,1))\end{array}$$ Note that in this definition, we still are linear in the variables $x_1,x_2.$

General

Now we go over how to write ${\tilde{V}}_i(x_1,x_2)$ in terms of ${\tilde{V}}_j(z)$ for $j>i.$ Recall the definition of ${\mathrm{add}}_{i,j,k}(z,x,y)$ and ${\mathrm{mul}}_{i,j,k}(z,x,y)$. For example, in the case of ${\mathcal{L}}_2$: $$\begin{gathered} {\mathrm{add}}_{2,3,3}((0,0),(0,1),(1,0))=1 \\ {\mathrm{mul}}_{2,3,3}((0,1),(0,0),(1,0))=1 \\ {\mathrm{mul}}_{2,3,3}((1,0),(0,1),(1,1))=1. \end{gathered}$$

If we use the indicator functions $\mathrm{add}$ and $\mathrm{mul}$ to translate the example above: $$\begin{gathered} {\tilde{V}}_i(x)=\sum _{z\in \{0,1{\}}^{s_i}}\sum _{x^{\prime }\in \{0,1{\}}^{s_j}}\sum _{y^{\prime }\in \{0,1{\}}^{s_k}}(\widetilde{\mathrm{eq}}(x;z){\mathrm{add}}_{i,j,k}(z,x^{\prime },y^{\prime })[{\mathrm{val}}_j(x^{\prime })+{\mathrm{val}}_k(y^{\prime })] \\ +\widetilde{\mathrm{eq}}(x;z){\mathrm{mul}}_{i,j,k}(z,x^{\prime },y^{\prime })[{\mathrm{val}}_j(x^{\prime })\cdot {\mathrm{val}}_k(y^{\prime })\left]\right) \end{gathered}$$ where $s_i,s_j,s_k$ are the number of bits needed to represent the node labels of that respective layer. We know that ${\mathrm{val}}_j(x^{\prime })$ and ${\mathrm{val}}_k(y^{\prime })$ can be computed using MLEs for ${\mathcal{L}}_j$ and ${\mathcal{L}}_k$, so we can rewrite the above as: $$\begin{gathered} {\tilde{V}}_i(x)=\sum _{z\in \{0,1{\}}^{s_i}}\sum _{x^{\prime }\in \{0,1{\}}^{s_j}}\sum _{y^{\prime }\in \{0,1{\}}^{s_k}}(\widetilde{\mathrm{eq}}(x;z){\mathrm{add}}_{i,j,k}(z,x^{\prime },y^{\prime })[{\tilde{V}}_j(x^{\prime })+{\tilde{V}}_k(y^{\prime })] \\ +\widetilde{\mathrm{eq}}(x;z){\mathrm{mul}}_{i,j,k}(z,x^{\prime },y^{\prime })[{\tilde{V}}_j(x^{\prime })\cdot {\tilde{V}}_k(y^{\prime })\left]\right). \end{gathered}$$ More detail and examples on transforming these indicator gate functions into MLEs are described in the section on canonic GKR.

Using the Equivalence between Layer Encodings

Now we have enough information to show how we can reduce claims on one layer to claims on the output of an MLE encoding a source layer (closer to the circuit input layer) for that layer.

Example

We start with the MLE encoding the output. $\mathcal{P}$ claims that the output of the circuit is $45$, i.e., ${\tilde{V}}_0=45$. Then, at any random point $\mathcal{V}$ challenges $\mathcal{P}$ with, say $g$, because ${\tilde{V}}_0$ is a constant function, an honest $\mathcal{P}$ claims that ${\tilde{V}}_0(g)=45$.

Another way, as expressed above to write ${\tilde{V}}_0(g)$ is as:

$$\begin{gathered} 45\stackrel{?}{=}{\tilde{V}}_0(g)=\sum _{z\in \{0,1{\}}^{s_0}}\sum _{x^{\prime }\in \{0,1{\}}^{s_j}}\sum _{y^{\prime }\in \{0,1{\}}^{s_k}}(\widetilde{\mathrm{eq}}(g;z){\mathrm{add}}_{0,1,1}(z,x^{\prime },y^{\prime })[{\tilde{V}}_1(x^{\prime })+{\tilde{V}}_1(y^{\prime })] \\ +\widetilde{\mathrm{eq}}(g;z){\mathrm{mul}}_{0,1,1}(z,x^{\prime },y^{\prime })[{\tilde{V}}_1(x^{\prime })\cdot {\tilde{V}}_1(y^{\prime })\left]\right). \end{gathered}$$

Note that while we expicitly write $z$ to maintain consistency between earlier examples, in this case, because there is only one output, there are no $z$ variables. Therefore, ${\mathrm{add}}_{0,1,1}(z,x,y)$ and ${\mathrm{mul}}_{0,1,1}(z,x,y)$ are constant functions, and their extensions are equal to their value in their first position: ${\mathrm{add}}_{0,1,1}(0,x,y)$ and ${\mathrm{mul}}_{0,1,1}(0,x,y)$.

$\mathcal{P}$ and $\mathcal{V}$ engage in a sumcheck protocol to verify this claim of the sum of a polynomial over the boolean hypercube. Recall that sumcheck requires binding the variables that the sum is over (in this case, $z,x^{\prime },y^{\prime }$), one by one, with random challenges.

If we follow the sumcheck protocol as is, at the end, $x$ is bound to $u$ and $y$ is bound to $v$. Let's say the prover's final univariate is $f_{s_j+s_k}(X)$ and the verifier's final challenge is $v_k.$ Then, we end with the final claim:

$$f_{s_k+s_k}(v_k)\stackrel{?}{=}{\mathrm{add}}_{0,1,1}(0,u,v)[{\tilde{V}}_1(u)+{\tilde{V}}_1(v)]+{\mathrm{mul}}_{0,1,1}(0,u,v)[{\tilde{V}}_1(u)\cdot {\tilde{V}}_1(v)].$$

$\mathcal{V}$ knows the structure of the circuit, so they can compute ${\mathrm{add}}_{0,1,1}(p,u,v),{\mathrm{mul}}_{0,1,1}(p,u,v)$ on their own. Additionally, $\widetilde{\mathrm{eq}}$ is publically computable, so $\mathcal{V}$ computes that on their own as well. Normally, sumcheck would require $\mathcal{V}$ make a query to an "oracle" to verify the claimed values $V_1(u)\stackrel{?}{=}{c}_1$ and ${\tilde{V}}_1(v)\stackrel{?}{=}{h}_2$.

However, instead we say that $\mathcal{P}$ "reduces" the claim that ${\tilde{V}}_0(g)\stackrel{?}{=}45$ to two claims on ${\tilde{V}}_1:V_1(u)\stackrel{?}{=}{c}_1;{\tilde{V}}_1(v)\stackrel{?}{=}{c}_2.$

Similarly, ${\tilde{V}}_1$ has a relationship to MLEs in later layers, so the sumcheck on ${\tilde{V}}_1$ will reduce to claims on these MLEs, eventually propagating to claims on the input layer.

For another example of claim reduction for structured GKR, see this section.

General

In general, GKR works very similarly to the example above. We cover the case where $\mathcal{V}$ expects the output of the circuit to be $0$. $\mathcal{P}$ receives a challenge from $\mathcal{V},g$ and claims that the MLE representing ${\mathcal{L}}_0$ still evaluates to $0$ over that random point. I.e., $\mathcal{P}$ claims that ${\tilde{V}}_0(g)=0.$ Using the encoding of ${\tilde{V}}_0$ using later layers, $\mathcal{P}$ reduces its claim on the output of the circuit to evaluations of MLEs representing future layers.

Note that there is an exponential blow-up of claims when reducing claims on one layer to the next. We describe a protocol to aggregate claims (and therefore achieve a one-to-one reduction) in the claims section.

Circuit Description

Throughout this section, we refer to $\mathcal{V}$ using the description of the circuit in order to evaluate the gates or to understand the layerwise relationships on their own. The circuit description is something agreed upon beforehand with $\mathcal{P}$ and $\mathcal{V}$ and visible to both parties -- it is the "shape" of the circuit, which includes how many nodes each layer contains, the number of layers, and which gates connect nodes from layer to layer.

Therefore, the circuit description of our example circuit is this:

Note: Transforming a Circuit to have Zero Output

In Remainder, $\mathcal{V}$ expects circuits to have output $0$. This is because certain types of circuits (such as those resulting from LogUp) require the output to specifically be $0$, and $\mathcal{V}$ needs to specifically verify this fact.

If a circuit does not have output $0$, one way to transform this is to add the negative of the expected output to the input. The last layer of the circuit can be the sum of this expected output, and the actual output of the circuit. This results in a circuit with the output layer evaluating to $0$. We show this transformation applied to our example above: