LogUp-GKR: The Air constraints

Recall from the previous article that running GKR on the LogUp circuit leaves us with the claims \(\tilde{f}_0(\rho), \dots, \tilde{f}_{m-1}(\rho)\), for some randomly sampled \(\rho \in \mathbb{F}^{\log n}\). We will be proving these claims in Air.

Rather than proving \(m\) separate claims, we will instead prove the random linear combination of these claims:

\[ \sigma = \sum_{j = 0}^{m-1} \alpha_j \tilde{f}_j(\rho) \]

for randomly sampled \(\alpha_j \in \mathbb{F}\), \(0 \leq j < m\).

Finally, let \(g\) be the generator of a cyclic group \(G\) of size \(n\), where \(G \subset \mathbb{F}\).

Conventions

Let \(i \in \mathbb{F}\). Then, we will use \(i^{\wedge}\) to denote the bit decomposition of \(i\). For example, if \(i = 4\), then \(i^{\wedge} = (0, 0, 1)\). Note that when representing bit decompositions, the least significant bit comes first, and the most significant bit comes last.

Given the trace length \(n\), let \(\mu = \log_2 n\).

The columns

We will first re-arrange the equation to better reflect how we will be proving \(\sigma\).

\[ \begin{align} \sigma &= \sum_{j = 0}^{m-1} \alpha_j \tilde{f}_j(\rho) \\ &= \sum_{j = 0}^{m-1} \alpha_j \sum_{x \in \{0, 1\}^{\mu}} \mathrm{eq}(x, \rho) f_j(x)\\ &= \sum_{x \in \{0, 1\}^{\mu}} \mathrm{eq}(x, \rho) \sum_{j = 0}^{m-1} \alpha_j f_j(x) \end{align} \]

We will use 2 auxiliary columns, called \(l\) and \(s\), to prove \(\sigma\). We will also refer to the \(l\) column as the "Lagrange kernel" column.

The Lagrange kernel column

Recall that the \(\mathrm{eq}\) polynomial is defined as

\[ \mathrm{eq}(x, \rho) = \prod_{k = 0}^{\mu - 1} (1 - x_k) (1 - \rho_k) + x_k \rho_k \]

for \(x \in \mathbb{F}^{\mu}\) and \(\rho \in \mathbb{F}^{\mu}\).

Then, at row \(i\), the Lagrange kernel column will store \(\mathrm{eq}(i^{\wedge}, \rho)\). For example, if \(\mu = 3\), then the column would be constructed as

The \(s\) column

The \(s\) column is defined as implementing a running sum of

\[ \sum_{x \in \{0, 1\}^{\mu}} \mathrm{eq}(x, \rho) \sum_{j = 0}^{m-1} \alpha_j f_j(x). \]

As we will see in later sections, since the Lagrange kernel column stores the expression \(\mathrm{eq}(x, \rho)\), the transition constraint for the \(s\) column will refer to \(l\).

Additionally, we need to remove \(\frac{i \cdot \sigma}{n}\) from row \(i\) to make the constraints work, as we will see in the last section.

For example, if \(\mu = 3\), then the column would be constructed as

Notice that the last row of the \(s\) column contains \(0\). Hence, by now we can see the whole picture of how \(l\) and \(s\) work together to prove \(\sigma\). The sum that defines \(\sigma\) is built row by row in \(s\), which uses the values in the Lagrange kernel column. The last row of the \(s\) column contains \(\sigma\), which will be ensured using a boundary constraint.

Next, we will look at the constraints that ensure \(l\) and \(s\) are well constructed.

The constraints

We will first define the Lagrange kernel column constraints, followed by the \(s\) column constraints.

The Lagrange kernel constraints

The Lagrange kernel constraints are unusual in that the number of transition constraints varies with the length of the trace. Also, the transition constraints rely on more rows than only the typical "current" and "next" rows. We will first the constraints, and follow up with an example that provides an intuition for why the constraints make sense.

The boundary constraints simply check that the first row is constructed correctly:

\[ l(0) = \mathrm{eq}(0^{\wedge}, \rho) \]

As for the transition constraints, for each \(\kappa \in \{1, \dots, \mu\}\),

\[ \rho_{\mu - \kappa} \cdot l(x) - (1 - \rho_{\mu - \kappa}) \cdot l(g^{2^{\mu - \kappa}}) = 0 \]

holds on the first \(2^{\kappa - 1}\) roots of unity. In other words, the transition constraint divisor is \(x^{2^{\kappa - 1}}\).

It's probably not immediately clear why these transition constraints make sense, and hence we will give an example where \(\mu = 3\) (i.e. the trace length \(n = 8\)).

Example

To ensure that \(l\) is properly built, we need the transition constraints to enforce the following 8 equations:

