Paper 2020/527

Aggregatable Subvector Commitments for Stateless Cryptocurrencies

Alin Tomescu, Ittai Abraham, Vitalik Buterin, Justin Drake, Dankrad Feist, and Dmitry Khovratovich

Abstract

An aggregatable subvector commitment (aSVC) scheme is a vector commitment (VC) scheme that can aggregate multiple proofs into a single, small subvector proof. In this paper, we formalize aSVCs and give a construction from constant-sized polynomial commitments. Our construction is unique in that it has linear-sized public parameters, it can compute all constant-sized proofs in quasilinear time, it updates proofs in constant time and it can aggregate multiple proofs into a constant-sized subvector proof. Furthermore, our concrete proof sizes are small due to our use of pairing-friendly groups. We use our aSVC to obtain a payments-only stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block’s proof overhead to a single group element, which is optimal. Furthermore, our subvector proofs speed up block verification and our smaller public parameters further reduce block size.

Note: Extended version of SCN 2020 paper. For an errata, see the latest GitHub diffs: https://github.com/alinush/asvc-paper/compare/b64131d..master

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. SCN 2020
Keywords
vector-commitmentsstateless-cryptocurrencykate-zaverucha-goldbergkzgpolynomial-commitmentsauthenticated-data-structures
Contact author(s)
atom @ alum mit edu
History
2021-06-03: last of 3 revisions
2020-05-05: received
See all versions
Short URL
https://ia.cr/2020/527
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/527,
      author = {Alin Tomescu and Ittai Abraham and Vitalik Buterin and Justin Drake and Dankrad Feist and Dmitry Khovratovich},
      title = {Aggregatable Subvector Commitments for Stateless Cryptocurrencies},
      howpublished = {Cryptology ePrint Archive, Paper 2020/527},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/527}},
      url = {https://eprint.iacr.org/2020/527}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.