Vitalik on the possible future of Ethereum (Part 4): The Verge

Previous Readings: "Vitalik on the Possible Future of Ethereum (Part 1): The Merge", "Vitalik on the Possible Future of Ethereum (Part 2): The Surge", "Vitalik on the Possible Future of Ethereum (Part 3): The Scourge"

Special thanks to Justin Drake, Hsia-wei Wanp, Guillaume Ballet, Icinacio, Rosh Rudolf, Lev Soukhanoy Ryan Sean Adams and Uma Roy for their feedback and review.

One of the most powerful features of the Block chain is that anyone can run a Node on their computer and verify the correctness of the Block chain. Even if 9596 Nodes running Consensus (PoW, PoS) immediately agree to change the rules and start producing Blocks according to the new rules, everyone running a fully validating Node will refuse to accept the chain. Coin minters who do not belong to this conspiracy will automatically gather on an on-chain that continues to follow the old rules and continue to build this chain, while fully validating users will follow this chain.

This is the key difference between blockchain and centralized systems. However, to make this feature work, it is indeed feasible for enough people to run a fully validating Node. This applies to both miners (because if miners do not validate the chain, they do not contribute to enforcing protocol rules) and ordinary users. Nowadays, running a Node on consumer laptops (including the laptop used to write this article) is possible but difficult. The Verge is aiming to change this situation by making the computational cost of running a fully validating chain affordable, so that every mobile wallet, browser wallet, and even smartwatch will default to validation.

The Verge 2023 Roadmap

Initially, "Verge" referred to the transfer of Ethereum state storage to the Verkle tree - a tree structure that allows for more compact proofs, enabling stateless verification of Ethereum blocks. A Node can verify an Ethereum block without needing to store any Ethereum state (account balances, contract code, storage space, etc.) on its hard drive, at the cost of a few hundred KB of proof data and a few hundred milliseconds of additional time to verify a proof. Today, Verge represents a larger vision, focusing on achieving maximum resource efficiency verification on the Ethereum chain, which includes not only stateless verification technology, but also using SNARK to verify all Ethereum executions.

In addition to long-term follow of the entire chain with SNARK verification, another new issue is related to whether Verkle tree is the best technology. Verkle tree is vulnerable to attacks from Quantum Computer, so if we use Verkle tree in the current KECCAK Merkle Patricia tree, we will have to replace the tree again in the future. The self-replacement method of Merkle tree is to directly skip using Merkle branches and put them into a binary tree with STARKs. Historically, this method has been considered impractical due to cost and technical complexity. However, recently, we have seen Starkware prove 1.7 million Poseidon hashes per second using ckcle STARKs on a laptop, and due to the emergence of technologies like GKB, the proof time for more "traditional" hash values is also rapidly decreasing. Therefore, in the past year, "Verge" has become more open, with several possibilities.

The Verge: Key Objectives

· Stateless client: The storage space required by the fully validated client and the tagged Node should not exceed several GB.

· (Long-term) fully verify the chain (Consensus and execution) on the smart watch. Download some data, verify SNARK, and complete.

In this chapter

· Statelessness client: Verkle or STARKs

· Validity proof executed by EVM

· Consensus validity proof

Statelessness Validation: Verkle or STARKs

What problem are we trying to solve?

Now, the ETH client needs to store hundreds of terabytes of state data to verify Blocks, and this amount is increasing every year. The original state data increases by about 30GB per year, and a single client must store some additional data on top of it to effectively update the triplet.

This reduces the number of users who can run a fully validating Ethereum Node: although it is possible to store all Ethereum states and even years of history on a large hard drive that is readily available, the computers people typically buy only have a few hundred gigabytes of storage space. The size of the state also creates significant friction in the process of setting up a Node for the first time: the Node needs to download the entire state, which can take hours or even days. This creates various chain reactions. For example, it greatly increases the difficulty for Node creators to upgrade their Node settings. Technically, it is possible to complete the upgrade without downtime - start a new client, wait for it to sync, then close the old client and transfer the Secret Key - but in practice, this is very complex technically.

How does it work?

