如果你不知道，查一下或者如何为零知识证明创建查找表

介绍

ZK-SNARKs（零知识简洁非交互知识论证）和 STARKs（可扩展透明知识论证）是功能强大的密码学结构，可应用于去中心化私有计算和区块链扩展。它们允许一方（证明者）向另一方（验证者）证明他正确地执行了计算，这种方式既节省内存又节省时间。换句话说，证明者可以提交一个简短的证明（比发送计算中涉及的所有值更简洁），验证所需的时间比我们独立重新执行计算所需的时间更少。这些结构依赖于将信息编码为多项式，并对其进行承诺（通过多项式承诺方案，例如 FRI 或 KZG），并表明多项式之间存在某些关系。有关这些概念的介绍，请参阅我们之前关于 STARKs、Plonk、Groth 16 的文章或 zkhack 上 Dan Boneh 的介绍性视频。

第一步是将代码转换为有限域上的多项式方程组。这被称为算术化，典型的算术化方案是 R1CS（秩 1 约束系统）、Plonkish 和 AIR（代数中间表示）。某些操作的算术化成本很高，这可能会导致证明者付出高昂的代价。查找参数是一种强大的技术，可以通过使用预先计算的值表（也可以是动态的）来帮助我们解决这个问题。在这篇博文中，我们将介绍查找参数的基础知识，并描述 PlookUp 方案。该主题已在正在进行的 Sparkling Water Bootcamp 中讨论过，我们将在我们的库 Lambdaworks 中提供不同查找的实现。

示例和工作原理

假设我们要检查变量 $a$ 是否在规定的范围内，例如 u8。一种简单但无效的方法是以二进制形式 $a_0a_1a_2a_3a_4a_5a_6a_7$ 来表示 $a$，并检查：

1. 每个变量都是布尔值 $a_i(1-a_i) = 0$
2. $a = \sum a_k2^k$

这种方法会使我们添加几个额外的约束，这些约束与位数成正比。另一种方法可能是证明该数字包含在变量的所有有效值的列表中。这是一个查找操作的示例。第一个查找参数取决于表的大小（我们为执行的查找操作和整个表付出了代价）。同时，更新的结构让我们只为查找操作的数量付费（加上一些预处理）。如果我们只需要做几个查找操作，那么使用这些参数是行不通的（我们可以接受有更多的约束）。尽管如此，随着操作的数量或复杂性的增加，支持查找是有意义的。

我们可以使用查找表来证明按位操作。例如，对于两个字节 $a$ 和 $b$ 之间的异或，$c = a \oplus b$，我们可以使用算术约束来表示操作，

$a_i(1-a_i) = 0$

$b_i(1-b_i) = 0$

$a_i + b_i - 2a_ib_i - c_i = 0$

我们还可以有一个包含所有可能组合的列表，$a$、$b$ 和 $c$。鉴于每个字节占用 256 个不同的值 ($2^8$)，我们可以有一个表列出所有有效的输入/输出三元组 ($2^{16} = 65536$)，并检查我们的 $(a, b, c)$ 是否在该列表中。

为了证明包含关系，我们将使用类似于我们在置换参数中应用的技巧。我们将首先将我们的元组 $(a, b, c)$ 在表 $T$ 中的声明简化为两个向量之间的关系。我们将证明，对于向量 $f$ 中的每个分量，向量 $t$ 中都存在某个分量，使得 $f_i = t_k$。我们可以通过对列执行随机折叠将表压缩成一个向量，

$t = col_0(T) + \zeta col_1(T) + \zeta^2 col_2(T)$

我们可以通过执行相同的操作将元组 $(a, b, c)$ 简化为向量 $f$，

$f = a + \zeta b + \zeta^2 c$

为了能够应用一种置换参数，我们应该知道 $f$ 中的每个元素在 $t$ 中出现的次数，这可能存在问题。相反，我们可以使用排序向量上的随机差分。该方法在 PlookUp 论文 中介绍。我们构建一个向量 $s$，它是由连接向量 $f$ 和 $t$ 并按它们在 $t$ 中出现的顺序对它们进行排序而产生的。如果 $s$ 中非零连续差分的集合与 $t$ 相同，那么这证明 $f$ 的所有值都在 $t$ 给定的集合中。如果 $t$ 的值在 $f$ 中出现多次，则连续差分将为相等元素产生 $0$，从而将它们从检查中消除。随机差分避免了检查初始值，

$\Delta s_i = si + \beta' s{i+1}$

$\Delta t_i = ti + \beta' t{i+1}$

在随机差分的情况下，即使连续的元素相同，差分也将是非零的。但是，我们知道差分将是 $1 + \beta'$ 的倍数，这使我们能够识别它们。检查涉及两个双变量多项式，$F$ 和 $G$，

$F = (1 + \beta')^n \prod (\gamma' + f_j) \prod (\gamma'(1 + \beta') + \Delta t_i)$

$G = \prod (\gamma'(1 + \beta') + \Delta s_i)$

