ETH1.x: How to Go to Stateless Ethereum

Original: blog.ethereum

Source: ECN Ethereum China

When I started writing an article with the intention of detailing the "roadmap" for Ethereum 1.x research and how to get to stateless Ethereum, I realized that strictly speaking, this could not be defined as traditional. route map. Although the 1.x team has a common goal, it is an eclectic collective, where developers and researchers work independently and intricately. Therefore, there is no such thing as an "official" roadmap, but this does not mean chaos. Team work follows a default "order", for example, some work must be prioritized, some solutions are mutually exclusive, and some work may be beneficial but not necessary.

If there is no "roadmap" to describe the process to stateless Ethereum, is there a better analogy? It is not easy to find a suitable metaphor, but I think stateless Ethereum is like the "full attribute" in the tech tree [1].

Some readers may immediately understand this analogy, so the next few paragraphs can be skipped. Some readers may not be game enthusiasts. I will explain a little bit: the tech tree is a common mechanism in the game. Players can unlock and upgrade new spells, technologies or skills, usually in a loose level or tree. Structure display classification.

In general, you can "expend" some XP (experience points) to get the elements (attributes) in the tree, and then unlock more advanced elements. Sometimes you need to get two irrelevant basic elements to unlock the third more advanced element, and sometimes unlocking a basic skill will open up more new options for the next upgrade. For players, half of the fun of the game comes from choosing the right path in the tech tree to match their character abilities, goals, and preferences.

The following is my rough technology tree map. I will explain a little bit about the arrangement, each upgrade and its relevance to the whole. The final "full-attribute" upgrade in the tech tree is "stateless Ethereum." In other words, a fully functional Ethereum mainnet will support full-state, partial-state, and zero-state nodes, and will effectively and reliably transmit witnesses and status information. It is ready until the bridge construction of eth2 is completed and able to land on the eth1 chain.

Note: As mentioned earlier, this is not the "official" route of work. These are the key challenges, milestones, and decisions that the 1.x team I have organized and organized must address, with the goal of eventually achieving stateless Ethereum. Feedback is welcome, and the plan will be updated and revised as research progresses.

The reading order is from left to right, and the purple information on the left is the "basic" element, which must be developed and determined before the elements on the right can be continued. The green part indicates that these elements are "benefit" projects in a sense. Although not necessary in the transition process and not specific enough in terms of research, they still have merit. The larger pink shape represents an important milestone for stateless Ethereum. To fully transition to stateless Ethereum, all four major milestones in the diagram must be "unlocked".

Witness paradigm

In the context of stateless Ethereum, there is a lot of discussion about witness. Therefore, my first major milestone is the final witness paradigm. This means that the structure of the state tree and related witnesses must be determined. The specification creation or reference implementation can be considered as a place for eth 1.x research “upgrading”; working on new forms of state will help clarify and focus on other issues that need to be addressed.

Binary tree

It is critical to switch the state of Ethereum to a binary tree structure, which can make the witness small enough to avoid bandwidth / latency issues during network communication. in

In the last researcher meeting [2], the conversion to binary tree structure will need to guarantee one of the following two mutually exclusive strategies:

💫 Progressive. Like the Ship of Theseus [3], the current hexadecimal state tree will be transformed segment by segment over a long period of time. In this way, any transaction or EVM execution involving the state part will automatically encode the state change into a new binary form. This means that with a "hybrid" tree structure, the hibernation state part still retains the current hexadecimal form. This process will never actually be completed, and it will be difficult for client developers to implement, but will largely protect users and higher-level developers from changes that occur behind the scenes at layer 0.

💫 clean and neat. Perhaps this strategy is more in line with the importance of changing the number of states. The strategy will formulate a clear timeline for the transition process by planning multiple hard forks, and calculate a new representation of the binary tree of states. Once the new state calculation is complete, it continues to Represented in binary form. Although not so complicated from an implementation perspective, all node operators need to be coordinated and will almost certainly bring some (limited) disruption to the network, which may affect the developer and user experience during the transition. On the other hand, for the longer-term eth2 transition plan, this process has certain reference value.

No matter which transition strategy is chosen, the binary tree will be the basic structure of the witness, that is, the order and hierarchy of the hashes that make up the state tree. Without optimization, through rough calculation (January 2020), the size of the witness in the hexadecimal tree structure will be reduced from about 800-3400 kB to about 300-1400 kB.

Code chunking (merkleization)

A major component of witnessing is code. Without code chunking, a transaction containing a contract call will require the full bytecode of the contract to verify its codeHash. The code size depends on the contract and can be very large. The code's 'merkleization' is a method of splitting the contract bytecode. It only needs to generate a part of the code to generate and verify the witness of the transaction. This is a technology that greatly reduces the average size of the witness. There are two ways to split the contract code, and it is unclear whether the two are mutually exclusive.

🔷 "Static" chunking. Split the contract code into a fixed size (about 32 bytes). In order for the chunked code to run correctly, this method also requires some additional metadata in each code block.

🔷 "Dynamic" chunking. The contract code is split into multiple pieces according to the content of the code itself, and divided according to the specific instructions (JUMPDEST) contained in it.

At first glance, the "static" chunking approach seems preferable to avoid abstraction leaks, that is, to prevent the content of the split code from affecting lower-level code chunks, which may also occur in the "dynamic" chunking approach. Having said that, both approaches have yet to be fully tested and are therefore only considered options.

Zero Knowledge (ZK) witness compression

About 70% of the witnesses are hashed. It may be possible to use ZK-STARK proof technology to compress and verify those intermediate hashes. There is a lot of research on zero-knowledge-related research, but there is no clear answer on how it works, or even if it works. Therefore, in a sense, this is a branch line in the main technological development route, or an unnecessary upgrade.

EVM semantics

We talked briefly about avoiding "abstract leaks" because it is most relevant to the milestone of EVM semantics, so here I will explain why this concept is so important. EVM is an abstract component of the large Ethereum protocol. In theory, the details of the internal operation of the EVM should not have any impact on the operation of the entire large-scale system, and vice versa, changes in the system should not have any impact on the abstract EVM interior.

However, in fact, certain aspects of the agreement do directly affect the internal operation of EVM. Gas cost is an obvious manifestation. Smart contracts (within the EVM abstraction) have exposed the gas costs of various stack operations (outside the EVM abstraction) through GAS opcodes. Changes to the Gas schedule may directly affect the performance of some contracts, but it depends on the specific situation and how the contract uses the information it has access to.

Due to the "leakage", it is necessary to carefully change the gas scheduling and EVM execution to avoid unexpected impact on smart contracts. This makes us have to face and solve the real problems. It is very difficult to design a system with zero abstraction leaks, and 1.x researchers do not have the time and energy to redesign from scratch. They need to work within the current Ethereum protocol At present, there are very few leaks in the abstraction of virtual state machines.

Back to our topic: the introduction of witnesses will require changes to the gas schedule. Witnesses need to be generated and disseminated on the network, and the activity needs to be included in EVM operations. The related topics of EVM semantic milestones are related to what these costs and incentives are, how to estimate them, and how to achieve them with minimal impact on other higher layers.

Witness Index / Gas Calculation

This section may have many details, and a few sentences may not be explained clearly, and I will explain it in more detail later. Currently, it is only necessary to know that each transaction is only responsible for a small part of the block witness. The generation of the witness of the block requires some calculations. The calculation is performed by the miners of the block, so the related gas costs will be incurred and paid by the transaction initiator.

Since multiple transactions may involve the same part of the state, it is unclear how best to estimate the gas cost of generating a witness when broadcasting a transaction. If the transaction party paid the full cost of the witness generation, we can imagine this situation: when transactions overlap, the same part of the block witness may be paid multiple times. It should be noted that this is obviously not a bad thing, it is just a better understanding of how this situation can bring real change to gas incentives.

No matter what the related gas cost is, the witness itself will need to be part of the Ethereum protocol, and may need to be incorporated into each block as a standard component, just like adding the message witnessHash to each block header.

UNGAS / Unversioned Ethereum

This category is mainly an upgrade orthogonal to stateless Ethereum, related to the gas cost in EVM, and can make up for the abstraction leaks I mentioned. UNGAS refers to "unobservable gas" (unobservable gas). This is a modification that explicitly prohibits the use of GAS opcodes in contracts to prevent smart contract developers from making any predictions about gas costs. UNGAS is

One of the suggestions in the Ethereum core file [4] to make up for some leaks and make future changes to gas scheduling easier to implement, especially those related to witness and stateless Ethereum.

Status availability

Stateless Ethereum does not completely eliminate the state, but makes the state optional, thereby giving the client a certain degree of freedom in tracking and calculating the amount of state. Therefore, the complete status must be provided somewhere so that the node can download part of the status from the complete status.