Stateless validation is a technique that allows Nodes to verify Blocks without having the entire state. Instead, each Block comes with a witness that includes: (i) values, code, balance, storage at specific positions in the state that the Block will access; (ii) encryption proofs that demonstrate the correctness of these values.

In fact, achieving stateless verification requires a change in the state tree structure of Ethereum. This is because the current Merkle Patricia tree is extremely unfriendly for implementing any encryption proof scheme, especially in the worst case. Whether it is the "original" Merkle branches or the possibility of being "wrapped" into STARK, the main difficulty arises from some weaknesses of the MPT.

1. This is a 6-ary tree (i.e., each Node has 16 child Nodes). This means that in a tree of size N, a proof requires an average of 32*(16-1)*log16(N) = 120* log2(N) bytes, or approximately 3840 bytes in a tree of 2^32 items. For a binary tree, only 32*(2-1)*log2(N) = 32* log2(N) bytes are needed, or about 1024 bytes.

2. The code has not been Merkleized. This means that to prove any access permission to the account code, the entire code, up to 24000 bytes, needs to be provided.

We can calculate the worst case as follows:

30000000 gas / 2400 (cold account reading cost) * (5 * 488 + 24000) = 330000000 bytes

The branching cost drops slightly (using 5*480 instead of 8*480), as the top part of the branch will be repeated when there are more branches. However, even so, the amount of data to be downloaded within one time slot is completely unrealistic. If we try to encapsulate it with STARK, we will encounter two problems: (i) KECCAK is relatively unfriendly to STARK; (ii) 330MB of data means that we must prove 5 million calls to the KECCAK round function, which may not be proven for all hardware except for the most powerful consumer-grade hardware, even if we can make STARK prove the efficiency of KECCAK.

If we directly use a binary tree to replace the hexadecimal tree and perform additional Merkleization on the code, the worst-case scenario will roughly become 30000000/2400*32*(32-14+8) = 10400000 bytes (14 is the subtraction of redundant bits for 2^14 branches, and 8 is the length of the proof entering the leaf in the code block). It is important to note that this requires changing the gas cost and charging for accessing each individual code block; EIP-4762 does this. 10.4 MB capacity is much better, but for many Nodes, the amount of data downloaded in one time slot is still too much. Therefore, we need to introduce more powerful techniques. In this regard, there are two leading solutions: Verkle tree and STARKed binary hash tree.

Verkle Tree

Verkle trees use vector commitments based on elliptic curves for shorter proofs. The key to unlocking is that, regardless of the width of the tree, each proof part corresponding to a parent-child relationship is only 32 bytes. The only limitation on the width of the proof tree is that if the proof tree is too wide, the efficiency of the proof calculation will drop. The proposed implementation width for Ethereum is 256.

Therefore, the size of a single branch in the proof becomes 32 - 1og256(N) = 4* log2(N) bytes. Therefore, the theoretical maximum proof size is approximately 30000000 / 2400 32 (32 -14 + 8) / 8 = 130000 bytes (the actual calculation result may vary slightly due to the uneven distribution of state blocks, but it is acceptable as a first approximation).

It should also be noted that in all of the above examples, this "worst case" is not the worst case: a worse case is when the attacker intentionally "mines" two Address, giving them a relatively long common prefix in the tree, and reads data from one of the Address, which may further extend the length of the worst case branch by 2 times. But even in such a case, the worst proof length of the Verkle tree is 2.6MB, which is basically consistent with the current worst case verification data.

We also did one more thing with this note: we made the cost of accessing 'adjacent' storage space very cheap: either multiple code blocks from the same contract or adjacent storage slots. EIP-4762 provides a definition for adjacency, and it charges only 200 gas for adjacent access. In the case of adjacent access, the worst-case proof size becomes 30000000 / 200*32 - 4800800 bytes, which is still roughly within the tolerance range. If, for safety reasons, we want to reduce this value, we can slightly increase the cost of adjacent access.

STARK Binary Hash Tree

