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 (i.e., state) that validators store to verify transactions increases. For example, in Bitcoin, state consists of a set of unspent transaction outputs (UTXOs). In Ethereum, state consists of the account balance of each account and the code and storage of each smart contract.
As a blockchain grows with enough accounts or UTXOs to support real daily transactions for a significant portion of the population, this storage burden will become unmanageable, making it difficult to become a validator and posing a threat to decentralization. The tempting 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 extensive research on them, they are still far from 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 scheme, no matter how clever, is unfeasible without additional measures to manage state. However, as we show at the end of this article, the improbability of this outcome should not be discouraging.
no status
Today, state is huge but manageable. For example, Bitcoin nodes store approximately 7 GB of data, and Ethereum nodes store approximately 650 GB of data. However, the storage burden of a full node grows roughly linearly with the chain’s throughput (transactions per second, or TPS), which is still unacceptable today. With current designs, the state required to truly support daily transactions (tens to hundreds of thousands of transactions per second) will become unmanageable, requiring the use of gigabytes or even petabytes of storage space.
This has prompted people to look for technical ways to significantly reduce the amount of state required by validators. It is crucial to implement a stateless blockchain, which would require validators to only store a constant size of state, regardless of transaction throughput (actually, this 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 running a validator node much easier; optimistically, everyone will be able to 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.
Although there has been considerable research on stateless blockchains (e.g., by Todd, Buterin, Boneh et al., and Srinivasan et al.), they are still 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 might be a Merkle inclusion proof showing that the users account and balance are included in the global state commitment. When users make a transaction, they submit this witness to the validator to show that their account has sufficient balance.
Unlike storing private keys, which never need to be changed, these witnesses change frequently, even for users who are not actively trading, placing an unrealistic burden on users. Similarly, imagine if you were constantly monitoring all other credit card transactions around the world and updating some local data accordingly for your own credit card. For a blockchain to be practical, users must be able to go offline and interact with the blockchain only when submitting transactions. In many cases, such as hardware wallets, updating a witness is not only inconvenient, but impossible.
This leads us to ask a natural research question: Can we build a stateless blockchain that does not require frequent witness updates (or a blockchain that only requires rarely updated witnesses)? To answer this question, we develop a novel theoretical framework (revocable proof system) that generalizes stateless blockchains. Using this framework, we demonstrate an impossibility: the trade-off between concise global state and frequent witness updates is inherently difficult to reconcile. Our proof technology 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 a stateless blockchain 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 perform the transaction. In a stateless blockchain scheme, the validator stores a constant size state. When users make a transaction, they must include a witness with the transaction. Validators can use the current state and user-submitted (transaction, witness) pairs to verify that the user has sufficient account balance to conduct transactions.
We first build a Merkle tree in which each (account ID, balance) pair (a, b) is included as a leaf node. The constant-size state V stored by the validator is the root of this tree, which serves as a commitment to a set of account balance pairs. Each user maintains their witness as a Merkle containing proof. The Merkle inclusion proof of a leaf (a, b) consists of the partner nodes (v1,…,vk) along the path from that leaf to the root of the tree. Given a transaction by account a and claimed balance b, the verifier can verify whether b is indeed the balance of account a by checking the proof (v1,...,vk) of (a, b) with its current state V. If so, the validator executes the transaction and must update the accounts balance accordingly. A convenient property of Merkle trees is that, given a Merkle containing proof of 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, user testimonials are relatively large, growing logarithmically with the total number of accounts in the system. Ideally, they should be constant size, and we can achieve this using schemes such as RSA accumulators.
The second drawback is harder to avoid: every time another user makes a transaction, the proof of the account balance pair changes. Recall that the proof of a leaf node consists of the partner nodes on the path from that leaf node to the root of the tree. If other leaf nodes change, one of the nodes will change, causing actual problems. 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 third parties can conduct this monitoring on behalf of users, this deviates from the standard stateless blockchain model. In fact, this is an insurmountable challenge for stateless blockchains, placing a heavy burden on users.
Our Conclusion: Statelessness Is Impossible
This phenomenon does not only apply to this Merkle tree structure - all known stateless blockchain schemes require users to frequently update their witness information, as 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 the validator is too small to capture the complete state (i.e. the set of all account balances), increasing the size of the compact state helps little. We plotted this relationship shown below based on our theorem, and the number of attestation information changes required per day for blockchains with different throughputs. These graphs show the number of times an optimal stateless blockchain needs 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.
The core of our proof is an information-theoretic argument. A core principle of information theory, formalized by Claude Shannon, is that if Alice randomly selects an object from a set of size 2 n and wishes to tell Bob which object she has selected, she must send him at least n bits. If there is a stateless blockchain scheme where users rarely update their witness information, Alice can tell Bob which object she chose in less than n bits, which is impossible, as Shannon demonstrated. 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. It is assumed that 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 calculates 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 calculating the number of bits Alice should send to Bob. There are 2 to the nth power of subsets that she can choose, so according to Shannons law, she should send at least n bits to Bob. However, she only sends a constant size state V, which is much shorter than n bits.
Although we use a stateless blockchain when describing our proof, Alice and Bob can perform similarly efficient communication using a variety of other authenticated data structures, including accumulators, vector commitments, and authenticated dictionaries. We formalize this type of data structure using a new abstraction that we call a revocable proof system.
impact of results
Our results show that you cannot cryptographically eliminate state and that there is no magic bullet for a commitment scheme that allows us to build a stateless blockchain where users never have to update their witnesses. State does not disappear, but is moved away from validators and pushed to users in the form of frequent witness updates.
There are other promising solutions that deviate from the strict stateless blockchain model. A natural relaxation of this model is to allow a third party (neither user nor validator) to be responsible for storing the complete state. This third party, called the attestation service node, uses the complete state to generate the latest attestation information for the user. Users can then conduct transactions using this witness information as in a regular stateless blockchain, where validators still only store concise state. The incentive mechanism of this system, especially how users compensate proof 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 status includes each users 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 users 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.
