多变量lookup argument

1. 引言

多变量lookup相关论文有：

• Orbis Labs（Cardano的layer2 zk-rollups）团队Ulrich Hab¨ock 2022年11月论文 Multivariate lookups based on logarithmic derivatives，也可参看：https://github.com/Orbis-Tertius/MVlookups。
  • zk-VM中密集使用的multi-column，其fractional decomposition lookups性能要 优于 Hyperplonk+ 中使用的基于boolean hypercube的“classical” plookup策略。
• Zeta Function Technologies团队Ariel Gabizon 和 以太坊基金会团队 Dmitry Khovratovich 2022年11月论文 Flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size

而TritonVM（Recursively verifiable STARKs ）——TIP 0001: Contiguity Argument for Memory Consistency中试图用derivatives for lookups（使用grand product来计算derivative）来解决其memory table的一致性证明。

2. 何为batch lookups？

所谓batch lookups（又名vector column lookups），是指由多个witness columns，对应单个lookup table：

应用场景有：

• zkVM：证明多个columns为word sized（如16-bit word）。
• hasher chip，用于基于lookup的哈希函数（如Tip5）。

相关研究成果有：

• L. Eagen：Bulletproof++
• A. Gabizon, D. Khovratovich：flookup
• L. Eagen, A. Gabizon：zq

3. Permutation argument和lookup argument

3.1 Permutation argument

Permutation argument背后的核心思想为multiset equality。
所谓multiset equality，是指：【2个sequence必须具有相同的长度。】

• 若2个sequence $(w_i),(t_j)$ 为permutation关系，当且仅当：
  ${\prod }_i(X-w_i)={\prod }_j(X-t_j)$
  over $F$。

不过，该多项式计算非常昂贵。为此：

• Bayer和Groth（2012）：通过引入一个random challenge $\alpha \stackrel{\S }{\leftarrow }F$，将该多项式identity reduce为grand product：
  ${\prod }_i(\alpha -w_i)={\prod }_j(\alpha -t_j)$

3.2 Lookup argument

Lookup argument背后的核心思想为set membership。
所谓set membership，是指：【与multiset equality有所不同，2个sequence可以具有不同的长度。】

• 已知2个sequence $(w_i),(t_j)$ in $F$，则 { w i } ⊆ { t j } \{w_i\}\subseteq \{t_j\} {wi​}⊆{tj​}，当且仅当存在multiplicity整数值$(m_j)$（即$w_i$值在$(t_j)$ sequence中出现的次数），满足：
  ${\prod }_i(X-w_i)={\prod }_j(X-t_j{)}^{m_j}$

对该多项式：

• Groth等人2018年Arya论文中：
  • 将$m_j$以二进制编码方式表示为：
    $m_j={\epsilon }_{j,l}\cdot 2^l+\cdots +{\epsilon }_{j,1}\cdot 2^1+{\epsilon }_{j,0}$
  • 引入随机值$\alpha$来对多项式进行reduce为grand product。

4. Plookup（the geometric way）

Plookup的核心思想为integrability criterion，是指：

• 已知2个sequence $(w_i),(t_j)$ in $F$，则 { w i } ⊆ { t j } \{w_i\}\subseteq \{t_j\} {wi​}⊆{tj​}为sets，当且仅当存在sequence $(s_k)$（其长度为 $(w_i),(t_j)$这2个sequence的长度之和），满足：
  $\{(s_k,s_{k+1})\}=\{(t_j,t_{j+1})\}\cup \{(w_i,w_i)\}$
  为multisets。

相应的polynomial identity为：【为具有2个变量的多项式】
${\prod }_k(X+s_k+s_{k+1}\cdot Y)={\prod }_j(X+t_j+t_{j+1}\cdot Y)\cdot {\prod }_i(X+w_i+w_i\cdot Y)$

同时，也可通过引入一个random challenge $\alpha ,\beta \stackrel{\S }{\leftarrow }F$，将该多项式identity reduce为grand product。

4.1 Plookup for batches

5. logUp：原理，及其，为何快？

Logarithmic derivative（对数导数）定义为：
$D_{log}(p(X)):=\frac{p^{\prime }(X)}{p(X)}$

Logarithmic（对数）运算的一个重要特性为：

• 可将乘法运算，转换为，加法运算，即：
  $\log (p(X)\cdot q(X))=\log (p(X))+\log (q(X))$
  从而基于对数运算再求导，即 Logarithmic derivative（对数导数），也可将乘法运算，转换为，加法运算：
  $D_{log}(p(X)\cdot q(X))=D_{log}(p(X))+D_{log}(q(X))$

如：
对于$p(X)=(X-w_1)\cdot (X-w_2)$，有：
$D_{log}(p(X))=\frac{1\cdot (X-w_2)+(X-w_1)\cdot 1}{(X-w_1)\cdot (X-w_2)}=\frac{1}{X-w_1}+\frac{1}{X-w_2}$

由此可知，对polynomial identity $p(X)$，经Logarithmic derivative（对数导数）运算之后，具有如下属性：

• 将zeros（即$p(X)$中的$w_1,w_2$），变为了，$D_{log}(p(X))$ 中的poles。
• $p(X)$中对zero的multiplication，变为了，$D_{log}(p(X))$ 中对pole的multiplication，即：
  $(X-w{)}^m\to \frac{m}{X-w}$

logUp的核心思想为，对${\prod }_i(X-w_i)={\prod }_j(X-t_j{)}^{m_j}$等式两侧做对数导数运算，即Key lemma为：

• 已知2个sequence $(w_i),(t_j)$ in $F$ 且 $\text{len}((w_i))<\text{char}(F)$，则 { w i } ⊆ { t j } \{w_i\}\subseteq \{t_j\} {wi​}⊆{tj​}，当且仅当存在multiplicity整数值$(m_j)$（即$w_i$值在$(t_j)$ sequence中出现的次数），满足：
  ${\sum }_i\frac{1}{X-w_i}={\sum }_j\frac{m_j}{X-t_j}$
  为基于$F$的有理函数（rational function）。

通过引入一个random challenge $\alpha \stackrel{\S }{\leftarrow }F$，将该多项式identity reduce为rational sumcheck：
${\sum }_i\frac{1}{\alpha -w_i}={\sum }_j\frac{m_j}{\alpha -t_j}$

5.1 logUp for batches

其与Plookup的重要区别在于：

• 使用grand sum来代替了grand product，无论要查找的列有多少，grand sum的degree都为1，与table size和查找值列表size均无关。

logUp与Plookup对比为：

从而使得：

• logUp少约50%的extra columns。
• helper columns数量，可通过为每个column block提供一个helper column，来进一步reduce。即，实际是在columns数量 与 degree $D$之间做取舍。

参考资料

[1] Twitter MVlookups——基于因式分解的多变量lookup argument
[2] 2023年4月4日在Lisbon ZK Summit 9上分享视频 ZK9: logUp - Lookup arguments based on the logarithmic derivative - Ulrich Haböck