The principle of this technology is self-evident: you simply need to create a binary tree, obtain a proof of up to 10.4 MB to prove the values in the block, and then replace the proof with the STARK proof. In this way, the proof itself only contains the proven data, plus a fixed overhead of 100-300kB from the actual STARK.

The main challenge here is validating time. We can do the same calculations as above, except instead of counting bytes, we count hash values. A 10.4 MB Block means 330,000 hash values. If we also consider the possibility of an attacker "mining" Address trees with longer common prefixes, then the worst-case hash value would be around 660,000 hash values. So, if we can prove a hash rate of 200,000 per second, then there is no problem.

On consumer laptops using the Poseidon hash function, these numbers have already reached, while the Poseidon hash function is specifically designed for STARK friendliness. However, the Poseidon system is still relatively immature, so many people do not trust its security. Therefore, there are two realistic paths forward:

1. Quickly conduct a large number of security analyses on Poseidon and become familiar enough with it to deploy it at L1.

2. Use a more "conservative" hash function, such as SHA256 or BLAKE

To demonstrate a conservative hash function, Starkware's STARK circle can only prove 10-30k hash values per second on consumer laptops at the time of writing this article. However, STARK technology is rapidly improving. Even today, GKR-based technology shows the potential to increase this speed to the range of 100-2O0k.

Witness usage cases outside of block verification

In addition to verifying Block, there are three other key use cases that require more efficient stateless verification:

• Memory Pool: When a transaction is broadcasted, Nodes in the P2P network need to verify the transaction's validity before rebroadcasting. Today, verification includes checking the signature and also verifying whether the balance is sufficient and the prefix is correct. In the future (for example, using native account abstraction, such as EIP-7701), this may involve running some EVM code that will perform some state access. If the Node is stateless, the transaction needs to be accompanied by proof of the state object.

• Containing list: This is a proposed feature that allows (possibly small-scale and uncomplicated) Proof of Stake validators to force the next Block to include transactions, regardless of the intentions of (possibly large-scale and complex) Block builders. This will weaken the ability of powerful entities to manipulate the Block chain through latency transactions. However, validators need a way to verify the validity of transactions included in the containing list.

· Light client: If we want users to access the chain through a wallet (such as Metamask, Rainbow, Rabby, etc.), they need to run a light client (such as Helios). The core module of Helios provides users with a verified state root. In order to achieve a fully trustless experience, users need to provide proof for every RPC call they make (for example, for an ETH network call request (users need to prove access to all states accessed during the call)).

All of these use cases have one thing in common, which is that they require a considerable amount of proof, but each proof is very small. Therefore, STARK proofs do not make much sense for them; instead, the most practical approach is to use Merkle proofs directly. Another advantage of Merkle proofs is that they are updatable: given a proof of a state object X with Block B as the root, if a sub-Block B2 and its witness are received, the proof can be updated to have Block B2 as the root. Verkle proofs are also natively updatable.

What are the connections with existing research:

· Verkle trees

· John Kuszmaul's original paper on Verkle tree

· Starkware

· Poseidon2 paper

· Ajtai (An alternative fast hash function based on lattice hardness)

· Verkle.info

What else can be done?

The remaining main work is

1. More Analysis on the Consequences of EIP-4762 (Changes in Stateless Gas Cost)

2. More work to complete and test the transition program, which is a major part of the complexity of any stateless environment implementation plan

3. More security analysis on Poseidon, Ajtai, and other 'STARK-friendly' hash functions.

4. To further develop the "conservative" (or "traditional") hash for the ultra-efficient STARK protocol functionality, such as based on the viewpoints of Binius or GKR.

In addition, we will soon decide to choose one of the following three options: (i) Verkle tree, (ii) STARK friendly hash function, and (iii) conservative hash function. Their characteristics can be roughly summarized in the table below:

In addition to these "headline numbers," there are other important considerations:

· Today, the Verkle tree code is quite mature. Using any other code besides Verkle would delay deployment and likely delay a hard fork. This is okay, especially if we need extra time for hash function analysis or validator implementation, or if we have other important features we want to incorporate into Ethereum earlier.

