Verkle Trees Vs STARKs: Which of the 2 ultimate routes to Ethereum stateless validation is better?

Ethereum’s network could progress towards stateless validation as its data storage and verification needs grow. Co-founder Vitalik Buterin proposes 2 solutions for this transition—Verkle trees and STARKs.

While both approaches make block verification more efficient and accessible, there are trade-offs regarding security, efficiency, and implementation complexity.

How STARKs weigh as an alternative to Verkle Trees?

Ethereum co-founder Vitalik Buterin has released another blog to explain the network’s possible future. Buterin has focused on stateless validation in this blog, where nodes can verify blocks without storing the full Ethereum state. Touching upon The Verge, he explains that it was earlier aimed at making the Ethereum protocol efficient by making the computational requirements for verification low. However, he adds that the goal now is to verify the chain with SNARKs.

Verkle trees and STARKs, both ways want to make the computational requirements for block verification lower. Meanwhile SNARKs—succinct non-interactive arguments of knowledge—are also part of Ethereum’s future.

Verkle trees would allow nodes to verify Ethereum blocks by generating compact proofs, which will reduce the need for nodes to store the entire state. However, Verkle trees could face potential limitations with quantum computing in the future. He believes that the complex technology is now more viable and could skip Verkle trees altogether.

Meanwhile, The Verge has 2 main goals. The first is to reduce the amount of data a node needs to store to verify Ethereum transactions. The second is to make the computational requirements for verification so low that even mobile devices and smartwatches can participate in the network.

So no matter which route Ethereum takes for stateless verification—Verkle or STARKs—the aim is to address the growing size of data. Buterin stated, “The raw state data increases by ~30 GB per year, and individual clients have to store some extra data on top to be able to update the trie efficiently.”

How deploying Stateless Verification could simplify node setup

Notably, growing size of Ethereum’s data has made it difficult for stakers to set up and upgrade their nodes. Due to this reason, Buterin advocates for stateless validation to solve this issue by letting nodes verify blocks without storing all the data. The process allows nodes to verify blocks using a witness that includes state values and cryptographic proofs. However, for stateless validation to work efficiently, Ethereum’s current Merkle Patricia tree structure would need to be replaced, as it’s not ideal for creating compact, easy-to-verify proofs.

But as stateless verification incorporates Verkle Trees or STARKs, which route would be better for Ethereum? Both methods have strengths and weaknesses. Verkle trees use elliptic curve-based vector commitments, which create compact proofs but may still be vulnerable to future quantum attacks. They are also easier to implement with Ethereum’s current architecture. STARKs, on the other hand, offer smaller proof sizes—about 100-300 kB compared to Verkle’s 2.6 MB—and potentially faster proving times. However, they require more computational power and have yet to be fully integrated into Ethereum’s system.

Ethereum needs to become faster and more efficient not only for verifying blocks but for other applications as well. It includes Mempools, Inclusion Lists, and Light Clients. All these use cases reportedly require a large number of proofs to verify items like account balances and transaction validity. Therefore, simpler Merkle branches might be used over STARK proofs. Buterin specifies that  Merkle branches are updateable and might provide an advantage.

Meanwhile, the Ethereum community needs to also navigate the remaining work. According to Buterin, it includes gas cost analysis with EIP-4762. It will note how changing gas fees for stateless clients would impact Ethereum. And since the switch to statelessness is complex, the transition process also needs to be tested. There is also reportedly a need to analyze the security of new STARK-friendly hash functions like Poseidon, which are less tested. Conducting security analyses of new hash functions and proof systems like SHA256 is also a crucial step.

Ethereum will have to look at quantum-safe cryptography

According to Buterin, the 3 algorithms Verkle, STARK with conservative hash functions and with new hash functions have trade-offs. He explains that Verkle trees are the most ready for deployment but are not quantum-resistant and are harder to prove in advanced systems like SNARKs.

Hash-based approaches (STARKs) can offer faster syncing times for nodes, but the technology still needs more development and security analysis. Verkle trees also allow easy updates (useful for mempools and inclusion lists) but are harder to work with for certain advanced cryptographic proofs (SNARKs).

To deal with these trade-offs, Buterin proposes lattice-based Merkle trees to become a quantum-safe alternative. However, integrating it into the current Ethereum structure would be complex. Another option is to introduce multidimensional gas to separate the efficiency gap between average-case and worst-case scenarios. This means that multidimensional gas could allow Ethereum to reduce the number of hashes needed in extreme cases. With that, Ethereum could delay the state root computation to the next block and increase the time available to generate proofs.

Route to Ethereum scalability will address the storage burden

Buterin’s blog also underlines that validity proofs for the EVM currently face challenges in security and prover time. Ethereum’s scalability and decentralization challenge also comes with addressing the challenges of proof generation. EIP-4444 suggests implementing stateless validation and history expiry to reduce the data storage burden on clients. In addition to that, the current validity proofs need optimization to improve speed and efficiency. Buterin suggests strategies like parallelization and the use of advanced hardware to help accelerate this process.

The Verge will be a transformation for Ethereum, focusing on statelessness and efficient verification. STARK-friendliness will reportedly be important for several other upgrades of the PoS network for it to scale. With whatever challenges remain, trade-offs associated with implementing these technologies also exist.