Title: Linear-map Vector Commitments and their Practical
Applications
Abstract. Vector commitments (VC) are a cryptographic
primitive that allows one to commit to a vector and then
“open” some of its positions efficiently by showing a small
proof. Vector commitments are increasingly recognized as
a central tool to scale highly decentralized networks of
large size and whose content is dynamic.
In this talk, we study a generalisation to linear-map openings
for vector commitments (LVC) and examine the demands
on the properties that a vector commitment should satisfy
in the light of the emerging plethora of applications: updatability
for commitments and openings, unbounded aggregation for
openings, linear homomorphism, and maintainability for stored
proofs of opening.
We propose new constructions that improve the state-of-the-art
in several dimensions and offer new trade-offs. We first present
two pairing-based VC constructions that allow openings to inner
products IP based on the properties of monomial and Lagrange
polynomial basis. Then extend them to generic LVC via aggregation.
Secondly, we show how to build a tree-based maintainable VC
scheme that can be instantiated from any underlying VC scheme
with homomorphic proofs of opening. We show how to achieve
a stronger, more flexible form of maintainability: our schemes
allow us to arbitrarily tune the memory used to save on the
opening time to obtain the desired trade-off.
Our focus is on building efficient schemes that do not require
a new trusted setup (we can reuse existing ceremonies for other
pairing-based schemes, such as “powers of tau” run by real-world
systems such as Zcash or Filecoin) and add maintainability to
existing VC or membership proofs (e.g. to Caulk).
We then show how these properties can be useful in the practical
setting of stateless cryptocurrencies, a payment system based
on a distributed ledger where neither validators of transactions
nor system users need to store the full ledger state.