· Updating the state root with hash values is faster than using Verkle trees. This means that the hash-based method can drop the synchronization time of the Full Node.

· The Verkle tree has interesting witnessing update properties - the Verkle tree witness is renewable. This property is useful for mempool, inclusion lists, and other use cases, and may also help improve implementation efficiency: if the state object is updated, the witness of the second-to-last layer can be updated without reading the content of the last layer.

· Verkle trees make it more difficult to perform SNARK proofs. If we want to reduce the proof size to a few thousand bytes, Verkle proofs will pose some challenges. This is because the verification of Verkle proofs introduces a large number of 256-bit operations, which requires either a significant overhead in the proof system or a custom internal structure that includes a 256-bit Verkle proof section. This is not a problem for statelessness itself, but it brings more difficulties.

If we want to achieve the verkle witness upgradability in a quantum-secure and reasonably efficient way, another possible approach is based on lattice-based merkle trees.

If in the worst case, it can be proven that the efficiency of the system is not high enough, then we can also use the unexpected tool of multidimensional gas to make up for this deficiency: separate gas limits for (i) calldata; (ii) computation; (iii) state access, and possible other different resource settings. Multidimensional gas adds complexity, but in exchange, it more strictly limits the ratio between average and worst case. With multidimensional gas, the maximum number of branches that need to be proven theoretically may be reduced from 12500 to, for example, 3000. This would make BLAKE3 barely sufficient even today.

Multidimensional gas allows the resource restrictions of Block to be closer to the resource restrictions of underlying hardware

Another unexpected tool is to calculate the latency of the state root to the Block afterward. In this way, we have a full 12 seconds to calculate the state root, which means that even in the most extreme cases, only 60000 hashes per second proof time is enough, once again making us think that BLAKE3 can barely meet the requirements.

The downside of this approach is that it will increase a light client's latency by one time slot, but there are also more clever techniques that can reduce this latency to only the proof generation latency. For example, proofs can be broadcast on the network immediately after being generated on any node, instead of waiting for the next Block.

How does it interact with other parts of the roadmap?

Solving the statelessness problem greatly increases the difficulty of single-person fixed-point. If there is technology to drop the minimum balance of single-person fixed-point, such as Orbit SSF or Application Layer strategies, such as team fixed-point, this will become more feasible.

If EOF is introduced at the same time, multi-dimensional gas analysis will become much easier. This is because the main source of complexity in multi-dimensional gas execution comes from handling sub-calls that do not pass all gas from the parent call, and EOF only needs to make such sub-calls illegal to make this issue insignificant (and the native account abstraction will provide an alternative solution within the protocol for the current main usage of part of the gas).

There is an important synergy between stateless validation and historical expiry. Today, clients must store nearly 1TB of historical data; this data is several times that of state data. Even if the client is stateless, the dream of almost no storage client will not be realized unless we can relieve the client of the responsibility of storing historical data. The first step in this direction is EIP-4444, which also means storing historical data in torrents or the Portal Network.

Validity proof of EVM execution

What problem are we trying to solve?

The long-term goal of ETH Block verification is clear - it should be possible to verify ETH Block in the following ways: (i) Download the Block, or even just a small portion of the Block's data availability sampling; (ii) Verify a small proof of the Block's validity. This will be a resource-intensive operation that can be completed in a mobile client, browser Wallet, or even in another chain (without data availability portion).

To achieve this, it is necessary to prove (i) the consensus layer (i.e. Proof of Stake) and (ii) the execution layer (i.e. EVM) through SNARK or STARK. The former itself is a challenge, and should be addressed in the process of further improving the consensus layer (e.g., targeting single-slot finality). The latter requires EVM execution proof.

What is it and how does it work?

On a formal level, in the ETH block specification, the EVM is defined as a state transition function: you have a pre-state S, a Block B, and you are computing a post-state S' = STF(S, B). If the user is using a light client, they do not have complete ownership of S and S', or even E; instead, they have a pre-state root R, a post-state root R', and a Block hash value H.

· Public input: previous state root R, subsequent state root R', block hash H

