Authors: Miranda Christ, Joseph Bonneau
Translation: Shenchao TechFlow
As blockchain supports more users and more frequent transactions, the number of validators’ storage of information (or “state”) to verify transactions is also increasing. For example, in Bitcoin, the state is composed of a set of unspent transaction outputs (UTXOs). In Ethereum, the state consists of the account balances of each account and the code and storage of each smart contract.
As the blockchain grows to support a significant portion of real daily transactions in the population, the storage burden becomes difficult to control, making it difficult to become a validator and posing a threat to decentralization. The enticing solution is to turn to cryptography, where tools such as Merkle trees and zero-knowledge proofs help us achieve things that were previously unimaginable.
- Sui Kiosk A self-service machine for creators to create encrypted assets
- Decoding the New Public Chain PGN Supported by Gitcoin
- Exploring the method of imposing income tax on stablecoins
This is the goal of “stateless blockchains”. But despite extensive research on them, they are still far from practical. However, it has been shown that this lag in progress is inherent – the gap between these constructs and practicality will never be bridged. Our recent work suggests that any stateless blockchain solution, no matter how clever, is impractical without additional measures to manage the state. However, as we show at the end of this article, this impossibility should not be discouraging.
Stateless
Today, the state is large but manageable. For example, Bitcoin nodes store about 7 GB of data, and Ethereum nodes store about 650 GB of data. However, the storage burden of a full node roughly grows linearly with the throughput of the chain (transactions per second or TPS), and today’s throughput is still unacceptable. According to the current design, the state required to support real daily transactions (with tens of thousands to hundreds of thousands of transactions per second) will become difficult to control, requiring storage space in the gigabytes or even terabytes.
This has led people to look for technical approaches to significantly reduce the amount of state required by validators. It is crucial to achieve a stateless blockchain, which would require validators to store a constant-size state regardless of the transaction throughput (in fact, this term is a misnomer: there is still state, but it is small enough to be practical at any future throughput – typically a constant size). This lightweight storage requirement would make running a validator node much easier; optimistically, anyone could run a node on their phone. It is important to lower the barrier to entry for validators as increasing the number of validators increases the security of the chain.
Despite extensive research on stateless blockchains (e.g., the research by Todd, Buterin, Boneh, and others and the research by Srinivasan and others), 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 a witness to help validators verify transactions involving their accounts. For example, this witness could be a Merkle proof showing that the user’s account and balance are included in a global state commitment. When users make transactions, they submit this witness to validators to show that their account has sufficient balance.
Unlike storing private keys, it never needs to be changed. These witnesses are often changed, even for inactive users, which brings unrealistic burdens to users. Similarly, imagine constantly monitoring all other credit card transactions worldwide and updating some local data accordingly to use your own credit card. In order for the blockchain to be practical, users must be able to be offline and interact with the blockchain only when submitting transactions. In many cases, such as hardware wallets, updating witnesses is not only inconvenient but also impossible.
This leads us to a natural research question: can we build a stateless blockchain that does not require frequent witness updates (or only requires minimal witness updates)? To answer this question, we have developed a novel theoretical framework (reversible proof system) that generalizes stateless blockchains. Using this framework, we have proved an impossibility result: the trade-off between concise global state and frequent witness updates is inherently difficult to reconcile. Our proof technique is information-theoretic, which means that future computers will not have enough power 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 result, we first describe a natural but inefficient method of using Merkle trees to build stateless blockchains. Our goal is to enable validators to determine whether the transactions submitted by users are valid—for example, whether the user has enough account balance to make the transaction. In a stateless blockchain scheme, validators store a state of constant size. When users make transactions, they must include a witness in the transaction. Validators can use the current state and the (transaction, witness) pair submitted by the user to verify if the user has enough account balance to make the transaction.
We first construct 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, serving as a commitment to a set of account balance pairs. Each user maintains a Merkle inclusion proof for their witness. A Merkle inclusion proof for a leaf (a, b) consists of the sibling nodes (v1, …, vk) along the path from that leaf to the tree root. Given a transaction performed by account a with claimed balance b, validators can verify if b is indeed the balance of account a by checking the proof (v1, …, vk) for (a, b) against their current state V. If so, validators execute the transaction and must update the balance of the account accordingly. A convenient property of Merkle trees is that given a Merkle inclusion proof for a leaf, it is easy to compute the resulting root when that leaf changes. In other words, validators 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 main drawbacks. First, the witnesses of users are relatively large and grow 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 disadvantage is more difficult to avoid: whenever other users make transactions, the proof of account balance will change. Remember that the proof of a leaf node consists of 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, which will cause actual problems. Most blockchain users prefer to passively keep their coins in their wallets and only go online when they want to make a transaction. However, in this stateless blockchain, users must constantly monitor the transactions of others to keep their witness information up to date. Although third parties can monitor this on behalf of users, it deviates from the standard stateless blockchain model. In fact, this is an insurmountable challenge for stateless blockchains, which imposes a heavy burden on users.
Our conclusion: statelessness is impossible
This phenomenon is not only applicable to this Merkle tree structure – all known stateless blockchain solutions require users to frequently update their witness information, as we have proven here. More accurately, we have shown that the number of users who need to update their witness information roughly increases in a linear manner with the total number of transactions performed by all users.
This means that even if the user Alice does not make any transactions, her witness information may need to change with the transactions of other users. Increasing the size of the concise state does little to help if the concise state stored by the validator is too small to capture the complete state (i.e., the collection of all account balances). We have drawn the following relationship diagram based on our theorem, as well as the number of witness information changes required for blockchains with different throughputs per day. These graphs show the number of times the witness information needs to be changed for the optimal stateless blockchain. 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. One of the core principles of information theory, formalized by Claude Shannon, is that if Alice randomly selects an object from a set of size 2n and wants to tell Bob which object she chose, she must send at least n bits to him. If there is a stateless blockchain scheme where users rarely update their witness information, Alice can tell Bob which object she chose with less than n bits, which is impossible, as Shannon has proven. Therefore, such a stateless blockchain does not exist.
For simplicity, we describe a slightly weaker statement of the proof here: there is no stateless blockchain where users never need to update their witness information. The key is that Alice uses a stateless blockchain scheme to encode her message and send it to Bob. Initially, Alice and Bob both know the complete set of account balance pairs for all n users. Assume that each account has at least one coin. Alice and Bob also know the concise state V of the stateless blockchain and the witness wi of all account balance pairs (ai, bi). Alice and Bob also agree on the mapping between messages and account sets. Alice will choose a set of accounts corresponding to her message and then spend coins from these accounts. She will use the stateless blockchain to convey her chosen set to Bob, from which he can infer her message.
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 if Verify(wi, (ai, bi)) is true. Bob outputs the set of accounts B for which Verify(wi, (ai, bi)) = false.
Bob successfully outputs the same set that Alice selected: 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 includes this account in B. On the other hand, Bob will never include accounts in B that Alice did not spend coins from, as the balances of these accounts remain unchanged, and their witnesses will never change (recall the relaxed statement we want to prove). Therefore, B is exactly equal to A.
Finally, we resolve our contradiction by calculating the number of bits Alice should send to Bob. The number of subsets she can choose from is 2 to the power of n, so according to Shannon’s law, she should send at least n bits to Bob. However, she only sends a constant-sized state V’ that is much shorter than n bits.
Although we used a stateless blockchain in describing our proof, Alice and Bob can perform similar efficient communication using various other authenticated data structures, including accumulators, vector commitments, and authenticated dictionaries. We use a new abstraction called a revocation proof system to formalize such data structures.
Implications of the Results
Our results indicate that you cannot “eliminate state through cryptography,” and there is no magic commitment scheme that allows us to build a stateless blockchain where users never have to update their witnesses. The state does not disappear; instead, it is transferred from the hands of the verifiers and pushed to the users in the form of frequent witness updates.
There are also other promising solutions that deviate from the strict stateless blockchain model. One natural relaxation of this model is to allow a third party (neither a user nor a verifier) to be responsible for storing the complete state. This third party, called a proof-of-service node, uses the complete state to generate the latest witness information for users. Users can then use this witness information for transactions, just like in a regular stateless blockchain, where verifiers still only store a concise state. The incentive mechanism of this system, particularly 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 use a commitment on L1 to store a large state. This state includes the accounts of each user on L2. We hope that these users can directly withdraw funds on L1 (without cooperation from L2 servers) by publishing witnesses to their current account balances. This setup is also an instance of the revocation proof system in our model. In fact, it can be said that stateless blockchains have already been realized in practice in the form of L2 Rollups.
However, unfortunately, this means that our impossibility result directly applies. The user’s Rollup withdrawal witness must be changed frequently, otherwise almost the entire L2 state must be written to L1. Therefore, today’s Rollups typically assume the existence of a data availability committee (sometimes called “validium”), similar to “proof-of-service nodes,” to help users calculate new witness information when preparing for withdrawal. Our results indicate that the Ethereum documentation’s warning to users, “Without transaction data, users cannot calculate Merkle proofs to prove ownership of funds and perform withdrawals,” will always apply.
Like what you're reading? Subscribe to our top stories.
We will continue to update Gambling Chain; if you have any questions or suggestions, please contact us!
