Multiset Equality Based Lookup

最近正值国庆假期，也没有其他安排，正好前一段时间有一个有关lookup的idea，看了一些lookup的论文，但是做完之后又觉得太无聊了。目前能想到的唯一（a）有趣的（b）在假期期间能做的事情就是把所有的lookup整理一下，

于是，我打算写一个系列的blog，把所有的lookup整理一下，主要包括以下主题：

• Multiset Equlity Based： Plookup、Halo2、Offline Memory Checking(e.g. Lasso、shout&twist)
• Log-devariate Based：logup、cq、cq+、cq++、$\mu$-seek、GKR-logup、protostar(folding)
• Matrix-vector multiplication Based：Baloo、Lasso、FLI(folding)
• others：Caulk、Caulk+、Flookup

因为打算只讲解一些intuition，并不会涉及太多细节，所以这次就不用我的“私藏”template来整理了，直接用markdown来写。
（博客仅代表个人理解，由于学识浅薄，能力有限，难免会有一些错误，欢迎大家批评指正，邮箱：lizhengwang1124@gmail.com）

Plookup

Plookup是大概是最早的Lookup协议，由Ariel Gabizon大佬提出。其主要的思想很简单，假设我们有两个向量$\mathbf{f}\in \mathbb{F}^n$和$\mathbf{t}\in \mathbb{F}^N$，想要判断是否$\mathbf{f}$中的每一个元素都来自于$\mathbf{t}$，我们将$\mathbf{f}$和$\mathbf{t}$拼接到一起，并根据$\mathbf{t}$中元素的顺序，重新排列，得到一个新的向量$\mathbf{s}$。

我们可以想到，在$\mathbf{s}$中的相邻元素有两种情况：

• 相邻元素不相等，即$s_i\neq s_{i+1}$，我们可以理解为该元素来自于$\mathbf{t}$。因为$\mathbf{t}$中的元素不重复，而$\mathbf{f}$中的元素来自于$\mathbf{t}$，所以只有$\mathbf{t}$能够引入“阶跃”。
• 相邻元素相等，即$s_i=s_{i+1}$，我们可以理解为该元素来自于$\mathbf{f}$。因为$\mathbf{f}$中的元素都存在于$\mathbf{t}$中，所以$\mathbf{f}$中每有一个元素，就会引入一次$s_i=s_{i+1}$。分两种情况：
  1. multiplicity
     $=$ 1，$f_j$与$t_{j^\prime}$组成一对；
  2. multiplicity $\ge$ 1，$f_j$与$f_{j^\prime}$组成一对；

则可以建立一个bi-variate polynomial：

$$\begin{gathered}F(X, Y):=(1+X)^n \cdot \prod_{i \in[n]}\left(Y+f_i\right) \prod_{i \in[d-1]}\left(Y(1+X)+t_i+X t_{i+1}\right) \\ G(X, Y):=\prod_{i \in[n+d-1]}\left(Y(1+X)+s_i+X s_{i+1}\right)\end{gathered}$$

通过判断$F\equiv G$，可以完成lookup argument。具体实现要靠grand product protocol，我个人不太喜欢这个protocol，太复杂了，看起来就不好算，其实是没有深入了解过如何优化（bushi）。

Protocol

Input: $f(X)\in \mathbb{F}_{<n}[X]$，$|\mathbb{H}| =n+1$

不失一般性的，我们假设$N=n+1$，可以通过引入dummy value来实现，原论文这么做可能只是想让grand product协议看起来简单一点。

Prover: 计算$h_1(g^i) = s_i$，$h_2(g_i) = s_{n+i}$，$i\in [n+1]$

Verifier: 随机选取两个域元素$\alpha, \gamma\in \mathbb{F}$

Prover: 计算多项式$Z(X)$并发送给Verifier，满足以下条件：

1. Z(g) = 1
2. For $2\leq i \leq n$, $Z(g^i) = \dfrac{(1+\alpha)^{i-1}\prod_{j<i}(\gamma + f(g^j))\prod_{j<i}(\gamma(1+\alpha)+t(g^i)+\alpha t(g^{i+1}))}{\prod_{j<i}(\gamma(1+\alpha)+h_1(g^i)+\alpha h_1(g^{i+1}))(\gamma(1+\alpha)+h_2(g^i)+\alpha h_2(g^{i+1}))}$
3. $Z(g^{n+1}) = 1$

Verifier :验证如下等式:

1. $L_1(\mathbf{x})(Z(\mathbf{x})-1)=0$

2. $$\begin{gathered} \left(\mathbf{x}-\mathbf{g}^{n+1}\right) Z(\mathbf{x})(1+\beta) \cdot(\gamma+f(\mathbf{x}))(\gamma(1+\beta)+t(\mathbf{x})+\beta t(\mathbf{g} \cdot \mathbf{x})) \\ =\left(\mathbf{x}-\mathbf{g}^{n+1}\right) Z(\mathbf{g} \cdot \mathbf{x})\left(\gamma(1+\beta)+h_1(\mathbf{x})+\beta h_1(\mathbf{g} \cdot \mathbf{x})\right)\left(\gamma(1+\beta)+h_2(\mathbf{x})+\beta h_2(\mathbf{g} \cdot \mathbf{x})\right) \end{gathered}$$
3. $L_{n+1}(\mathbf{x})\left(h_1(\mathbf{x})-h_2(\mathbf{g} \cdot \mathbf{x})\right)=0$
4. $L_{n+1}(\mathbf{x})(Z(\mathbf{x})-1)=0$

