Thanks to Toni Wahrstätter for double-checking and feedback. This document describes a construction that tries to maximize non-compressible EL payload size for EIP-7623. The new formula for gas used per transaction is: tx.gasUsed = ( 21000 + max(

Note: if you spot any missing case, feel free to get in touch! This document describes at a high-level test scenarios for EIP-7748 (overview of the EIP). The following are main drivers for potential bugs: The stride allows account partial-migrations i.e., an account is not fully migrated in a single block, so proper resuming of an account migration in multiple blocks should be done. The MPT key values might be stale since previously executed txs i.e., MPT values are stale and must not be moved. The block where an MPT key is moved can have also a tx that writes the state (i.e., both in the same block). Tx revertions in this scenario add a further dimension to cover. EIP-161 accounts are not migrated, thus must not count to the stride quota.

[This document is not deprecated, please continue the discussion in the draft EIP PR] This document contains a draft version of a renewed Binary tree proposal for the Ethereum state. Compared to EIP-3102 it proposes a single balanced tree and pulls other ideas similar to EIP-6800 which are agnostic to Verkle (e.g: packing of account data, storage-slot, and code chunks). Hash-based state-trees have renewed interest due to 1) Potential PQ concerns, 2) Proving systems advancing at a fast pace getting closer to viable proving state via SNARK/STARKs. There are two main open questions about a Binary Tree design: Sparse vs Non-Sparse Which hash function to use for merkelization

This document gives a quick description of the current (2024/12) zkL2 state-tree designs. ZKSync Era Tree: based on Jellyfish Merkle Tree (Diem) Arity: 16 Hash: Blake2s256 for merkelization, field is Goldilocks (more info about field, proving system, etc).The proving system they use is Boojum (based on RedShift) Code of circuits They proving strategy relies on using L4, so that explains why Blake2 is an option. More prover docs here. Tree implementation

Thanks to Guillaume Ballet, Gottfried Herold, Łukasz Rozmej, and Josh Rudolf for the fruitful discussions. Ethereum using Verkle Trees requires a bunch of changes at many layers. Apart from the data structure, gas model, and cryptography changes, the chain will have to migrate the state of the current Merkle Patricia Trie to the new Verkle Tree (assuming no State Expiry is implemented). Without getting into details about the migration method, the current path is to do it via the Overlay tree method. This means we’ll migrate 1 billion (estimated) key values from the Merkle Patricia Tree to the Verkle Tree on each block. I highly recommend watching this EthCC 2023 talk if you want more details. So, what is the relationship between migrating X key-values per block and preimages? On each block, the nodes will deterministically walk the MPT taking the next key-values to migrate. Then, it will insert these same key-values into the VKT. But there’s a catch: the keys in the MPT are Keccak hashed values, but we need the preimages to recalculate the corresponding new key in the VKT. More concretely, one of the key-values to migrate has the MPT key 0xabddde... which results from keccack(someAddress). To know where to store someAddress account information in the new VKT, we need to apply another kind of hashing (Pedersen Hash) to someAddress. Walking the MPT only give us 0xabdde..., but we need the preimage of that hash (i.e: someAddress) to be able to migrate it.

Thanks to Guillaume, Josh, and Dankrad for their feedback. Verkle Trees enables Ethereum to go stateless which requires adding contracts code to the tree in addition to the usual account data and contract storage. This allows stateless clients to validate blocks -- required account data, contract storage and code can be verified with a state proof. Code-chunking is the process of transforming the contract bytecodes into tree key-values. This document analyzes a recent set of ~1 million mainnet transactions to answer: What is the expected code-access gas overhead on current mainnet txs access patterns? How does the 31-byte code-chunker and proposed 32-byte code-chunker compare on real txs? h/t to Paweł Bylica, who inspired the technical angle for this exploration in a chat we had while I was implementing the 32-chunker.

Thanks to Guillaume and Vitalik for discussions and feedback This is a fresh look at Binary Trees in L1, motivated by recent interest, offline discussions, etc. EIP-3102 is still there but might be stale regarding how it would fit more recent ideas introduced in Verkle, which also applies to Binary. This can generate confusion when trying to compare Verkle vs. Binary fairly. These notes might be useful to other core-devs to catch up on the topic and engage in discussions more efficiently. This document is a personal summary, not a formal proposal -- it can have mistakes and be improvable. Reach out if you have any further ideas or improvements! Shape - Sparse vs Prefixed There are two main options for a binary tree:

Verkle testing updates (VIC - 2024-08-26) execution-spec-tests repo The main branch is verkle/main Verkle tests are under tests/verkle folder EIP-6800 tests examples EIP-4762 tests examples Latest release

Why is this relevant for the Verkle conversion? We have to migrate all the data from MPT to VKT The keys in MPT are hashed We need the preimage of the hash to rekey it into the VKT Thus, we need all the preimages of the MPT tree Overlay Tree overview & timeline mental model image Current proposed strategy

Context & goals EOF considered for Prague Verkle considered for Osaka How can each EIP affect each other? Impact for:Ethereum users? VKT spec and implementation? Risks for EOF adoption? TL;DR verkle trees Motivation: viable stateless clients

This document revisits potential Verkle Tree-related Multiscalar Multiplications (MSM) optimizations. The main gist of this round is to focus on how Gottfried Herold's ideas in Notes on MSMs with Precomputation could improve our current (Geth) performance (but the ideas apply to any other VKT crypto library). Refresher on Verkle Trees and MSM Most non-proof-related cryptography in Verkle Trees involves an MSM with a fixed basis of length 256. The fundamental work of the following EL tasks are a fixed-basis MSM calculation: Calculating the tree key for an account header or contract storage slot.

