License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AFT.2023.29
URN: urn:nbn:de:0030-drops-192184
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19218/
Go to the corresponding LIPIcs Volume Portal

Tas, Ertem Nusret ; Boneh, Dan

Vector Commitments with Efficient Updates

pdf-format:
LIPIcs-AFT-2023-29.pdf (1.0 MB)

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^ν and k^{1-ν} for any ν ∈ (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. While in practice, the construction is not yet competitive with Verkle commitments, our approach may point the way towards more performant vector commitments.

BibTeX - Entry

@InProceedings{tas_et_al:LIPIcs.AFT.2023.29,
  author =	{Tas, Ertem Nusret and Boneh, Dan},
  title =	{{Vector Commitments with Efficient Updates}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{29:1--29:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19218},
  URN =		{urn:nbn:de:0030-drops-192184},
  doi =		{10.4230/LIPIcs.AFT.2023.29},
  annote =	{Keywords: Vector commitments, stateless clients}
}

Keywords: Vector commitments, stateless clients
Collection: 5th Conference on Advances in Financial Technologies (AFT 2023)
Issue Date: 2023
Date of publication: 18.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI