The Revised Stateless Ethereum Tech Tree
I apologize for the postponement of this article; there have been some unavoidable interruptions in my life lately, much like in yours. I hope you are managing to navigate your situation as best you can, regardless of what it entails, and I urge you to maximize your empathy for the coming months, assisting those in your community who are at risk in any way possible :pray:.
That being said, let us delve into Stateless Ethereum and the modifications made to the Tech Tree!
Visually, the tree has undergone a complete redesign, however, if you were to compare it to the initial version, you would observe that much of the content remains unchanged. For the sake of thoroughness and to avoid any misunderstanding, we will still cover everything in this article, so feel free to dismiss that tab you just opened in the background. Without further delay, I present to you the revised Stateless Tech Tree:
Each significant milestone shown in pink signifies a broadly defined category that needs to be “resolved” prior to advancing to more complex ones. These categories are purposely a little ambiguous, and do not represent any specific EIPs or consolidated features, even though some may ultimately be categorized as such.
Smaller components of the tree illustrated in purple are more specific dependencies that will lead to the unlocking of the major milestones. The purple elements are essential in the context that they must be fully comprehended before the milestone can be deemed complete, but they don’t necessarily need to be executed or acknowledged. For instance, it is possible that after further investigation, we might conclude that code merkleization does not sufficiently reduce witness sizes to warrant the time and effort required for implementation; we would then consider it ‘complete’, as it no longer requires further exploration.
As you may have already inferred, items depicted in green are the “side quests” that could theoretically be beneficial in Stateless Ethereum, but may not represent the most effective allocation of a researcher’s limited time and resources. There are likely more such items to be identified along the way; I will add them as necessary.
Furthermore, we have components in yellow that relate to the category of tools. These are yet-to-be-developed software tools that will assist in validating assumptions, testing implementations, and more broadly accelerating the workflow. Ideally, these tools will be of sufficient quality and well-maintained– enough to provide value to the broader developer ecosystem, even beyond the Stateless Ethereum scope.
Alternative Sync Protocol
A significant takeaway from the summit in Paris was that sync is the primary milestone in Stateless Ethereum. Specifically, we need to devise a method for new nodes to obtain the current state trie without depending on the network primitive GetNodeData. Until we devise a reliable substitute for this network primitive (beam sync and fast sync are predicated on it), endeavors to construct Stateless Ethereum will be hindered and could even be counterproductive. It is worthwhile to elaborate on this a bit to clarify why this represents such an issue. If you are unfamiliar with the principles of the Ethereum state, I suggest reviewing my earlier article in this series concerning the topic.
Let’s clarify some terminology first. There isn’t exactly a unique technical definition for the term “network primitive” in this context; it simply refers to “the fundamental grammar of Ethereum network communication” in a trendy way. One client might ask, “hey, what’s the data for the node with hash 0xfoo? And a peer may respond, “oh, it’s 0xbeef. In most instances, the response will include additional hashes of child nodes in the trie, which can then be requested in a similar fashion. This game of marco-polo persists until the requester is satisfied, usually after requesting each of the approximately 400 million nodes in the current state trie individually.
Syncing in this manner can still be quick, as a client can manage multiple tasks, asking various full nodes for different segments of the state simultaneously. However, a more fundamental issue arises in how the primitive operates: the ‘leechers’ soliciting state can do so on their own terms, and they can only obtain what they need from the ‘seeders’, meaning full nodes containing the complete state. This asymmetric interaction is the current operational norm, and it functions sufficiently well due to two interconnected facts about the network: First, there are enough full nodes actively providing state upon request. Second, anyone requesting state will eventually transform into a full node, so the demand for state is self-limiting.
Now we can understand why this poses a problem for Stateless Ethereum: in a stateless framework, nodes that do not maintain the state data they request will have to simply continue requesting data indefinitely. If operating a stateless node is easier than running a full node (which it is), we would expect the number of stateless nodes to increase more rapidly than that of full nodes, eventually resulting in the state being unable to propagate quickly throughout the network. Uh oh.
We cannot delve into additional details at this moment, so I will direct you to Piper’s analysis on the issue, and then we can transition to the emerging solutions, which are all different strategies for enhancing the state sync protocol, either to mitigate the severity of the problem or to resolve it completely. Here are the three most promising alternative sync protocols:
Ethereum Snapshot Protocol (SNAP). We have discussed this previously, though I called it “state tiling”. Recently, it was more thoroughly characterized by Peter in the devp2p repository. Snap divides the state into several large chunks and proofs (around 10,000 trie nodes) that can be reassembled into the complete state. A syncing node would request a subsection of the state from multiple nodes, and within a short time, have an almost complete representation of the state stitched together from approximately 100 different similar state roots. To finalize, the client ‘patches up’ the segment by reverting to getNodeData until it possesses a validstate.
Fire Queen’s Sync. Not a lot has shifted since this was discussed in the initial tech tree article, apart from the title, which merges “firehose” and “Red Queen’s” sync. These are quite alike proposals to substitute getNodeData with a different compilation of primitives for various facets of state.
Merry-go-round. This is a novel concept for synchronization elucidated at a high level on ethresear.ch and more concretely detailed in notes. In merry-go-round synchronization, the entire state is circulated in a predetermined sequence, ensuring that all participants share the same segments of the state trie simultaneously. To synchronize the entire state, one must complete a full “revolution” on the merry-go-round, encompassing all segments of the state. This design features several advantageous properties. Firstly, it enables new nodes joining to contribute instantly to state dissemination, rather than becoming beneficial to the network only post-sync. Secondly, it reverses the current framework of ‘leecher-driven sync’ where nodes lacking data can demand state pieces from complete nodes at will. Instead, new syncing nodes in merry-go-round sync are aware of which segments of state are being offered at any given time and adjust as necessary.
The final sync strategy worth highlighting is beam sync, which is currently supported by not one, but two alternative clients. Beam sync still depends on getNodeData, but it presents an optimal entry point for experimentation and data gathering for these alternative synchronization methods. It’s vital to highlight that there remain numerous uncertainties surrounding sync, and having these distinct, independently developed strategies to address sync is crucial. The upcoming months could be seen as a sync hackathon of sorts, where concepts are prototyped and trialed. Ideally, the strongest features of each of these alternative sync protocols can be integrated into a unified new standard for Stateless Ethereum.
Witness Spec Prototype
There exists a preliminary specification in the Stateless Ethereum specs repository that outlines at a high level the formation of a block witness, and the semantics of constructing and modifying one from the state trie. The intent of this document is to define witnesses without ambiguity, enabling implementers, regardless of client or programming language, to create their own implementation with reasonable assurance that it aligns with other, distinct implementations.
As noted in the most recent call digest, there appears to be no drawback to developing a reference implementation for block witnesses and integrating that into current clients for testing. A witness prototype feature on a client would resemble an optional flag to activate, and having a few testers on the network generating and transmitting witnesses could offer valuable insights for researchers to use in subsequent enhancements.
Two aspects need to be “resolved” before witnesses are robust enough to be regarded as prepared for widespread deployment.
Witness Indexing. This issue is relatively simple: we require a dependable method of determining which witness correlates with which block and associated state. This could be as straightforward as integrating a witnessHash field into the block header, or some alternative that fulfills the same function but in a different manner.
Stateless Tx Validation. This presents an intriguing initial challenge thoroughly summarized on the ethresearch forums. To summarize, clients need to swiftly verify if incoming transactions (awaiting inclusion in a future block) are at least eligible for inclusion in a future block. This prevents malicious actors from overloading the network with fraudulent transactions. However, the current validation process necessitates access to data that is part of the state, namely the sender’s nonce and account balance. If a client is stateless, it won’t be able to perform this validation.
There is certainly more to address than these two specific dilemmas before we achieve a functional prototype of witnesses, but these two matters must undeniably be ‘resolved’ in the quest to deliver a viable prototype to a beam-syncing node nearby.
EVM
As in the original rendition of the tech tree, some modifications will need to be made within the EVM abstraction. Specifically, witnesses must be generated and disseminated across the network, and that process must be accounted for in EVM operations. The topics associated with this milestone are concerned with identifying those costs and motivations, how they’re assessed, and how they can be implemented with minimal repercussions on upper layers.
Witness gas accounting. This remains unchanged from previous discussions. Every transaction will be accountable for a small segment of the complete block’s witness. Creating a block’s witness involves some computation that will be performed by the block’s miner, and as such will require a corresponding gas cost, which will be borne by the transaction’s sender.
Code Merkleization. A significant aspect of a witness is the associated code. Without this feature, a transaction invoking a contract call would necessitate the complete bytecode of that contract to validate its codeHash. That could entail a substantial amount of data, depending on the contract. Code ‘merkleization’ is a technique for partitioning contract bytecode so that only the segment of the code invoked is essential for generating and verifying a witness for the transaction. This is one approach to considerably reducing the average size of witnesses, though it has not yet been thoroughly investigated.
The UNGAS / Versionless Ethereum modifications have been excluded from the ‘critical path’ of Stateless Ethereum. While these features may still hold potential advantages for Ethereum, it became evident during the conference that their values and specifics can and should be deliberated separately from the Stateless objectives.
The Shift to Binary Trie
Transforming Ethereum’s state to a Binary Trie framework is essential for minimizing witness sizes enough to be disseminated across the network without encountering bandwidth/latency complications. In theory, the reduction should exceed three times, though in practice, this figure is slightly less striking (due to the contract code size in witnesses, marking the significance of code merkleization).
The move to an entirely different data representation is a considerably substantial shift, and executing that transition through a hard fork will be a sensitive undertaking. The two approaches mentioned in the previous article remain unchanged:
Progressive. The existing hexary state trie would be converted incrementally over an extended duration. Each transaction or EVM execution that interacts with sections of state would, via this approach, automatically encode adjustments to state into the new binary format. This indicates the implementation of a ‘hybrid’ trie structure that will retain portions of state in their current hexary format. The process would technically never conclude and would be challenging for client developers to execute, yet it would largely shield users and higher-layer developers from the underlying changes taking place in layer 0.
Clean-cut. This approach would generate a new binary trie representation of the state at a specified moment, then proceed in binary format once the new state has been generated. Although more direct from an implementation viewpoint, a clean-cut necessitates coordination from all node operators and would almost certainly result in some (limited) disruption to the network, impacting developer and user experiences during the transition.
Nevertheless, a fresh proposal for the transition has surfaced, which bridges the gap between the progressive and clean-cut methodologies. It is fully discussed on the ethresearch forums.
Overlay. Fresh values from transactions after a specific time are stored directly in a binary tree positioned “above” the hexary, while the “historical” hexary tree is converted concurrently in the background. When the foundational layer has been entirely transformed, the two can be unified.
One further aspect to contemplate for the transition to a binary trie involves the database designs of clients. Presently, all clients utilize the ‘naive’ method for the state trie, storing each node in the trie as a [key, value] pair where the hash of the node serves as the key. It could be that the transition strategy may provide an occasion for clients to migrate to an alternative database configuration, following the model of turbo-geth.
Genuine Stateless Ethereum
The final components of the tree come together after the witness prototype has undergone testing and enhancement, the necessary modifications to the EVM have been executed, and the state trie has transitioned to binary. These are the more distant objectives and side missions that we know must eventually be accomplished, but it may be prudent not to delve too deeply into them until more urgent matters have been addressed.
Mandatory Witnesses. Witnesses must be created by miners, and at this moment it’s uncertain whether spending that additional few milliseconds to produce a witness will be something miners choose to avoid. Some of this can be counterbalanced by adjusting the fees that miners retain from the partial witnesses included with transactions, but a foolproof method is simply to integrate witnesses into the core Ethereum protocol. This is a change that can only transpire once we’re certain everything is functioning as intended, making it one of the final adjustments in the tree.
Witness Chunking. Another more distant characteristic to consider is the capability for a stateless network to circulate smaller segments of witnesses, rather than entire blocks. This would be especially advantageous for partial-state nodes, which might opt to ‘monitor’ the segments of state they are particularly interested in and then depend on corresponding witness pieces for other transactions.
Historical Accumulators. Initially conceived as some form of magical moon mathematics zero-knowledge scheme, a historical accumulator would simplify the verification of a historical witness. This would enable a stateless node to perform checks and queries on, for instance, the historical balances of an account it was interested in, without the necessity to retrieve a specific piece of archived state.
DHT Chain Data. Even though the concept of an Ethereum data delivery network for state has been largely abandoned, it would still be quite beneficial and far simpler to implement one for historical chain data like transaction receipts. This might represent another avenue for enabling stateless clients to gain on-demand access to historical data that would typically be obtained from an archive node.
Stay Secure, and Stay Updated
Thank you for reading, and I appreciate the many warm positive remarks I’ve received recently regarding these updates. I have something even more… magical in store for upcoming posts concerning Stateless Ethereum research, which I’ll be posting periodically on the Fellowship of the Ethereum Magician’s forum, and on this blog when suitable. Until next time, maintain your social distance, and wash your hands frequently!
As always, if you have feedback, inquiries, or topic requests, please @gichiba or @JHancock on Twitter.