Paper 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