# Table lookups *powdr seminar* --- ## Building blocks **Vectors** (= columns): Ordered list of field elements, e.g.: $A = (a_1, ..., a_n)$ Two primitives: - **Zero-Check**: All entries of the vector are 0 - Example: `C = A * B` &rarr; The vector $C - A \circ B$ is zero everywhere - **Sum-Check**: Prove that $\sum_i a_i = v$ for some $v$ These checks exist both in the *univariate* and *multivariate* setting! ---- ## Building blocks A vector $A = (a_1, ..., a_n)$ can be encoded as a **polynomial**, for example: - **Univariate** polynomial: $\forall i \in [1, n]: p_A(\omega^i) = a_i$ - $\omega$ is a field element such that $\omega^{n + 1} = \omega$ - **Multilinear** polynomial: $\forall b_1, ..., b_{\log n} \in \{0, 1\}^{\log n}: p_A(b_1, ..., b_{\log n}) = a_i$ where $i = \sum_j 2^j \cdot b_j$ The sets $\{\omega_i\}_{i \in [1, n]}$ and $\{0, 1\}^{\log n}$ are called the **evaluation domain** and denoted $H$. ---- ## Building blocks A **polynomial commitment scheme** allows the prover to commit to a polynomial in a way that it can later prove that $p(x_1, ..., x_k) = v$ for values $x_1, ..., x_k$ chosen by the verifier. **Schwartz-Zippel Lemma**: If two polynomials of bounded degree agree on a random point, they are likely equal. --- ## Warmup: Permutation argument via product check - Assume we have two vectors $A = (a_1, ..., a_n)$ and $B = (b_1, ..., b_n)$ and want to show that $A$ is a permutation of $B$ - **Observation**: This is the case iff. polynomials $p_A$ and $p_B$ are equal where: - $p_A(X) := \prod_{i = 1}^n (X - a_i)$ - $p_B(X) := \prod_{i = 1}^n(X - b_i)$ - &rarr; Check that $p_A(\beta) / p_B(\beta) = 1$ for a random challenge $\beta$ ---- ## Warmup: Permutation argument via product check This can be done by adding a new witness column $Z = (z_0, ..., z_n)$ such that: $$ z_0 = z_n = 1 $$ and $$ z_{i + 1} = z_i \cdot \frac{(\beta - a_i) }{(\beta - b_i)} \iff z_{i + 1} \cdot (\beta - b_i) = z_i \cdot (\beta - a_i) $$ &rarr; Possible to express in PIL with challenge API! ---- ### Example: | A | B | Z | |---|---|--------------------------------------------------| | 1 | 4 | $z_0 = z_4 = 1 = z_3 \cdot\frac{\beta - 3}{\beta - 1}$ | | 2 | 3 | $z_1 = z_0 \cdot\frac{\beta - 1}{\beta - 4}$ | | 4 | 2 | $z_2 = z_1 \cdot\frac{\beta - 2}{\beta - 3}$ | | 3 | 1 | $z_3 = z_2 \cdot\frac{\beta - 4}{\beta - 2}$ | --- ## Halo2 lookup argument (similar to Plookup) To show that $A \subseteq B$, we let the prover compute columns $X$ and $Y$ such that: - $X$ is a permutation of $A$ - $Y$ is a permutation of $B$ - In each row: - $X_{i + 1} = X_i$, OR - $X_{i + 1} = Y_{i + 1}$ ---- ### Example: | A | B | X | Y | | ---- | ---- | ---- | ---- | | 4 | 4 | **1** | **1** | | 1 | 3 | 1 | 2 | | 1 | 2 | **4** | **4** | | 4 | 1 | 4 | 3 | --- ## Lookup argument via product check We can adopt this technique to show $A \subseteq B$ by showing that: $$ \prod_{i = 1}^n (X - a_i) = \prod_{i = 1}^n(X - b_i)^{m_i} $$ where $m_i$ is the *multiplicity*, i.e., the number of times $b_i$ occurrs in $A$. **Problem:** Computing the exponentiation requires a bit-decomposition of $m_i$ --- ## Logarithmic Derivative $$ \prod_{i = 1}^n (X - a_i) = \prod_{i = 1}^n(X - b_i)^{m_i} $$ Apply $\log()$ on both sides: $$ \sum_{i = 1}^n \log(X - a_i) = \sum_{i = 1}^n m_i \cdot \log(X - b_i) $$ Take the derivative: $$ \sum_{i = 1}^n \frac{1}{X - a_i} = \sum_{i = 1}^n \frac{m_i}{X - b_i} $$ &rarr; Turns a product of polynomials into a sum of fractions! --- ## LogUp - Commit to vectors $A, B$ and the multiplicities $M$ - Commit to a *helper* vector $H$ with $h_i := \frac{1}{\beta - a_i} - \frac{m_i}{\beta - b_i}$ - Prove that $H$ is formed correctly (via a polynomial identity) - $\forall i: h_i \cdot (\beta - a_i) \cdot (\beta - b_i) = (\beta - b_i) + m_i \cdot (\beta - a_i)$ - Run a *sum-check* to prove that $\sum_{i = 1}^n h_i = 0$ - Batching multiple lookups with the same right-hand side is efficient, but might require more helper vectors to keep the degree of the identity low ---- ## LogUp + GKR - **Idea**: Instead of having to commit to the helper vector $H$, compute the fractional sum directly using GKR! - Fractions are represented as tuples $(num, den)$ and updated as: $\frac{num_1}{den_1} + \frac{num_2}{den_2} = \frac{num_1 \cdot den_2 + num_2 \cdot den_1}{den_1 \cdot den_2}$ - &rarr; computing a sum of size $n$ can be implemented in a *layered* arithmetic circuit of depth $O(\log n)$ ---- ## cq (= "Cached Quotients") Main achivement: Look up $n$ elements into a table of size $N$ in $O(n \log n)$ time (requiring $O(N \log N)$ preprocessing time) - Instantiation of LogUp in the *univariate* (instead of *multivariate*) setting using KZG commitments - Multivariate sum-check &rarr; univariate sum-check - Multivariate zero-check &rarr; univariate zero-check - They use use one helper polynomial for each column ($h_A$ and $h_B$) **where the degree of $h_A$ is smaller than the degree of $h_B$** - But $h_B$ is *sparse*, so its commitment can be computed in size $O(n)$ by adding pre-computed (homomorphic) commitments to Lagrange polynomials - Also, the quotient polynomial required for the zero-check is sparse, but in a different basis that can be pre-computed! --- ## Sources - Relevant pages of: [georgwiese.github.io/crypto-summaries](https://georgwiese.github.io/crypto-summaries) - [Permutation Check via Product Check](https://georgwiese.github.io/crypto-summaries/Concepts/Protocols/Permutation-Check-via-Product-Check) - [Halo2 Lookup Argument](https://georgwiese.github.io/crypto-summaries/Concepts/Protocols/Lookup-Arguments/Halo2-Lookup-Argument) - [LogUp & cq](https://georgwiese.github.io/crypto-summaries/Concepts/Protocols/Lookup-Arguments/LogUp--and--cq) <style> .reveal { font-size: 30px; } </style>