Simple Summary Introduce a new Verkle state tree alongside the existing hexary Patricia tree. After the hard fork, the Verkle tree stores all edits to state and a copy of all accessed state, and the hexary Patricia tree can no longer be modified. This is a first step in a multi-phase transition to Ethereum exclusively relying on Verkle trees to store execution state. Motivation Verkle trees solve the key problem standing in the way of Ethereum being stateless-client-friendly: witness sizes. A witness accessing an account in today's hexary Patricia tree is, in the average case, close to 3 kB, and in the worst case it may be three times larger. Assuming a worst case of 6000 accesses per block (15m gas / 2500 gas per access), this corresponds to a witness size of ~18 MB, which is too large to safely broadcast through a p2p network within a 12-second slot. Verkle trees reduce witness sizes to ~200 bytes per account in the average case, allowing stateless client witnesses to be acceptably small. Specification Verkle tree definition We define a Verkle tree here by providing the function to compute the root commitment given a set of 32-byte keys and 32-byte values. Algorithms for updating and inserting values are up to the implementer; the only requirement is that the root commitment after the update must continue to match the value computed from this specification. We will then define an embedding that provides the 32-byte key at which any particular piece of state information (account headers, code, storage) should be stored.
11/24/2022Special thanks to Justin Drake, Dankrad Feist, Alex Obadia, Hasu, Anders Elowsson and miscellaneous hackmd anons for feedback and review of various versions of this post. Today, Ethereum blocks take 64-95 slots (~15 minutes) to finalize. This was justified as picking a compromise position on the decentralization / finality time / overhead tradeoff curve: 15 minutes is not too long and it's comparable to existing exchanges' confirmation times, it allows users to run nodes on regular computers, even with the large number of validators arising from a deposit size of 32 ETH (as opposed to the earlier value of 1500 ETH). However, there are a lot of good arguments for decreasing the finality time to a single slot. This is a state-of-research post reviewing the roadmap for how to do so. How and why Ethereum staking works today Ethereum's LMD GHOST + Casper FFG consensus is a compromise between the two major styles of consensus popular in proof of stake blockchains: Chain-based consensus, where one message (the block) is produced during each slot (a pre-determined interval of time, eg. 12 seconds in Ethereum). Chain-based consensus maximizes the number of participants and minimizes chain load, but easily forks and does not have any notion of finality. Traditional BFT consensus, where each validator makes two messages ("attestations") per slot in addition to one validator making a block, and one slot's block gets irreversibly "finalized" before the next slot begins. Traditional BFT consensus minimizes time to finality, but at the cost of high chain load and only supporting a small number of participants.
10/20/2022Account abstraction allows us to use smart contract logic to specify not just the effects of the transaction, but also the fee payment and validation logic. This allows many important security benefits, such as multisig and smart recovery wallets, being able to change keys without changing wallets, and quantum-safety. Many approaches to account abstraction have been proposed and implemented to various degrees, see: EIP-86, EIP-2938, and this doc from two years ago. Today, development on EIPs is stalled due to a desire to focus on the merge and sharding, but an alternative that does not require any consensus changes has seen great progress: ERC-4337. ERC-4337 attempts to do the same thing that EIP-2938 does, but through extra-protocol means. Users are expected to send off-chain messages called user operations, which get collected and packaged in bulk into a single transaction by either the block proposer or a builder producing bundles for block proposers. The proposer or builder is responsible for filtering the operations to ensure that they only accept operations that pay fees. There is a separate mempool for user operations, and nodes connected to this mempool do ERC-4337-specific validations to ensure that a user operation is guaranteed to pay fees before forwarding it. ERC-4337 can do a lot as a purely voluntary ERC. However, there are a few key areas where it is weaker than a truly in-protocol solution: Existing users cannot upgrade without moving all their assets and activity to a new account Extra gas overhead (~42k for a basic UserOperation compared to ~21k for a basic transaction)
10/1/2022Currently, we limit the memory consumption of the EVM in two ways: a quadratic memory expansion cost and a de-facto call stack depth limit enforced with the EIP-150 "63/64 rule". These mechanisms are reasonably effective at their desired goal, but are both needlessly complicated and inefficient, punishing regular users too much and DoS attackers too little. This post proposes some alternative designs that better meet the key goal of limiting EVM memory usage. How does memory gas pricing work today? Quadratic memory expansion cost Extending memory in a callframe to $L$ chunks (so, $L * 32$ bytes) requires paying $\lfloor \frac{L^2}{512} \rfloor + 3L$ gas. This is charged in real time. For example, if memory is currently 16 chunks long, and a MSTORE op fills bytes 682...713, then memory is extended to 23 chunks, and $(\lfloor \frac{23^2}{512} \rfloor + 3 * 23) - (\lfloor \frac{16^2}{512} \rfloor + 3 * 16) =$ $(1 + 69) - (0 + 48) = 22$ extra memory expansion gas is charged. See implementation here. Note that this is on a per-call-frame basis: if a call makes a child call, memory in the child call is initialized as empty and pricing for it starts from zero.
7/30/2022