Author: Miranda Christ (Ph.D student in computer science at Columbia University/a16z encryption research intern), Joseph Bonneau (a16zcrypto) Source: a16z crypto; Compiler: Yvonne, MarsBit
As the blockchain supports more users and more frequent transactions, the amount of information (“state”) stored by validators to verify transactions grows. For example, in Bitcoin, the state consists of a set of unspent transaction outputs (utxo). In Ethereum, the state consists of the account balance of each account and the code and storage of each smart contract.
This storage burden would become unmanageable for a blockchain with enough accounts or UTXOs to support most people’s real day-to-day transactions, making it difficult to be a validator and a threat to decentralization. It’s tempting to look to cryptography as a solution, and tools like Merkle trees and zero-knowledge proofs have helped us achieve previously unbelievable goals.
This is exactly the goal of a “stateless blockchain”. However, despite a great deal of work in this area, they are still far from being practical. But it turns out that this lag in progress is inherent—the gap between these structures and practicality can never be bridged. Our recent work shows that any stateless blockchain scheme, no matter how smart, is not feasible without additional measures to manage state. As we demonstrate at the end of this article, this improbable outcome should not be disheartening.
stateless state
Today, the state size is large but manageable. For example, a Bitcoin node stores about 7GB of data, and an Ethereum node stores about 650GB of data. However, the storage burden on full nodes scales roughly linearly with the chain’s throughput (transactions per second, or TPS), which is currently unacceptably low. According to the current design, the state required to truly support daily transactions (hundreds of thousands to millions of TPS) will become unmanageable, requiring the use of several terabytes or even petabytes of storage space.
This has prompted people to look for technical ways to drastically reduce the amount of state required by validators - a stateless blockchain would require validators to only store a constant-size state regardless of transaction throughput. (Actually, the term is a misnomer: there is still state, just small enough to accommodate any future throughput—often constant size.) This lightweight storage requirement will make it easier to run validator nodes ; Optimistically, everyone can run a node on their phone. Since increasing the number of validators will increase the security of the chain, it is important to lower the barriers to entry for validators.
Despite a great deal of research on stateless blockchains (e.g. Todd, Buterin, Boneh et al., 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 its balance are included in the global state commitment. When a user makes a transaction, they submit this witness to a validator, showing that their account has a sufficient balance.
Unlike storing private keys that 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 had to constantly monitor all other credit card transactions globally and update some local data accordingly to use your own credit card. For a blockchain to be practical, users must be able to remain offline, interacting with the blockchain only when submitting transactions. In many cases, such as hardware wallets, updating witnesses is not only inconvenient, but impossible.
This leads to a natural research question: Can we build a stateless blockchain that does not need to update witnesses (or rarely needs to update witnesses)? To answer this question, we develop a new theoretical framework (which can be Revocation Proof System), which generalizes stateless blockchains. Using this framework, we demonstrate a conclusively impossible result: the trade-off between compact global state and frequent witness updates is fundamental. 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 structure and practicality will never be bridged.
Research Background
To help develop intuition for impossible outcomes, we will first describe the natural but inefficient construction of a stateless blockchain using Merkle trees. Our goal is for validators to determine whether a transaction submitted by a user is valid - for example, whether the user has a large enough 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. The constant-size state V stored by validators is the root of this tree, which acts as a commitment to the set of account balance pairs. Each user maintains its Merkle proof of inclusion of (account ID, balance) pair as its witness. The Merkle proof of inclusion of a leaf ( a , b ) consists of partner nodes ( v 1 , …, vk ) along its path to the root of the tree. Given a transaction by a user using account a and claiming a balance b, a validator can check that b is indeed the balance of account a by checking that (a, b) proves (v 1 , …, vk ) with its current state V. If so, the validator will execute the transaction and must update the account balance accordingly. A convenient property of Merkle trees is that, given a leaf’s Merkle containment proof, it is easy to compute the resulting root when that leaf changes. In other words, a validator can easily compute an updated state V’ that captures the new balance of account a after the transaction is executed.
The Merkle tree approach has two major drawbacks. First, the number of user witnesses is relatively large, growing logarithmically in the total number of accounts in the system. Ideally, they should be of constant size, which we can achieve using schemes such as RSA accumulators (Boneh et al. in the context of stateless blockchains).
The second disadvantage is more difficult to avoid: whenever other users make a transaction, the proof of the account-balance pair changes. Recall that a leaf’s proof consists of partner nodes on the path from that leaf to the root of the tree. If any other leaf changes, one of these nodes changes, causing problems in practice. Most blockchain users want to passively keep their coins in a wallet, only logging in when they want to make a transaction. However, in the practice of this stateless blockchain, users must constantly monitor other people’s transactions to keep their witnesses up to date. (While third parties can perform this monitoring on behalf of users, this deviates from the standard stateless blockchain model. We will discuss this issue at the end of this article.) In fact, this is a problem for stateless blockchains. An insurmountable challenge that places a heavy burden on users.
Our conclusion: statelessness is impossible
This phenomenon is not unique to Merkle tree structures - all known stateless blockchain schemes require users to update their witnesses frequently. We illustrate this in this article. More precisely, we show that the number of users who must update their witness grows roughly linearly with the total number of transactions made by all users.
This means that even if user Alice has not made any transactions, her witness 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 not help much. We plot this relationship following the theorem below, along with the number of witness changes required per day for blockchains of different throughputs. These graphs show how many times the witness needs to change for an optimal stateless blockchain. Here, the data field refers to the total number of accounts (in the account model) or UTXO (in the UTXO model).
At the heart of our proof is an information-theoretic argument. A central tenet of information theory proposed 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 is a stateless blockchain scheme where users rarely update their witnesses, then Alice can tell Bob which object she has chosen in less than n bits - Shannon proves that this is impossible. Therefore, such a stateless blockchain cannot exist.
For simplicity, we will describe here a proof of a slightly weaker statement: there cannot be a stateless blockchain where users never need to update their witnesses. The key idea is that Alice encodes her message to Bob using a stateless blockchain scheme. Initially, both Alice and Bob know the complete 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 would choose a set of A accounts corresponding to her message, and she would spend tokens from those accounts. She will use the stateless blockchain to communicate with Bob the set she chooses, and from that set he can learn what her messages are.
Encoding: Alice spends one token from each of A’s accounts. Using a stateless blockchain scheme, Alice computes an updated state V’ and sends V’ to Bob.
Decoding: For each i, Bob checks if Verify( wi , ( ai , bi )) . Bob outputs the account set B such that Verify( wi , ( ai , bi )) = false.
Bob successfully outputs the same set that Alice chose: B = A. First, observe that if Alice has spent one token from account ai, no more witnesses to its old balance should 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 that account in B. On the other hand, Bob will never include in B the account identified by Alice. There is no _ to spend a coin, because the balances of these accounts remain the same, and (recall the loose statement we were trying to prove) their witnesses never change. Therefore, B is exactly equal to A.
Finally, the contradiction is resolved by calculating the number of bits Alice should send to Bob. There are 2n possible subsets of accounts she can choose, and according to Shannon’s law, she should send at least n bits to Bob. However, she only sends a constant-sized state V’, much shorter than n bits.
(Readers familiar with cryptography may notice that we gloss over some details here; for example, Bob’s decoding fails with negligible probability. Our paper includes a full proof.)
While we describe our proofs in terms of stateless blockchains, Alice and Bob can perform similar overly efficient communication using various other authenticated data structures (e.g. accumulators, vector commitments). We formalize such data structures using a new abstraction, which we call reversible proof systems.
IMPACT OF THE RESULTS
Our results show that you cannot “encrypt state” - there is no silver bullet solution that would allow us to build a stateless blockchain where users never have to update their witnesses. The state does not disappear, but is transferred from the validator to the user, and pushed to the user in the form of frequently updated witnesses.
Some potential solutions do exist, but these break away from the strictly stateless blockchain model. This model allows a third party (neither a user nor a validator) to be responsible for storing the full state. This party is called a Proof Service Node (with the most stringent checks by Srinivasan et al.), and it uses the full state to generate up-to-date witnesses on behalf of users. Users can then use these witnesses to transact, just like in a regular stateless blockchain, where validators still only store a compact state. The system’s incentive mechanism, 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. A rollup (whether optimistic or ZK) typically takes a large state and commits it using a small value stored on L1. 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 of their current account balance. This setup is also an instance of the reversible proof system in our model. In fact, one could argue that stateless blockchains are already implemented in practice in the form of L2 rollups.
Unfortunately, this means that our impossibility results apply directly. A user’s rollup withdrawal witness must change frequently, otherwise almost the entire L2 state would have to be written to L1. As a result, collections today typically assume a data availability committee (sometimes called a “validity committee”) that functions like a “proof service node” that helps users compute new witnesses when they’re ready to exit. Our findings suggest that the warnings to users in the Ethereum documentation — “Without access to transaction data, users cannot compute the Merkle proofs required to prove ownership of funds and perform withdrawals.” — will always apply.
As blockchain systems develop, it will become even more important to develop more efficient ways to manage blockchain state. Although our results for excluding stateless blockchains may seem negative, the impossibility results are useful for blockchain designers, as they tell us to focus our research elsewhere, ideally helping us Find viable solutions faster.
