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 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 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 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