Paper 2022/621

Caulk: Lookup Arguments in Sublinear Time

Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, and Mark Simkin

Abstract

We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or $m$ values that comprise commitment cm all belong to the vector of size $N$ committed to in C. Our construction Caulk 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 Caulk beats SNARKed Merkle proofs by the factor of 100 even if the latter instantiated with Poseidon hash. Asymptotically our prover needs $O(m^2 + m\log N)$ time to prove a batch of $m$ openings, whereas proof size is $O(1)$ and verifier time is $O(\log(\log N))$. As a lookup argument, Caulk is the first scheme with prover time sublinear in the table size, assuming $O(N\log N)$ preprocessing time and $O(N)$ 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
arantxa zapico @ upf edu
mary maller @ ethereum org
khovratovich @ gmail com
History
2022-05-23: received
Short URL
https://ia.cr/2022/621
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/621,
      author = {Arantxa Zapico and Vitalik Buterin and Dmitry Khovratovich and Mary Maller and Anca Nitulescu and Mark Simkin},
      title = {Caulk: Lookup Arguments in Sublinear Time},
      howpublished = {Cryptology ePrint Archive, Paper 2022/621},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/621}},
      url = {https://eprint.iacr.org/2022/621}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.