多重集合相等

ZK白板系列S2 - M3：Lookups 更新

在本模块中，Ariel Gabizon 对查找协议进行了更新，重点介绍了三种主要的查找方法，并深入探讨了“对数导数”方法。以下是视频的核心内容和关键论据总结： 1. **核心内容概括**： - 视频讨论了查找协议的最新进展，特别是对数导数方法的应用。Ariel 介绍了三种主要的查找方法：基于多重集合相等的协议、基于对数导数的协议以及基于矩阵-向量乘法的协议。重点放在了对数导数方法及其变体上。 2. **关键论据和信息**： - **查找协议的三种主要方法**： - **多重集合相等**：包括 Halo 2 和 plookup 协议。 - **对数导数**：基于分数和的查找协议，如 logUp 和 cq 协议。 - **矩阵-向量乘法**：如 Baloo 和 Lasso 协议。 - **对数导数方法的基本引理**：通过定义向量 f 和 t，提出了一个查找条件，即存在一个向量 m，使得某个有理函数的等式成立，从而判断 f 是否包含在 t 中。 - **logUp 协议的实现**：通过承诺向量 m 和随机挑战 Beta，利用 Schwartz-Zippel 测试来验证查找条件。 - **cq 协议的优化**：在表格大小远大于见证的情况下，探讨如何在预处理后仍能保持查找协议的运行时间依赖于小 n。 - **GKR 协议的应用**：介绍了如何在不需要承诺大值的情况下，通过 GKR 协议来证明查找条件的有效性，尤其是在结构化电路的情况下。 总的来说，视频深入探讨了查找协议的不同方法及其实现细节，强调了对数导数方法在查找协议中的重要性，并介绍了如何通过 GKR 协议优化承诺过程。