Written by: Vitalik Buterin
Compilation: Mensh, ChainCatcher
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 reviews.
One of the most powerful features of blockchain is that anyone can run a node on their own computer and verify the correctness of the blockchain. Even if 9,596 nodes running chain consensus (PoW, PoS) immediately agree to change the rules and start producing blocks according to the new rules, anyone running a fully verifying node will refuse to accept the chain. Miners not part of this conspiracy group will automatically converge onto a chain that continues to follow the old rules and keep building that chain, while fully verified users will follow that chain.
This is the key difference between blockchain and centralized systems. However, for this feature to hold, running a fully verified node must be practically feasible for a sufficient number of people. This applies to both proponents (because if proponents do not verify the chain, they are not contributing to enforcing protocol rules) and ordinary users. Nowadays, it is possible to run a node on consumer laptops (including the laptop used to write this article), but it is quite challenging. The Verge aims to change this situation, making the computational cost of fully verifying the chain cheap enough for every mobile wallet, browser wallet, and even smartwatch to validate by default.
The Verge 2023 Roadmap
Initially, 'Verge' referred to moving Ethereum state storage to Verkle Trees—a tree structure that allows for more compact proofs, enabling stateless verification of Ethereum blocks. Nodes can verify an Ethereum block without storing any Ethereum state (account balances, contract code, storage...) on their 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 focused on achieving maximum resource-efficient verification of the Ethereum chain, which includes not only stateless verification technology but also using SNARKs to verify all Ethereum execution.
In addition to the long-term focus on SNARK verifying the entire chain, another new issue relates to whether Verkle Trees are the best technology. Verkle Trees are vulnerable to attacks from quantum computers, so if we replace the current KECCAK Merkle Patricia Trees with Verkle Trees, we would need to replace the trees again in the future. The self-replacement method of Merkle Trees is to directly skip using Merkle branches in STARK and place them in a binary tree. Historically, this approach has been considered infeasible due to overhead and technical complexity. However, recently, we have seen Starkware proving 1.7 million Poseidon hashes per second on a laptop using ckcle STARKs, and with the emergence of technologies like GKB, the proof times for more 'traditional' hashes are also rapidly decreasing. Therefore, in the past year, 'Verge' has become more open, with several possibilities.
The Verge: Key Goals
Stateless clients: the storage space required for fully verifying clients and tagged nodes should not exceed a few GB.
(Long term) fully verifying the chain on a smartwatch (consensus and execution). Download some data, verify SNARK, done.
In this chapter
Stateless clients: Verkle or STARKs
Validity proofs for EVM execution
Validity proofs for consensus
Stateless Verification: Verkle or STARKs
What problem are we solving?
Nowadays, Ethereum clients need to store hundreds of gigabytes of state data to verify blocks, and this amount is increasing every year. The raw state data increases by about 30GB annually, and a single client must store some additional data on top of that to effectively update tuples.
This reduces the number of users who can run a fully validating Ethereum node: while large hard drives capable of storing all Ethereum states or even years of history are widely available, computers that people default to purchasing often only have a few hundred gigabytes of storage. The state size also adds significant friction to the process of initially establishing a node: nodes need to download the entire state, which can take hours or days. This creates various chain reactions. For example, it greatly increases the difficulty for node makers to upgrade their node setups. Technically, upgrades can be done without downtime—by starting a new client, waiting for it to sync, then shutting down the old client and transferring keys—but in practice, this is technically very complex.
How does it work?
Stateless verification is a technique that allows nodes to verify blocks without having the entire state. Instead, each block comes with a witness that includes: (i) the values, code, balances, storage at specific locations in the state that the block will access; (ii) cryptographic proofs that these values are correct.
In fact, implementing stateless verification requires changing the structure of Ethereum's state tree. This is because the current Merkle Patricia Tree is extremely unfriendly for implementing any cryptographic proof scheme, especially in the worst-case scenarios. This applies to both 'raw' Merkle branches and the possibility of 'wrapping' them into STARKs. The main difficulties stem from some weaknesses in MPT.
1. This is a six-way tree (i.e., each node has 16 children). This means that in a tree of size N, an average proof requires 32*(16-1)*log16(N) = 120*log2(N) bytes, or about 3840 bytes for 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. Code is not Merkleized. This means that to prove access to any account code, the entire code must be provided, up to 24,000 bytes.
We can calculate the worst-case scenario as follows:
30000000 gas / 2400 (cold account read cost) * (5 * 488 + 24000) = 330000000 bytes
Branch costs are slightly reduced (using 5*480 instead of 8*480) because when there are more branches, the top part will repeat. However, even so, the amount of data to be downloaded in a time slot is completely unrealistic. If we try to encapsulate it with STARK, we run into two issues: (i) KECCAK is relatively unfriendly to STARK; (ii) 330MB of data means we have to prove 5 million calls to the KECCAK round function, which could be impossible for all hardware except the most powerful consumer-grade hardware, even if we can make STARK prove KECCAK more efficiently.
If we directly replace the hex tree with a binary tree and perform additional Merkleization on the code, the worst-case scenario would roughly become 30000000/2400*32*(32-14+8) = 10400000 bytes (14 is the subtraction of redundancy bits for 2^14 branches, while 8 is the length of the proof entering the code block leaf). It's worth noting that this requires changing gas costs to charge for access to each individual code block; EIP-4762 does this. A capacity of 10.4 MB is much better, but for many nodes, the amount of data to be downloaded in a time slot is still too much. Therefore, we need to introduce more powerful technologies. In this regard, there are two leading solutions: Verkle Trees and STARKed binary hash trees.
Verkle Tree
Verkle Trees use elliptic curve-based vector commitments to achieve shorter proofs. The key to unlocking this is that, regardless of the width of the tree, each parent-child relationship corresponds to a proof part that is only 32 bytes. The only limitation on the proof tree's width is that if the proof tree is too wide, the computational efficiency of the proof will decrease. The proposed implementation width for Ethereum is 256.
Thus, the size of a single branch in the proof becomes 32 - 1og256(N) = 4 * log2(N) bytes. Therefore, the theoretical maximum proof size is roughly 30000000 / 2400 * 32 * (32 - 14 + 8) / 8 = 130000 bytes (the actual result may vary slightly due to uneven distribution of state blocks, but serves as a first approximation).
Additionally, it should be noted that in all the examples above, this 'worst case' is not the worst case: a worse case would be if an attacker intentionally 'mined' two addresses to have a long common prefix in the tree and read data from one of those addresses, which could further double the worst-case branch length. However, even with such a scenario, the worst proof length for Verkle Trees is 2.6MB, which aligns closely with the current worst-case verification data.
We also leveraged this consideration to achieve another thing: we made the cost of accessing 'adjacent' storage spaces very cheap: either many code blocks of the same contract or adjacent storage slots. EIP-4762 provides a definition of adjacency, charging only 200 gas for adjacent accesses. In the case of adjacent access, the worst-case proof size becomes 30000000 / 200 * 32 - 4800800 bytes, which is still roughly within tolerance. If we want to reduce this value for safety, we can slightly increase the cost of adjacent access.
STARKed Binary Hash Tree
The principle of this technology is self-evident: you just need to create a binary tree, obtain a maximum of 10.4 MB of proof, prove the values in the block, and then replace the proof with STARK. Thus, the proof itself only contains the data being proven, plus a fixed overhead of 100-300kB from the actual STARK.
The main challenge here is verification time. We can perform calculations similar to the basic ones above, except we compute hashes instead of byte counts. A 10.4 MB block means 330,000 hashes. Additionally, if the attacker 'mines' addresses in the tree with a long common prefix, the worst-case number of hashes will rise to about 660,000. Therefore, if we can prove 200,000 hashes per second, we should be fine.
On consumer laptops using Poseidon hash functions, these numbers have already been reached, and Poseidon hash functions are specifically designed for STARK friendliness. However, the Poseidon system is still relatively immature, so many people do not yet trust its security. Thus, there are two realistic paths forward:
Quickly conduct a large security analysis of Poseidon and become sufficiently familiar with it to deploy on L1
Use more 'conservative' hash functions, such as SHA256 or BLAKE
If we want to prove conservative hash functions, Starkware's STARK circle can only prove 10-30k hashes per second on consumer-grade laptops at the time of writing this article. However, STARK technology is rapidly improving. Even today, GKR-based technology shows promise in raising this speed to the range of 100-200k.
Use cases for witnesses beyond block verification
In addition to verifying blocks, there are three other key use cases that require more efficient stateless verification:
Mempool: when transactions are broadcast, nodes in the P2P network need to verify whether the transaction is valid before rebroadcasting. Today's verification includes checking signatures, as well as checking that balances are sufficient and prefixes are correct. In the future (e.g., using native account abstraction like EIP-7701, which may involve running some EVM code that performs some state access), if a node is stateless, the transaction needs to come with a proof of the state object.
Inclusion lists: this is a proposed feature that allows (possibly small and simple) proof-of-stake validators to force the next block to include transactions, regardless of the (possibly large and complex) desires of block builders. This would weaken the ability of the powerful to manipulate the blockchain by delaying transactions. However, this requires validators to have a way to verify the validity of transactions in the inclusion list.
Light clients: if we want users to access the chain via wallets (like Metamask, Rainbow, Rabby, etc.), they need to run light clients (like Helios). The Helios core module provides users with verified state roots. And to achieve a completely trustless experience, users need to provide proofs for every RPC call they make (e.g., for Ethereum call requests, users need to prove all states accessed during the call).
All these use cases have one thing in common: they require a considerable number of proofs, but each proof is small. Therefore, STARK proofs are not practically significant for them; conversely, the most realistic approach is to use Merkle branches directly. Another advantage of Merkle branches is that they are updatable: given a proof of a state object X with a root of block B, 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 connections exist with current research?
Verkle Trees
John Kuszmaul's original paper on Verkle Trees
Starkware
Poseidon2 paper
Ajtai (a lattice-hardness-based alternative fast hash function)
Verkle.info
What else can be done?
The remaining main work is
1. More analysis of the implications of EIP-4762 (stateless gas cost changes)
2. Complete and test the transitional programs, which are 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. Further develop ultra-efficient STARK protocol capabilities for 'conservative' (or 'traditional') hashes, such as those based on Binius or GKR.
Additionally, we will soon decide on one of the following three options: (i) Verkle Trees, (ii) STARK-friendly hash functions, and (iii) conservative hash functions. Their features can be roughly summarized in the table below:
In addition to these 'headline numbers', there are other important considerations:
Today, Verkle Tree code is quite mature. Aside from Verkle, using any other code would delay deployment and likely postpone a hard fork. This is not a concern, especially if we need extra time for hash function analysis or validator implementation, or if we have other significant features we wish to incorporate into Ethereum sooner.
Updating the state root with hash values is faster than using Verkle Trees. This means that hash-based methods can reduce the synchronization time for full nodes.
Verkle Trees have interesting witness update properties—Verkle Tree witnesses are updatable. This property is useful for mempools, inclusion lists, and other use cases, and may also help improve implementation efficiency: if a state object is updated, the penultimate layer of the witness can be updated without reading the last layer's content.
Verkle Trees are harder to prove with SNARK. If we want to keep reducing proof sizes to a few kilobytes, Verkle proofs will pose some difficulties. This is because the verification of Verkle proofs introduces a large number of 256-bit operations, which necessitates either a significant overhead for the proof system or having a custom internal structure that includes 256-bit Verkle proof components. This is not a problem for statelessness itself but will introduce more complications.
If we want to achieve Verkle witness updatability in a quantum-safe and reasonably efficient manner, another possible route is Merkle trees based on lattice.
If the efficiency of the proof system is not high enough in the worst case, we can also leverage multi-dimensional gas as this unexpected tool to compensate for this deficiency: by setting separate gas limits for (i) calldata; (ii) computation; (iii) state access, and possibly other different resources. Multi-dimensional gas adds complexity, but in exchange, it more strictly limits the ratio between average and worst-case scenarios. With multi-dimensional gas, the maximum number of branches that need to be proven could theoretically be reduced from 12,500 to, for example, 3,000. This would make BLAKE3 barely sufficient even today.
Multi-dimensional gas allows the resource limits of blocks to be closer to the underlying hardware's resource limits.
Another unexpected tool is to delay the computation of the state root until after the block's time slot. This gives us a full 12 seconds to compute the state root, meaning that even in the most extreme cases, a proof time of only 60,000 hashes per second is sufficient, which again leads us to believe that BLAKE3 can barely meet the requirements.
The downside of this approach is that it adds latency for light clients by one time slot, but there are more clever techniques that can reduce this latency to just the proof generation delay. For example, proofs can be broadcast across the network immediately after being generated on any node, rather than waiting for the next block.
How does it interact with other parts of the roadmap?
Resolving the stateless issue significantly raises the difficulty of solo staking. If there are technologies that can lower the minimum balance for solo staking, such as Orbit SSF or application-layer strategies like team staking, this will become more feasible.
If EOF is introduced simultaneously, multi-dimensional gas analysis becomes much easier. This is because the main execution complexity of multi-dimensional gas comes from handling child calls that do not pass the entire gas of the parent call, and EOF can trivialize this issue by simply making such child calls illegal (and native account abstraction will provide an in-protocol alternative for part of the current main use case of gas).
There is also an important synergy between stateless verification and historical expiration. Nowadays, clients must store nearly 1TB of historical data; this data is several times larger than the state data. Even if a client is stateless, unless we can relieve the client of the responsibility to store historical data, the dream of nearly stateless clients will remain unachievable. The first step in this regard is EIP-4444, which also implies storing historical data in torrents or the Portal Network.
Validity proofs for EVM execution
What problem are we solving?
The long-term goal of Ethereum block verification is clear—it should be possible to verify an Ethereum block by: (i) downloading the block, or even just downloading a small portion of the data availability sampling in the block; (ii) verifying the validity of the block with a small proof. This will be a resource-efficient operation that can be done on mobile clients, browser wallets, or even on another chain (without data availability parts).
To achieve this, SNARK or STARK proofs are needed for (i) the consensus layer (i.e., proof of stake) and (ii) the execution layer (i.e., EVM). The former is a challenge in itself and should be addressed in the ongoing improvements to the consensus layer (e.g., for single-slot finality). The latter requires EVM execution proofs.
What is it, and how does it work?
Formally, in Ethereum specs, the EVM is defined as a state transition function: you have some previous state S, a block B, and you are computing a next state S' = STF(S, B). If the user is using a light client, they do not fully possess S and S', or even E; instead, they have a previous state root R, a next state root R', and a block hash H.
Public inputs: previous state root R, next state root R', block hash H
Private inputs: program block body B, objects accessed in the state by program block Q, the same objects after executing program block Q', state proof (e.g., Merkle branch) P
Claim 1: P is a valid proof that Q contains certain parts of the state represented by R
Claim 2: If STF is run on Q, (i) the execution process only accesses objects within Q, (ii) the data block is valid, (iii) the result is Q'
Claim 3: If the new state root is recomputed using information from Q' and P, it will yield R'
If such a scenario exists, a fully verifying lightweight Ethereum EVM execution client can be achieved. This makes the client's resource requirements already quite low. To create a truly fully verifying Ethereum client, similar work needs to be done on the consensus side.
Implementations of validity proofs for EVM computations already exist and are widely used in L2. However, much work remains to make EVM validity proofs feasible in L1.
What connections exist with current research?
EFPSE ZK-EVM (now deprecated due to better options)
Zeth, which works by compiling EVM to the RISC-0 ZK-VM
ZK-EVM formal verification project
What else can be done?
Today, the validity proofs of electronic bookkeeping systems are deficient in two aspects: security and verification time.
A secure validity proof requires that SNARK truly verifies the computations of the EVM, with no vulnerabilities. The two main techniques to enhance security are multi-verifier and formal verification. Multi-verifier refers to having multiple independently written validity proof implementations, just like having multiple clients; if a block is proven by a sufficiently large subset of these implementations, the client will accept that block. Formal verification involves using tools typically used to prove mathematical theorems, such as Lean4, to prove that the validity proofs only accept correctly executed underlying EVM specifications (e.g. EVM K semantics or the Ethereum execution layer specification (EELS) written in Python).
Sufficiently fast verification time means any Ethereum 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, we need to make progress in three directions:
Parallelization—currently, the fastest EVM validator can prove an Ethereum block in an average of 15 seconds. This is achieved by parallelizing across hundreds of GPUs, then aggregating their work at the end. Theoretically, we know exactly how to create an EVM validator that can prove computations in O(log(N)) time: have one GPU complete each step, then create an 'aggregation tree.'
Challenges exist in achieving this. Even in the worst case, where a very large transaction occupies the entire block, the computation's partitioning cannot be done by calls but must be done by opcodes (EVM or RISC-V, etc., underlying virtual machine opcodes). Ensuring that the 'memory' of the virtual machine stays consistent across different parts of the proof is a key challenge in the implementation process. However, if we can achieve this recursive proof, we know that at least the delay issue for provers is resolved, even without other improvements.
Proof system optimization—new proof systems like Orion, Binius, GRK, and more are likely to significantly shorten verification times for general computation.
Other changes in EVM gas costs—many things in the EVM can be optimized to be more favorable to provers, especially in the worst-case scenarios. If attackers can construct a block that blocks the prover for ten minutes, then being able to prove a standard Ethereum block in just 4 seconds is not enough. The required EVM changes can be roughly classified into the following categories:
Changes in gas costs—if an operation takes a long time to prove, then even if its computational speed is relatively fast, it should have a high gas cost. EIP-7667 is an EIP proposed to address this most severe issue: it significantly increases the gas cost of (traditional) hash functions because the opcodes and precompiles of these functions are relatively cheap. To offset these increased gas costs, we can lower the gas costs of EVM opcodes that are relatively low in proof costs, thus maintaining average throughput.
Data structure replacement—besides replacing the state tree with a more STARK-friendly approach, we also need to replace transaction lists, receipt trees, and other structures with high proof costs. Etan Kissling's proposal to move transactions and receipt structures to SSZ EIP is a step in this direction.
In addition, the two tools mentioned in the previous section (multi-dimensional gas and delayed state roots) can also help in this regard. However, it is worth noting that unlike stateless verification, using these two tools means that we already have sufficient technology to accomplish the work we currently need, and even with these techniques, full ZK-EVM verification will require more work—it just requires less work.
One point not mentioned above is about prover hardware: generating proofs faster using GPUs, FPGAs, and ASICs. Fabric Cryptography, Cysic, and Accseal are three companies that have made progress in this area. This is very valuable for L2, but it is less likely to be a decisive factor for L1, as there is a strong desire for L1 to remain highly decentralized, meaning that proof generation must be within a reasonable range for Ethereum users and should not be bottlenecked by the hardware of individual companies. L2 can make more aggressive trade-offs.
There is still more work to be done in these areas:
Parallelizing proofs requires different parts of the proof system to be able to 'share memory' (such as lookup tables). We know how to do this technically, but it needs to be implemented.
We need to conduct more analysis to identify the ideal gas cost variance set to minimize the worst-case verification time.
We need to do more work on the proof system.
Possible costs include:
Security vs. validator time: opting for more aggressive hash functions, more complex proof systems, or more aggressive security assumptions or other design schemes may shorten validator time.
Decentralization vs. prover time: the community needs to reach consensus on the 'specifications' for the targeted prover hardware. Is it acceptable for provers to be large entities? Do we want high-end consumer laptops to be able to prove an Ethereum block in 4 seconds? Somewhere in between?
The extent of breaking backward compatibility: deficiencies in other areas can be compensated for by more aggressive gas cost changes, but this is more likely to disproportionately increase costs for certain applications, forcing developers to rewrite and redeploy code to maintain economic viability. Similarly, both tools also have their own complexities and drawbacks.
How does it interact with other parts of the roadmap?
The core technology required to implement L1 EVM validity proofs largely overlaps with the other two areas:
L2 validity proofs (i.e., 'ZK rollup')
Stateless 'STARK binary hash proof' method
Successfully implementing validity proofs on L1 will ultimately enable easy solo staking: even the weakest computers (including phones or smartwatches) will be able to stake. This further enhances the value of solving other limitations of solo staking, such as the 32ETH minimum cap.
Moreover, L1 EVM validity proofs can significantly raise the gas limit for L1.
Validity proofs for consensus
What problem are we solving?
If we want to fully verify an Ethereum block using SNARK, then the execution of the EVM is not the only part we need to prove. We also need to prove consensus, which is the part of the system that handles deposits, withdrawals, signatures, validator balance updates, and other elements of Ethereum's proof of stake.
Consensus is much simpler than EVM, but the challenge it faces is that we do not have L2 EVM convolution, so in any case, most of the work must be completed. Therefore, any implementation of Ethereum consensus proofs needs to be 'built from scratch', even though the proof system itself can be built on 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 consists mainly of three parts:
ECADD (used to verify BLS signatures)
Pairing (used to verify BLS signatures)
SHA256 hash value (used for reading and updating states)
In each block, we need to prove 1-16 BLS12-381 ECADDs for each validator (potentially more than one, as signatures may be included in multiple sets). This can be mitigated through subset precomputation techniques, allowing us to say 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 either direction: if we take the 'brute force' route, the number of validators per slot could increase to 1 million. Meanwhile, if using Orbit SSF, the number of validators would remain at 32,768 or even decrease to 8,192.
How BLS aggregation works: verifying the total signatures only requires one ECADD per participant, rather than an ECMUL. However, 30,000 ECADDs is still a large amount of proof.
Regarding pairing, currently there are at most 128 proofs per slot, which means 128 pairings need to be verified. With ElP-7549 and further modifications, this can be reduced to 16 pairings per slot. The number of pairings is small, but the cost is extremely high: the running (or proving) time of each pairing is thousands of times longer than ECADD.
A major challenge in proving BLS12-381 operations is that there is no convenient curve with an order equal to the BLS12-381 field size, which adds significant overhead to any proof system. On the other hand, the proposed Verkle tree for Ethereum is constructed with 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 the proof speed fast enough, clever techniques like GKR will almost certainly be needed.
For SHA256 hashes, the worst case currently is epoch transition blocks, where the entire validator short balance tree and large validator balances will be updated. Each validator's short balance tree is only one byte, so 1 MB of data will need to be rehashed. This equates to 32,768 SHA256 calls. If there are one thousand validators whose balances are above or below a threshold, the valid balance in the validator records will need to be updated, which equates to one thousand Merkle branches, thus potentially requiring ten thousand hashes. The shuffling mechanism requires each validator 90 bits (thus needing 11 MB of data), but this can be calculated at any time within an epoch. In the case of single-slot finality, these numbers may vary based on specific situations. Shuffling becomes unnecessary, although Orbit may restore some of this need.
Another challenge is the need to retrieve all validator states, including public keys, to verify a block. For 1 million validators, just reading public keys requires 48 million bytes, plus Merkle branches. This requires millions of hashes per epoch. If we must prove the validity of PoS, a realistic approach would be some form of incremental verifiable computation: storing a separate data structure in the proof system that is optimized for efficient lookup and proves updates to that structure.
In summary, there are many challenges. To most effectively address these challenges, it will likely require a deep redesign of the beacon chain, which may coincide with the shift to single-slot finality. Features of this redesign might include:
Changes in hash function: currently, the 'full' SHA256 hash function is used, meaning that due to padding, each call corresponds to two calls to the underlying compression function. If we switch to the SHA256 compression function, we can at least achieve a 2x gain. If we switch to Poseidon, we might achieve a 100x gain, thus completely solving all our problems (at least in terms of hashes): at 1.7 million hashes per second (54MB), even a million verification records can be 'read' into proof in a few seconds.
If using Orbit, directly store the shuffled validator records: if a certain number of validators (like 8192 or 32768) are chosen as the committee for a given slot, place them directly adjacent to each other in state so that the public keys of all validators can be read into the proof with minimal hashes. This also allows for all balance updates to be efficiently completed.
Signature aggregation: any high-performance signature aggregation scheme will involve some form of recursive proof, where different nodes in the network will perform intermediate proofs on subsets of signatures. This naturally distributes the proof workload among multiple nodes in the network, significantly reducing the workload of the 'final prover.'
Other signature schemes: for Lamport+Merkle signatures, we need 256 + 32 hashes to verify the signature; multiplying by 32,768 signers gives us 9,437,184 hashes. 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 connections exist with current research?
Concise Ethereum consensus proofs (synchronous committee only)
Concise SP1 within Helios
Concise BLS12-381 precompile
BLS collective signature verification based on Halo2
What work remains to be done, and how to prioritize:
In reality, it will take years to achieve validity proofs for Ethereum consensus. This aligns with the time required to achieve single-slot finality, Orbit, modifications to signature algorithms, and the time needed for security analysis, as sufficient confidence is needed to utilize 'radical' hash functions like Poseidon. Therefore, the most prudent approach is to address these other issues while considering STARK friendliness.
The main trade-off is likely between the order of operations, between a more incremental approach to reforming Ethereum's consensus layer and a more aggressive 'change many at once' approach. For the EVM, the incremental approach is reasonable as it minimizes disruption to backward compatibility. For the consensus layer, the impact on backward compatibility is smaller, and a more 'comprehensive' rethink of various details of how the beacon chain is constructed to optimize for SNARK friendliness is also beneficial.
How does it interact with other parts of the roadmap?
In the long-term redesign of Ethereum PoS, STARK friendliness must be a primary consideration, especially regarding single-slot finality, Orbit, signature scheme changes, and signature aggregation.
