Lookup Argument 综述

eigenlab
发布于 2023-10-27 23:10
阅读 13

本文介绍了lookup协议，它用于处理SNARKs难以处理的特定操作。文章详细阐述了多种lookup协议，包括Plookup、Caulk、Caulk+、Baloo、Flookup、cq和LogUp，并探讨了它们在范围检查、有限域函数、有限状态机、zkEVM/zkVM等领域的应用，最后总结了lookup协议通过牺牲更高的证明大小来换取更快的证明和验证的优势。

![](https://img.learnblockchain.cn/2025/10/21/1BUAphndBkEiOZfISKx25lg.jpeg)

## 1. 简介

查找协议旨在处理对于 SNARKs (简洁的非交互式知识论证) 来说具有挑战性的特定操作。广义地说，这些协议能够证明以下形式的陈述：

- 给定一个由不同值组成的表 T={t\_i},i=0,…,N−1（称为“行”），
- 以及一个查找列表 F={f\_j}j=0,…,m−1（可能多次出现），
- 所有的查找都包含在该表中，即 F⊆T。

在这个框架中，表 T 通常被认为是公开的，而查找列表 F 被视为私有 witness。可以将该表理解为保存给定变量的所有允许值，而查找则是特定程序执行期间生成的该变量的特定实例。要证明的陈述确认了变量在该程序的整个执行过程中都保持在合法范围内。

为了便于讨论，假设 m<N，并且在大多数情况下 m≪N，除非另有说明。我们的目标是回顾可用查找协议的演变和多样性，并探索证明此类陈述的各种应用。

## 2. 查找论证方案

**Plookup：** Plookup 是最早的查找协议之一，旨在证明已提交的多项式 f 仅包含来自公共表 t 的元素。该协议使用辅助多项式 F 和 G 来确认这一点。Prover 提交代表排序向量 s 的多项式 h\_1 和 h\_2，然后使用证明多项式 Z 响应验证者 challenge β 和 γ。验证者检查特定的 identities 以确认正确性。Prover 的计算复杂度为 O(NlogN) 域运算，并且该协议可以推广以处理多个表和向量查找。

**Caulk：** Caulk 提供了一种证明已提交向量 cm 是更大的已提交向量 C 的一部分的方法。它依赖于多项式 commitments，并将大部分计算转移到预处理阶段。这使得 Prover 的工作依赖于 cm 的大小 m，而不是 C 的大小 N。Prover 识别包含 cm 元素的子集 C\_I，并使用 KZG commitment 显示 C−C\_I=Z\_I(x)×H\_I(x)。该协议具有亚线性效率，Prover 复杂度为 O(mlogN)。

**Caulk+：** Caulk+ 通过进一步降低 Prover 的计算复杂度来改进 Caulk。它用更高效的可分性检查替换了 logN 项。该协议涉及计算多项式 Z\_I、C\_I 和 U，以表明 Z\_I 可除 C−C\_I 和 X^n−1。它通过引入 blinding factors 保留了零知识属性，从而将 Prover 复杂度降低到 O(m^2)。

**Baloo：** Baloo 通过以 vanishing polynomial 形式提交表子集来扩展 Caulk+，并在子集大小中使用准线性时间。它引入了一种“提交并证明”论证和一种广义的 Sumcheck 协议，以将证明简化为内部积论证。该协议效率很高，并且可以扩展到多列查找，为 zkEVM 等 SNARKs 提供了有希望的应用。

**Flookup：** Flookup 旨在有效地证明已提交多项式的值是大型表的一部分。该协议使用 pairings 来提取相关表子集的 vanishing polynomial，从而为证明引入了一种新的多项式 IOP。在 O(Nlog^2N) 预处理之后，Prover 以准线性时间 O(mlog^2m) 运行，从而改进了先前的二次 Prover 复杂度。它对于大型域上的 SNARK 证明特别有用。

**cq：** cq 利用对数导数方法将成员资格证明简化为有理 identity 检查。通过预先计算商多项式的“缓存商”，它可以有效地计算表条目。凭借 O(NlogN) 的 Prover 时间和 O(N) 的证明大小，它超越了 Baloo 和 Flookup 的效率，同时保持了同态等属性。

**LogUp：** Logup 有效地证明了 Boolean 超立方体查找表中存在一组 witness 值。使用对数导数，它将集合包含转换为有理函数等式检查，要求 Prover 仅提供一个 multiplicity 函数。LogUp 比多元 Plookup 变体更有效，所需的 Oracle commitments 减少 3-4 倍。对于大型批量大小，它也优于 Plookup 的有界 multiplicity 优化。该方法用途广泛，可扩展到向量值查找，并适用于范围证明。它与 PLONK 和 Aurora 等 SNARKs 以及 tinyRAM 和 zkEVM 等应用尤其相关。

## 3. 应用

- **范围检查：** 证明数字 x 在范围 {0,…,N-1} 内，对于 N = 2^n，可以使用 n+1 个算术约束来完成，或者使用单个查找约束来检查 x 是否在范围内所有数字的表中。
- **有限域函数：** 任何有限域函数都可以使用包含所有输入 - 输出对的查找表来实现。与使用算术约束相比，这可以更有效地实现 k 位 XOR 等复杂函数。
- **更好的 XOR：** 通过使用零交错将 XOR 和 AND 结果组合到单个表查找中，可以更有效地实现按位 XOR。这会将表大小从 2^{2^k} 减少到 k=16 时仅为 384kB。
- **有限状态机：** 查找表可以对有限状态机的转换表进行编码。通过检查表中的每个（状态，输入，下一个状态）转换，可以证明执行跟踪有效。
- **zkEVM/zkVM：** 查找表可以应用于 CPU 和内存跟踪表，以进行实时监控和验证。在 CPU 跟踪表中，查找表可以包含有效的指令或状态，从而有助于立即标记未经授权或错误的操作。这有助于调试并增强安全性。对于内存跟踪表，查找表列出了有效的内存地址和允许的操作。每个读取或写入都在实时交叉引用，从而确保数据完整性并防止未经授权的访问。这两种应用都有助于提高系统的安全性和操作准确性，使其成为调试和性能优化的宝贵工具。

## 4. 结论

查找的主要好处是降低了对诸如位运算，转换等“SNARK 不友好”的操作的约束复杂度。查找以更大的证明大小换取更快的证明和验证。因此，总而言之，查找通过检查编码允许值的公共表中的成员资格，可以有效地证明有关复杂函数，机器状态，范围等的语句。这提高了非算术约束的性能。

## 5. 参考文献

```
1. Gabizon A, Williamson Z J. plookup: A simplified polynomial protocol for lookup tables[J]. Cryptology ePrint Archive, 2020.
2. Zapico A, Buterin V, Khovratovich D, et al. Caulk: Lookup arguments in sublinear time[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 3121–3134.
3. Posen J, Kattis A A. Caulk+: Table-independent lookup arguments[J]. Cryptology ePrint Archive, 2022.
4. Gabizon A, Khovratovich D. flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size[J]. Cryptology ePrint Archive, 2022.
5. Zapico A, Gabizon A, Khovratovich D, et al. Baloo: Nearly optimal lookup arguments[J]. Cryptology ePrint Archive, 2022.
6. Eagen L, Fiore D, Gabizon A. cq: Cached quotients for fast lookups[J]. Cryptology ePrint Archive, 2022.
7. Haböck U. Multivariate lookups based on logarithmic derivatives[J]. Cryptology ePrint Archive, 2022.
```

8. 查找论证简史。[https://github.com/ingonyama-zk/papers/blob/main/lookups.pdf](https://github.com/ingonyama-zk/papers/blob/main/lookups.pdf)

>- 原文链接： [eigenlab.medium.com/a-re...](https://eigenlab.medium.com/a-review-of-lookup-arguments-edecf6aa73cb)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

1. 简介

查找协议旨在处理对于 SNARKs (简洁的非交互式知识论证) 来说具有挑战性的特定操作。广义地说，这些协议能够证明以下形式的陈述：

给定一个由不同值组成的表 T={t_i},i=0,…,N−1（称为“行”），
以及一个查找列表 F={f_j}j=0,…,m−1（可能多次出现），
所有的查找都包含在该表中，即 F⊆T。

2. 查找论证方案

Plookup： Plookup 是最早的查找协议之一，旨在证明已提交的多项式 f 仅包含来自公共表 t 的元素。该协议使用辅助多项式 F 和 G 来确认这一点。Prover 提交代表排序向量 s 的多项式 h_1 和 h_2，然后使用证明多项式 Z 响应验证者 challenge β 和 γ。验证者检查特定的 identities 以确认正确性。Prover 的计算复杂度为 O(NlogN) 域运算，并且该协议可以推广以处理多个表和向量查找。

Caulk： Caulk 提供了一种证明已提交向量 cm 是更大的已提交向量 C 的一部分的方法。它依赖于多项式 commitments，并将大部分计算转移到预处理阶段。这使得 Prover 的工作依赖于 cm 的大小 m，而不是 C 的大小 N。Prover 识别包含 cm 元素的子集 C_I，并使用 KZG commitment 显示 C−C_I=Z_I(x)×H_I(x)。该协议具有亚线性效率，Prover 复杂度为 O(mlogN)。

Caulk+： Caulk+ 通过进一步降低 Prover 的计算复杂度来改进 Caulk。它用更高效的可分性检查替换了 logN 项。该协议涉及计算多项式 Z_I、C_I 和 U，以表明 Z_I 可除 C−C_I 和 X^n−1。它通过引入 blinding factors 保留了零知识属性，从而将 Prover 复杂度降低到 O(m^2)。

Baloo： Baloo 通过以 vanishing polynomial 形式提交表子集来扩展 Caulk+，并在子集大小中使用准线性时间。它引入了一种“提交并证明”论证和一种广义的 Sumcheck 协议，以将证明简化为内部积论证。该协议效率很高，并且可以扩展到多列查找，为 zkEVM 等 SNARKs 提供了有希望的应用。

Flookup： Flookup 旨在有效地证明已提交多项式的值是大型表的一部分。该协议使用 pairings 来提取相关表子集的 vanishing polynomial，从而为证明引入了一种新的多项式 IOP。在 O(Nlog^2N) 预处理之后，Prover 以准线性时间 O(mlog^2m) 运行，从而改进了先前的二次 Prover 复杂度。它对于大型域上的 SNARK 证明特别有用。

cq： cq 利用对数导数方法将成员资格证明简化为有理 identity 检查。通过预先计算商多项式的“缓存商”，它可以有效地计算表条目。凭借 O(NlogN) 的 Prover 时间和 O(N) 的证明大小，它超越了 Baloo 和 Flookup 的效率，同时保持了同态等属性。

LogUp： Logup 有效地证明了 Boolean 超立方体查找表中存在一组 witness 值。使用对数导数，它将集合包含转换为有理函数等式检查，要求 Prover 仅提供一个 multiplicity 函数。LogUp 比多元 Plookup 变体更有效，所需的 Oracle commitments 减少 3-4 倍。对于大型批量大小，它也优于 Plookup 的有界 multiplicity 优化。该方法用途广泛，可扩展到向量值查找，并适用于范围证明。它与 PLONK 和 Aurora 等 SNARKs 以及 tinyRAM 和 zkEVM 等应用尤其相关。

3. 应用

范围检查： 证明数字 x 在范围 {0,…,N-1} 内，对于 N = 2^n，可以使用 n+1 个算术约束来完成，或者使用单个查找约束来检查 x 是否在范围内所有数字的表中。
有限域函数： 任何有限域函数都可以使用包含所有输入 - 输出对的查找表来实现。与使用算术约束相比，这可以更有效地实现 k 位 XOR 等复杂函数。
更好的 XOR： 通过使用零交错将 XOR 和 AND 结果组合到单个表查找中，可以更有效地实现按位 XOR。这会将表大小从 2^{2^k} 减少到 k=16 时仅为 384kB。
有限状态机： 查找表可以对有限状态机的转换表进行编码。通过检查表中的每个（状态，输入，下一个状态）转换，可以证明执行跟踪有效。
zkEVM/zkVM： 查找表可以应用于 CPU 和内存跟踪表，以进行实时监控和验证。在 CPU 跟踪表中，查找表可以包含有效的指令或状态，从而有助于立即标记未经授权或错误的操作。这有助于调试并增强安全性。对于内存跟踪表，查找表列出了有效的内存地址和允许的操作。每个读取或写入都在实时交叉引用，从而确保数据完整性并防止未经授权的访问。这两种应用都有助于提高系统的安全性和操作准确性，使其成为调试和性能优化的宝贵工具。

4. 结论

5. 参考文献

1. Gabizon A, Williamson Z J. plookup: A simplified polynomial protocol for lookup tables[J]. Cryptology ePrint Archive, 2020.
2. Zapico A, Buterin V, Khovratovich D, et al. Caulk: Lookup arguments in sublinear time[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 3121–3134.
3. Posen J, Kattis A A. Caulk+: Table-independent lookup arguments[J]. Cryptology ePrint Archive, 2022.
4. Gabizon A, Khovratovich D. flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size[J]. Cryptology ePrint Archive, 2022.
5. Zapico A, Gabizon A, Khovratovich D, et al. Baloo: Nearly optimal lookup arguments[J]. Cryptology ePrint Archive, 2022.
6. Eagen L, Fiore D, Gabizon A. cq: Cached quotients for fast lookups[J]. Cryptology ePrint Archive, 2022.
7. Haböck U. Multivariate lookups based on logarithmic derivatives[J]. Cryptology ePrint Archive, 2022.

查找论证简史。https://github.com/ingonyama-zk/papers/blob/main/lookups.pdf

原文链接： eigenlab.medium.com/a-re...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

翻译
学分: 0
分类: 密码学
标签: lookup协议 SNARKs Plookup Caulk Baloo zkEVM

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。