Cryptology ePrint Archive: Report 2020/419

Pointproofs: Aggregating Proofs for Multiple Vector Commitments

Sergey Gorbunov and Leonid Reyzin and Hoeteck Wee and Zhenfei Zhang

Abstract: Vector commitments enable a user to commit to a sequence of values and provably reveal one or many values at specific positions at a later time. In this work, we construct Pointproofs--a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. Our construction enables any third party to aggregate a collection of proofs with respect to different, independently computed commitments into a single proof represented by an elliptic curve point of 48-bytes. In addition, our scheme is hiding: a commitment and proofs for some values reveal no information about the remaining values.

We build Pointproofs and demonstrate how to apply them to blockchain smart contracts. In our example application, Pointproofs reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state-of-art vector commitments.

Pointproofs are also efficient: on a single-thread, it takes 0.08 seconds to generate a proof for 8 values with respect to one commitment, 0.25 seconds to aggregate 4000 such proofs across multiple commitments into one proof, and 23 seconds (0.7 ms per value proven) to verify the aggregated proof.

Category / Keywords: commitments, blockchain, aggregation

Original Publication (with minor differences): ACM CCS 2020

Date: received 13 Apr 2020, last revised 7 Jun 2020

Contact author: reyzin at bu edu

Available format(s): PDF | BibTeX Citation

Note: Added references to recent work plus minor corrections.

Version: 20200607:151530 (All versions of this report)

Short URL: ia.cr/2020/419