不懂就查（如何创建零知识证明查找表）
原文： https://blog.lambdaclass.com/lookups/
作者：LambdaClass
译者：Kurt Pan
1引言
ZK-SNARK（零知识简洁非交互知识论证）和 STARK（可扩展透明知识论证）是强大的密码学构造，可应用于去中心化隐私计算和区块链扩容。其允许一方（证明者）以一种既节省内存又节省时间的方式向另一方（验证者）证明他正确地执行了计算。换句话说，证明者可以提交一个短证明（比发送计算中所涉及的所有值更简洁），可以在比独立重新执行计算所需的时间更短的时间内验证该证明。这些构造依赖于将信息编码为多项式，对其进行承诺（通过多项式承诺方案，例如 FRI 或 KZG），并显示多项式之间的某些关系成立。有关这些概念的介绍，请参阅我们之前关于 STARKs、Plonk、Groth 16 的文章或 zkhack 上 Dan Boneh 的介绍视频。
第一步是将代码转换为有限域上的多项式方程组。这称为算术化，典型的算术化方案是 R1CS（秩一约束系统）、Plonkish 和 AIR（代数中间表示）。有些操作的算术化成本很高，这可能会给证明者带来巨大的开销。查找论证是一种强大的技术，可以通过预计算的（也可以是动态的）值表来帮助我们解决这个问题。这篇文章中，我们将介绍查找论证的基础知识并描述 PlookUp 方案。该主题已在正在进行的 Sparkling Water Bootcamp 中进行了讨论，也将在我们的库 Lambdaworks 中提供不同查找的实现。
2示例及工作原理
假设我们要检查变量 是否必须在一个规定的范围内, 例如 u8 。一种简单但低效的方法是以二进制形式 表示 并检查:
每个变量都是布尔值
这种方法会添加一些额外的约束，数量与比特数成正比。另一种方法是说明该数包含在一个变量的所有有效值的列表中。这就是一个查找操作的示例。第一个查找论证取决于表的大小（我们为所做的查找操作和整个表都付出代价）。同时，较新的构造使我们只需为查找操作的数量（加上一些预处理）付出代价。如果我们只需要执行少量查找操作，那么使用这些论证并没有什么回报（我们可以接受更多的约束）。不过，随着操作数量或复杂性的增加，支持查找就会越来越有意义。
我们可以使用查找表来证明位运算。例如, 对于两个字节 和 之间的异或, 我们可以使用算术约束来表示该操作,
我们还可以有一个包含所有可能 和 组合的列表 。鉴于每个字节采用 256 个不同的值 , 我们可以有一个表格列出所有有效的输入/输出三元组 ( 并检查我们的 都在那个表里。
为了证明包含性, 我们将使用类似于置换论证的技巧。首先将表 中具有元组 的声明归约为两个向量之间的关系。我们将证明, 对于向量 中的每个分量, 向量 中都存在一些分量, 使得 。可以通过对列进行随机折叠来将表压缩为单个向量,
通过执行相同的操作将元组 化简为向量 ,
为了能够应用某种置换论证, 我们需要知道 中的每个元素在 中出现的次数, 这可能会比较难做。相反, 我们会去使用排序向量的随机差异。PlookUp 论文中介绍了这种方法。构造一个向量 , 它是连接向量 和 并按它们在 中出现的顺序对它们进行排序的结果。如果 中的非零连续差集与 相同, 则证明了 的所有值都在 给定的集合中。如果 的值在 中出现多次, 则连续差对相同元素会产生 0 , 从而将它们从检查中消除。随机差异避免了检查初始值,
在随机差的情况下, 即使连续元素相同, 差也将不为零。但是, 我们知道差将是 的倍数, 这使得可以识别它们。检查涉及两个二元多项式 和 ,
如果这两个多项式相同, 我们就证明了 的所有值都包含在 给出的集合中。
与置换检查一样, 定义向量 很有用, 定义如下:
然后我们可以对 的值进行插值以获得必须满足下列条件的多项式 :
其中多项式 和 分别由多项式 和 插值得出。这些约束必须添加到正在使用的证明系统的约束中。
3Plonk 和查找表
要回顾 Plonk 协议, 建议阅读我们之前的文章或 Lambdaworks 文档。Plonk 的算术化使用选择子变量 来描述不同类型的门, 对有效执行 应满足以下等式:
将查找引入 Plonk , 要添加一个新的选择子变量 。当必须检查 的值是否属于给定表时, 此变量将等于 1 。在这种情况下, 其他选择子将为0, 这将平凡地满足其他类型门的方程。建议关注 PlonkUp 论文以获得更多信息。
设置和预处理输入
在 Plonk 中, 我们从常见的预处理输入开始, 它由选择子多项式 以及复制约束多项式 组成。在查找的情况下, 我们有更多的预处理信息, 例如 、 。
第 1 轮 - 对电路执行承诺
Plonk 协议中的第 1 轮包括对列多项式 和 进行插值并承诺它们。这样, 证明者承诺给定的电路执行, 并且他将无法更改执行跟踪的值。
第 2 轮 - 进行查找
当我们进行查找时, 会添加新的一轮。我们将其称为第 2 轮。这里, 证明者会将表压缩为向量，并开始进行证明查找论证的所有工作。证明者对表和接线的折叠系数 进行采样, 并获得压缩表和查询,
最后一个多项式需要盲化以达到零知识, 遵循第1轮中相同的方法:
之后, 证明者构建向量 , 按 排序。由于该向量的长度大于在其上插值 和 的域 的大小, 因此我们将其分为两部分, 和 , 创建多项式 和 。打破多项式有两种常见的方法：对前半部分进行插值, 然后对后半部分进行插值, 或者分成奇数项和偶数项。第二种方法少一次检查, 因此我们将在此采用该策略, 遵循 PlonkUp。由于多项式 和 包含有关见证的信息, 因此我们还要向这些多项式添加盲化。
该轮以查询多项式 以及有序向量 和 部分的承诺结束。
第 3 轮 - 计算置换和 Plookup 多项式
第 3 轮包括复制约束多项式 和 Plookup 多项式 的计算。置换论证多项式 由以下三项给出:
第一项对应于盲多项式, 第二项是第一个拉格朗日基多项式（如果 则为 1 , 否则为零），第三项包含大乘积。
Plookup 多项式 看起来非常类似, 由三个项给出,
这些多项式的最佳计算方法是获取大乘积检查的分量（以求值形式），然后使用快速傅立叶变换进行插值。证明者对这两个多项式进行承诺。
第5轮 - 转化为商
第 4 轮计算约束多项式、复制约束多项式和 Plookup 约束的线性组合。我们有以下约束限制:
所有赋值都必须满足一般门方程。 置换检查多项式 在第一个求值点应等于 1 。使用我们在 STARK 中学到的机制, 我们可以将条件转换为
应该是一个多项式。我们可以将其转化为更合适的形式 (使得所有约束具有相同的消失多项式）
置换论证的约束
执行查找门,
Plookup 多项式的乘积检查
多项式在第一个点应等于 1 ,
所有约束都应在插值域上都成立。每个多项式都可以被 整除, 多项式的随机线性组合也是如此。结果是商多项式 , 它分为三个部分, 每个部分最多 次：
证明者承诺每个部分。
第5轮 - 求值
第 5 轮计算随机点 处多个多项式的求值并将其发送给验证者, 以便验证者有足够的信息来检查商与原始多项式之间的关系。证明者从脚本 中采样并计算:
第6论-包裹证明
第 6 轮执行线性化并生成打开证明。目前为止, 证明者已经在某个时刻对多项式及其求值做出了承诺。现在是链接两者并生成求值证明的时候了。首先, 证明者计算线性化多项式 , 它应在 处为 0 。证明者计算第 5 轮 处列出的所有多项式的求值证明,
对 处的多项式做同样的事情,
证明者对这些商多项式承诺。
第 5 轮的所有求值都给出证明, 以及对第 和 6 轮中所有多项式的承诺。
4结论
在这篇文章中，我们介绍了查找论证的基础知识，可以通过在包含所有有效输入/输出关系的表中检查特定计算的结果，来证明特定计算的正确性。当我们尝试证明难以或昂贵的运算的算术化（例如范围检查或位运算（被广泛使用））时，这些技术可以节省大量成本。我们描述了 Plookup 的工作原理，这是最开始提出的论证之一。它可以非常巧妙地集成到 Plonk 协议中，但会导致额外的成本，因为我们的计算时间随着表大小的增加而增加。最近的构造降低了与表大小相关的成本，只需支付与查找次数成比例的开销。接下来的文章中，我们将介绍如何编写 Plookup 协议的代码以及介绍更新的查找论证。