效率

我们来分析一下开销：

Prover：需要对向量进行排序，最少$O(n\log n)$；commit两个n+1长度的多项式$h_1,h_2$；计算累乘$Z_i$是线性的；还有涉及到FFT。因此至少是$O(n\log n)$的开销

Verifier：验证5个多项式的opening proof，然后自行验证4个等式

Halo2 Lookup

Halo2 的 lookup 机制并不直接借助 Plookup 那种 multiset 重排 + grand product 的方式，而是用一种 “subset argument” 的视角：把 A 和 S 各自看成一个 multiset（带重复），然后让 Prover 提供 两个 permutation 列 A′、S′，后面把 A′、S′ 排成特定顺序，使得所有 A′ 的元素与某个 S′ 匹配或者重复于自己上一行，从而间接说明 A ⊆ S。

核心思想

首先，为了讲清楚，我们暂时忽略零知识填充行，把查表看作在完整的 2ᵏ 行上进行。

设电路有两列：

• 原始的列 A(X)
• 查表列 S(X)

Prover 还额外提供两列 A′(X) 和 S′(X)。A′ 是 A 的一个排列（permute），S′ 是 S 的一个排列（permute）。我们用一个 permutation product 列 Z(X) 来“连接”这些排列，使得 A, A′ 保持排列关系，S, S′ 也同样，并让 A′ 与 S′ 之间建立 subset 关系。

具体约束如下：

1. 排列一致性 / product 约束

   $$Z(ωX) \cdot (A^\prime(X) + β)\cdot(S^\prime(X) + γ) \;-\; Z(X)\cdot (A(X) + β)\cdot (S(X) + γ) \;=\; 0$$

   同时再加一条：

   $$ℓ_0(X)\cdot (1 - Z(X)) = 0$$

   这个结构类似经典 permutation argument：它强制 Z 在逐行积累 “(A′+β)(S′+γ)/(A+β)(S+γ)” 的比率，从而实现 A′ 是 A 的一个排列、S′ 是 S 的一个排列（β, γ 是避免交叉干扰的随机挑战）。

2. subset 关系约束
   在排列之后，A′ 列会将相同值聚在一起（即排序后使重复值连续）。然后我们要保证：对于每一行 i，要么 $A^\prime_i = S^\prime_i$，要么$ A^\prime_i = A^\prime_{i-1}$。这就保证每个 A′ 要么直接匹配 S′，要么继承自己前一行（表示重复值被“附属”）。
   对应在多项式形式中，我们写：

   $$(A^\prime(X) - S^\prime(X)) \cdot (A^\prime(X) - A^\prime(ω^{-1}X)) = 0$$

   再加一条确保首行匹配：

   $$ℓ_0(X)\cdot (A^\prime(X) - S^\prime(X)) = 0$$

这两套约束合起来，就可以论证出：每个 A 的元素都落在 S 集合中。

为什么呢？用行的归纳思想：

• 第一行强制 $A^\prime_0 = S^\prime_0$。
• 若到某行 i，若 $A^\prime_i \neq S^\prime_i$，则必然有 $A^\prime_i = A^\prime_{i-1}$，那就表示它“继承”上一行的值；递归向上要么最终追溯到那个被 matched 的那一行。
• 同时因为 A′ 是 A 的排列，S′ 是 S 的排列，那么这种匹配或继承实际上就说明 A 中的每个值都能在 S 中“找到根源”。

零知识

在真实电路中，为了实现零知识保护，通常会在最后插入几行随机填充行（blinding rows），这些行不能按照上面那套约束强行算。Halo2 在文档里用以下 technique 做调整：

• 设完整行数为 $2^k$，把最后的 $t$ 行用于随机填充（blind rows），剩下 $u = 2^k - t - 1$ 行作为 usable rows（可参与约束的部分）。
• 引入两个 selector 多项式：
  • $ q_{\text{blind}}(X) $ 在最后 t 行取 1，其余取 0
  • $ q_{\text{last}}(X) $ 在可用区最后一行（第 u 行）取 1，其余取 0

然后将之前的两个主要约束加上掩码使其仅在 usable rows 生效：

$$(1 - (q_{\text{last}}(X) + q_{\text{blind}}(X))) \cdot \left[ Z(ωX)\,(A^\prime + β)(S^\prime + γ) - Z(X)\,(A + β)(S + γ) \right] = 0$$ $$(1 - (q_{\text{last}}(X) + q_{\text{blind}}(X))) \cdot (A^\prime - S^\prime)(A^\prime - A^\prime(ω^{-1}X)) = 0$$

原本在第 0 行的约束仍保持不变：

$$\ell_0(X)\cdot (A^\prime(X) - S^\prime(X)) = 0,\quad \ell_0(X)\cdot (1 - Z(X)) = 0$$

对于 wrap-around（即 Z 最后一行要回 1）的约束，现在不能简单地写 $Z(ω^u) = 1$，因为扔进了 blind rows 后 wrap-around 性质被破坏。Halo2 的 trick 是：对于那条 wrap-around 的约束，我们允许 $Z$ 在那一行变成 0 或 1，而不是必须为 1：

$$q_{\text{last}}(X)\cdot (Z(X)^2 - Z(X)) = 0$$

换句话说，在那一行（q_last 行），Z 的值要么 0 要么 1。这样即便在某些行出现除零风险（$A_i + β = 0$ 或 $S_i + γ = 0$）的情况，也能让 Z 从那一行起归零、继续维持约束一致性，而不影响 soundness

Offline Memory Checking