1 引言

Lookup Argument 是一种重要的密码学原语，用于证明一个集合（或结构化对象，如多项式）的元素属于另一个预先计算的集合或结构。它在零知识证明系统中具有重要作用，可以在不泄露敏感信息的前提下强制验证数据的一致性和约束。

在zkVM应用背景下，Lookup Argument 被用于高效验证输入与预计算表之间的包含关系。这在以下场景中尤为重要：

• 基于电路的证明：确保输入值满足特定约束，例如在算术电路中。
• 范围证明：验证一个值是否落在特定范围内。
• 预计算表：证明私有输入属于预先批准的数据，例如查找表。

2 预备知识

2.1 Schwartz–Zippel 引理

令 $P$ 为有限域 $\mathbb{F}$ 上的 $n$ 元多项式 $P = F(x_1, ..., x_n)$，其阶为 $d$。令 $S$ 为有限域 $\mathbb{F}$ 的子集，从 $S$ 中选择随机数 $r_1, ..., r_n$，则多项式等于零的概率可忽略，即 $$ \Pr[P(r_1, ..., r_n) = 0] \leq \frac{d}{|S|} $$ 在单变量情况下，一元多项式的阶为 $d$，则最多有 $d$ 个根。

2.2 乘积一致性检测原理

给定有限域 $\mathbb{F}$ 上的多项式 $\mathbb{F}$ 的系数 $a_1, ..., a_n$ 与多项式 $g$ 的系数 $b_1, ..., b_n$，以及一个子集 $H = {x_1, ..., x_n} \subset \mathbb{F}$。

1. 如果两个集合 ${a_i}, i = 1, ..., n$ 和 ${b_i}, i = 1, ..., n$ 中的元素对应相等 $a_i = bi, i \in [n]$，则乘积值相等： $$ \prod{i \in [n]} ai = \prod{i \in [n]} b_i $$

2. 反之，如果 $\prod_{i \in [n]} ai = \prod{i \in [n]} b_i$，则根据 Schwartz–Zippel 引理，能够构造多项式： $$ P(X_1, ..., Xn) := \prod{i \in [n]} (X_i - a_i) = 0 $$ 在子集 $H$ 上随机选择 $(b_1, ..., b_n)$，使得多项式 $P(X_1, ..., X_n)$ 等于零的概率可忽略。

因此，如果多项式 $P(X_1, ..., X_n)$ 等于零，则 $(b_1, ..., b_n)$ 是解，所以两个集合中的元素对应相等 $a_i = b_i, i \in [n]$。因此，能够推导出多项式 $\mathbb{F}$ 与多项式 $g$ 相等。

2.3 多集合相等性检测

通过添加一个随机数，可以将乘积一致性检测原理转换为一个更有用的工具：多集合相等性检测。

给定两个向量 $\vec{a} = (a_1, ..., a_n), \vec{b} = (b_1, ..., b_n)$，检测两个向量是否包含相同的元素，甚至以不同的顺序计算重复性。

多集合相等性到乘积一致性的归约：验证方 $V$ 选择随机数 $\gamma \in \mathbb{F}$，并对随机转移向量 $a' := a + \gamma, b' := b + \gamma$（$\gamma$ 被添加到所有的坐标中）检测以下等式是否成立：

$$ \prod_{i \in [n]} (ai + \gamma) = \prod{i \in [n]} (b_i + \gamma) $$

对于多项式中的 $\gamma$，由 Schwartz–Zippel 引理表明，除非 $a'$ 和 $b'$ 两个集合是相等的，否则上述等式成立的概率可忽略。

3 多项式与集合的转换关系

3.1 多项式协议

证明方 $\mathcal P$ 发送一个 $d$ 阶多项式给可信第三方 $\mathcal{I}$（由$\mathcal P$ 多项式承诺实现）。当协议运行完毕，验证方 $\mathcal V$ 询问可信第三方 $\mathcal{I}$：定义在集合 $H$ 上的 $d$ 阶保密输入多项式和公开且正确的预计算多项式是否满足某种性质（等价于：$\mathcal V$ 检查商多项式是否存在，等价于检测随机打开点是否正确）。对于固定整数 $d, D, t, l$ 和 $H \subset \mathbb{F}$：

1. 公开且正确的预计算 $t_1, ..., t_l \in \mathbb{F}_d[X]$ 和初始化多项式 $g_1, ..., g_l \in \mathbb{F}_d[X]$。
2. 证明方 $P$ 与可信第三方 $\mathcal{I}$ 之间的消息是保密多项式形式 $f \in \mathbb{F}_d[X]$（$\mathcal P$ 多项式承诺）。
3. 验证方 $\mathcal V$ 发送随机数 $\alpha$ 给证明方 $\mathcal P$。
4. 协议执行完毕，证明方 $\mathcal P$ 将多项式 $f_1, ..., f_t$ 发送给可信第三方 $\mathcal{I}$（$\mathcal P$ 多项式随机打开值与商多项式承诺）。

