Caulk: Lookup Arguments in Sublinear Time

What is Caulk?
Possible Applications of Caulk
More
More in Detail
Watch the talk
Comparison with other works
Comparison for single openings:
Comparison for lookup tables with many openings:

What is Caulk?

A linkable vector commitment scheme which allows one to prove in zero-knowledge that a committed value is contained in a public vector commitment. For a vector commitment of size N, we achieve O(log(N)) online prover time assuming O(N log(N)) preprocessing and O(N) storage.

DRI: Anca Nitulescu

Joint work with: Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Mark Simkin

Paper: Caulk: Lookup Arguments in Sublinear Time in CCS22

Possible Applications of Caulk

For privacy-preserving applications it is vital to make proofs zero-knowledge, i.e. hiding the element that is asserted to be in a commitment to a big table, while still establishing a certain relationship, or link, to that element.

Applications include membership proofs, ring signatures, anonymous credentials and other schemes:

in anonymous credentials to avoid SNARKs and Merkle tree
to multi-position opening where we have a single compact commitment $cm$ to all evaluations hiding the indexes as well
provable look-up table search to prove that the values in a VC are all in a look-up table
for PoS we can have a commitment to the indexes in a set one published as a challenge and then, the prover can use it to open and the verifier will only need to trust this commitment cm and efficiently check the opening with respect to it
an index-hiding VC could be used to do a “vector opening” version of the “set membership” work in here

‣

A vector commitment to $𝑐 = (𝑐_1, . . . , 𝑐_𝑁 )$ is linkable, if it permits proving that you know a secret $𝑠_𝑖$ mathematically linked to $𝑐_𝑖$ . The simplest example is a proof of authorization where a party proves knowledge of a secret key belonging to one of multiple public keys in a set.

A more elaborate example is a proof of coin ownership in private cryptocurrencies:

coins are stored as hashes of a secret $𝑘$ and values $𝑣$ in a list or a tree
to spend $𝑣$ one proves knowledge of $𝑣$ and $𝑘$ without revealing them.

A third example are lookup arguments in verifiable computation: prove that intermediate values $𝑎_1, 𝑎_2, \dots , 𝑎_𝑚$ are all contained in a certain table, e.g., a table of all 16-bit numbers for the purpose of overflow checks in financial or mathematical computations.

More in Detail

Caulk is a special case of a more general family of protocols that add a property called position-hiding linkability to vector commitment schemes.

This primitive asserts that all (hidden) entries committed in an element $cm$ are also (publicly) committed to in a committed table $C$ .

Position-hiding refers to the fact that no information about which elements were taken to

construct $cm$ should be leaked.

Caulk can be used for the case of proving membership of a single element ( $𝑚 = 1$ )

Caulk extension to $𝑚$ -subsets ( $𝑚 > 1$ ) proofs, with some values from the subvector possibly repeating can be seen as a lookup table, and is thus a prover efficient alternative to schemes such as Plookup.

Watch the talk

Comparison with other works

Comparison for single openings:

Caulk for vectors of size $𝑁$ elements.
MT-Pos: SNARKed Merkle Poseidon tree with $𝑁$ elements.
MT-SHA: SNARKed Merkle SHA-2 tree with $𝑁$ elements.
RSA Acc Harisa: RSA-2048 accumulator of $𝑁$ elements.

Comparison for lookup tables with many openings:

MTPos-20: SNARKed Merkle tree with Poseidon hashes and $𝑁 = 2^{20}$ elements.
MTPos-8: SNARKed Merkle tree with Poseidon hashes and $𝑁 = 2^{8}$ elements.
RSA Harisa: RSA-2048 accumulator for vectors of size $𝑁 = 2^{16}$ elements.
Caulk-8: Caulk for vectors of size $𝑁 = 2^{8}$ elements.
Caulk-20: Caulk for vectors of size $𝑁 = 2^{20}$ elements.

Caulk’s prover is almost 100 times as fast as Merkle trees instantiated with a Poseidon Hash and Groth16 zkSNARK on top, and 10 times as fast as the RSA accumulator. Although the latter stays constant while Caulk’s time grows slowly, Caulk will still perform better for all values $𝑁$ that can be consider practical.

The performance of the prover in RSA accumulators is independent on the size of the vector. Caulk is faster than Harisa for all the values of $𝑁$ we were able to compute, but approaches as $𝑁$ grows, and will perform worse for bigger tables. Also, we consider small values for $𝑚$ (up to 50) but we expect that for larger values of $𝑚$ the quadratic component of Caulk’s prover time would make it unpractical. Both constructions are significantly faster than Merkle-SNARK.