Introduction Aim of this research is to design the DA solution of Twine catering to it's unique needs, model will first develop and implement the DA layer for Twine, using both Etheurem L1 and Celestia, and the extend the modification to incorporate a volition kind of model enabling contract deployers and account addresses to enjoy the liberty of choosing their own preferred DA while maintaining a system that can optimize for both security, cost and efficiency at a granular level. The article will incorporate all the details needed for actual implementation and code modifications required in Twine's node and sequencer, which api's to interact including eth-client's and celestia client's, high level construct of appropiate zk-circuits required to construct proof of Data availability and L2 execution, state management and database changes to be introduced in node. High level overview A very high level overview can be: Posting of transaction data to the selected DA Layer. Gathring required proofs and data once the data is posted, from the DA layer. sending the above gathered data with public inputs, along with proof of correct state transition to Settlement contract on L1, which will verify the correctness of data availaibility along with proper rollup execution, image

Content of the blog I worked on verkle trie and state trie migration from MPTs to Verkle in reth execution client as part of my ethereum protocol fellowship cohort 5 from May 2024 to Nov 2024, will go through the depth of that work in this blog post along with explainations of related tech. The Verge Before explaining the verkle structure and my work, let's understand The Verge(the hardfork which will incorporate verkle and stateless validation of the ethereum L1). The Verge is focused on enabling stateless validation of ethereum L1 by moving state storage to verkle trie, and the stateless validation is done by incorporating each block with a witness, which includes: (i) the values (eg. code, balances, storage) at the specific locations in the state that the block will access (ii) a cryptographic proof that those values are correct. and then the execution of the new block is conducted using this witness instead of the local state storage, along with stateless validation. The Verge will be beneficial in also adding these important aspects to L1 ecosystem:

