Caulk

https://eprint.iacr.org/2022/621.pdf

Caulk来了！

论文作者为：Arantxa Zapico , Vitalik Buterin , Dmitry Khovratovich , Mary Maller , Anca Nitulescu , Mark Simkin （可以看到V神和Mary Maller都在里面）。

Caulk 进行零知识lookup证明和成员资格证明的速度比 Poseidon Merkle 树快 100 倍。Caulk 具有对数证明者、常数证明大小，且验证需要常数次配对。Setup是universal的， 可以使用公开的setup运行，例如 Zcash、Filecoin 或 Perpetual 的powers-of-tau。

对于成员资格证明，Caulk 证明一个Pedersen 承诺中包含一个匿名集中的值，可以比 Poseidon Merkle 树快 100 倍，不只因为证明者是对数时间，还因为不需要去算术化哈希函数。

对于lookup argument，Caulk 是一个重大突破。在之前我们甚至不知道lookup argument到底能不能达到亚线性，而Caulk是对数的，即 O(m^2 + m log(N)) （N是表的大小）。怎么做到的？

• 为 KZG（需要线性内存）预处理单个打开证明，以防止证明者每次执行线性数量的计算。
• 在隐藏位置证明 KZG 打开知识。
• 证明隐藏位置是第 N 个单位根。

提供了一个 Rust 实现，性能优于之前方案（RSA 累加器和 MT+zkSNARKs）几个数量级：

https://github.com/caulk-crypto/caulk