If an attacker can construct a block that blocks a prover for ten minutes, then it is not enough to prove a regular Ethereum block in only 4 seconds. The required EVM changes can be roughly divided into the following categories:
Changes in gas cost – If an operation takes a long time to prove, even if its computation speed is relatively fast, it should have a high gas cost. EIP-7667 is an EIP proposed to address this most serious issue: it significantly increases the gas cost of (traditional) hash functions because the opcodes and precompiles of these functions are relatively cheap. To compensate for the increased gas cost, we can reduce the gas cost of EVM opcodes that have relatively low proof costs, thus maintaining the average throughput.
Data structure replacement – In addition to replacing the state tree with a STARK-friendly method, we also need to replace the transaction list, receipt tree, and other costly structures. Moving the transaction and receipt structures to EIP SSZ is a step in this direction, as done by Etan Kissling.
In addition, the two tools mentioned in the previous section (multivariate gas and delayed state root) can also help in this regard. However, it is worth noting that, unlike stateless validation, using these two tools means that we already have enough technology to do what we need to do at the moment, and even with these technologies, the complete ZK-EVM validation requires more work – just less work is needed.
One point not mentioned in the previous section is the hardware of the prover: using GPUs, FPGAs, and ASICs to generate proofs faster. Fabric Cryptography, Cysic, and Accseal are three companies making progress in this area. This is very valuable for L2, but it is unlikely to be a decisive factor for L1, as people strongly want L1 to remain highly decentralized, which means that proof generation must be within a reasonable range for Ethereum users and not limited by the bottleneck of a single company’s hardware. L2 can make more positive trade-offs.
There is more work to be done in these areas:
Parallelizing proof requirements – Different parts of the proof system should be able to “share memory” (such as lookup tables). We know the techniques to do this, but they need to be implemented.
We need more analysis to find the ideal set of gas cost changes to minimize the worst-case verification time.
We need to do more work on the proof system.
Possible trade-offs include:
Security vs. prover time – If more aggressive hash functions, more complex proof systems, or more aggressive security assumptions or other design choices are chosen, it may be possible to shorten prover time.
Decentralization vs. prover time – The community needs to agree on the “specification” of the prover hardware they are targeting. Can the provers be large entities? Do we want high-end consumer laptops to be able to prove an Ethereum block in 4 seconds? Something in between?
Degree of backward compatibility – Other deficiencies can be compensated for by more aggressive gas cost changes, but this is more likely to disproportionately increase the cost of certain applications, forcing developers to rewrite and redeploy code to maintain economic viability. Similarly, these two tools also have their own complexities and drawbacks.
How does it interact with other parts of the roadmap?
The core technology needed to implement L1 EVM validity proofs is largely shared with the other two areas:
Validity proofs for L2 (i.e., “ZK rollup”)
Stateless “STARK binary hash proofs”
By successfully implementing validity proofs for L1, we can ultimately achieve easy single-person staking: even the weakest computers (including smartphones or smartwatches) can stake. This further improves the value proposition of addressing other constraints on single-person staking, such as the minimum requirement of 32 ETH.
In addition, L1 EVM validity proofs can greatly increase the gas limit for L1.
Validity proofs for consensus
What problem are we trying to solve?
If we want to fully verify an Ethereum block with SNARKs, the execution of the EVM is not the only part we need to prove. We also need to prove the consensus, which involves parts of the system that handle deposits, withdrawals, signatures, validator balance updates, and other elements of Ethereum’s proof of stake.
Consensus is much simpler than the EVM, but the challenge is that we don’t have an L2 EVM convolution, so most of the work needs to be done regardless. Therefore, any implementation of a proof of Ethereum consensus needs to be built “from scratch,” although the proof system itself can be built on top of shared work.
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 primarily consists of three parts:
ECADD (used to verify BLS signatures)
Pairing (used to verify BLS signatures)
SHA256 hashes (used for reading and updating the state)
In each block, we need to prove 1-16 BLS12-381 ECADDs for each validator (possibly more than one as signatures can be included in multiple sets). This can be mitigated through subset precomputation techniques, 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 a “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 either 8,192 or decrease to 3,2768.
How BLS aggregation works: Verifying the overall signature only requires one ECADD per participant, instead of an ECMUL. However, 30,000 ECADDs is still a large amount of proofs.
As for pairing, currently there are a maximum of 128 proofs per slot, which means 128 pairings need to be verified. Through EIP-7549 and further modifications, this can be reduced to 16 per slot. The number of pairings is small, but the cost is extremely high: the runtime (or proof) time for each pairing is thousands of times longer than ECADD.
One major challenge in proving BLS12-381 operations is that there is no convenient curve with a curve order equal to the size of the BLS12-381 field, which adds significant overhead to any proof system. On the other hand, the Verkle tree proposed for Ethereum is built using the Bandersnatch curve, which makes BLS12-381 itself a sub-curve used for proving Verkle branches in SNARK systems. A relatively simple implementation can prove 100 G1 additions per second; to make the proof speed fast enough, clever techniques like GKR are almost certainly needed.
For SHA256 hashes, the worst-case scenario currently is the epoch transition block, where the entire validator short balance trees and a large number of validator balance updates will be updated. Each validator’s short balance tree is only one byte, so 1MB of data will be rehashed. This is equivalent to 32,768 SHA256 calls. If there are a thousand validators with balances above or below a threshold, updates to the effective balance in the validator records will be required, which amounts to a thousand Merkle branches and potentially ten thousand hash calls. The shuffling mechanism requires 90 bits per validator (thus 11MB of data), but this can be computed at any time during an epoch. In the case of single-slot finality, these numbers may change depending on the specifics. Shuffling becomes unnecessary, although Orbit may reintroduce some need for it to some extent.
Another challenge is the need to retrieve all validator states, including public keys, in order to verify a block. For 1 million validators, just reading the public keys requires 48 million bytes, plus the Merkle branches. This requires millions of hash calls per epoch. If we need to prove the validity of PoS, a practical approach is some form of incremental verifiable computation: storing a separate data structure within the proof system that has been optimized for efficient lookup and proving updates to that structure.
In summary, there are many challenges. To address these challenges most efficiently, it is likely that a deep redesign of the beacon chain will be needed, which may coincide with the shift to single-slot finality. The characteristics of this redesign may include:
Changes in hash functions – Currently, a “full” SHA256 hash function is used, so each call corresponds to two underlying compression function calls due to padding. If we switch to SHA256 compression functions, we can gain at least a 2x improvement. If we switch to Poseidon, we may gain a 100x improvement, thus solving all our problems (at least in terms of hash values): we can “read” even a million validator records in seconds at a rate of 1.7 million hash values per second (54MB).
If Orbit is used, store the shuffled validator records directly – If a certain number of validators (such as 8,192 or 32,768) are selected as committees for a given slot, they can be directly placed into adjacent states, requiring minimal hashing to read all validator public keys into the proof. This can also efficiently handle all balance updates.
Signature aggregation – Any high-performance signature aggregation scheme would involve some form of recursive proof where different nodes in the network prove intermediate subsets of signatures. This naturally offloads 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 a signature; multiplied by 32,768 signers, we get 9,437,184 hash values. After optimizing the signature scheme, this 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?
Concise Ethereum consensus proofs (limited to synchronous committees)
Helios within Concise SP1
Concise BLS12-381 precompile
BLS set signature verification based on Halo2
What other work needs to be done and how to trade off:
In practice, it will take several years to obtain validity proofs for Ethereum consensus. This is roughly the same amount of time needed for single-slot finality implementation, Orbit, changes to the signature algorithm, and security analysis, which requires enough confidence to use “aggressive” hash functions like Poseidon. Therefore, the wisest approach is to address these other issues and consider STARK-friendliness while doing so.
The main trade-off is likely to be in the order of operations, between a more gradual approach to reforming the Ethereum consensus layer and a more aggressive “many changes at once” approach. For the EVM, a gradual approach makes sense as it minimizes interference with backward compatibility. For the consensus layer, the impact on backward compatibility is smaller, and there are benefits to rethinking various details of how the beacon chain is constructed to optimize SNARK-friendliness in the best possible way.
How does it interact with other parts of the roadmap?
When rethinking Ethereum PoS for the long term, STARK-friendliness must be a top consideration, especially with single-slot finality, Orbit, changes to the signature scheme, and signature aggregation.
