a16z: On the Impossibility of "Stateless Blockchains"
TechFlow Selected TechFlow Selected
a16z: On the Impossibility of "Stateless Blockchains"
The state has not disappeared, but has been moved out of the validators' hands and pushed to users in the form of frequent witness updates.
Navigating Web3 tides with focused insightsWritten by: Miranda Christ, Joseph Bonneau
Compiled by: TechFlow
As blockchains support more users and more frequent transactions, the amount of information validators must store to verify transactions—known as “state”—also grows. In Bitcoin, for example, state consists of a set of unspent transaction outputs (UTXOs). In Ethereum, state includes each account’s balance, along with the code and storage of every smart contract.
As blockchains grow large enough to support a significant portion of the population conducting everyday transactions, this storage burden becomes unmanageable, making it difficult to become a validator and threatening decentralization. A compelling solution is to turn to cryptography, where tools such as Merkle trees and zero-knowledge proofs enable what once seemed impossible.
This is precisely the goal of “stateless blockchains.” Yet despite extensive research, they remain far from practical. It turns out this lack of progress is inherent—the gap between their construction and practicality can never be bridged. Our recent work shows that without additional mechanisms to manage state, any stateless blockchain scheme, no matter how clever, is infeasible. However, as we show at the end of this article, this impossibility result should not be discouraging.
Statelessness
Today, state is large but manageable. For instance, Bitcoin nodes store about 7 GB of data, while Ethereum nodes store around 650 GB. However, the storage burden on full nodes grows roughly linearly with the chain’s throughput (transactions per second, or TPS), and current throughput remains unacceptably low. Under current designs, the state required to support truly everyday transaction volumes—tens or hundreds of thousands of TPS—would become unmanageable, requiring terabytes or even petabytes of storage.
This motivates the search for technical solutions to significantly reduce the amount of state validators need to store. Crucially, this leads to the idea of stateless blockchains, which would require validators to store only a constant-sized state, regardless of transaction throughput (in practice, this term is a misnomer: state still exists, but is small enough to remain practical at any future throughput—typically of constant size). This lightweight storage requirement would make running a validator node much easier; optimistically, everyone could run a node on their phone. Since increasing the number of validators enhances chain security, lowering the barrier to entry for validators is crucial.
Despite substantial research into stateless blockchains (e.g., by Todd, Buterin, Boneh et al., and Srinivasan et al.), they remain far from practical, and to our knowledge, none have been deployed. The fundamental issue with all known stateless blockchain schemes is that they require users to store additional data called *witnesses* to help validators verify transactions involving their accounts. For example, a witness might be a Merkle inclusion proof showing that a user’s account and balance are included in a global state commitment. When a user submits a transaction, they include this witness to prove their account has sufficient funds.
Unlike private keys, which never need changing, these witnesses change frequently—even for users who do not actively transact—imposing an impractical burden. Imagine, for instance, having to constantly monitor all other credit card transactions globally and update local data accordingly just to use your own card. For blockchains to be practical, users must be able to stay offline and interact with the chain only when submitting transactions. In many cases—such as with hardware wallets—updating witnesses is not merely 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 requires them very rarely? To answer this, we developed a novel theoretical framework—revocable proof systems—that generalizes stateless blockchains. Using this framework, we prove an impossibility result: the trade-off between succinct global state and frequent witness updates is inherently irreconcilable. Our proof technique is information-theoretic, meaning no future computational advances will overcome it—the gap between stateless blockchain constructions and practicality can never be closed.
Background of Our Research
To help understand our impossibility result, we first describe a natural but inefficient way to build a stateless blockchain using Merkle trees. Our goal is to allow validators to determine whether a user-submitted transaction is valid—e.g., whether the user has sufficient account balance. In a stateless blockchain scheme, validators store only a constant-sized state. When a user transacts, they must include a witness in the transaction. Validators use the current state and the (transaction, witness) pair to verify that the user has sufficient balance.
We begin by constructing a Merkle tree where each (account ID, balance) pair (a, b) is included as a leaf. The constant-sized state V stored by validators is the root of this tree, serving as a commitment to the set of account balances. Each user maintains their witness as a Merkle inclusion proof. A Merkle inclusion proof for a leaf (a, b) consists of the sibling nodes (v₁,…,vₖ) along the path from the leaf to the root. Given a transaction from account a claiming balance b, a validator verifies b is indeed a’s balance by checking the proof (v₁,…,vₖ) against the current state V. If valid, the validator executes the transaction and updates the account’s balance. A convenient property of Merkle trees is that, given a leaf’s inclusion proof, computing the new root after a change to that leaf is easy. That is, validators can efficiently compute an updated state V’ reflecting the new balance of account a.
This Merkle tree scheme has two major drawbacks. First, user witnesses are relatively large, growing logarithmically with the total number of accounts in the system. Ideally, they should be of constant size, which can be achieved using schemes like RSA accumulators.
The second drawback is harder to avoid: whenever another user conducts a transaction, the proof for an account balance pair changes. Recall that a leaf’s proof consists of the sibling nodes along its path to the root. If any other leaf changes, one of these nodes changes, causing practical problems. Most blockchain users want to passively hold coins in their wallets and go online only when transacting. However, in this stateless blockchain, users must continuously monitor others’ transactions to keep their witnesses up to date. While third parties could perform this monitoring on behalf of users, this deviates from the standard stateless blockchain model. In practice, this presents an insurmountable challenge, imposing a heavy burden on users.
Our Conclusion: Statelessness Is Impossible
This phenomenon is not limited to Merkle tree constructions—all known stateless blockchain schemes require users to frequently update their witnesses, and we prove this here. More precisely, we show that the number of users required to update their witnesses grows roughly linearly with the total number of transactions conducted by all users.
This means that even if user Alice performs no transactions, her witness may still need to change due to transactions by other users. As long as the succinct state stored by validators is too small to fully capture the complete state (i.e., the full set of account balances), increasing its size offers little help. We illustrate this relationship below based on our theorem, showing the number of required witness updates per day for blockchains of different throughputs. These graphs depict the minimum number of witness updates required even under the best possible stateless blockchain design. Here, "data universe" refers to the total number of accounts in an account model or the total number of UTXOs in a UTXO model.
At the core of our proof is an information-theoretic argument. A central principle of information theory, formalized by Claude Shannon, states that if Alice randomly selects an object from a set of size 2ⁿ and wants to tell Bob which one she chose, she must send him at least n bits. If a stateless blockchain scheme existed where users rarely updated their witnesses, Alice could communicate her choice to Bob using fewer than n bits—contradicting Shannon’s proven lower bound. Therefore, such a stateless blockchain cannot exist.
For simplicity, we describe a slightly weaker version of the proof: there is no stateless blockchain where users never need to update their witnesses. The key idea is that Alice uses a stateless blockchain scheme to encode a message to Bob. Initially, both Alice and Bob know the full set of n users’ account-balance pairs. Assume each account holds at least one coin. Both also know the succinct state V of the stateless blockchain and the witness wᵢ for each (aᵢ, bᵢ). They agree on a mapping between messages and subsets of accounts. Alice selects a subset A corresponding to her message and spends one coin from each account in A. She uses the stateless blockchain to convey this choice to Bob, who infers the message from A.
Encoding: Alice spends one coin from each account in A. Using the stateless blockchain scheme, she computes the updated state V’ and sends it to Bob.
Decoding: For each i, Bob checks whether Verify(wᵢ, (aᵢ, bᵢ)) is true. Bob outputs the set B of accounts for which Verify(wᵢ, (aᵢ, bᵢ)) = false.
Bob successfully recovers Alice’s chosen set: B = A. First, observe that if Alice spent a coin from account aᵢ, the old balance’s witness should no longer be accepted—otherwise, Alice could double-spend. Thus, for each aᵢ in A, Verify(wᵢ, (aᵢ, bᵢ)) = false, so Bob includes aᵢ in B. Conversely, Bob never includes an account Alice did not spend from, because its balance remains unchanged—and by assumption (the relaxed statement we’re proving), its witness never changes. Hence, B exactly equals A.
Finally, we reach a contradiction by calculating how many bits Alice sent. There are 2ⁿ possible subsets, so by Shannon’s law, she must send at least n bits. Yet she only sent the constant-sized state V’, which is much shorter than n bits.
Although we described the proof using stateless blockchains, Alice and Bob could achieve similar efficient communication using other authenticated data structures, including accumulators, vector commitments, and authenticated dictionaries. We formalize this class of structures using a new abstraction we call revocable proof systems.
Implications of the Result
Our result shows you cannot “eliminate state via cryptography.” There is no magical commitment scheme that enables building a stateless blockchain where users never need to update their witnesses. State does not disappear—it is shifted away from validators and pushed onto users in the form of frequent witness updates.
There are, however, other promising approaches that relax the strict stateless blockchain model. One natural relaxation allows a third party—neither user nor validator—to store the full state. This third party, called a proof service node, uses the full state to generate up-to-date witnesses for users. Users then use these witnesses to transact, just as in a conventional stateless blockchain, while validators still store only a succinct state. The incentive mechanisms for this system—particularly how users compensate the proof service node—are an interesting open research direction.
While our discussion so far focused on L1 blockchains, our results also impact L2 systems such as rollup servers. Rollups—whether optimistic or ZK—typically store a commitment to a large state on L1 using a small value. This state includes the account of each user on L2. We want users to be able to directly withdraw funds on L1 (without cooperation from the L2 server) by publishing a witness to their current account balance. This setup is also an instance of a revocable proof system in our model. Indeed, one could argue that stateless blockchains have already been realized in practice in the form of L2 rollups.
Unfortunately, this means our impossibility result applies directly. Users’ rollup withdrawal witnesses must change frequently, or nearly the entire L2 state must be written to L1. As a result, most rollups today assume the existence of a data availability committee (sometimes called “validium”), analogous to a “proof service node,” that helps users compute new witnesses when preparing withdrawals. Our result confirms that warnings in Ethereum documentation—such as “Without transaction data, users cannot compute Merkle proofs to prove ownership of funds and execute withdrawals”—will always remain applicable.
Join TechFlow official community to stay tuned
Telegram:https://t.me/TechFlowDaily
X (Twitter):https://x.com/TechFlowPost
X (Twitter) EN:https://x.com/BlockFlow_News
a16z
