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:

1. in anonymous credentials to avoid SNARKs and Merkle tree
2. to multi-position opening where we have a single compact commitment $cm$ to all evaluations hiding the indexes as well
3. provable look-up table search to prove that the values in a VC are all in a look-up table
4. 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
5. an index-hiding VC could be used to do a “vector opening” version of the “set membership” work in here

More

More in Detail

https://docs.google.com/presentation/d/18B9aVpT3Z1KRbobkTTCbNNH3I_kSw5bviZvMEPH_CFY/embed?start=false&loop=false&amp

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

https://www.youtube.com/watch?v=uEssF2WzIeU

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.