U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

Presentation

Modern zk-SNARKs (feat. Caulk)

June 15, 2022

Presenters

Mary Maller - Ethereum Foundation

Description

Note. The initially advertised title was "Caulk: Lookup Arguments in Sublinear Time", with the abstract below. The actual talk covered more broadly the topic of modern zk-SNARKs, though still including some notes on sublinear time lookup arguments.

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.

Paper reference: https://eprint.iacr.org/2022/621

Presented at

Crypto Reading Club talk on 2022-Jun-15

Downloads

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created June 29, 2022, Updated July 22, 2022