[PlatON Tech-Column]A detailed explanation of the Stateless concept (I)
Back in 2017, Ethereum opinion leader Vitalik introduced the concept of Stateless clients at The Ethereum developer conference(Devcon), with the intention of solving the problem of growing on-chain data faced by public chains by reducing on-chain state storage. The concept was conceived as an ideal solution for blockchains to get rid of state bloat, and over the past few years, through the continuous in-depth research of Alexey Akhunov and Igor Mandrigin and others, the Stateless concept has become more fruitful. The purpose of this article is to provide a preliminary interpretation of the latest results of the research on the concepts of “stateless”, “state expiration” and “state cleanup” in the public chain domain.
To understand what Stateless clients are we must first look at the background to the idea of Stateless clients.
The blockchain is decentralised and neither subordinated to powerful institutions nor privately owned; it is a ‘commons’. The biggest challenge facing the commons is how to make the limited resources as energy efficient as possible, and avoid the ‘tragedy’ of the whole ‘commons’ becoming less efficient or even disappearing due to the ineffective occupation of resources. In the case of Ethereum, for example, with the increasing amount of account and contract data, the state data saved on all nodes has exceeded 2TB so far, and the increasing state data poses a series of risks to all public chains.
01 Boosting node running costs
Growing state data inevitably requires the full node to invest more and more in storage, and as TPS continues to increase, querying or inserting new keys in the context of exponential data growth is bound to increase IO overhead (even with a key-value database like leveldb), so a fullnode must constantly optimise and upgrade its hardware to meet the requirements of out-of-block ( miner) or validate the node’s requirements.
02 The threat to decentralisation
Vitalik once described the current transaction billing mechanism as one-time gas paid, impose permanent ongoing costs on the network , current per-state storage blockchains do not charge extra for storing user data over time, which means that there is no additional financial incentive for a node to run a full node. As a matter of course, as the cost increases, fewer nodes in the network will be able to propose blocks (miner) or verify blocks, which will largely threaten the decentralisation of the entire network and pose a significant threat to overall security.
03 Increased risk of DDoS attacks
On Ethereum, transactions are charged on a Gas basis, and while miners have the initiative to package transactions at a Gas price (pre-EIP1559), in general, the price depends on how busy the network is rather than the actual price of the Token. A bad result of this mismatch is that it costs very little to post a transaction on the network when the Token price is low (at least from a stable coin/fiat currency perspective), which would be vulnerable to malicious attacks that use a small cost to populate the network’s state data with a large number of spam transactions. And as we said before the sender of the transaction only pays once, but places a permanent burden on the network.
These problems are common to almost all public chains today, and it is in this context that the Stateless concept was born.
The Stateless concept
The Stateless concept can be simply summarised as trading bandwidth overhead for storage overhead and was originally described by Vitalik in the following terms.
STF(S, B) -> S’
STF (state transition function): state transition method
S (state): state, i.e. the data associated with an account such as balance, nonce, etc.
B (block): block, or it can also be understood as the state storage of the current transaction in the blockchain, which can be described as: state S is transformed to state S’ by the STF transition function and the block (or transaction).
Suppose we use the root of all accounts in the MPT tree (State Root) as S and a set of Roots of all Merkle branches that can prove that the block or transaction needs to be accessed as witness data W (Witness), such that there is.
STF(S, B) -> S’
The above equation can be described as follows: there can be such a state transition function STF’ that calculates a new state S’ by taking as input the root node StateRoot of the previous block’s state S, the block or transaction B and the witness data W needed to verify B.
The significance of this formula is that the verifier only needs to store the latest StateRoot to make a verification of a block or transaction B, completely free from the drag of state data and completely free from state inflation.
In short, the Stateless concept is that nodes are expected to complete the validation of a block or transaction by verifying the witness data of the block or transaction without accessing or with less access to the state data, thus achieving the goal of reducing the storage of state data.
However, it is not acceptable for all nodes to have no state data, users must have access to current state information (e.g. account balance, nonce, etc.) in order to initiate transactions based on the latest state, so user data (state) must be stored in some way, hence Vitalik’s Stateless clients and state expiration scheme.
Considering the classification in terms of the different divisions of the nodes, the clients on the network can be divided into Stateless clients and clients.
01 Weak Stateless
Block producers are required to keep state data in order to be able to generate the block witness data Witness, while block validators do not need state data but only need to validate Witness, i.e. block producer nodes are State clients and block validators are Stateless clients.
02 Strong Stateless
Neither the nodes producing the blocks nor the nodes validating the blocks need to maintain Stateless clients, the producer generates a new block and validates the transaction against the Witness of the transaction, thus requiring only the sender of the transaction to maintain the full amount of State clients to ensure that it can provide Witness.
However, regardless of the division of labour between the nodes, as more and more account data becomes available, the Witness of the transaction or block will become larger and larger, increasing the burden on the network, so this solution may not be the optimal solution.
A more modest solution is ‘state expiry’, which assumes that accounts must be continuously accessed to remain ‘active’ and that accounts that have been untouched for a long time will become ‘inactive’ (or ‘expired’). The general principle is that unless a status object is explicitly updated, it will somehow become inactive. Therefore, any creation of a new account object (or refreshing of an existing one) only burdens the network for a limited period of time; once an account is inactivated, it will disappear into history.
Status expiry can be divided into the following categories：
01 Status leasing
Status leasing is intended to be an economic solution to the problem of status abuse, where the proponent of each block deducts the status leasing fee directly from the balance of each account as agreed, and when the account balance is reduced to zero, the account is then wiped out.
02 Time Leasing
Time leasing does not charge users rent, but stores a time-to-live value for each account on the chain, which decreases with each block and is cleared when the account’s time-to-live value is reduced to 0. This value can be increased by a specific transaction.
03 Access Refresh
A time-to-live value is stored for each account, decremented per block and cleared when the account’s time-to-live value is reduced to 0. This value is automatically increased when there is a read or write to this state.
It seems that the ‘refresh by access’ approach makes the most sense as it does not require a complex incentive strategy and ensures that there is a clear upper limit to the size of the active state (block Gas limit/amount of Gas consumed to reach the state object x length of time the state is alive). In practice, state expiration is still in the exploratory stage of research as each new state generated requires traversing all accounts to find out if there is an expiration, which greatly increases the state maintenance overhead and cost.
It is precise because of the impracticality of state expiration that a mechanism to periodically clean up state through specific rules has received increasing attention from researchers, with Semi-Stateless and Re-genesis schemes being the most representative.
Semi-Stateless is also a Stateless scheme, which has the following basic process.
- The latest state of each node is T1, and the node provides additional witness data W1, W2 each time it validates or executes block B …. 1. each node provides additional witness data W1, W2 each time it validates or executes block B. These witness data can convert T1 to T2
- Execute W1, W2, …… on T1 in sequence and finally obtain T2, without querying the database in the process
- Execute block B on T2, also without querying the database
- Leave T2 for subsequent use, T1 and previous states can be cleaned up
According to mandrigin’s Semi-Stateless Initial Sync Experiment, the use of this solution significantly reduces the size of the witness data during block synchronisation compared to full stateless.
Re-genesis can be thought of as a ‘periodic cleanup’ solution, originally inspired by Alexey’s Cosmos upgrade, and is now one of the hottest of the Stateless solutions.
This solution takes a snapshot of the state data on the chain by specifying the block height periodically through a hash, while cleaning up the state data, and the block after regenesis records the new state data and witness data witness based on the previous block’s hash. The scheme proposes the concepts of explicit state and implicit state.
01. implicit state
If you receive block data N from a node on the other side at any given time, the other side assumes that the node already has all the state data necessary to validate the transaction in the block and has already synchronised to block N-1, i.e. the other side assumes that you have the state and therefore does not pass the state data itself.
02. explicit state
If you receive block data N from a node on the other side at any given time, the other side assumes that the node does not have an implicit state, so the block is sent not only with the block data but also with the Witness of the block.
The Re-genesis scheme periodically regenesis the current data on the chain into a 32-byte hash value. Each block after regenesis requires all counterparts to send “explicit state”, but as the state data grows, the witness data becomes smaller and smaller, thus achieving a balance between storage overhead and witness data overhead.
The goal of Re-genesis：
- For every N blocks generated, we will zero out all state and keep only the root hash
- Re-genesis should not be started too often, the recommended setting on Ether is every 1 million or 10 million blocks
- The transaction sender needs to provide explicit state (as a transaction witness)
- The transaction sender pays a Gas fee for the transaction based on the size of the transaction witness
- Transaction senders must retain the pre-genesis launch state of the contract/account they are interested in
- If a transaction fails due to insufficient explicit state, the proof provided for that transaction can be added to the implicit state so that we don’t need to provide the same proof the next time we send a transaction.
- The explicit state from the proof of the transaction is merged with the implicit state generated by an earlier running transaction in the block via a smart merge mechanism.
- This option has the following advantages.
- Changes the incentive balance between transaction senders and infrastructure nodes, thus increasing the decentralization of the state store
- Limiting state growth through ReGenesis
- Allowing the use of transaction witnesses and simplifying the pricing of Gas per transaction witness
An implementation of regenesis can be found in this article by Vitalik: Vitalik: Resurrection-conflict-minimized state bounding, take 2
The above is a brief introduction to the Stateless concept and its related solutions, which are only macro ideas and provide us with some ideas to solve the ‘state inflation’ problem. What are the problems in engineering implementation? We will explore this in more depth in the next section.