[Note: this document is under review and might be changing in the next days] [Follow-up: Please look at Gottfried document for a more formal approach to the topic] This document explores an attempt to attack a particular branch in a Verkle Tree. By "attack" I mean making that branch have a depth higher than expected. Attacking tree branches isn't a new idea, and it's a known attack vector for any self-balancing tree based on hashes (e.g: the current Merkle Patricia Tree (MPT)). The Ethereum protocol plans to change from a Merkle Patricia Tree to a Verkle tree (VKT). Thus, this tree new design motivates re-exploring this attack vector since:

Note: this document is still a draft This document describes some high-level description of test-vectors to generate, separating in three categories: Cryptography test vectors: test vectors that test fundamental cryptography primitives and border cases. Tree test vectors: test vectors that test tree mutation and key generation. Current repo: verkle-test-vectors Cryptography test vectors

Update (2023-11-28): this document was created ~2023-05 -- all the ideas are still relevant. I've also worked on a parallelized version in the Go library that you might also find interesting here. This document contains notes about implementation optimizations for Verkle Tree proof generation and verification. Some of these optimizations are present in the spec implementation, while others aren't since the spec code is meant to optimize to be understandable. We list them here and provide links to the reference implementation and other documents with explanations (if available). Proof generation PreprocessingCollecting polynomials in eval form involves doing toFr at each relevant internal node to prove, which means doing inversions.[x] Optimization: If you're collecting polynomials of relevant internal nodes recursively, at least batch inverses per node (i.e.: between 1 and 256 Point->Fr transformations per internal node). Do the same on leaf nodes. Idea: Note there's no dependency between levels so that you can batch everything in a single batch. Idea: The EL pipeline might already serialized the tree. Try caching the already calculating Frs and avoid redoing work altogether. (Might consume extra memory).

Last updated: 2023-11-05 The following is an automatically generated report from a modified geth node that captures metrics from the Kaustinen network. This modified geth node is planned to continue running in Kaustinen, so as the state grows and have bigger state we can keep track if the metrics makes sense considering the design. Once in a while I'll be updating this document with fresher reports. Warn: take numbers with a grain of salt -- we're in early stages of Kaustinen and the geth-vkt version is underly heavy development. There might be bugs, optimizable code, etc. If something looks odd, ask!

This document aims to explore if using batch affine additions is faster than adding in projective form for VKT MSM. A while ago Kev mentioned this idea, and we left that convo in "We should do the counting and see", so I'm doing this here. :) What is batch affine point additions? This is a trick used by gnark used in some cases when aggregating points in Pippenger buckets. In our case, we don't use Pippenger to do the MSM but use a precomputed list of points, but the idea can still apply (more on this later). The idea is simple: you have N pair of affine points that you need to aggregate. That's a number of finite field multiplications and inverses. Given that you know the N pairs of affine points upfront, you can use the Montgomery trick for the inverses. The important question is: is that faster than summing in projective form?

This document contains some quick notes comparing calculating $\sqrt{n}$ using the latest gnark ( “normal” Tonelli-Shanks) versus using precomputed tables for solving $b^2 \equiv n^Q \mod{p}$. The optimized version described in this document has the twist of using gnark for doing multiplications, so both approaches can be fairly compared. (gnark has some advanced multiplication optimizations with and without assembly). So, it isn’t that code but a slightly modified version with some plumbing. I’ll call Before to the latest-gnark approach and After to the optimized approach. This optimization is relevant for: Clients running the chain since if they save points in compressed form, they'll have to uncompress them every time you load tree nodes (with potentially many commitments) from disk. Proof verification since the points are compressed.

This is a mirror document to apply the same optimizations I wrote in a document related to Geth libraries. Proof generation Multiproof[Done] Fiat-Shamir: We start by adding all Cs to the transcript. This requires serializing the points. Probably, you store them in projective form in memory, normalize them (i.e: to affine) in batch mode (i.e: Montgometry trick for $Z$ coordinate). [go-ipa] [Done] Aggregate all polynomials by evaluation domain before starting with any heavy work. This avoids repeated heavy work when you're aggregating many openings (which is usually the case). [go-ipa] When calculating $g(x)$, we have to do polynomial division on the domain[x] Rewrite $q_m$ in terms of $q_j$. [spec code, explanation] [x] Removing field inversions in $q_j$ [spec code, explanation] [x] Leverage precomputed terms when calculating $\frac{A'(x_m)}{A'(x_i)}$ [spec code, explanation]. [x] When calculating $g_1(x)$, do batch inversion for $\frac{1}{t-z_i}$ terms.

This document tries to show the maximum number of polynomial openings that a block proof might contain. Rationale The logic is the following: Maximum gas per block is 30M (i.e: 15M*ELASTICITY_MULTIPLIER). A freshly accessed LeafNode incurs in 1900 of gas cost. Max storage-slot accesses (approx): 30M/1900 ~= 16k. Assuming a worst-case scenario of storage-slot access being random, that would mean 16k uniquely accessed LeafNodes. The number of openings that only involve the relevant LeafNodes is 5 openings:3 openings from the extension node (see illustration)1 for position 0 (i.e: 1)

This document contains a comparison between our laste VKT call, and today. The comparsion is in my desktop machine. Results may vary in other setups, so see numbers as guides to signal "good ideas" and not precise speedups. Here we're only mentioning "CPU work". The overall benchmark has other kind of bottlenecks such as disk IO (which are a separate topic). TL;DR Here's a summary of speedups: Total running time: 1.36x speedup [recall overall running time isn't only about VKT stuff]