a16z: On the Impossibility of "Stateless Blockchain"

Originally written by Miranda Christ and Joseph Bonneau

Compilation of the original text: Deep Tide TechFlow

As the blockchain supports more users and more frequent transactions, the amount of information (or “state”) stored by validators to verify transactions increases. For example, in Bitcoin, the state consists of a set of unspent transaction outputs (UTXOs). In Ethereum, the state consists of the account balance of each account and the code and storage of each smart contract.

As the blockchain grows with enough accounts or UTXOs to support real daily transactions for a sizable portion of the population, this storage burden will become unmanageable, making becoming a validator difficult and a threat to decentralization. A tantalizing solution is to turn to cryptography, where tools like Merkle trees and zero-knowledge proofs help us achieve things that were previously unimaginable.

This is exactly the goal of a “stateless blockchain”. But despite a lot of research on them, they are still far from being practical. But it turns out that this lag in progress is inherent—the gap between these builds and practicality will never be bridged. Our recent work shows that any stateless blockchain proposal, no matter how clever, is not feasible without additional measures to manage state. However, as we show at the end of this article, this improbability result should not be discouraging.

no status

Today, state is huge but manageable. For example, a Bitcoin node stores about 7 GB of data, and an Ethereum node stores about 650 GB of data. However, the storage burden on full nodes scales roughly linearly with the chain’s throughput (transactions per second, or TPS), which is still unacceptable today. As currently designed, the state required to truly support day-to-day transactions (tens to hundreds of thousands of transactions per second) would become unmanageable, requiring gigabytes or even petabytes of storage.

This has motivated people to find technical ways to significantly reduce the amount of state required by validators. Crucial is the implementation of a stateless blockchain, which would require validators to only store state of constant size regardless of transaction throughput (actually, the term is a misnomer: there is still state, just small enough, so as to be practical at any future throughput - usually constant size). This lightweight storage requirement will make it easier to run a validator node; optimistically, everyone can run a node on their phone. Since increasing the number of validators increases the security of the chain, it is important to lower the barrier to entry for validators.

Despite a great deal of research on stateless blockchains (e.g., by Todd, Buterin, Boneh et al., and Srinivasan et al.), they are far from practical, and to our knowledge, none have been deployed. The fundamental problem with all known stateless blockchains is that they require users to store additional data called witnesses to help validators verify transactions involving their accounts. For example, this witness could be a Merkle proof of inclusion showing that the user’s account and balance are included in the global state commitment. When users make transactions, they submit this witness to validators to show that their accounts have sufficient balances.

Unlike storing private keys, which never need to be changed, these witnesses change frequently, even for users who are not actively transacting, placing an unrealistic burden on users. Similarly, imagine if you were constantly monitoring all other credit card transactions globally and updating some local data accordingly to use your own credit card. For a blockchain to be practical, users must be able to interact with the blockchain offline and only when submitting transactions. In many cases, such as hardware wallets, updating witnesses is not only inconvenient, but impossible.

This leads us to a natural research question: Can we build a stateless blockchain that does not require frequent witness updates (or one that requires only infrequent witness updates)? To answer this question, we develop a novel theoretical framework (Revocable Proof System) that generalizes stateless blockchains. Using this framework, we demonstrate an improbable result: the trade-off between compact global state and frequent witness updates is inherently difficult to reconcile. Our proof technique is information-theoretic, which means that future computers will not be powerful enough to solve this problem: the gap between stateless blockchain construction and practicality will never be bridged.

Background of our research

To help understand our impossibility results, we first describe a natural but inefficient way to build stateless blockchains using Merkle trees. Our goal is to enable validators to determine whether a transaction submitted by a user is valid - for example, whether the user has sufficient account balance to make the transaction. In a stateless blockchain scheme, validators store a state of constant size. When users make a transaction, they must include a witness in the transaction. A validator can use the current state and the (transaction, witness) pair submitted by the user to verify that the user has sufficient account balance to make the transaction.

We first build a Merkle tree where each (account ID, balance) pair (a, b) is included as a leaf node. The constant-size state V stored by validators is the root of this tree, which acts as a commitment to a set of account balance pairs. Each user maintains their witness as a Merkle proof of inclusion. A Merkle proof of inclusion for a leaf (a,b) consists of partner nodes (v1,…,vk) along the path from that leaf to the root of the tree. Given a transaction by account a and a claimed balance b, a verifier can verify that b is indeed account a’s balance by checking the proof (v1,…,vk) of (a,b) against its current state V. If so, the validator executes the transaction and must update the account’s balance accordingly. A convenient property of Merkle trees is that, given a Merkle proof of inclusion for a leaf, it is easy to compute the root of the result when that leaf changes. In other words, the verifier can easily compute an updated state V’ that captures the new balance of account a after the transaction is executed.

This Merkle tree scheme has two major drawbacks. First, a user’s witness is relatively large, growing logarithmically with the total number of accounts in the system. Ideally, they should be of constant size, and we can achieve this using schemes such as RSA accumulators.