Private Input: Objects in the state accessed by program block B and program block Q, the same objects after executing program block Q', and proof of state (such as Merkle branches) P.

· Proposition 1: P is a valid proof that demonstrates that Q contains certain parts of the state represented by R

· Proposition 2: If STF runs on Q, (i) the execution process only accesses objects inside Q, (ii) the data blocks are valid, (iii) the result is Q'

· Proposition 3: If the information of Q' and P is used to recalculate the new state root, R' will be obtained.

If this is the case, a lightweight client that fully verifies the execution of the ETH blockchain EVM can be owned. This makes the client's resources quite low. To achieve a truly fully verified ETH blockchain client, the same work needs to be done in terms of Consensus.

The implementation of validity proof for EVM computation already exists and is widely used on L2. However, there is still a lot of work to be done to make EVM validity proof feasible on L1.

What are the connections with existing research?

· EFPSE ZK-EVM (discontinued due to better alternatives)

· Zeth, its working principle is to compile EVM into RISC-0 ZK-VM

· ZK-EVM Formal Verification Project

What else can be done?

Currently, the validity proof of the electronic accounting system is lacking in two aspects: security and verification time.

A secure validity proof needs to ensure that SNARK does verify the computation of EVM and there are no vulnerabilities. The two main techniques to enhance security are multi-validator and formal verification. Multi-validator refers to having multiple independent validity proof implementations, just like having multiple clients, and if a Block is proven by a sufficiently large subset of these implementations, the client will accept the Block. Formal verification involves using tools typically used to prove mathematical theorems, such as Lean4, to prove that the validity proof only accepts the correct execution of the underlying EVM specification (such as the EVM K semantics or the ETH execution layer specification (EELS) written in Python).

A fast enough verification time means that any ETH block can be verified in less than 4 seconds. Today, we are still far from this goal, although we are much closer than we imagined two years ago. To achieve this goal, we need to make progress in three directions:

· Parallelism - The fastest EVM validator can currently prove an Ethereum Block in an average of 15 seconds. This is achieved by parallelizing across hundreds of GPUs and then aggregating their work together. In theory, we know exactly how to make an EVM validator that can prove computation in O(log(N)) time: have a GPU perform each step and then create an 'aggregation tree'.

Achieving this presents a challenge. Even in the worst case, that is, when a very large transaction occupies the entire Block, the computation cannot be done in a linear manner, but must be done by opcode (the opcode of the underlying Virtual Machine such as EVM or RISC-V). Ensuring the consistency of the 'memory' of the Virtual Machine between different parts of the proof is a key challenge in the implementation process. However, if we can achieve this recursive proof, then we know that at least the latency problem of the prover has been solved, even if there are no improvements in other aspects.

· Proof system optimization--New proof systems like Orion, Binius, GRK, and more are likely to significantly shorten the verification time for general computing once again.

· Other changes in EVM gas costs - Many things in EVM can be optimized to make it more favorable to validators, especially in the worst case. If an attacker can construct a Block that blocks validators for ten minutes, then it is not enough to prove a normal ETH Block in 4 seconds. The required EVM changes can be roughly divided into the following categories:

• The change in gas costs - if an operation takes a long time to prove, then even if its computation is relatively fast, it should have a high gas cost. EIP-7667 is an EIP proposed to address the most serious issue in this aspect: it greatly increases the gas cost of (traditional) hash functions, as the opcodes and precompiles of these functions are relatively cheap. To offset the increase in these gas costs, we can drop the gas cost of EVM opcodes that prove to be relatively low, thus maintaining the average throughput unchanged.

• Data structure replacement - In addition to replacing the state tree with a more friendly method for STARK, we also need to replace the transaction list, receipt tree, and other costly structures. Moving the transaction and receipt structures to the SSZ EIP is a step in this direction taken by Etan Kissling.

In addition, the two tools mentioned in the previous section (multidimensional gas and latency state root) can also provide assistance in this regard. However, it is worth noting that, unlike stateless validation, using these two tools means that we already have enough technology to complete the work we currently need, and even with the use of these technologies, more work is needed for a complete ZK-EVM validation - just less work is required.

