I began crafting a post that outlined a “roadmap” for Ethereum 1.x research and the journey towards stateless Ethereum, only to realize that it’s not truly a roadmap in the conventional sense we associate with products or companies. The 1.x team, while converging towards a shared objective, comprises a diverse group of developers and researchers working independently on deeply interconnected issues. As a result, there isn’t a formal “roadmap” available. However, the scenario isn’t entirely chaotic! There exists a recognized “order of operations”; certain tasks must precede others, some solutions cannot coexist, and while other efforts may be advantageous, they aren’t critical.
So what metaphor better captures the process toward achieving stateless Ethereum than a roadmap? After some contemplation, I settled on an apt one: Stateless Ethereum is akin to the ‘full spec’ in a tech tree.
Some readers may immediately grasp this analogy. If you do, feel free to skip the following paragraphs. However, if you typically don’t consider the world through a gaming lens: A tech tree is a common feature in games that lets players unlock and enhance new spells, technologies, or skills, which are organized into a loose hierarchy or tree structure.
Typically, players accumulate some form of XP (experience points) that can be “spent” to acquire elements in the tree (‘spec’), subsequently unlocking more advanced elements. Occasionally, it is necessary to secure two unrelated basic elements to access a more advanced third element; other times, unlocking one basic skill can lead to multiple new options for advancement. A significant part of the enjoyment for players lies in choosing the right path in the tech tree that aligns with their abilities, aspirations, and inclinations (do you pursue the full spec in Warrior, Thief, or Mage?).
This, quite surprisingly, mirrors the structure we have in the 1.x research room: A flexible hierarchy of topics to address, with limited time and expertise to devote to research, implementation, and testing. Much like in a well-designed RPG, experience points are finite: there’s only so much that a small group of capable and enthusiastic individuals can achieve in a couple of years. Depending on delivery requirements, it may be advisable to prioritize more straightforward upgrades over more ambitious or abstract developments, steering towards a direct route to the final specification. Everyone is aiming for the same ultimate goal, but the chosen paths to reach it will rely on the solutions that are fully researched and implemented.
Now, I will present my rough representation of the tree, discuss its organization, and briefly explain each upgrade and its relation to the whole. The terminal “full-spec” upgrade in the tech tree is “Stateless Ethereum”, signifying a fully functional Ethereum mainnet that accommodates full-state, partial-state, and zero-state nodes; that efficiently and reliably circulates witnesses and state information; and that is fundamentally prepared to scale until the bridge to Eth2.0 is constructed and ready to integrate with the legacy chain.
Note: As mentioned above, this isn’t an ‘official’ work scheme. It’s my best attempt to compile and organize the key features, milestones, and decisions that the 1.x working group needs to reach to bring Stateless Ethereum into existence. Feedback is encouraged, and updates/revisions to this plan will undoubtedly occur as research progresses.
The diagram should be read from left to right: purple elements on the left are ‘fundamental’ and must be developed or determined before subsequent improvements can occur further right. Elements with a greenish tint indicate they are “bonus” items — desirable but not strictly essential for the transition, and may be less precisely defined within the research scope. The larger pink shapes symbolize crucial milestones for Stateless Ethereum. All four major milestones must be “unlocked” before a nationwide transition to Stateless Ethereum can be implemented.
The Witness Format
There’s been considerable discussion about witnesses concerning stateless Ethereum, so it’s no surprise that the first significant milestone I want to address is a finalized witness format. This entails decisively establishing the state trie structure and its associated witnesses. The creation of a specification or reference implementation can be seen as the point where ETH 1.x research “levels up”; streamlining around a new state representation will help define and direct the work necessary to achieve other milestones.
Binary Trie (or “trie, trie again”)
Transitioning Ethereum’s state to a Binary Trie structure is critical for minimizing witness sizes, allowing them to be efficiently shared throughout the network without causing bandwidth or latency problems. As discussed in the last research call, establishing a Binary Trie will necessitate commitment to one of two mutually exclusive strategies:
-
Progressive. Similar to the Ship of Theseus, the current hexary state trie would be transformed gradually over an extended period. Any transaction or EVM execution affecting state would automatically encode changes into the new binary format. This implies adopting a ‘hybrid’ trie structure that would allow dormant parts of the state to retain their current hexary representation. The process would effectively be ongoing and complex for client developers to execute, yet would mostly shield users and higher-layer developers from the underlying changes in layer 0.
-
Clean-cut. More aligned with the significance of the underlying trie change, a clean-cut transition strategy would entail drafting a clear timeline of transition over multiple hard forks, compute a fresh binary trie representation of the state at that time, then proceed in binary form once the new state is computed. While more straightforward from an implementation perspective, a clean-cut approach necessitates coordination from all node operators, likely leading to some (limited) disruption to the network, impacting developer and user experiences during the transition. Conversely, the process may provide valuable insights for planning the more distant transition to Eth2.
Regardless of the chosen transition strategy, a binary trie serves as the foundation for the witness structure, determining the order and hierarchy of hashes constituting the state trie. Without further refinements, rough estimates (from January 2020) suggest witness sizes could range from ~300-1,400 kB, down from ~800-3,400 kB in the hexary trie configuration.
Code Chunking (merkleization)
A critical component of a witness is the accompanying code. Without code chunking, a transaction with a contract call would necessitate the entire bytecode of that contract to verify its codeHash. This could result in substantial data loads, depending on the contract. Code ‘merkleization’ involves partitioning contract bytecode so that only the relevant portion of the code invoked is required to create and validate a witness for the transaction. This technique can significantly reduce the average size of witnesses. There are two methods for splitting up contract code, and currently, it’s unclear whether the two approaches are mutually exclusive.
- “Static” chunking. Dividing contract code into fixed sizes, approximately 32 bytes. For the merkleized code to function properly, static chunks must also encompass additional metadata with each chunk.
- “Dynamic” chunking. Segmenting contract code into chunks based on its content, cleaving at specific instructions (JUMPDEST) present within it.
At first glance, the “static” code chunking method appears preferable to eliminate leaky abstractions, i.e., to ensure that the content of the merkleized code does not impact the lower-level chunking, which may occur in the “dynamic” scenario. Nevertheless, both options have yet to undergo comprehensive testing, thus both remain under consideration.
ZK witness compression
Approximately 70% of a witness comprises hashes. Utilizing a ZK-STARK proofing technique could possibly compress and validate those intermediate hashes. As is often the case with current zero-knowledge efforts, exactly how this will be implemented, or even if it will work at all, is not thoroughly defined or straightforward to ascertain. Thus, this aspect is somewhat of a side-quest, or a non-essential upgrade within the main technical development tree.
EVM Semantics
We’ve briefly touched on avoiding “leaky abstraction,” which is especially relevant to this milestone, so I want to take a moment to elaborate on its significance. The EVM is an abstract component of the broader Ethereum protocol. In theory, the operations within the EVM shouldn’t impact at all how the overall system functions, and modifications outside the abstraction should not influence anything inside it.
However, certain aspects of the protocol directly affect functionality within the EVM. These issues manifest clearly in gas costs. A smart contract (inside the EVM abstraction) encounters gas costs associated with various stack operations (outside the EVM abstraction) via the GAS opcode. Alterations in gas scheduling may directly influence the performance of specific contracts, depending on the context and how the contract utilizes the accessible information.
Due to these ‘leaks,’ modifications to gas scheduling and EVM execution must be undertaken cautiously, as they could unintentionally affect smart contracts. This is a reality we must deal with; designing systems without any abstraction leakage is particularly challenging, and moreover, the 1.x researchers lack the luxury of completely redesigning anything — they must operate within today’s Ethereum protocol, which is, to some degree, leaky regarding the virtual state machine abstraction.
Returning to the main subject: Introducing witnesses will necessitate changes to gas scheduling. Witnesses must be generated and disseminated throughout the network, and this activity needs to be accounted for in EVM operations. The topics associated with this milestone relate to what these costs and incentives will be, how they are estimated, and how they can be implemented with minimal impact on higher layers.
Witness Indexing / Gas Accounting
This section likely contains more intricacies than can be effectively captured in a few sentences; we will probably delve deeper into this later. For now, understand that each transaction will contribute to a small portion of the entire block’s witness. Generating a block’s witness involves computations to be performed by the block’s miner, necessitating an associated gas cost to be borne by the transaction’s sender.
Since multiple transactions might interact with the same segment of the state, it’s unclear how best to estimate gas costs for witness production at the point of transaction broadcasting. If transaction senders cover the entire cost of witness creation, scenarios might arise where the same segment of a block witness is paid for multiple times by ‘overlapping’ transactions. While this isn’t inherently detrimental, it introduces real changes to gas incentives that require better understanding.
Regardless of the associated gas costs, witnesses will need to be integrated into the Ethereum protocol and probably included as a standard component of each block, perhaps through a simple inclusion of a witnessHash in each block header.
UNGAS / Versionless Ethereum
This category of upgrades is mostly tangential to Stateless Ethereum, focusing on gas costs in the EVM and addressing the abstraction leaks I’ve mentioned. UNGAS stands for “unobservable gas,” referring to a modification that would explicitly prevent contracts from utilizing the GAS opcode, thereby disallowing any assumptions about gas costs from being made by smart contract developers. UNGAS is part of several proposals outlined in the Ethereum core paper, aimed at addressing some of these leaks, making all future modifications to gas scheduling easier to implement, particularly those associated with witnesses and Stateless Ethereum.
State Availability
Stateless Ethereum will not eliminate state entirely. Instead, it will provide optionality, allowing clients some independence regarding how much state they track and compute. Therefore, the full state must be made accessible somewhere, enabling nodes to download part or all of the state as needed.
In some respects, current paradigms like fast sync already facilitate this functionality. However, the introduction of zero-state and partial-state nodes complicates matters for new nodes trying to catch up. Presently, a new node expects to download the state from any active peers it connects to, as all nodes maintain a copy of the current state. Yet, that assumption changes if some of the peers are potentially zero-state or partial-state nodes.
The prerequisites for this milestone relate to how nodes communicate what pieces of state they possess and the methods for transferring those pieces reliably across a constantly evolving peer-to-peer network.
Network Propagation Rules
The diagram below illustrates a potential network topology that could manifest within stateless Ethereum. In this setup, nodes will need to position themselves based on which parts of the state they wish to keep, if any.
Improvements like EIP #2465 fall into the general category of network propagation rules: new message types in the network protocol that provide deeper insights into the information nodes possess and specify how this information is relayed to other nodes in potentially convoluted or limited network topologies.
Data Delivery Model / DHT Routing
If improvements such as the new message types discussed earlier are adopted, nodes will be able to discern what parts of the state are held by their connected peers. But what if none of the connected peers possess a required piece of state?
Data delivery remains an open-ended challenge with various potential solutions. One could envision utilizing more ‘mainstream’ solutions, making some or all of the state accessible via HTTP requests from a cloud server. A bolder approach would incorporate features from peer-to-peer data delivery systems, enabling requests for state pieces to navigate through connected peers, reaching their intended destinations through a Distributed Hash Table. These two extremes aren’t fundamentally incompatible; why not both?
State Tiling
One potential strategy for enhancing state distribution involves dividing the full state into more manageable segments (tiles), saved in a networked cache that can serve state to nodes across the network, thereby alleviating the load on full nodes providing state. The aim is that despite relatively large tile sizes, some tiles are likely to remain unchanged from block to block.
The geth team has conducted experiments suggesting that state tiling is viable for improving the availability of state snapshots.
Chain Pruning
Much has been discussed regarding chain pruning, so an extensive explanation isn’t required. It is crucial to note, however, that full nodes can securely prune historical data such as transaction receipts, logs, and past blocks only on the condition that historical state snapshots are readily available for new full nodes, potentially through state tiling and/or a DHT routing scheme.
Network Protocol Spec
Finally, the complete picture of Stateless Ethereum is crystallizing. The three milestones of Witness Format, EVM Semantics, and State Availability collectively provide a comprehensive description of a Network Protocol Specification: the well-defined upgrades that should be implemented across all client variations and deployed during the next hard fork to transition the network into a stateless framework.
We have traversed a lot of ground in this article; however, a few loose ends from the diagram still require clarification:
Formal Stateless Specification
Ultimately, there is no requirement that the complete stateless protocol be defined formally. It is plausible to devise a reference implementation that serves as a basis for all clients’ re-implementation. Nevertheless, creating a “formalized” specification for witnesses and stateless clients offers undeniable advantages. This would represent an extension or appendix fitted into the Ethereum Yellow Paper, articulating in precise terms the expected conduct of an Ethereum stateless client implementation.
Beam Sync, Red Queen’s Sync, and Other State Sync Optimizations
Sync strategies aren’t core to the network protocol; rather, they are implementation specifics impacting how efficiently nodes operate under the protocol. Beam sync and Red Queen’s sync are linked strategies for establishing a local copy of state from witnesses. Some effort should be dedicated to refining these strategies and adapting them for the finalized version of the network protocol when that becomes established and implemented.
For now, these remain classified as ‘bonus’ aspects within the tech tree, as they can develop independently of other matters, and their implementation details hinge on more fundamental decisions such as the witness format. It’s worth noting that these extra-protocol topics can serve as useful venues for implementing and testing the more foundational enhancements on the left side of the tree.
Wrapping Up
What a long journey it has been! I hope that the topics, milestones, and the general concept of the “tech tree” have been helpful in framing the scope of “Stateless Ethereum” research.
I intend to keep the structure of this tree updated as progress continues. As mentioned previously, it’s not an ‘official’ or ‘final’ work scope, but rather the most accurate representation we possess at this moment. Please feel free to reach out with suggestions for improvement or amendments.
As always, if you have questions, requests for new topics, or wish to engage in stateless Ethereum research, don’t hesitate to introduce yourself on ethresear.ch, and/or contact @gichiba or @JHancock on Twitter.
