Caulk: Lookup arguments in sublinear time
发表信息
作者
- Arantxa Zapico
- Vitalik Buterin
- Dmitry Khovratovich
- Mary Maller
- Anca Nitulescu
- Mark Simkin
笔记
We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or m values that comprise commitment all belong to the vector of size committed to in . Our construction can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude. For both single- and multi-membership proofs the protocol beats SNARKed Merkle proofs by the factor of 100 even if the latter is instantiated with Poseidon hash. Asymptotically our prover needs time to prove a batch of m openings, whereas proof size is and verifier time is . As a lookup argument, is the first scheme with prover time sublinear in the table size, assuming preprocessing time and storage. It can be used as a subprimitive in verifiable computation schemes in order to drastically decrease the lookup overhead. Our scheme comes with a reference implementation and benchmarks.
我们提出了向量承诺方案的位置隐藏可链接性：可以在零知识条件下证明构成承诺 cm 的一个或 m 个值都属于在承诺 C 中大小为 N 的向量。我们的构造方案 Caulk 可用于成员证明和查找论证，在证明者计算时间方面比所有现有方案都优越数个数量级。
对于单成员和多成员证明，Caulk 协议比经过 SNARK 处理的 Merkle 证明快 100 倍，即使后者使用 Poseidon 哈希函数实现。从渐近角度看，我们的证明者需要 O(m² + m log N) 时间来证明 m 个开启的批处理，而证明大小为 O(1)，验证者时间为 O(log(log N))。作为查找论证，Caulk 是首个证明者时间小于表大小的方案，前提是需要 O(N log N) 预处理时间和 O(N) 存储空间。它可以作为可验证计算方案中的子原语使用，从而大幅降低查找开销。
我们的方案附有参考实现和基准测试。