The second disadvantage is more difficult to avoid: every time another user makes a transaction, the proof of the account balance pair changes. Recall that the proof for a leaf node consists of the partner nodes on the path from that leaf node to the root of the tree. If the other leaf nodes change, one of the nodes will change, causing a real problem. Most blockchain users want to passively keep their coins in wallets and only go online when they want to make transactions. However, in such a stateless blockchain, users must constantly monitor other people’s transactions to keep their witness information up to date. While a third party could conduct this monitoring on behalf of the user, this deviates from the standard stateless blockchain model. In practice, this is an insurmountable challenge for stateless blockchains, placing a heavy burden on users.

Our conclusion: statelessness is not possible

This phenomenon does not only apply to this kind of Merkle tree structure - all known stateless blockchain schemes require users to update their witness information frequently, which we demonstrate here. More precisely, we show that the number of users who must update their witness information grows roughly linearly with the total number of transactions made by all users.

This means that even if user Alice does not make any transactions, her witness information may need to change with other users’ transactions. As long as the compact state stored by validators is too small to capture the full state (i.e. the set of all account balances), increasing the compact state size does little help. We plot this relationship shown below based on our theorem, along with the number of witness changes required per day for blockchains with different throughputs. These graphs show the number of times an optimal stateless blockchain would need to change witness information. Here, the data universe refers to the total number of accounts in the account model or the total number of UTXOs in the UTXO model.

At the heart of our proof is an information-theoretic argument. A central tenet of information theory, formalized by Claude Shannon, is that if Alice chooses an object at random from a set of size 2n, and wishes to tell Bob which object she has chosen, she must send him at least n bits. If there exists a stateless blockchain scheme where users rarely update their witness information, Alice can tell Bob which object she has chosen with less than n bits, which is impossible, as Shannon proved. Therefore, such a stateless blockchain does not exist.

For simplicity, we describe here a proof of a slightly weaker statement: there is no stateless blockchain where users never need to update their witness information. The point is that Alice uses a stateless blockchain scheme to encode her message to Bob. Initially, both Alice and Bob know the complete set of account balance pairs for all n users. Assume each account has at least one coin. Both Alice and Bob also know the succinct state V of the stateless blockchain and the witnesses wi of all account balance pairs (ai, bi). Alice and Bob also agree on a mapping between messages and sets of accounts. Alice will choose a set A of accounts corresponding to her message, and she will then spend coins from those accounts. She will use the stateless blockchain to communicate to Bob the set of her choice from which he can learn about her.

Encoding: Alice spends one coin from each account in A. Using a stateless blockchain scheme, Alice computes the updated state V’ and sends it to Bob.

Decoding: For each i, Bob checks whether Verify(wi, (ai, bi)) is true. Bob outputs the account set B such that Verify(wi, (ai, bi)) = false.

Bob successfully outputs the same set Alice chose: B = A. First, observe that if Alice spends a coin from account ai, the witness of its old balance should no longer be accepted—otherwise, Alice would be able to double-spend. Therefore, for each account ai in A, Verify(wi, (ai, bi)) = false, and Bob will include this account in B. On the other hand, Bob will never include in B accounts from which Alice did not spend coins, because the balances of these accounts remain the same, and (recall the relaxed statement we want to prove) their witnesses will never change. Therefore, B is exactly equal to A.

Finally, we resolve our contradiction by computing the number of bits that Alice should send to Bob. There are 2^n subsets she can choose, so according to Shannon’s law, she should send at least n bits to Bob. However, she only sends a constant-sized state V’, which is much shorter than n bits.

Although we used a stateless blockchain when describing our proof, Alice and Bob can perform similar efficient communication using a variety of other authenticated data structures, including accumulators, vector commitments, and authenticated dictionaries. We formalize such data structures using a new abstraction that we call a reversible proof system.

Effect of the result

Our results show that you cannot “cryptographically eliminate state”, and that there is no silver bullet for a commitment scheme that allows us to build a stateless blockchain where users never have to update their witnesses. The state does not disappear, but is transferred from validators and pushed to users in the form of frequent witness updates.

Some other promising solutions exist that deviate from the strictly stateless blockchain model. A natural relaxation of this model is to allow a third party (neither users nor validators) to be responsible for storing the complete state. This third party, called a proof service node, uses the complete state to generate the latest witness information for the user. Users can then transact using these witnesses as in a regular stateless blockchain, where validators still only store compact state. The incentive mechanism of this system, especially how users compensate proof-of-service nodes, is an interesting open research direction.

While our discussion so far has focused on L1 blockchains, our results also have implications for L2 systems such as Rollup servers. Rollups (whether Optimistic or ZK) typically store a commitment to a large state on L1 with a small value. This state includes every user’s account on L2. We want these users to be able to withdraw funds directly on L1 (without the cooperation of L2 servers), by publishing a witness to their current account balance. This setup is also an instance of a reversible proof system in our model. In fact, it can be argued that stateless blockchains are already implemented in practice, in the form of L2 Rollups.

Unfortunately, however, this means that our impossibility results apply directly. A user’s Rollup fetch witness must change frequently, otherwise almost the entire L2 state would have to be written to L1. As a result, Rollups today typically assume the existence of a data availability committee (sometimes called a “validium”), similar to a “proof service node” that helps users compute new witnesses when they are ready to pull. Our results show that the warning to users in the Ethereum documentation: “Without transaction data, users cannot compute Merkle proofs to prove ownership of funds and perform withdrawals.” will always apply.