In a sense, existing paradigms (such as fast sync) already provide this functionality. But the addition of zero state nodes and some state nodes makes the speed of new nodes more complicated. Currently, since all nodes retain a copy of the current state, the new node can download the state from any normal node to which it is connected. However, if some nodes are zero-state nodes or partial-state nodes, this assumption no longer holds.

The prerequisites for reaching the state availability milestone are related to these factors: how nodes tell each other which states they have; how to reliably transfer these states in a continuously changing point-to-point network.

Network propagation rules

The following figure shows the network topology assumptions that may exist in stateless Ethereum. In this network, a node will need to have the ability to locate itself based on the part (if any) of the state it wants to keep.
Improvements such as EIP 2465 [5] belong to the general category of network propagation rules: new message types in network protocols that indicate what information a node has and define how to pass that information to other nodes, which may be in Poor or limited network.

Data transfer model / DHT routing

If improvements such as the above message types are accepted and implemented, nodes will be able to easily determine which parts of the state are retained by other nodes. What if all connected nodes do not have the required state for that node?

Data transfer is an open problem and there are many potential solutions. A "mainstream" solution is to provide some or all of the status via HTTP requests from the cloud server. A more ambitious solution is to use the functions in the relevant peer-to-peer data transfer scheme, allowing requests for partial state to be proxied by connected nodes and distributed through

The hash table [6] finds the correct attribution.

These two extreme schemes are not inherently incompatible, so why can't fish and bear's paw have both?

State tiling arrangement

One way to improve the state distribution is to decompose the complete state into multiple manageable parts (slices) and store them in network caches, which can provide states to the nodes in the network, thereby reducing the burden on the entire node. Even for relatively large state slices, some state slices between blocks may remain the same.

The Geth team performed some experiments on this, and experiments have shown that state slicing helps improve the usability of state screenshots.

Chain pruning

There have been many articles about chain pruning [7], which will not be repeated here. But it must be clear that only through solutions such as state slicing and / or DHT routing solutions, the new node can safely use historical state screenshots at any time, and the full node can safely trim historical data, such as transaction receipts, logs And historical blocks.

Network Protocol Specification

Finally, the full landscape of stateless Ethereum will be the focus of attention. The three milestones of witness paradigm, EVM semantics, and state availability together constitute a complete description of the network protocol specification: well-defined upgrades should be coded into each client implementation and deployed in the next hard fork to The network enters a stateless paradigm.

This article already contains a lot of background knowledge, but there are some subtleties in the picture that need to be explained:

♦ ️ Formal stateless specifications

In summary, we do not have to formally define a complete stateless agreement. It is also reasonable to code the reference implementation directly and use it as the basis for all client re-implementations. However, creating "formal" specifications for witness and stateless clients has irrefutable benefits. This can actually serve as an extension or appendix to the Ethereum Yellow Book, as the specification will describe the expected behavior of the Ethereum stateless client implementation in precise detail.

♦ ️ Optimize Beam Sync, Red Queen's S y nc and other status synchronization methods

Synchronization is not a critical part of a network protocol, but it is a detail that affects how effective nodes execute the protocol. Beam Sync and Red Queen's Sync help create a local copy of the state from the witness. When deciding and implementing the final version of the network protocol, we need to improve the synchronization method to adapt it to the network protocol.

At present, this is a "gain" project in the technology tree, because it can be developed independently of other topics, and its implementation details depend on more basic factors, such as the witness paradigm. It's worth noting that since the topics outside these agreements have no "core" changes, they help implement and test the radical improvements on the left side of the tech tree.

Conclusion

Seeing here, we combed the technology tree from left to right. I hope that the themes, milestones, and general ideas in the "Tech Tree" will help clarify the research scope of "Stateless Ethereum."

I hope to update the structure of the technology tree based on actual progress. As said before, this is not the "official" or "final" scope of work, but the most accurate sketch at the moment. If you have any suggestions for improvement, please contact me.

If you have questions and would like to suggest new topics or join stateless Ethereum research work, please introduce yourself on ethresear.ch or contact @gichiba or @JHancock on Twitter.

Text link:

[1] https://en.wikipedia.org/wiki/Technology_tree

[2] https://blog.ethereum.org/2020/01/17/eth1x-files-digest-no-2/

[3] https://en.wikipedia.org/wiki/Ship_of_Theseus[4] https://corepaper.org/ethereum/#proposals

[5] https://github.com/ethereum/EIPs/issues/2465

[6] https://en.wikipedia.org/wiki/Distributed_hash_table

[7] https://gist.github.com/karalabe/60be7bef184c8ec286fc7ee2b35b0b5b