Vector Commitments for Stateless Cryptocurrencies
Recently, Merkle trees have been proposed as a way to scale block validation in cryptocurrencies such as Ethereum (or Bitcoin). The key insight is that block validators can verify Merkle proofs of account balances (or of unspent coins) against a Merkle root of the cryptocurrency’s state (i.e., the database of every user’s balance). This so-called stateless validation approach eliminates the need for block validators (e.g., miners, P2P nodes) to store large amounts of data and access it from disk during validation, which can be slow. At the same time, stateless validation no longer requires block validators in sharded cryptocurrencies to transfer large amounts of state whenever they switch shards, which could help scalability. Finally, stateless validation could significantly lower the barrier to entry for new nodes in the P2P network.
Although Merkle trees have the computational efficiency required for stateless validation, they lack the necessary functionality. First, Merkle proofs cannot be aggregated efficiently, which makes the proof size for a block of transactions too large. Second, Merkle root hashes cannot be updated after a change to the state, unless a Merkle proof for the changed data is given as an update hint, which is not always possible. Similarly, Merkle proofs cannot be updated either, unless an update hint is given. This need to provide update hints doubles the proof overhead in Merkle-based stateless cryptocurrencies.
In this talk, we present two alternatives to Merkle trees that address these limitations. First, we present authenticated multipoint evaluation trees (AMTs), which support efficient proof updates and digest updates without requiring update hints. Importantly, AMT proofs are as big as Merkle proofs although, due to their algebraic nature, they are slower to compute. Second, we present aggregatable subvector commitments (aSVCs), which in addition to proof and digest updates also support proof aggregation. Furthermore, aSVC proofs are constant-sized and much smaller than Merkle proofs in practice. They are also almost as fast to compute as AMT proofs. Although our constructions improve Merkle trees in multiple ways, they create new computational efficiency challenges, which we hope to address in future work.
Alin was born and raised in Pitești, a small city in Romania, and moved to the US in 2008. He enjoys cryptography, motorcycles and managing his academic bibliography using CK. Alin blogs often about some of these on alinush.github.io and on decentralizedthoughts.github.io.
Currently, Alin is a Postdoctoral Researcher at VMware Research, where he likes to mix his love for authenticated data structures with his generalized anxiety about consensus protocols. In the past, Alin has tried to make logs transparent, signatures thresholdized and cryptocurrencies anonymous. In general, if you give Alin a polynomial, you can be sure he will commit to it using KZG and try to make some sort of Merkle tree out of it.