# Lookup arguments

$$\gdef\vec#1{\bm{#1}} \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\mathcal{#1}} \gdef\mset#1{\mathrm{#1}} \gdef\g{\mathrm{g}} \gdef\F{\mathbb{F}} \gdef\S{\mathcal S} \gdef\X{\mathcal X} \gdef\Z{\mathrm{Z}} \gdef\∀{\mathop{\huge ∀}\limits}$$

## Zero polynomials

Given a multiset $\mset A$ over $𝔽$ define the zero polynomial $\Z_{\mset A} ∈ 𝔽[X]$ as

$$\Z_{\mset A}(X) = \prod_{a ∈ \mset A} \p{X - a}$$

Alternatively using the base set $\set A ⊆ 𝔽$ and multiplicities $m_A: 𝔽 → ℕ$ we can collect factors

$$\Z_{\mset A}(X) = \prod_{a ∈ 𝔽} \p{X - a}^{m_A(a)}$$

To guarantee uniqueness we require $m_A(a) < p$ where $p$ is the characteristic of $𝔽$.

The logarithmic derivative of $\Z_{\mset A}$ has the curious property that all zeros turn into pole,s perserving multiplicities:

$$\frac{\Z_{\mset A}'(X)}{\Z_{\mset A}(X)} = \sum_{a ∈ \mset A} \frac{1}{X - a} = \sum_{a ∈ \set A} \frac{m_A(a)}{X - a}$$

## Aurora lemma

Let $H ⊆ 𝔽$ be a multiplicative subgroup of size $n$, then for $f ∈ 𝔽_{<n}[X]$

$$\sum_{x ∈ H} f(x) = n ⋅ f(0)$$

This follows from the non-zero elements of $H$ being $n$-th roots of unity, that sum to zero for $n>1$.

$$\sum_{x ∈ H} x^k = \begin{cases} n & k = 0 \mod \p{n - 1} \\ 0 & \text{otherwise} \end{cases}$$

## Cached Quotients

Cached quotiens (EFG22) builds on a series of prior protocols H22, ZBK+22, PAK22, GK22, ZGK+22. We want to proof that some $f ∈ \F[X]$ evaluates to values in a certain set $\S$ on a domain $\X$, i.e.

$$\∀_{x \in \X}\quad f(x) \in \S$$

In H22 it is shown that this holds if and only if there exists $m_s ∈ \F$ such that

$$\sum_{x ∈ \X} \frac{1}{X + f(x)} = \sum_{s ∈ \S} \frac{m_s}{X + s}$$

This follows from the uniqueness of the fractional decomposition and the observation that the values of $f$ on $\X$ should differ only in multiplicities form $\S$, where the multiplicity can also be zero.

This rational identity can be checked by evaluating in a random $x ∈ 𝔽$. Computing polynomial commitments to either side is not a problem as they both only have $|\set X|$ non-zero terms. The challenge is to show that the commitment to the right hand side is computed correctly.

$$A(X) ⋅ \p{T(X) + x} - m(X) = Q_A(X) ⋅ \Z_{\set Y}(X)$$

where $T(X)$ evaluates to $\set S$ on the domain $\set Y$.

### Setup

Given elliptic curve pairing $\mathrm{e}:𝔾_1 × 𝔾_2 → 𝔾_T$ with generators $\g_1 ∈ 𝔾_1, \g_2 ∈ 𝔾_2, \g_T ∈ 𝔾_T$.

• Pick secret $s ∈ 𝔽$ and compute $\p{s^0, …, s^{n-1}}⋅\g_1$ and $\p{s^0, …, s^n}⋅\g_2$
• Compute $\Z_{\set Y}(s)⋅\g_2$.
• Compute $T(x)⋅\g_2$ where $T(X) = \sum_{i ∈ [0,N)} s_i ⋅ \mathrm L_i(x)$



## Lasso lookups

For fixed sparse matrix $\mathrm M$ and committed vectors $\vec v$ and $\vec a$ show:

$$\mathrm M ⋅ \vec v = \vec a$$

## References

• H22 Ulrich Haböck (2022). Multivariate lookups based on logarithmic derivatives.
• ZBK+22 Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, Mark Simkin (2022). Caulk: Lookup Arguments in Sublinear Time.
• PAK22 Jim Posen, Assimakis A. Kattis (2022). Caulk+: Table-independent lookup arguments.
• GK22 Ariel Gabizon, Dmitry Khovratovich (2022). flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size.
• ZGK+22 Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, Carla Ràfols (2022). Baloo: Nearly Optimal Lookup Arguments.
• EFG22 Liam Eagen, Dario Fiore, Ariel Gabizon (2022). cq: Cached quotients for fast lookups.
• FK23 Dankrad Feist, Dmitry Khovratovich (2023). Fast amortized KZG proofs.
• ABTD23 Alexandr Bulkin, Tim Dokchitser (2023). Plonkup scheme with multiple queries.
• STW23 Srinath Setty, Justin Thaler, Riad Wabby (2023). Unlocking the lookup singularity with Lasso.
• CFF+23 Matteo Campanelli , Antonio Faonio , Dario Fiore , Tianyu Li , Helger Lipmaa (2023). Lookup Arguments: Improvements, Extensions and Applications to Zero-Knowledge Decision Trees.
• PH23 Shahar Papini, Ulrich Haböck (2023). Improving logarithmic derivative lookups using GKR.

Remco Bloemen
Math & Engineering
https://2π.com