## 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

### More

## 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.