Blog
Apr 21, 2020
Pointproofs: Algorand Team Designs a New Commitment Scheme to Improve Blockchain Scalability
By: Sergey Gorbunov
Blockchain systems are inherently stateful. For instance, they capture information about users’ public keys, their balances, or smart contracts’ data. Subsequently, validators rely on state information to verify transactions. However, over the long-term, this state becomes unmanageable and causes multiple scalability issues. Furthermore, high storage requirements add friction to decentralization since only validators that can allocate large amounts of storage can participate in consensus.
Stateless blockchain model
A stateless blockchain model replaces on-chain storage with cryptographic commitments. For instance, a user can commit to her smart contract data and then append to her transaction the values that she wants to update with the associated cryptographic proofs. The traditional way to commit to a set of data, taken by Ethereum and other blockchains, is using Merkle Trees. Unfortunately, Merkle Trees are known to have very long proofs. For instance, a user that commits to 1000 values in a smart contract would need to propagate 320 bytes of additional data (cryptographic proof) to change just one of these values. In distributed networks, where every transaction propagates across all nodes, this can eat up a lot of network bandwidth and add substantial costs for nodes participating in the consensus.
To solve these problems, we designed a new commitment scheme — Pointproofs [1]. Pointproofs is a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. They enable a user to commit to a sequence of values V1, …, V_n, and provably reveal one or many values at specific positions at a later time. Both the commitment and the proof size is only 48-bytes. Moreover, Pointproofs enable any third party to aggregate a collection of proofs with respect to different, independently computed commitments (generated, for instance, by distinct users) into a single proof represented by an elliptic curve point of 48-bytes! Cross-commitments aggregation is a brand new property that none of the previous constructions achieved. Pointproofs also satisfy hiding properties: a commitment and proofs for some values reveal no information about the remaining values.
When applied to blockchain smart contracts, Pointproofs can reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state-of-art vector commitments (in specific instantiations; savings vary depending on the use-case).
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 aggregate proof.
In summary, Pointproofs can be used to reduce on-chain storage and minimize network bandwidth requirements, enabling more efficient decentralized networks.
Take a look at the white-paper and Algorand’s open-source implementation.
[1] “Pointproofs: Aggregating Proofs for Multiple Vector Commitments” by Sergey Gorbunov, Leonid Reyzin, Hoeteck Wee, and Zhenfei Zhang. The paper will appear at the ACM Conference on Computer and Communications Security 2020.
