How to make Kakarot zk-EVM type 1

Kakarot is currently proving (almost) all the precompiles and opcodes in the same way as Ethereum is running precompiles and the opcodes.

Big issue for kakarot is the proving time of using storage specified by Ethereum as of August 2023. (MPT with keccak hashes of addresses and RLP values).

"The verge" - officialy a roadmap for ethereum should happen in 1.5-2 years per https://github.com/gballet/ estimations. This could potentialy improve proving time of type 1 zkevm on starknet. Why? Because "the verge" removes keccak and uses PCS(polynomial commitemnte scheme) for commiting to values in the trie. PCS specified in VKT is Pedersen commitment + IPA. This document is not about VKT, you can find more here: https://verkle.info/

What's interesting is that curve which pedersen commitment uses is based on bandersnatch which has a base field same as the order of bls12-381. Currently "SNARK" zk rollups use bn254, and STARKs don't even use EC's but still i think there is some work to make STARKs work efficient over non-native fields. Also there is "EC STARK" paper, for making STARK even more friendly but nobody has worked on the implementation for the prover.

Screenshot from https://vitalik.ca/general/2023/03/31/zkmulticlient.html :

This means there is a motivation for kakarot to become zk-evm type 1 in future.

That means we could already start working on Verkle Tries as a storage structure for kakarot. My understanding is that kakarot uses starknet-os for storage: https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/state.cairo which is written in cairo0 and describes "patricia trie" and uses poseidon and/or pedersen hash for crypto primitive.

We could deploy kakarot on madara with "forked" version of state described above where we could write verkle trie instead of patricia trie and that would make kakarot type 1. Maybe i'm wrong here, will discuss with more people this.

There is Garaga repo: https://github.com/keep-starknet-strange/garaga

Which can help in creating crypto primitive for verkle tries. So for pedersen commitment we need:

• bandersnatch eliptic curve
• banderwagon subgroup (i need to investigate how could this be done with Garaga)

Luckly Garaga already has the framework for building <256 bits base field eliptic curves with scalar multiplication. We only need to put bandersnatch parameters and scalar Mul should work. I still need to investigate on points used for pedersen commitment in verkle tries and with that we could create an MSM (pedersen commitment) for verkle tries. Next steps are to create ipa_multipoint, and here's a rust code for that: https://github.com/crate-crypto/ipa_multipoint

I started working on bandersnatch curve PR for Garaga, still need time to finish it.

Then we would need to work on verkle tries structure (leaf nodes, branch nodes, extension and suffix nodes) etc.

But we have time - estimation 1.5-2 years :).