Notes: logUp-lookup

logUp

TL;DR

Idea is to convert the linear product into fractional sums of reciprocals using logarithmic derivatives.

Logarithmic derivative is a popular method to differentiate functions which have high multiplicities as logarithms turn that into summations.

${\Pi }_{i=0}^n(X-z_i)$ is ${\sum }_{i=0}^n\frac{1}{X-z_i}$

Identity underlying logarithm based lookup arguments is: Assuming set $A=\left\{a_0,a_1,\dots ,a_N\right\}$ and table $t=\left\{t_0,t_1,\dots ,t_M\right\}$ such that $N\le M$, then if $A\subseteq t$, then there must exist a sequence $m=\left\{m_0,m_1,\dots ,m_M\right\}$ such that following relation holds: ${\sum }_{i=0}^N\frac{1}{X-a_i}={\sum }_{j=0}^M\frac{m_j}{X-t_j}$

TODO: sketch proof of above relation

logUp focuses for lookups in multivariate setting where multiple columns are required to be looked upon from same table.

why are logarithmic derivatives useful here? Can a cheating prover create a false relation where it shows existence of a vector $A^{\prime }=\left\{a_0^{\prime },a_1^{\prime },\dots ,a_N^{\prime }\right\}$ which doesn't exist in the table $t$?

To do this, prover needs to choose $m_i$‘s and create a linear combination of $\sum \frac{m_i}{X-a_i}$ such that it can create a summand $\frac{1}{X-s}$, where $s\notin t$. But, set of all element $\frac{1}{X-b}$ such that $b\in \mathbb{F}$ are linearly independent, so no combination of elements in LHS can ever give an element which is not in the table.

Another thing that prover can do to cheat is choose $m_i$‘s such that terms cancel each other, then it can cheat with extra elements.

Let’s see how logUp prevents this:

• $\mathcal{P}\to \mathcal{V}$ commits to $m$
• \beta \xleftarrow{\}\mathcal{V}$andsendsto$\mathcal{P}$
• Uses Aurora lemma to prove a sub-relation:

Previous Research

• Lookups popularised by Plookup
• Logarithmic derivatives first used in Bulletproofs++ paper
• Large table lookups introduced by Caulk, Caulk+
• Cached Quotients used logarithmic derivatives based lookups for large-table lookup protocols

Preliminaries

Lagrange Kernel of Boolean Hypercube

Boolean Hypercube: $H={\left\{\pm 1\right\}}^n$ as multiplicative subgroup of ${\left\{{\mathbb{F}}^{\ast }\right\}}^n$, Lagrange polynomial for a multivariate function $f(\vec{X})$ is written as: $L_H(\vec{X},\vec{Y})=\frac{1}{2^n}\cdot {\prod }_{j=1}^n(1+X_j\cdot Y_j)$

• Lemma 1 (Boolean Hypercube): For function $f$, $⟨f,L_H(\cdot ,y){⟩}_H:={\sum }_{\vec{x}\in H}f(\vec{x})\cdot L_H(\vec{x},\vec{y})=f(\vec{y})$
• Lemma 2 (Formal Derivative): for a polynomial $p(X)\in \mathbb{F}[X]$ where characteristic of field $\mathbb{F}$ is $p$, if $p^{\prime }(X)=0$, then $p(X)=g(X^p)$. Thus, if $\mathrm{deg}p(X)<p$ and $p^{\prime }(X)=0$, then $p(X)$ must be a constant.
  • Let $\frac{p(X)}{g(X)}$ be a rational function for polynomial $p(X),g(X)\in \mathbb{F}[X]$, where $\mathrm{deg}p(X)<p,\mathrm{deg}g(X)<p$. If $(\frac{p(X)}{g(X)}{)}^{\prime }=0$, then $\frac{p(X)}{g(X)}$ must be a constant.
• Lemma 3 (Logarithmic derivative): if $(a_i{)}_{i=1}^N$,$(b_i{)}_{i=1}^N$ are sequences over field $F$, then ${\prod }_{i=1}^N(X+a_i)={\prod }_{i=1}^N(X+b_i)⟺{\sum }_{i=0}^N\frac{1}{X-a_i}={\sum }_{i=i}^N\frac{m_i}{X-t_i}$.
• Lemma 4: let $m_1,m_2$ be functions $\mathbb{F}\to \mathbb{F}$, then ${\sum }_{z\in \mathbb{F}}\frac{m_1}{X-z}={\sum }_{z\in \mathbb{F}}\frac{m_2}{X-z}⟺m_1=m_2\forall z\in \mathbb{F}$
• Lemma 5 (Set inclusion): Let $(a_i{)}_{i=1}^N,(b_i{)}_{i=1}^N$ be two sequences of elements in field $\mathbb{F}$, then $a\subseteq b$ iff there exists a sequence $(m_i{)}_{i=1}^N$ such that ${\sum }_{i=1}^N\frac{1}{X+a_i}={\sum }_{i=1}^N\frac{m_i}{X+b_i}$.

Sumcheck protocol

Technical Deep dive (magic)

Let $f_1,\dots ,f_M$ and $t:H\to \mathbb{F}$ be functions over $H$, then ${\cup }_{i=1}^M{\left\{f_i(\vec{x})\right\}}_{\vec{x}\in H}\subseteq {\left\{t(\vec{x})\right\}}_{\vec{x}\in H}$ iff there exists a function $m:H\to \mathbb{F}$ such that: ${\sum }_{\vec{x}\in H}{\sum }_{i=1}^M\frac{1}{X+f_i(\vec{x})}={\sum }_{i=1}^M\frac{m(\vec{x})}{X+t(\vec{x})}$

• Prover commits to $m$.
• Verifier sends a random value $x\in \mathbb{F}$. Mostly, this value doesn’t lie in $H$.
• turns above relation into an identity by shifting RHS, and equaling to 0.
• To turns this into a polynomial, $P$ divides the relation into partial sums of roughly the same number of terms $l$.
• combines using random scalars from verifier
• prove 2 relations in a single polynomial using sumcheck

Protocol

Let $l$ be the chosen number, then $K=\lceil \frac{M+1}{l}\rceil$ subintervals $I_K=[(k-1)\cdot l,k\cdot l]\in [0,M]$ is formed.

$h_k={\sum }_{i\in I_K}\frac{m_i(\vec{x})}{{\phi }_i(\vec{x})},k=1,\dots ,K$

Above relation represents $\frac{m(x)}{x+t(x)}-\frac{1}{x+f_1(\vec{x})}-\frac{1}{x+f_2(\vec{x})}-\cdots -\frac{1}{x+f_M(\vec{x})}$. Thus, $m_0=m(x)$, and for $i>1,m_i(x)=-1$. Similarly for ${\phi }_0(x)=x+t(x)$, and for $i>1,{\phi }_i(x)=x+f_i(\vec{x})$.

This gets reduced to 2 expression combined using random scalars ${\lambda }_i$ by verifier:

• ${\sum }_{i=1}^K{h}_i(\vec{x})=0$ at $H$
• $\forall k\in [1,K],h_k(\vec{x}){\prod }_{i\in I_k}\phi (\vec{x})={\sum }_{i\in I_k}{m}_i(\vec{x}){\prod }_{j\in I_k\setminus \{i\}}{\phi }_i(\vec{x})$

Cost

Soundness/ZK Proofs

References

• notes on logup