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, give an efficient construction in prime-order groups from constant-sized polynomial commitments and use it to bootstrap a highly-efficient stateless cryptocurrency.

Our aSVC supports (1) computing all $n$ $O(1)$-sized proofs in $O(n\log{n})$ time, (2) updating a proof in $O(1)$ time and (3) aggregating $b$ proofs into an $O(1)$-sized subvector proof in $O(b\log^2{b})$ time. Importantly, our scheme has an $O(n)$-sized proving key, an $O(1)$-sized verification key and $O(1)$-sized update keys. In contrast, previous schemes with constant-sized proofs in prime-order groups either (1) require $O(n^2)$ time to compute all proofs, (2) require $O(n)$-sized update keys to update proofs in $O(1)$ time, or (3) do not support aggregating proofs. Furthermore, schemes based on hidden-order groups either (1) have larger concrete proof size and computation time, or (2) do not support proof updates.

We use our aSVC to obtain a stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block's proof overhead to just one group element, which is optimal. In contrast, previous work required $O(b\log{n})$ group elements, where $b$ is the number of transactions per block. Furthermore, our smaller proofs reduce the block verification time from $O(b\log{n})$ pairings to just two pairings and an $O(b)$-sized multi-exponentiation. Lastly, our aSVC's smaller update keys only take up $O(b)$ block space, compared to $O(b\log{n})$ in previous work. Also, their zverifiability reduces miner storage from $O(n)$ to $O(1)$. The end result is a stateless cryptocurrency that concretely and asymptotically outperforms the state of the art

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

Date: received 5 May 2020

Contact author: alint at vmware com

Available format(s): PDF | BibTeX Citation

Version: 20200505:225400 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]