One point not mentioned above is the proof hardware: using GPU, FPGA, and ASIC to generate proofs faster. Fabric Cryptography, Cysic, and Accseal are three companies making progress in this area. This is very valuable for L2, but is unlikely to be a decisive factor for L1, as people strongly desire L1 to maintain a high level of Decentralization, which means proof generation must be within a reasonable range of Ethereum users and should not be limited by the bottleneck of a single company's hardware. L2 can make more proactive trade-offs.

There is still more work to be done in these areas:

· Parallel proof requires demonstrating that different parts of the system can "share memory" (such as lookup tables). We know the technology to do this, but it needs to be implemented.

· We need to conduct more analysis to identify the ideal gas cost change set in order to minimize the verification time in the worst case scenario.

· We need to do more work in the proof system aspect

Possible costs are:

· Security and validator time: Choosing more aggressive hash functions, more complex proof systems, or more aggressive security assumptions or other design schemes may shorten the validator time.

· Decentralization and Prover Time: The community needs to agree on the 'specifications' for the prover hardware in question. Can the prover be a large-scale entity? Can we expect a high-end consumer notebook to prove an ETH block in 4 seconds? Or something in between?

· Degree of breaking backward compatibility: Other shortcomings can be compensated by more active gas cost changes, but this is more likely to disproportionately increase the costs of certain applications, forcing developers to rewrite and redeploy code to maintain economic viability. Similarly, these two tools also have their own complexity and drawbacks.

How does it interact with other parts of the roadmap?

The core technology required to achieve L1 EVM validity proof is largely shared with the other two fields:

· L2 validity proof (i.e. 'ZK rollup')

· Stateless 'STARK binary hash proof' method

Upon successfully achieving validity proof on L1, it is possible to easily stake as a single individual: even the weakest of computers (including mobile phones or smartwatches) can stake. This further enhances the value of addressing other restrictions of single-person stake (such as the minimum limit of 32ETH).

In addition, the EVM validity proof of L1 can greatly increase the gas limit of L1.

Consensus validity proof

What problem are we trying to solve?

If we want to fully verify an ETH block with SNARK, the execution of EVM is not the only part we need to prove. We also need to prove Consensus, which includes the part of the system that handles deposits, withdrawals, signatures, validator balance updates, as well as other elements of the ETH Proof of Stake section.

Consensus is much simpler than EVM, but the challenge it faces is that we don't have L2 EVM convolution, so most of the work has to be done anyway. Therefore, any implementation of the Consensus of ETH blockchain needs to start from scratch, although the proof system itself can be built on a shared work basis.

What is it and how does it work?

The beacon chain is defined as a state transition function, just like the EVM. The state transition function mainly consists of three parts:

· ECADD (used for BLS signature verification)

· Pairing (used for BLS signature verification)

· SHA256 hash value (used for reading and updating state)

In each Block, we need to prove 1-16 BLS12-381 ECADD for each validator (there may be more than one, as the signature may be included in multiple sets). This can be compensated by subset precomputation technology, so we can say that each validator only needs to prove one BLS12-381 ECADD. Currently, each slot has 30,000 validator signatures. In the future, with the implementation of single-slot finality, this situation may change in two directions: if we take the "brute force" route, the number of validators per slot may increase to 1 million. At the same time, if Orbit SSF is adopted, the number of validators will remain at 32,768 or even decrease to 8,192.

How does BLS aggregation work: Verifying the aggregate signature only requires one ECADD per participant, instead of one ECMUL. However, 30000 ECADD is still a large amount of proof.

In terms of pairing, currently each slot can have up to 128 proofs, which means verifying 128 pairs. With ElP-7549 and further modifications, the number of proofs per slot can be reduced to 16. The number of pairings is small, but the cost is extremely high: the runtime (or proof) time for each pairing is several times longer than ECADD.

One of the main challenges of proving BLS12-381 operations is the lack of a convenient curve with curve order equal to the field size of BLS12-381, which adds a considerable overhead to any proof system. On the other hand, the Verkle tree proposed for Ethereum is constructed using the Bandersnatch curve, making BLS12-381 itself a self-curve used to prove Verkle branches in SNARK systems. A relatively simple implementation can prove 100 G1 additions per second; to make proof speeds fast enough, clever techniques like GKR are almost certainly needed.