\[ \begin{align} l(0) &= \mathrm{eq}(0^{\wedge}, \rho) = (1-\rho_2)(1-\rho_1)(1-\rho_0) \\ l(1) &= \mathrm{eq}(1^{\wedge}, \rho) = (1-\rho_2)(1-\rho_1)\rho_0 \\ l(2) &= \mathrm{eq}(2^{\wedge}, \rho) = (1-\rho_2)\rho_1(1-\rho_0) \\ l(3) &= \mathrm{eq}(3^{\wedge}, \rho) = (1-\rho_2)\rho_1\rho_0 \\ l(4) &= \mathrm{eq}(4^{\wedge}, \rho) = \rho_2(1-\rho_1)(1-\rho_0) \\ l(5) &= \mathrm{eq}(5^{\wedge}, \rho) = \rho_2(1-\rho_1)\rho_0 \\ l(6) &= \mathrm{eq}(6^{\wedge}, \rho) = \rho_2\rho_1(1-\rho_0) \\ l(7) &= \mathrm{eq}(7^{\wedge}, \rho) = \rho_2\rho_1\rho_0 \end{align} \]

The first equation is enforced using a boundary constraint. Hence, we will then explore how the 3 transition constraints enforce these remaining 7 equations.

Notice that we can rewrite the 7 equations in terms of one another:

\[ l(1) = \frac{\rho_0}{1-\rho_0}l(0) \]

\[ l(3) = \frac{\rho_0}{1-\rho_0}l(2) \]

\[ l(5) = \frac{\rho_0}{1-\rho_0}l(4) \]

\[ l(7) = \frac{\rho_0}{1-\rho_0}l(6) \]

\[ l(2) = \frac{\rho_1}{1-\rho_1}l(0) \]

\[ l(6) = \frac{\rho_1}{1-\rho_1}l(4) \]

\[ l(4) = \frac{\rho_2}{1-\rho_2}l(0) \]

Note that there are more than one way to write these constraints; any two rows can be written in terms of one another if their index differs by 1 bit (i.e. they have a Hamming distance of 1). We chose this way specifically to serve the rest of the argument.

Recall the following key identity used in STARKs:

\[x^n - 1 = \prod_{i=0}^{n-1} (x - g^i).\]

To make a long story short, if the enforcement domain of a transition constraint is \(x^n - 1\), then the transition constraint applies to the domain points \(\{g^0, g^1, ..., g^{n-1}\}\).

Note that the use of varying length enforcement domains is the key idea that enables us to enforce the \(n\) equations using \(\log n\) transition constraints.

As a reminder the transition constraint formula is as follows (rewritten slightly for readability). For \(\kappa \in \{1, ..., \mu \}\),

\[ l(g^{2^{\mu - \kappa}} x) = \frac{\rho_{\mu - \kappa}}{1 - \rho_{\mu - \kappa}} l(x) \]

for \(x \in \{ g^0, ..., g^{2^{\kappa - 1}}\}\).

Let's build our intuition of why this works by going back to our \(\mu = 3\) example. We have 3 constraints over the following domains:

\[ \begin{align} \kappa = 1 & \rightarrow \{g^0 \}, \\ \kappa = 2 & \rightarrow \{g^0, g^4 \}, \\ \kappa = 3 & \rightarrow \{g^0, g^2, g^4, g^6 \} \\ \end{align} \]

Let's now evaluate the transition constraint formula for \(\kappa=1\), where the enforcement domain is \(\{g^0 \}\). If we plug in to the formula \(x=g^0\) and \(\kappa=1\), we get

\[ l(4) = \frac{\rho_2}{1-\rho_2} l(0) \]

Notice that this is the 7th equation defined previously!

For \(\kappa=2\), the enforcement domain is \(\{g^0, g^4 \}\). If we plug \(x=g^0\) and \(\kappa=2\) in the formula, we get

\[ l(2) = \frac{\rho_1}{1-\rho_1} l(0) \]

and with \(x=g^4\), we get

\[ l(6) = \frac{\rho_1}{1-\rho_1} l(4) \]

our 5th and 6th equations!

For \(\kappa=2\), the enforcement domain is \(\{g^0, g^2, g^4, g^6 \}\); we leave it as an exercise to show that we recover the remaining 4 equations.

The \(s\) column constraints

The \(s\) column has no boundary constraint - everything is encoded in the transition constraint. As for the transition constraint, it is unlike traditional transition constraints in that its enforcement domain is the entire \(G\). That is, we can think of the transition constraint as "wrapping around" from \(g^{n-1}\) back to \(g^0\).

The transition constraint is as follows:

\[ s(i) = s(i-1) - \frac{\sigma}{n} + \sum_{j = 0}^{m-1} \alpha_j f_j(i^{\wedge}) \]

If we look back at how the \(s\) column was built, you should verify that the constraint holds over all pairs subsequent rows. Specifically, referring back to the example \(s\) column, you should verify that

\[ s(0) = s(7) - \frac{\sigma}{n} + \sum_{j = 0}^{m-1} \alpha_j f_j(0^{\wedge}) \]

Conclusion

This article is the conclusion of the book! Hopefully, you are now better equipped to understand how to offload the proving of LogUp to GKR.

If you've spotted a mistake, or something still isn't clear, please drop a comment directly in the note, or DM me on X. I will be happy to rework parts of the book.