Cryptology ePrint Archive: Report 2020/527

Aggregatable Subvector Commitments for Stateless Cryptocurrencies

Alin Tomescu and Ittai Abraham and Vitalik Buterin and Justin Drake and 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.

Category / Keywords: public-key cryptography / vector-commitments, stateless-cryptocurrency, kate-zaverucha-goldberg, kzg, polynomial-commitments, authenticated-data-structures

Original Publication (with major differences): SCN 2020

Date: received 5 May 2020, last revised 21 Jul 2020

Contact author: alint at vmware com

Available format(s): PDF | BibTeX Citation

Note: Extended version of SCN 2020 paper.

Version: 20200722:033729 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]