LogUp & cq

Sources:

Background: Lookup argument via product check

Analogously to the the Permutation Check via Product Check, for multi-set $A$ and set $B$ , we have $A \subseteq B$ if there exist values ${m_{b} ∣ b \in B}$ such that the following two polynomials are equal:

p_{A} (X) := a \in A \prod (X - a)

p_{B} (X) := b \in B \prod (X - b)^{m_{b}}

The values ${m_{b} ∣ b \in B}$ are the multiplicities, i.e., $m_{b}$ denotes the number of times $b$ appears in $A$ .

The problem with this approach is that computing the exponentiation requires a bit-decomposition of $m_{b}$ , which adds logarithmic overhead.

Logarithmic Derivative

Applying the logarithm to and the taking the derivative of $p_{A}$ and $p_{B}$ , we can transform the product check into a sum check over fractions:

a \in A \sum \frac{1}{X - a} = ? b \in B \sum \frac{m _{b}}{X - b}

LogUp based on fractional sum check

(Multivariate lookups based on logarithmic derivatives)

The paper describes the protocol in the multivariate setting, but this can be adopted to the univariate setting by using the Univariate Sum-Check Protocol and Univariate Zero-Check Protocol instead of the multivariate variants.

Example: Looking up one column, no batching

Let $f_{A}, f_{B}, m : F^{n} \to F$ be the two multilinear polynomials that map each element of the boolean hypercube $H$ to an element in $A$ , $B$ , and the multiplicity respectively.

To show that the equality above holds, the verifier first samples a random $x \in F$ . Then, the prover needs to show that:

x \in H \sum \frac{1}{x - f _{A} ( x )} - \frac{m ( x )}{x - f _{B} ( x )}

The problem is that the expression we’re summing over is not a polynomial, so the sum-check protocol is not directly applicable!

To get around this, prover interpolates and commits to a polynomial $h$ such that:

\forall x \in H : h (x) = \frac{1}{x - f _{A} ( x )} - \frac{m ( x )}{x - f _{B} ( x )}

or, equivalently:

\forall x \in H : h (x) \cdot (x - f_{A} (x)) \cdot (x - f_{B} (x)) - (x - f_{B} (x)) + m (x) \cdot (x - f_{A} (x) = 0

So, we:

Apply the Multivariate Sum-Check Protocol to show that $\sum_{x \in H} h (x) = 0$
Apply the Multivariate Zero Check Protocol to prove the identity above

The two protocols can be run in one go, as a single sum-check applied to:

h (x) + e q (z, x) \cdot (h (x) \cdot (x - f_{A} (x)) \cdot (x - f_{B} (x)) - (x - f_{B} (x)) + m (x) \cdot (x - f_{A} (x))

where $z$ is a verifier challenge and $e q$ is the unique multilinear extension of the equality function on the Boolean hypercube.

Batching

In principle, this technique can be generalized to looking up many columns, by defining $h$ such that:

\forall x \in H : h (x) = (i \sum \frac{1}{x - f _{A_{i}} ( x )}) - \frac{m ( x )}{x - f _{B} ( x )}

The problem with this is that the degree of the zero-check expression grows linearly with each column. The paper describes a way to split $h$ into $h_{1}, ..., h_{K}$ such that $h = \sum_{i} h_{i}$ . This decreases the degree, but requires the prover to commit to more polynomials. The ideal value for $K$ depends on the polynomial commitment scheme being used.

Fractional sum-check via GKR

(Improving logarithmic derivative lookups using GKR)

With this approach, we get rid of the need to commit to the “helper polynomials” $h_{i}$ .

Let $f, m : F^{n} \to F$ be the concatenations of the table values and multiplicities ( $- 1$ for each column on the LHS of the lookup, otherwise the combined multiplicity). We essentially want to show that:

x \in H \sum \frac{m ( x )}{f ( x )} = 0

Adding to rational numbers $\frac{a _{0}}{b _{0}}$ and $\frac{a _{1}}{b _{1}}$ can be achieved by mapping $(a_{0}, b_{0})$ and $(a_{1}, b_{1})$ to $(a_{0} \cdot b_{1} + a_{1} \cdot b_{0}, b_{0} \cdot b_{1})$ . So, we can compute the sum as a layered arithmetic circuit of depth $O (lo g n)$ by explicitly keeping track of the numerators and denominators and summing them up pair-wise in each layer!

The execution of the circuit can then be proven using the GKR protocol.

cq (cached quotients)

cq is essentially an instantiation of LogUp (in its original variant) in the univariate setting, using KZG commitments.

The main achievement is that the prover time is independent of the table size: We can prove a subset relation for a multi-set of size $n$ into a table of size $N$ in time $O (n lo g n)$ (and pre-processing time $O (N lo g N)$ ).

In a nutshell:

The prover commits to polynomials $f_{A}$ , $f_{B}$ , and $m$
The verifier sends a random challenge $β$
Now, the prover computes and commits to $h_{A}$ and $h_{B}$ such that:
- $\forall x \in H : h_{A} (x) \cdot (f_{A} (x) + β) - 1 = 0$
- $\forall x \in H : h_{B} (x) \cdot (f_{B} (x) + β) - m (x) = 0$
- $\sum_{x \in H} h_{A} (x) = \sum_{x \in H} h_{B} (x)$

Note that:

The degree of $f_{A}$ and $h_{A}$ is $n$ ; the degree of $f_{B}$ and $h_{B}$ is $N$
However, because $f_{B}$ is $n$ -sparse, its commitment can be computed in $O (n)$ time, by adding pre-computed commitments to the Lagrange polynomials
The main issue is that the Univariate Zero-Check Protocol requires computing a commitment to an $N$ -degree quotient polynomial $q$ such that $h_{B} (X) \cdot (f_{B} (X) + β) - m (X) = q (X) \cdot Z_{H} (X)$

The key insight is that the quotient $q$ is also $n$ -sparse (but in a different basis) and can be computed in $O (n)$ time!

First, note that the $q$ we’re computing is the same quotient that we get from dividing $h_{B} (X) \cdot f_{B} (X)$ by $Z_{H} (X)$ with remainder:

h_{B} (X) \cdot f_{B} (X) = q (X) \cdot Z_{H} (X) + r (X)

(where it happens that $r (X) = m (X) - β \cdot h_{B} (X)$ )

Second, because $h_{B}$ is just a linear combination of Lagrange polynomials, we can write $q$ as the same linear combination of polynomials $q_{i}$ where:

L_{i} (X) \cdot f_{B} (X) = q_{i} (X) \cdot Z_{H} (X) + r_{i} (X)

Note that the quotients $q_{i}$ are independent of $A$ ! Therefore, we can pre-compute their commitments once and use them to compute the commitment to $q$ in $O (n)$ time.

Crypto Summaries

Explorer