verkle trie will be using Banderwagon curve(https://hackmd.io/@kevaundray/BJ2-L6Nzc), which is defined over scalar field of BLS12-381, which are a family of pairing-friednly elliptic curves, for proving verkle-proofs associated with a VPT. One of the key advantage of verkle trie over merkle is that the proof size does not depend upon the width of the trie, though it depends upon the depth of trie, as the number of commitments to be included in verkle proof increases as the depth of to prove node increase. The main problem that can be encountered here by prover is combining(folding) of all these pedersan-style commitments for batch reduction, the technique of Multi Scalar Multiplication(MSM) is used for this purpose, it involves multiplication of a curve point with a scalar(doubling) and adding of result for getting a folded commitment.A key point to note here is that all these MSM operations will involve native artihmatics of elliptic curve based SNARK optimized for BLS12-381 scalar field. The problem here is, the computational cost of MSM increases with the number of terms involved(say k-commitments are required to be passed to verkle proof for proving the current node), for example: for a 256 bit integer, in a brute force approach we will perform addition and doubling for each bit, this will lead to 256k adds + 256k doubles, these numbers are high, but can be reduced further, for example some naive techniques for operations reduction we may use: combining doubling and adding in MSM process, which leads to making doubling cost trivial, and main cost will be of 256k adds, also we may consider 4 bits at a time for doubling and adding instead of 1-bit a time. There are some named techniques that may used for these optimizations like Stratus method, batch-inversion with sliding window, Yao's algorithm and Pippenger's algorithm. The main challenge lies here will be in balancing the efficiency of MSM operations with the constraints of ZK-circuits, which might limit the use of certain advanced MSM algorithms mentioned above. Another bottlneck is number of arithmatics performed by the verifier in the scalar field of Banderwagon curve for folding claimed evaluations(which are to be proved), these arithmatics are linearly dependant on number of commitments to be evaluated(sent by the prover), and we're unsure of this number of arithmatics, this number will depend upon the underlying batching and opening protocol used, currently we're using PCS multiproofs: PCS multiproofs(https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html) but there are other altervatives like Multipoint, multipolynomial batched openings(https://hackmd.io/f6ShwcCLTfmClTmmmMUjuA?view). As we've seen till now, that folding of commitments through MSM is performed by the prover in native field of ellitic curve based SNARK optimized for BLS12-381, and verfiers work is done in native field of Banderwagon. The problem which will be encountered here is, in many ZkPs especially those optimized for a specific curve (like BLS12-381), arithmetic in other fields (like Banderwagon's scalar field) isn't natively supported, this means we can't directly perform these operations in our proof system, research needs to be done on methods for performing these operations between the two fields, some methods that can be used for this are precomputed look-up tables(https://eprint.iacr.org/2020/315.pdf), casting(https://eprint.iacr.org/2022/1470), range proofs(https://eprint.iacr.org/2024/430) and limb decomposition. Altough, this is not a new problem though, SNARKs that enable recurssive proofs like plonky1 developed by (tag polygon), pickles by (tag Mina) and Halo systems encounters same scenario, these ZKPs enable recurssion by using a pair of elliptic curves, where the base field of one curve is the scalar field of the other, and vice versa, same obstacle is faced in these systems, when verifying a proof from the previous cycle, you need to perform arithmetic in a field that isn't native to the current curve. This is similar to the problem we face with Verkle proofs, where we need to perform arithmetic in Banderwagon's scalar field. This problem is tackled by forwarding parts of proof verification to next cycle, that is to defer some computations to the next proof in the cycle. However, this deferral mechanism itself requires some non-native arithmetic to prove correct storage of deferred computations, ex: You might need to prove you've correctly encoded the deferred computation in a format the next proof can use. This challenge parallels the issue faced in Verkle proofs, where arithmetic in Banderwagon's scalar field is needed but isn't native to the main proving system (assumed to be BLS12-381 based).

week 19 updates New alpha verison of spec tests were launched: https://github.com/ethereum/execution-spec-tests/releases was going through the made changes. Apart from reth modifications, studied joining of devnets and Kurtosis tech. preparing reth for joinning of devnet-7 with as much tests passed till now. week 20 roadmap Next week will be spent on revm modifications for incorporating the remmainign new gas-costs in the interpreter.

week 20 updates This week I spen some time in reading about Verkle Sync: https://hackmd.io/@W3tic1bbRka1R7HA1o1D_A/By_MyNy3h and associated implementation in Nethermind: https://github.com/NethermindEth/nethermind/blob/verkle-sync-devnet-6/src/Nethermind/Nethermind.Synchronization/VerkleSync/VerkleProgressTracker.cs#L115 https://github.com/NethermindEth/nethermind/blob/verkle-sync-devnet-6/src/Nethermind/Nethermind.Synchronization/VerkleSync/VerkleProgressTracker.cs#L101 along with effort of passing 4762 and 6800 spec-tests I will try implementing this process in reth, it will help in further research and benchmarking of Verkle Sync process. I think Besu is looking to implement this, hence will be in touch with them for more information. week 21 roadmap Next week I will resume my work on execution spec tests.

week 18 updates Not much work was done in this week, got stuck on an execution-spec-test for EIP-4762, spent most of the time in resolving that only. verkle execution spec tests: https://github.com/ethereum/execution-spec-tests/tree/verkle/main/tests/verkle week 19 roadmap Next week will aslo be spent on passing these spec-tests

Introduction Verkle trie will be using Banderwagon curve (https://hackmd.io/@kevaundray/BJ2-L6Nzc), which is defined over scalar field of BLS12-381, which are a family of pairing-friendly elliptic curves, for proving verkle-proofs associated with a VPT. Key Advantages One of the key advantage of verkle trie over merkle is that the proof size does not depend upon the width of the trie, though it depends upon the depth of trie, as the number of commitments to be included in verkle proof increases as the depth of to prove node increase. Technical Implementation Multi-Scalar Multiplication (MSM) The main problem that can be encountered here by prover is combining(folding) of all these pedersan-style commitments for batch reduction, the technique of Multi Scalar Multiplication(MSM) is used for this purpose, it involves:Multiplication of a curve point with a scalar(doubling) Adding of result for getting a folded commitment

week 17 updates This week I focused on going through geth's implementation of eip-4762 in detail: There’re two main places where gas cost changes and handling access events happen:The message call logic Particular instructions that affect the witness This function: https://github.com/gballet/go-ethereum/blob/jsign-witness-fix/core/state_transition.go#L352 has the main logic for executing a state transition. Some examples:

week 16 updates This week I focused majorly on implementing the ideas which I got from nethermind implementation: major task is to create an ExecutionWitness struct which will be responsible for managing accessed_leaves, accesed_stems, accessed_branch stores which will be used for determining warm-cold gas costs changes according to eip-4762. this will include functions to add gas cost of witness access during execution of various opcodes whose gas-costs needs to be changed according to eip-4762. all this functions will then lead to creation of new interpreter functions for each opcodes. these interpreter functions will then replace the existing gas-cost function in the main evm loop which executes opcodes. week 17 roadmap Next week I will focus on implementing this changes and going through geth implementation as well.

week 15 updates This week I went through Nethermind's implementation of EIP-4762: The main logic of ExecutionWitness implemented by nethermind for adding modified gas-cost changes can be found here: https://github.com/NethermindEth/nethermind/blob/feature/verkle/src/Nethermind/Nethermind.Evm/Witness/VerkleExecWitness.cs Trie storage design implemented in nethermind for verkle can be found here: https://github.com/NethermindEth/nethermind/blob/feature/verkle/src/Nethermind/Nethermind.Verkle.Tree/TreeStore/VerkleTreeStore.cs week 16 roadmap Next week I will be focusing on formulating the design pattern for revm and reth.

week 14 updates rust-verkle got finally integrated in reth's disk storage, and I raised the pr for the same: feat: verkle integration with disk db Two tests were added to the pr: verkle_storage_cursor_abstraction: tests the cursor which iterates over verkle trie's storage in disk for reads. test_trie_root_commitment: tests computation of trie root using the built VerkleDb reviews were added to this pr, it was found that my method is some what inefficient since the db-Transaction is kept open for a long time which may lead to db bloating due to general working of LMDB databases, will fix this now. week 15 roadmap Next will be focussed on raising prs for EIP-6800 execution-spec-tests and correcting this pr

week 13 updates This week I started working on reth finally, the project started with integration of rust-verkle in reth's disk db. Two methods currently are supported in rust-verkle for any one to utilise rust-verkle: see rocksDB impl either implement similar functionality for reth's MDBX or create a DB struct and implement required traits for it (Flush, ReadOnlyHigherDb, WriteOnlyHigherDb) see here for more reference week 14 roadmap Next week I will focus on completing and raising my pr

week 12 updates This week I focused mostly on Zk-friendliness of verkle tries, tried to benchmark various approaches, and what would be better, Zk-Friendly hash functions for example if we use the method of GKR to reduce the cost of hash function inside a SNARK or elliptc curve based SNARK, most of the week was spent in this only.

week 11 updates Latest verkle-devnet 7 test-fixtures has been released: devnet-7 execution spec tests, once my verkle-trie get integrated completly in reth, and passes basic tests like MPT_to_VKT_conversion_tests then I will begin with these execution spec tests, after talking to Tanishq from Nethermind teamd and Ignacio from geth team, I will be starting with EIP-6800 tests first as they only test basic verkle-trie changes. also follow Ignacio's slide on describing these test-fixtures: verkle testing updates week 12 roadmap Implement devnet-7 execution spec tests in reth, specifically 6800 tests: eip6800_genesis_verkle_tree tests references devnet-7 execution spec tests verkle testing updates

week 10 updates This week I deep dived in exploring LMDBX database structure of reth, the main bottleneck of this project which I will be facing is to add changes to existing database structure of reth, for verkle-integration: there are two ways, that rust-verkle provides for it's integation by client teams: Implement own version of the traits : Flush, WriteOnlyHigherDb, ReadOnlyHigherDb, compatible with client's db structure Implement lower level traits in verkle-db, then use VerkleDb. The traits then the above traits will be automatically implemented using the traits in verkle-db, that is direct implementation of BareMetalDiskDB and BatchDB for reth's database. for more reference see rust-verkle: DB I have decided to move forward with first method first.

week 9 updates a proposal was developed to integrate verkle in reth: reth-verkle PoC started working on the first phase of implementation in reththis involves implementation of two functions: deserialize_and_verify and prove_and_serialize functions these will implement proper proving mechanisms in reth. once we're able to properly verify witness content using verkle-proof, will start with next phase: execution of block using this witness as stateDB week 10 roadmap complete understanding of banderwagon implementation in go-verkle and rust-verkle. add few optimisations and test to rust-verkle repo, which I have in mind complete proper understanding of nethermind implementation

week 7 updates this week I connected with my mentors from the reth team, and finalized this proposal: reth-verkle PoC after that I started reading code of go-verkle. looked after the implementation in geth:geth has all the proving mechanisms in place, that is getting the witness data, then for the provided stateDiffs construction of pre-state trie and verifying the correctness of given witness data against our trusted pre-state root. but witness construction during execution and block execution using witness as stateDB is yet to be implemented. week 9 roadmap this week will focus on exploring banderwagon and IPA implementation in rust-verkle and go-verkle and exploring nethermind implementation

Motivation stateless-cleints are very much necessary for the decentralisation of ethereum, due to following reasons: ethereum's current state size is too large for many nodes to keep in working memory, requiring expensive SSDs for storage and slowing down block validation and chain syncing, stateless clients will allow validators to validate blocks without maintaining the full state, significantly reducing their resource requirements and also reducing sync times. using verkle tries for statelessness makes client architecture more compatible with a Zk-EVM future, with some added explored benefits like increasing of gas-limits to large extents. the main motivation of creating a reth-verkle poc is is to develop more working implementation of verkle-integration in EL-clients, which will help in running interop with other clients, further research and allow reth to prepare for the verge, learn more about why statelessness is important here: Why it's so important to go stateless Abstract this project aims to integrate rust-verkle crytographic primitives into reth, and enable it to act as a stateless client.

articles A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography Exploring Elliptic Curve Pairings KZG polynomial commitments Verkle trie for Eth1 state How does a Merkle-Patricia-trie tree work? Merkling in Ethereum MERKLE PATRICIA TRIE Understanding the ethereum trie bulletproof-style commitments

week 7 updates this week I mostly focused of reading ethereumJS codebase and it's implementation of stateless-client:ethereumJS uses the rust-verkle cryptography compiled into wasm in this repository: https://github.com/ethereumjs/verkle-cryptography-wasm which is then imported in the ethereumjs monorepo as javascript. The two main sections of code where the verkle cryptography is used are:the verkle package: https://github.com/ethereumjs/ethereumjs-monorepo/tree/master/packages/verkle the verkle file in the util package: https://github.com/ethereumjs/ethereumjs-monorepo/blob/master/packages/util/src/verkle.ts VerkleStatelessStateManager provides an overview of how this components are used: https://github.com/ethereumjs/ethereumjs-monorepo/blob/master/packages/statemanager/src/statelessVerkleStateManager.ts week 8 roadmap