如果这两个多项式相同，我们已经证明 $f$ 的所有值都包含在 $t$ 给定的集合中。

与置换检查一样，定义向量 $z$ 很有用，定义如下：

$z_0 = 1$

$z_i = \prod \frac{(1 + \beta')(\gamma' + f_i)(\gamma'(1 + \beta') + \Delta ti)}{(\gamma'(1 + \beta') + s{2i-1} + \beta' s{2i})(\gamma'(1 + \beta') + s{2i} + \beta' s_{2i+1})}$

然后我们可以插值 $z$ 的值以获得多项式 $z(x)$，该多项式必须满足以下条件：

1. $z(x=1) = 1$
2. $z(x=g^N) = 1$
3. $z(x)U(x) - z(gx)V(x) = 0$

其中多项式 $U(x)$ 和 $V(x)$ 是分别从多项式 $F$ 和 $G$ 插值得到的。这些约束必须添加到我们正在使用的证明系统的约束中。

Plonk 和查找表

有关 Plonk 协议的回顾，我们建议阅读我们之前的文章或 Lambdaworks 文档。Plonk 的算术化使用选择器变量 $q_l, q_r, q_m, q_o, q_c$ 来描述不同类型的门，对于有效的执行 $(a, b, c)$，这些变量应满足以下等式：

$q_l(x)a(x) + q_r(x)b(x) + q_ma(x)b(x) + q_o(x)c(x) + q_c(x) + p_i(x) = 0$

当将查找引入 Plonk 时，我们添加一个新的选择器变量 $q_{lu}$。当必须检查 $(a, b, c)$ 的值是否属于给定的表时，此变量将等于 $1$。在这种情况下，其他选择器将为零，这将简单地满足其他类型门的等式。我们建议阅读 PlonkUp 论文 了解更多详情。

设置和预处理输入

在 Plonk 中，我们从公共预处理输入开始，它由选择器多项式 $q_l(x), q_r(x), q_m(x), q_o(x), qC(x)$ 加上复制约束多项式 $S{\sigma1}(x), S{\sigma2}(x), S{\sigma3}(x)$ 组成。在查找的情况下，我们有更多的预处理信息，例如$q_{lu}(x)$ 、$col_0(T)(x), col_1(T)(x), col_2(T)(x)$ 。

第 1 轮 - 承诺电路的执行

Plonk 协议中的第一轮包括插值列多项式 $a(x)$、$b(x)$ 和 $c(x)$ 并对它们进行承诺。这样，证明者承诺给定的电路执行，并且他将无法更改执行轨迹的值。

第 2 轮 - 进入查找

当我们有查找时，我们添加一个新回合。我们将其称为第 2 轮。在这里，证明者会将表压缩成一个向量，并开始所有工作来证明查找参数。证明者对表的折叠系数 $\zeta$ 和连线进行采样，并获得压缩后的表和查询，

$t = col_0(T) + \zeta col_1(T) + \zeta^2 col_2(T)$

$f' = a + \zeta b + \zeta^2 c$

这个最后的多项式需要盲化来使其零知识，遵循第 1 轮的相同方法：

$f(x) = f'(x) + Z_H(x)(b_7 + b_8x)$

之后，证明者构建向量 $s$，该向量按 $t$ 排序。由于此向量的长度大于我们插值 $t$ 和 $f$ 的域 $H$ 的大小，因此我们将其分解为两部分，$h_1$ 和 $h_2$，并创建多项式 $h_1(x)$ 和 $h_2(x)$。有两种常见的方法可以分解多项式：取前半部分并插值，然后取后半部分，或者分成奇数项和偶数项。第二种方法需要的检查更少，因此我们将在这里采用该策略，遵循 PlonkUp。由于多项式 $h_1(x)$ 和 $h_2(x)$ 包含有关见证的信息，因此我们还在这些多项式中添加盲化。

这一轮以承诺查询的多项式 $f(x)$ 以及排序向量 $h_1(x)$ 和 $h_2(x)$ 的部分结束。

第 3 轮 - 计算置换和 Plookup 多项式

第 3 轮涉及计算复制约束多项式 $z_1(x)$ 和 Plookup 多项式 $z_2(x)$。置换参数多项式 $z_1(x)$ 由以下三项给出：

$z{11} = (b{14}x^2 + b{15}x + b{16})Z_H(x)$

$z_{12} = L_1(x)$

$z{13} = \sum L{i+1}(x) \prod \frac{(\gamma + \beta\omega^i + a_i)(\gamma + k_1\beta\omega^i + b_i)(\gamma + k_2\beta\omega^i + ci)}{(\gamma + \beta S{\sigma1,i} + a_i)(\gamma + k1\beta S{\sigma2,i} + b_i)(\gamma + k2\beta S{\sigma3,i} + c_i)}$

第一项对应于盲化多项式，第二项是第一个拉格朗日基多项式（如果 $x=g$，则为 1，否则为零），第三项包含总乘积。