For the SHA256 hash value, the worst case currently is the epoch transition block, the entire validator short balance tree and a large number of validator balances will be updated. Each validator's short balance tree has only one byte, so 1 MB of data will be rehashed. This is equivalent to 32768 SHA256 calls. If the balance of a thousand validators is higher or lower than a threshold, the valid balance in the validators record needs to be updated, which is equivalent to a thousand Merkle branches, so it may require ten thousand hash values. The shuffle mechanism requires 90 Bit per validator (thus 11 MB of data), but this can be calculated at any time in an epoch. In the case of a single slot termination, these numbers may increase or decrease depending on the specific circumstances. Shuffling becomes unnecessary, although Orbit may partly restore this need.

Another challenge is that to verify a Block, all validator states, including Public Key, need to be reacquired. For 1 million validators, simply reading the Public Key requires 48 million bytes, plus the Merkle branch. This requires millions of hash values for each epoch number. If we have to prove the validity of PoS, a practical approach is some form of incremental verifiable computation: store a separate data structure within the proof system that is optimized for efficient lookup and proving updates to that structure.

In short, there are many challenges. To address these challenges most effectively, it may be necessary to deeply redesign the beacon chain, which may be done in conjunction with a shift to a single-slot termination. The characteristics of this redesign may include:

· Changes to the hash function: Now using the "complete" SHA256 hash function, so due to padding, each call needs to correspond to two calls to the underlying compression function. If we switch to the SHA256 compression function, we can at least double our profits. If we switch to Poseidon, we may get 100 times the gain, thus completely solving all our problems (at least in terms of hash values): 1.7 million hash values per second (54MB), even a million verification records can be "read" in a few seconds in the proof.

· If it is Orbit, the shuffled validator records are stored directly: if a certain number of validators (such as 8192 or 32768) are selected as the committee for a given slot, they are directly placed in the state next to each other, so that the Public Key of all validators can be read into the proof with the minimum hash. This also allows for efficient completion of all balance updates.

· Signature aggregation: Any high-performance signature aggregation scheme will involve some form of recursive proof, where different Nodes in the network will provide intermediate proofs for subsets of signatures. This naturally distributes the proof work to multiple Nodes in the network, greatly reducing the workload of the 'final prover'.

· Other signature schemes: For Lamport+ Merkle signatures, we need 256 + 32 hash values to verify the signature; multiplied by 32768 signers, we get 9437184 hash values. After optimizing the signature scheme, this result can be further improved by a small constant factor. If we use Poseidon, this can be proven within a single slot. However, in practice, using a recursive aggregation scheme would be faster.

What are the connections with existing research?

· Simple ETH Consensus Proof (limited to synchronous committee)

· Helios within the concise SP1

· Concise BLS12-381 Precompiled

· BLS aggregate signature verification based on Halo2

What other tasks need to be done and how to make choices:

In fact, it will take us several years to obtain the validity proof of ETH blockchain Consensus. This is roughly the same amount of time we need to achieve single-slot finality, Orbit, modify the Signature Algorithm, and conduct security analysis. Security analysis requires enough confidence to use "aggressive" hash functions like Poseidon. Therefore, the wisest approach is to address these other issues while considering the friendliness of STARKs.

The main trade-off is likely to be in the order of operations, between a more progressive approach to reforming the Ethereum consensus layer and a more radical 'change many at once' approach. For the EVM, a progressive approach makes sense as it minimizes disruption to backward compatibility. For the consensus layer, there is less impact on backward compatibility and there are benefits to rethinking various details of the beacon chain construction in a more 'comprehensive' way to optimize SNARK-friendliness.

How does it interact with the other parts of the roadmap?

When redesigning ETH PoS for the long term, STARK friendliness must be the primary consideration, especially single-slot finality, Orbit, changes in signature scheme, and signature aggregation.

Original Text Link