LogUp GKR

Code: crates/hypercube/src/logup_gkr/verifier.rs

There are two forms of constraints that we check on the committed tables. The first type is known as "AIRs" (Arithmetic Intermediate Representation) and enables specifying uniform constraints on rows of each table. The second type of constraint is known as "interactions" and connects between columns of different tables.

More generally, an interaction between table $i$ and table $j$ is specified by several linear combinations of columns of table $i$ and some corresponding linear combinations of columns of table $j$. The claim is that the linear combination results are permutations of one another.

Thus, we construct three virtual multilinear polynomials $a$, $t$ and $m$. The two former polynomials are obtained by taking a random linear combinations of the linear combinations involved in the interactions and the third multilinear specifies a desired multiplicity.

Thus, the claim we need to verify is that for every $\vec{x} \in \{0,1\}^h$ the item $t(\vec{x})$ appears exactly $m(\vec{x})$ times in $a(\vec{x})$.

We do so using the LogUp GKR protocol. Thus, the verifier chooses a random $\rho \in \mathbb{F}$. The claim reduces to checking that $\sum_{\vec{x}} \frac{m(\vec{x})}{\rho-t(\vec{x})} = \sum_{\vec{x}} \frac{1}{\rho-a(\vec{x})}$.

The Logup GKR protocol enables one to verify $\sum_x \frac{p(\vec{x})}{q(\vec{x})}$ for two given multilinears $p$ and $q$. It does so by defining $p_h \equiv p$ and $q_h \equiv q$ and inductively defining intermediate polynomials (which are not committed to):

$$p_k(\vec{x}) = p_{k+1}(\vec{x} || 0) \cdot q_{k+1}(\vec{x} || 1) + p_{k+1}(\vec{x} || 1) q_{k+1}(\vec{x} || 0)$$ $$q_k(\vec{x}) = q_{k+1}(\vec{x} || 0) \cdot q_{k+1}(\vec{x} || 1)$$

so that

$$\frac{p_k(\vec{x})}{q_k(\vec{x})} =\frac{p_{k+1}(\vec{x} || 0)}{q_{k+1}(\vec{x} || 0)} + \frac{p_{k+1}(\vec{x} || 1)}{q_{k+1}(\vec{x} || 1)}$$

Each of these polynomials is a multilinear extension of the data defined above.

The starting evaluation claim can be decomposed (by the prover) into claims on $p_1(0), p_1(1), q_1(0), q_1(1)$. Following the GKR protocol, we now reduce each claim about each $p_{k+1},q_{k+1}$ into two claims about $p_k,q_k$. The two claims are then recombined using the "two-to-one trick". We also use Fiat-Shamir randomness to combine the two sumchecks underlying the above transitions.

This process eventually ends with multilinear evaluations claims on the polynomials $p_h$ and $q_h$. These claims are then decomposed by the prover into claims about the columns involved in the interaction's linear combinations.