Structured ("Sector") GKR

Source: Tha13, section 5 ("Time-Optimal Protocols for Circuit Evaluation").

Review: Equality MLE

We begin by briefly recalling the $\widetilde{\mathrm{eq}}$ MLE (see this section for more details). We first consider the binary string equality function $\mathrm{eq}:\{0,1{\}}^{2n}\mapsto \{0,1\}$, where

$$\mathrm{eq}(X_1,...,X_n;Y_1,...,Y_n)=\{\begin{array}{ll}1& \text{if ∀i:Xi=Yi}\\ 0& \text{otherwise}\end{array}$$

This function is $1$ if and only if $X$ and $Y$ are equal as binary strings, and $0$ otherwise. We can extend this to a multilinear extension via the following -- consider $\widetilde{\mathrm{eq}}:{\mathbb{F}}^{2n}\mapsto \mathbb{F}$, where

$$\widetilde{\mathrm{eq}}(X_1,...,X_n;Y_1,...,Y_n)=\prod _{i=1}^n(1-X_i)(1-Y_i)+X_i{Y}_i$$

Structured Layerwise Relationship

See Tha13, page 25 ("Theorem 1") for a more rigorous treatment. Note that Remainder does not implement Theorem 1 in its entirety, and that many circuits which do fulfill the criteria of Theorem 1 are currently not expressible within Remainder's circuit frontend.

Structured layerwise relationships can loosely be thought of as data relationships where the bits of the index of the "destination" value in the $i$'th layer are a (optionally subset) permutation of the bits of the index of the "source" value in the $j$'th layer for $j>i$. As a concrete example, we consider a layerwise relationship where the destination layer is half the size, and its values are the element-wise products of the two halves of the source layer's values: Let ${\tilde{V}}_i(Z_1,Z_2)$ represent the MLE of the destination layer, and let ${\tilde{V}}_j(Z_1,Z_2,Z_3)$ represent the MLE of the source layer.

Let the evaluations of ${\tilde{V}}_j$ over the hypercube be $[a,b,c,d,e,f,g,h]$. Then we wish to create a layerwise relationship such that the evaluations of ${\tilde{V}}_i$ over the hypercube are $[ae,bf,cg,dh]$. We can actually write this as a simple rule in terms of the (integer) indices of $V_i$ as follows:

$$V_i(z)=V_j(z)\cdot V_j(4+z)$$

If we allow for our arguments to be the binary decomposition of $z$ rather than $z$ itself, we might have the following relationship:

$$V_i(z_1,z_2)=V_j(0,z_1,z_2)\cdot V_j(1,z_1,z_2)$$

where $0z_1{z}_2$ is the binary representation of $z$ and $1z_1{z}_2$ is the binary representation of $4+z$. This is in fact very close to the exact form-factor of the polynomial layerwise relationship which we should create between the layers -- we now consider the somewhat un-intuitive relationship

$$V_i(Z_1,Z_2)=\sum _{b_1,b_2\in \{0,1{\}}^2}\mathrm{eq}(Z_1,Z_2;b_1,b_2)\cdot V_j(0,b_1,b_2)\cdot V_j(1,b_1,b_2)$$

One way to read the above relationship is the following: for any (binary decomposition) $Z_1,Z_2$, the value of the $i$'th layer at the index represented by $Z_1,Z_2$ should be $V_j(0,Z_1,Z_2)\cdot V_j(1,Z_1,Z_2)$. We are summing over all possible values of the hypercube above, $b_1,b_2\in \{0,1{\}}^2$, and for each value we check whether the current iterated hypercube value $b_1,b_2$ "equals" the argument $Z_1,Z_2$ value. If so, we contribute $V_j(0,b_1,b_2)\cdot V_j(1,b_1,b_2)$ to the sum and if not, we contribute zero to the sum.

In this way we see for $Z_1,Z_2\in \{0,1\}$ that all of the summed values will be zero except for when $b_1,b_2$ are exactly identical to $Z_1,Z_2$, and thus only the correct value $V_j(0,b_1,b_2)\cdot V_j(1,b_1,b_2)$ will contribute to the sum (and thus the value of $V_i(Z_1,Z_2)$).

As described, the above relationship looks extremely inefficient in some sense -- why bother summing over all the hypercube values when we already know that all of them will be zero because $\mathrm{eq}$ will evaluate to zero at all values except one?

The answer is that it's not enough to only consider $V_i(Z_1,Z_2)$ for binary $Z_1,Z_2$, as our claims will be of the form ${\tilde{V}}_i(g_1,g_2)=c$, where $g_1,g_2,c\in \mathbb{F}$, and ${\tilde{V}}_i$ is the multilinear extension of $V_i$ (see claims section for more information on prover claims). Another way to see this is that the above relationship is able to be shown for each $Z_1,Z_2\in \{0,1\}$, but we want to make sure that the relationship holds for all $Z_1,Z_2\in \{0,1\}$. Rather than checking each index individually, it's much more efficient to check a "random combination" of all values simultaneously by evaluating ${\tilde{V}}_i$ at a random point $g_1,g_2$. We thus have, instead, that

$${\tilde{V}}_i(Z_1,Z_2)=\sum _{b_1,b_2\in \{0,1{\}}^2}\widetilde{\mathrm{eq}}(Z_1,Z_2;b_1,b_2)\cdot {\tilde{V}}_j(0,b_1,b_2)\cdot {\tilde{V}}_j(1,b_1,b_2)$$

Since ${\tilde{V}}_i$ is identical to $V_i$ (and similarly for $\widetilde{\mathrm{eq}}$ and ${\tilde{V}}_j$) everywhere on the hypercube, the above relationship should still hold for all binary $Z_1,Z_2$. Moreover, the above relationship is now one which we can directly apply sumcheck to, since we have a summation over the hypercube!

But wait, you might say. This still seems wasteful -- why are we bothering with this summation and $\widetilde{\mathrm{eq}}$ polynomial? Why can't we just have something like

$${\tilde{V}}_i(Z_1,Z_2)={\tilde{V}}_j(0,Z_1,Z_2)\cdot {\tilde{V}}_j(1,Z_1,Z_2)$$

Unfortunately the above relationship cannot work, as $Z_1,Z_2$ are linear on the LHS and quadratic on the RHS. The purpose of the summation and $\widetilde{\mathrm{eq}}$ polynomial is to "linearize" the RHS and quite literally turn any high degree polynomial (such as ${\tilde{V}}_j(0,Z_1,Z_2)\cdot {\tilde{V}}_j(1,Z_1,Z_2)$) into its unique multilinear extension (recall the definition of multilinear extension).

We see that the general pattern of creating a "structured" layerwise relationship is as follows:

• First, write the relationship in terms of the binary indices of values between each layer. In our case, $V_i(z_1,z_2)=V_j(0,z_1,z_2)\cdot V_j(1,z_1,z_2)$.
• Next, replace $z_i$ on the LHS of the equation with formal variable $Z_i\in \mathbb{F}$, and allow the LHS to be a multilinear extension. We now have ${\tilde{V}}_i(Z_1,Z_2)$ on the LHS.
• Next, replace $z_i$ on the RHS of the equation with boolean $b_i$ values and add an $\widetilde{\mathrm{eq}}$ predicate between $Z_i,b_i$, and add a summation over all $b_i$ values. Additionally, extend all $V_j$ to their multilinear extensions ${\tilde{V}}_j$ (this is importantly only for sumcheck):

$${\tilde{V}}_i(Z_1,Z_2)=\sum _{b_1,b_2\in \{0,1{\}}^2}\widetilde{\mathrm{eq}}(Z_1,Z_2;b_1,b_2)\cdot {\tilde{V}}_j(0,b_1,b_2)\cdot {\tilde{V}}_j(1,b_1,b_2)$$

Structured "Selector" Variables

Some relationships between layers are best expressed piece-wise. For example, let's say that we have a destination layer, ${\tilde{V}}_i(Z_1,Z_2)$, and a source layer of the same size, ${\tilde{V}}_j(Z_1,Z_2)$, where we'd like to square the first two evaluations but double the last two.

In other words, if ${\tilde{V}}_j(Z_1,Z_2)$ has evaluations $[a,b,c,d]$ over the boolean hypercube, then ${\tilde{V}}_i(Z_1,Z_2)$ should have evaluations $[a^2,b^2,2c,2d]$. If we follow our usual protocol for writing the layerwise relationship here, we would have something like the following for the "integer index" version of the relationship:

$$V_i(z)=\{\begin{array}{ll}{V}_j(z{)}^2& \text{if z < 2}\\ 2\cdot V_j(z)& \text{otherwise}\end{array}$$

We notice that in binary form, $z<2$ whenever $z_1=0$ (and $z\ge 2$ when $z_1=1$). We can thus re-write the above as

$$V_i(z_1,z_2)=(1-z_1)\cdot V_j(0,z_2{)}^2+z_1\cdot 2\cdot V_j(1,z_2)$$

In other words, when $z_1=0$ the second summand on the RHS is zero, and the first summand is just $V_j(0,z_2)=V_j(z_1,z_2)$ since we already know that $z_1=0$, and vice versa for when $z_1=1$. At a first glance, this may look similar to the earlier example in which we took the products of adjacent pairs of layer values, but the two are not the same --

• First, the current setup is semantically quite different; in the previous example we applied a binary "shrinking" transformation between the source and destination layers by multiplying pairs of values, while in the current example we are "splitting" the circuit into two semantic halves and applying a different unary operation element-wise to each half.
• Second, the current setup actually has its $z_1$ variable outside of the argument to an MLE representing data in a previous layer. This is precisely what allows us to "select" between the two semantic halves of the circuit and compute an element-wise squaring in the first and a doubling in the second.

Applying the third transformation rule from above and extending everything into its multilinear form, we get

$${\tilde{V}}_i(Z_1,Z_2)=\sum _{b_1,b_2\in \{0,1{\}}^2}\widetilde{\mathrm{eq}}(Z_1,Z_2;b_1,b_2)\cdot [(1-b_1)\cdot {\tilde{V}}_j(0,b_2{)}^2+b_1\cdot 2\cdot {\tilde{V}}_j(1,b_2)]$$

However, now the observation that $\widetilde{\mathrm{eq}}$ should only apply to variables which are nonlinear on the RHS is helpful here -- notice that although $b_2$ as a variable would be quadratic on the RHS, $b_1$ is linear and can thus be removed from the summation altogether and replaced directly with $Z_1$:

$${\tilde{V}}_i(Z_1,Z_2)=\sum _{b_2\in \{0,1\}}\widetilde{\mathrm{eq}}(Z_2;b_2)\cdot [(1-Z_1)\cdot {\tilde{V}}_j(0,b_2{)}^2+Z_1\cdot 2\cdot {\tilde{V}}_j(1,b_2)]$$

This layerwise relationship form-factor is called a "selector" in Remainder terminology and in general refers to an in-circuit version of an "if/else" statement where MLEs representing the values of layers can be broken into power-of-two-sized pieces.

Why Structured Circuits?

Compared to canonic GKR, structured circuits are good for two reasons -- verifier runtime and circuit description size. Note that every layerwise relationship which can be expressed as a structured layer (using $\widetilde{\mathrm{eq}}$) can be written as an equivalent series of $\widetilde{\mathrm{add}}$ and $\widetilde{\mathrm{mul}}$ gate layers.

To see why structured layers are good for circuit description size, we compare the following layer-wise relationships which describe the same circuit wiring pattern, but with different verifier cost and circuit description complexities (let $Z=Z_1,...,Z_n$ and $b=b_1,...,b_n$ for shorthand). Firstly, the structured version, which computes an element-wise product between each pair of evaluations:

$${\tilde{V}}_i(Z_1,...,Z_n)=\sum _{b_1,...,b_n\in \{0,1{\}}^n}\widetilde{\mathrm{eq}}(Z;b)\cdot {\tilde{V}}_j(b_1,...,b_{n-1},0)\cdot {\tilde{V}}_j(b_1,...,b_{n-1},1)$$

And secondly, the multiplication gate version:

$${\tilde{V}}_i(Z_1,...,Z_n)=\sum _{x\in \{0,1{\}}^n,y\in \{0,1{\}}^n}{\widetilde{\mathrm{mul}}}_{i,j,j}(Z,x,y)\cdot [{\tilde{V}}_j(x)\cdot {\tilde{V}}_j(y)]$$

We first consider the verifier runtime for both. Note that the sumcheck verifier performs $O(1)$ operations per round of sumcheck, plus the work necessary for the oracle query. In the structured relationship's case, there are $n$ rounds of sumcheck, and assuming that $b_1,...,b_n$ get bound to $r_1,...,r_n\in \mathbb{F}$, the oracle query which the verifier must evaluate is of the form

$$f_n(r_n)\stackrel{?}{=}\widetilde{\mathrm{eq}}(Z_1,...,Z_n;r_1,...,r_n)\cdot {\tilde{V}}_j(r_1,...,r_{n-1},0)\cdot {\tilde{V}}_j(r_1,...,r_{n-1},1)$$

where $f_n$ is the $n$'th univariate polynomial which the prover sends during sumcheck. The prover sends the claimed values for both ${\tilde{V}}_j(r_1,...,r_{n-1},0)$ and ${\tilde{V}}_j(r_1,...,r_{n-1},1)$, and so the verifier doesn't do any work there. The verifier additionally evaluates $\widetilde{\mathrm{eq}}(Z_1,...,Z_n;r_1,...,r_n)$ on its own, which it can do in $O(n)$ time.

Next, we consider the verifier runtime for the multiplication gate case: let $x_1,...,x_n$ be bound to $u_1,...,u_n\in \mathbb{F}$ and let $y_1,...,y_n$ be bound to $v_1,...,v_n\in \mathbb{F}$ during sumcheck. The oracle query is then

$$f_n(r_n)\stackrel{?}{=}{\widetilde{\mathrm{mul}}}_{i,j,j}(Z_1,...,Z_n,u_1,...,u_n,v_1,...,v_n)\cdot [{\tilde{V}}_j(u_1,...,u_n)\cdot {\tilde{V}}_j(v_1,...,v_n)]$$

Similarly to the structured case, the prover sends claimed values for ${\tilde{V}}_j(u_1,...,u_n)$ and ${\tilde{V}}_j(v_1,...,v_n)$, and so the verifier doesn't have to do any work here. However, the verifier must also evaluate ${\widetilde{\mathrm{mul}}}_{i,j,j}(Z_1,...,Z_n,u_1,...,u_n,v_1,...,v_n)$ on its own. This requires time linear to the sparsity of the ${\widetilde{\mathrm{mul}}}_{i,j,j}$ polynomial, i.e. $O(2^{n-1})$ in this example, since there are $2^{n-1}$ nonzero multiplication gates (one for each pair of values in layer $i+1$).

A circuit description size comparison between the two can be seen in a very similar light. In particular, the representation of $\widetilde{\mathrm{eq}}$ requires just $O(n)$ words to store (assuming each word can hold an $n$-bit value), as we simply enumerate the indices between the $Z_i$'s and the $b_i$'s. On the other hand, storing the sparse representation of $\widetilde{\mathrm{mul}}$ required for linear-time proving requires storing all nonzero evaluations, i.e. $O(2^{n-1})$ such indices in the above example (although one might argue that the representation is quite structured and can therefore be further compressed).

A note on claims

The above example (and other similar layerwise relationships) give us a further prover speedup through the structure of the claims which arise from the oracle query during sumcheck. In particular, the claims which the prover makes to the verifier in the structured case are as follows:

$$\begin{gathered} {\tilde{V}}_j(r_1,...,r_{n-1},0)\stackrel{?}{=}{c}_0 \\ {\tilde{V}}_j(r_1,...,r_{n-1},1)\stackrel{?}{=}{c}_1 \end{gathered}$$

These claims can be aggregated with almost no additional cost to the prover and verifier, as the first $n-1$ challenges are identical between the two and the last challenges are precisely a $0$ and a $1$. In particular, the verifier can simply sample $r^{\star }$ and have the prover instead show that

$${\tilde{V}}_j(r_1,...,r_{n-1},r^{\star })=(1-r^{\star })\cdot c_0+r^{\star }\cdot c_1$$

On the other hand, the claims generated by the multiplication gate version of the layer above are in the form

$$\begin{gathered} {\tilde{V}}_j(u_1,...,u_n)\stackrel{?}{=}{c}_u \\ {\tilde{V}}_j(v_1,...,v_n)\stackrel{?}{=}{c}_v \end{gathered}$$

These claims have no challenges in common, and can only be aggregated through interpolative or RLC claim aggregation, both of which are significantly more expensive than the above method.

Costs

In general (note that this does not capture all possible structured layer cases, but should be enough to give some intuition on the prover/verifier/proof size costs for most structured layers), let us assume that our layerwise relationship can be expressed in the following manner -- $${\tilde{V}}_i(Z_1,...,Z_n)=\sum _{b_1,...,b_n\in \{0,1{\}}^n}\widetilde{\mathrm{eq}}(Z_1,...,Z_n;b_1,...,b_n)[\sum _{k=1}^s\prod _{\ell =1}^d{\tilde{V}}_{j_{k,\ell }}(b_1,...,b_n)]$$ In other words, we have a layerwise relationship over $n$ variables, where the values in ${\tilde{V}}_i$ are a function of those in layers ${\tilde{V}}_{j_{k,\ell }}$, where $j_{k,\ell }>i$, such that we have $s$ total summand "groups" of MLEs over $n$ variables of size up to $d$, i.e. the total polynomial degree in each of the $b_i$ is $d+1$.

The prover costs are as follows:

• For simplicity here, we assume that the prover has $O(1)$ access to any value in $\widetilde{\mathrm{eq}}(Z_1,...,Z_n;b_1,...,b_n)$ (note that these evaluations must be either precomputed in linear time, e.g. Tha13, or can be streamed in linear time in a clever way, e.g. Rot24).

• Additionally, we assume that the prover has $O(1)$ access to any value in any ${\tilde{V}}_{i_{k,\ell }}(b_1,...,b_n)$, since the prover presumably knows all of the circuit values ahead of time.

• Finally, we assume that the prover can use the "bookkeeping table folding" trick from Tha13 to compute both $\widetilde{\mathrm{eq}}(Z_1,...,Z_n;r_1,b_2,...,b_n)$ from $\widetilde{\mathrm{eq}}(Z_1,...,Z_n;b_1,b_2,...,b_n)$ and ${\tilde{V}}_{i_{k,\ell }}(Z_1,...,Z_n;r_1,b_2,...,b_n)$ from ${\tilde{V}}_{i_{k,\ell }}(Z_1,...,Z_n;b_1,b_2,...,b_n)$ in $O(2^n)$ field operations.

• We thus see that in the first round of sumcheck, the prover must do the following:

  • Evaluate each of the terms in the summation for every $b_1,...,b_n\in \{0,1{\}}^n$ and sum them together. Each evaluation takes $O(sd)$ field operations, as there are $s$ summands and each requires $d$ multiplications.
  • Since there are $2^n$ values of $b_1,...,b_n$, the above costs $O(s\cdot d\cdot 2^n)$ field operations. This is the total cost for the prover to compute the claimed sum for the first round.
  • Next, the prover must evaluate the RHS of the sumchecked equation at $X=0,...,d+1$ in the place of $b_1$ to compute the univariate sumcheck message. Each evaluation of $X$, similarly to the above, costs $O(s\cdot d\cdot 2^n)$ field operations.
  • The total cost for the prover to compute the claimed sum + univariate message in the first round is thus $O(s\cdot d\cdot 2^n+(d+1)\cdot s\cdot d\cdot 2^n)=O(s\cdot d(d+2)\cdot 2^n)$ field operations.

• We can generalize the above to the $t$'th round of sumcheck (let $t=0$ for the first round) by noting that rather than $n$ variables, there are $n-t$ variables which are being summed over in the outer sum. Since the other values $s,d$ remain constant, the prover's total cost is simply $O(s\cdot d(d+1)\cdot 2^{n-t})$.

• Finally, as mentioned earlier, the prover can generate the necessary precomputed values from the $t$'th round from those of the $t-1$'th round in $O((s\cdot d+1)\cdot 2^{n-t})$, as there are $s\cdot d+1$ MLEs (including the $\widetilde{\mathrm{eq}}$ polynomial) which need their bookkeeping tables to be "folded" in $O(2^{n-t})$.

• Putting it altogether, the prover's total cost across all sumcheck rounds is thus $$\sum _{t=0}^{n-1}O(s\cdot d(d+2)\cdot 2^{n-t})+O((s\cdot d+1)\cdot 2^{n-t})$$

• Since the above is a geometric series in $2^n$, we have that the prover's total cost across all rounds is simply $$O(s\cdot d(d+2)\cdot 2^{n+1})$$

The proof size is as follows:

• For each of the $n$ rounds of sumcheck, the prover must send over a degree $d+1$ univariate polynomial to the verifier. Additionally, the prover must send the original sum (although this is actually free in GKR since the verifier already has the prover-claimed sum implicitly through the prover's claim from a previous sumcheck's oracle query).
• Finally, the prover must send over each of its claimed values for the ${\tilde{V}}_{j_{k,\ell }}(r_1,...,r_n)$ at the end of sumcheck. There are at most $s\cdot d$ claims.
• The proof size is thus simply $O((d+2)\cdot n+s\cdot d)$ field elements.

The verifier runtime is as follows:

• For each round of sumcheck, let the prover's univariate polynomial message be $f_t(X)\in {\mathbb{F}}^{<d+2}[X]$. The verifier samples a random challenge $r_t\stackrel{\$}{\leftarrow }\mathbb{F}$ and checks whether $$f_{t-1}(r_t)\stackrel{?}{=}{f}_t(0)+f_t(1)$$
• Since the verifier can evaluate $f_t$ and $f_{t-1}$ in $O(d+2)$ and performs this check for each of the $n$ rounds of sumcheck, they can compute all the intermediate checks in $O(n\cdot (d+2))$.
• During the final oracle query, the verifier must check whether $$f_n(r_1,...,r_n)\stackrel{?}{=}\widetilde{\mathrm{eq}}(Z_1,...,Z_n;r_1,...,r_n)[\sum _{k=1}^s\prod _{\ell =1}^d{\tilde{V}}_{j_{k,\ell }}(r_1,...,r_n)]$$
• The verifier can compute $\widetilde{\mathrm{eq}}(Z_1,...,Z_n;r_1,...,r_n)$ on its own in $O(n)$, and has access to each of the prover-claimed values for ${\tilde{V}}_{j_{k,\ell }}(r_1,...,r_n)$. It can thus compute the RHS of the above in $O(n+s\cdot d)$.
• The verifier's total runtime is thus $$O(n\cdot d+n+s\cdot d)=O((s+n)\cdot d)$$