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 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 are also (publicly) committed to in a committed table .
Position-hiding refers to the fact that no information about which elements were taken to
construct should be leaked.
Caulk can be used for the case of proving membership of a single element ()
Caulk extension to -subsets () 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 elements.
- MTPos-8: SNARKed Merkle tree with Poseidon hashes and elements.
- RSA Harisa: RSA-2048 accumulator for vectors of size elements.
- Caulk-8: Caulk for vectors of size elements.
- Caulk-20: Caulk for vectors of size 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.