验证方 $\mathcal V$ 询问可信第三方 $\mathcal{I}$，多项式 $f_1, ..., f_t, g_1, ..., g_l$ 在 $H$ 范围内对随机数 $\alpha$ 是否满足某个运算关系：

$$ F(X) = G(\alpha, X, h_1(v_1(X)), ..., h_M(v_M(X))) \equiv 0 $$

其中，$h_i \in {f_1, ..., f_t, g_1, ..., g_l}$，$G \in \mathbb{F}_d[X, X_1, ..., X_M]$，$v_1, ..., v_M \in \mathbb{F}d[X]$，使得 $F \in \mathbb{F}{<D}[X]$。（等价于：$V$ 验证商多项式是否存在，等价于验证多项式的值是否正确。）

当验证方 $V$ 从可信第三方 $\mathcal{I}$ 接收到结果，则接受或拒绝。

3.2 拉格朗日选择多项式

上述多项式协议中，$H$ 为乘法子群，阶为 $N$，生成元为 $g$。对 $i \in [N]$，令 $Li \in \mathbb{F}{<N}[X]$ 为 $H$ 的第 $i$ 个拉格朗日多项式，且满足：

• $L_i(g^j) = 1, i = j$
• $L_i(g^j) = 0, i \neq j$

对于 $x \in H$，要求 $L_i(x)f(x) = 0$，则等价于 $f(g^i) = 0$。

3.3 多项式与集合划分

3.3.1 乘法群上实现多项式

对于整数 $n, d$，向量 $f \in \mathbb{F}^n, t \in \mathbb{F}^d$，使用符号 $f \subset t$ 表示 ${fi}{i \in [n]} \subset {ti}{i \in [d]}$。

令 $H = {g, ..., g^{n+1} = 1}$ 为在域上的阶为 $n+1$ 的乘法子群。 对于保密多项式 $f \in \mathbb{F}[X]$ 且 $i \in [n+1]$，记为 $fi := f(g^i)$。 对于保密向量 $f \in \mathbb{F}^n$，在域 $\mathbb{F}{<n}[X]$ 上的 $\mathbb{F}$ 保密多项式也记为 $f(g^i) = f_i$。

