Lookup arguments

(updated )

$$ \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} $$

FK lemma

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$.

$$

$$

logUp

Lasso lookups

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

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

References

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