Plookup 多项式 $z_2(x)$ 看起来非常相似，由三项给出，

$z{21} = (b{17}x^2 + b{18}x + b{19})Z_H(x)$

$z_{22} = L_1(x)$

$z{23} = \sum L{i+1}(x) \prod \frac{(1 + \beta')(\gamma' + f_i)(\gamma'(1 + \beta') + ti + \beta' t{i+1})}{(\gamma'(1 + \beta') + s{2i-1} + \beta' s{2i})(\gamma'(1 + \beta') + s{2i} + \beta' s{2i+1})}$

最好通过获得总乘积检查的组件（以评估形式）然后使用快速傅里叶变换进行插值来计算这些多项式。证明者承诺这两个多项式。

第 4 轮 - 转换为商

第 4 轮计算约束多项式、复制约束多项式和 Plookup 约束的线性组合。我们有以下约束：

1. 所有赋值都必须满足一般门等式。
2. 置换检查多项式 $z_1(x)$ 在第一个评估点应等于 1。 使用我们在 STARK 中学到的机制，我们可以将条件转换为

$\frac{z_1(x) - 1}{x - g}$

应该是一个多项式。我们可以将其转换为更合适的形式（以便所有约束都具有相同的消失多项式）

$L_1(x)(z_1(x) - 1)$

3. 置换参数的约束

$(\gamma + \beta x + a(x))(\gamma + k_1\beta x + b(x))(\gamma + k_2\beta (x) + c(x))z1(x) - (\gamma + \beta S{\sigma1}(x) + a(x))(\gamma + k1\beta S{\sigma2}(x) + b(x))(\gamma + k2\beta S{\sigma3}(x) + c(x))z_1(gx)$

4. 实施查找门，

$q_{lu}(x)(a(x) + \zeta b(x) + \zeta^2 c(x) - f(x))$

5. Plookup 多项式的乘积检查

$(1 + \beta')(\gamma' + f(x))(\gamma'(1 + \beta') + t(x) + \beta' t(gx))z_2(x) - (\gamma'(1 + \beta') + h_1(x) + \beta' h_2(x))(\gamma'(1 + \beta') + h_2(x) + \beta' h_1(gx))z_2(gx)$

6. Plookup 多项式在第一个点应等于 1，

$L_1(x)(z_2(x) - 1)$

所有约束都应在插值域上成立。因此，每个多项式都可以被 $Z_H(x)$ 整除，多项式的随机线性组合也可以被 $Z_H(x)$ 整除。结果是商多项式 $q(x)$，它分为三个部分，每个部分的度数最多为 $N+1$

$q(x) = q{lo}(x) + x^{N+2}q{mid}(x) + x^{2N+4}q_{hi}(x)$

证明者承诺每个部分。

第 5 轮 - 评估

第 5 轮计算几个多项式在随机点 $z$ 处的评估，并将它们发送给验证者，以便他有足够的信息来检查商和原始多项式之间的关系。证明者从成绩单中采样 $z$ 并计算：

• $a(z)$
• $b(z)$
• $c(z)$
• $S_{\sigma1}(z)$
• $S_{\sigma2}(z)$
• $f(z)$
• $t(z)$
• $t(gz)$
• $z_1(gz)$
• $z_2(gz)$
• $h_1(gz)$
• $h_2(z)$

第 6 轮 - 包装证明

第 6 轮执行线性化并生成打开证明。到目前为止，证明者已经给出了多项式的承诺以及它们在某些点处的评估。现在是链接两者并生成评估证明的时候了。首先，证明者计算线性化多项式 $r(x)$，它在 $z$ 处应等于 $0$。证明者计算第 5 轮中列出的所有多项式在 $z$ 处的评估证明，

$W_z(x) = \frac{1}{x-z}(r(x) + \sum \alpha_i(p_i(x) - p_i(z)))$

他对 $gz$ 处的多项式执行相同的操作，

$W_{gz}(x) = \frac{1}{x-gz}(\sum \alpha_i(p_i(x) - p_i(gz)))$

证明者承诺这些商多项式。

第 5 轮中的所有评估都给出了证明，以及对第 1、2、3、4 和 6 轮中所有多项式的承诺。

结论

在这篇文章中，我们介绍了查找参数的基础知识，它使我们能够通过检查包含所有有效输入/输出关系的表中的结果来证明特定计算是正确的。当我们尝试证明难以或昂贵的算术化操作时，例如范围检查或按位操作（可以广泛使用），这些技术可以带来显着的节省。我们描述了 Plookup 的工作原理，它是最早提出的参数之一。它可以非常巧妙地集成到 Plonk 协议中，但会导致额外的成本，因为我们有计算时间会随着表大小的增加而增加。最近的结构降低了与表大小相关的成本，仅支付与查找次数成正比的价格。在接下来的文章中，我们将介绍如何编写 Plookup 协议和更新的查找参数的代码。

• 原文链接： blog.lambdaclass.com/loo...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～