当 $f \subset t$ 时，如果元素出现在 $\mathbb{F}$ 中的顺序与出现在 $t$ 中的顺序相同，则称 $\mathbb{F}$ 由 $t$ 划分。 对任意 $i < i' \in [n]$，使得 $fi \neq f{i'}$；如果 $j, j' \in [d]$ 使得 $t_j = fi, t{j'} = f_{i'}$，则 $j < j'$。

3.3.2 二元多项式

给定 $f \in \mathbb{F}^n, t \in \mathbb{F}^d, s \in \mathbb{F}^{n+d}$，如下定义两个二元多项式 $F(\beta, \gamma)$ 和 $G(\beta, \gamma)$：

$$ F(\beta, \gamma) := (1 + \beta)^n \cdot \prod_{i \in [n]} (\gamma + fi) \prod{i \in [d-1]} (\gamma(1 + \beta) + ti + \beta \cdot t{i+1}) $$

$$ G(\beta, \gamma) := \prod_{i \in [n+d-1]} (\gamma(1 + \beta) + si + \beta \cdot s{i+1}) $$

定理：二元多项式 $F \equiv G$ 当且仅当 $f \subset t$ 且 $s = (f, t)$ 由 $t$ 划分。

证明： 情况 1： 如果 $f \subset t$ 且 $s = (f, t)$ 由 $t$ 划分：

1. 对每个 $j \in [d-1]$，存在一个索引 $i \in [n+d-1]$ 使得 $(tj, t{j+1}) = (sj, s{j+1})$，即 $\mathbb{F}$ 和 $G$ 中对应的因子是相等的：

   $$ \gamma + \frac{ti + \beta \cdot t{i+1}}{1 + \beta} = \gamma + \frac{si + \beta \cdot s{i+1}}{1 + \beta} $$

2. 对于补集索引 $i \in P$，$si = s{i+1}$，且集合 ${si}{i \in P}$ 等于集合 ${fi}{i \in [n]}$。对应因子等于 $\mathbb{F}$ 中的因子，因此 $F \equiv G$ 成立。

情况 2： 如果 $F \equiv G$：

1. 对于每个 $i \in [d-1]$，$G$ 一定包含一个因子：

   $$ \gamma + \frac{ti + \beta \cdot t{i+1}}{1 + \beta} = \gamma + \frac{si + \beta \cdot s{i+1}}{1 + \beta} $$

   根据 Schwartz–Zippel 引理，得出 $t_i = si, t{i+1} = s_{i+1}$。

2. 对于补集索引 $j \in [n+d-1] / P'$，存在 $i \in [n]$ 使得 $f_i = s_i$，因此 $f \subset t$ 且 $s = (f, t)$ 由 $t$ 划分。

综合情况 1 和情况 2，定理成立。

4 Plookup Argument 原理

预计算： 公开且正确的 Table 多项式：$ t \in \mathbb{F}_{<n+1}[X] $，查找表由多项式值表达。

证明方输入： 保密多项式：$ f \in \mathbb{F}_{<n}[X] $，witness 由多项式值表达。

1. 多项式组合与划分
   令 $ s \in \mathbb{F}^{2n+1} $ 为多项式 $ f $ 和 $ t $ 的组合 $ s = (f, t) $，由 $ t $ 划分。
   使用两个多项式 $ h_1, h2 \in F{<n+1}[X] $ 表达 $ s $ 多项式：
   $$ h_1(g^i) = s_i, \quad i \in [n+1], \quad h2(g^i) = s{n+i}, \quad i \in [n+1]. $$

2. 多项式承诺
   证明方 $ \mathcal P $ 计算多项式 $ h_1, h_2 $ 并发送给可信第三方 $\mathcal{I}$；
   （$ P $ 对 $ s $ 或 $ h_1, h_2 $ 进行多项式承诺）。

3. 随机数生成
   验证方 $ \mathcal V $ 选择随机数 $ \beta, \gamma \in F $ 并发送给证明方 $ \mathcal P $；

4. 聚合多项式
   证明方 $ \mathcal P $ 计算多项式 $ Z \in F{<n+1}[X] $ 和二元多项式聚合 $ F(\beta, \gamma)/G(\beta, \gamma) $ 的函数值，满足以下性质： $$ Z(g) = 1, $$ $$ Z(g^i) = \frac{(1+\beta)^{i-1} \cdot \prod{j<i}(\gamma + fj) \cdot \prod{1<j<i}(\gamma(1+\beta) + tj + \beta \cdot t{j+1})}{\prod_{1<j<i}(\gamma(1+\beta) + sj + \beta \cdot s{j+1})(\gamma(1+\beta) + s{n+j} + \beta \cdot s{n+j+1})}, $$ $$ Z(g^{n+1}) = 1. $$
   证明方 $ \mathcal P $ 将 $ Z $ 发送给可信第三方 $\mathcal{I}$；

5. 一致性验证
   验证方 $ \mathcal V $ 检测 $ Z $ 是否满足以下一致性条件（对 $ x \in H $ 验证）：
   $$ L_1(x)(Z(x) - 1) = 0, $$ $$ (x - g^{n+1})Z(x)(1+\beta) \cdot (\gamma + f(x))(\gamma(1+\beta) + t(x) + \beta \cdot t(g \cdot x)) = $$ $$ (x - g^{n+1})Z(g \cdot x)(\gamma(1+\beta) + h_1(x) + \beta \cdot h_1(g \cdot x))(\gamma(1+\beta) + h_2(x) + \beta \cdot h2(g \cdot x)), $$ $$ L{n+1}(x)(h_1(x) - h2(g \cdot x)) = 0, $$ $$ L{n+1}(x)(Z(x) - 1) = 0. $$
   如果以上 4 条均成立，则接受，否则拒绝。

协议安全性与证明长度分析

• 如果 $ {t(g^i)}{i \in [n+1]} \not\subset {f(g^i)}{i \in [n]} $，则攻击者 $ \mathcal A $ 扮演证明方 $ \mathcal P $ 的角色运行协议，验证方 $ \mathcal V $ 接受的概率可忽略。
• 上述协议的证明长度为 $ 5n + 4 $。

因此，当 $ F \equiv G $ 时，可以推导出 $ f \subset t $。由此证明方 $ \mathcal P $ 的 witness 存在于公开且正确的数据表中，表明输入和输出的约束是正确的，从而证明方 $ \mathcal P $ 的计算是正确的。

5 总结

Lookup Argument在零知识证明中有广泛的应用，包括：

• 通用零知识证明系统：优化约束验证过程。
• 可扩展验证：支持大规模数据集或复杂计算，开销小。
• 高效的成员测试：验证私有输入是否属于一组有效值。 Lookup Argument 是现代密码学协议的核心，能够高效且安全地进行成员关系证明。通过利用多项式承诺、随机挑战和见证生成，确保了协议的健全性、完备性和隐私性。它在构建可扩展、鲁棒且安全的零知识证明系统中发挥了重要作用。