Paper 2023/1830

Vector Commitments with Efficient Updates

Ertem Nusret Tas, Stanford University
Dan Boneh, Stanford University
Abstract

Dynamic vector commitments that enable local updates of opening proofs have applications ranging from verifiable databases with membership changes to stateless clients on blockchains. In these applications, each user maintains a relevant subset of the committed messages and the corresponding opening proofs with the goal of ensuring a succinct global state. When the messages are updated, users are given some global update information and update their opening proofs to match the new vector commitment. We investigate the relation between the size of the update information and the runtime complexity needed to update an individual opening proof. Existing vector commitment schemes require that either the information size or the runtime scale linearly in the number $k$ of updated state elements. We construct a vector commitment scheme that asymptotically achieves both length and runtime that is sublinear in $k$, namely $k^\nu$ and $k^{1-\nu}$ for any $\nu \in (0,1)$. We prove an information-theoretic lower bound on the relation between the update information size and runtime complexity that shows the asymptotic optimality of our scheme. For $\nu = 1/2$, our constructions outperform Verkle commitments by about a factor of $2$ in terms of both the update information size and runtime, but makes use of larger public parameters.

Note: Related work section was expanded.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. 5th Conference on Advances in Financial Technologies (AFT 2023)
DOI
10.4230/LIPICS.AFT.2023.29
Keywords
vector commitmentsstateless clients
Contact author(s)
nusret @ stanford edu
dabo @ cs stanford edu
History
2024-05-04: revised
2023-11-28: received
See all versions
Short URL
https://ia.cr/2023/1830
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1830,
      author = {Ertem Nusret Tas and Dan Boneh},
      title = {Vector Commitments with Efficient Updates},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1830},
      year = {2023},
      doi = {10.4230/LIPICS.AFT.2023.29},
      url = {https://eprint.iacr.org/2023/1830}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.