The WhitePaper Reading Club Singapore [23] 5 Nov 2024
Verkle Tree Stateless Clients Marcus (prev. Nethermind)
Summary
Verkle Trees enable personal devices like smart watches and mobile phones to validate Ethereum's state, because only a small amount of data is needed to prove every new block (as opposed to a relatively larger amount with Merkle Patricia Trees).
Why This Is Important
Stateless clients contribute to Ethereum’s decentralization - as more actors verify incoming blocks, the more confident we can be that block producers are not misbehaving. Using Verkle Trees also reduces overall bandwidth since less data needs to be transmitted to check for inclusion.
Overview
Modifying Ethereum's execution logic and state management to support stateless clients.
Background
(i) As a normal user, we can partake in Ethereum by running a validator node (with stake), which gives us the chance to make the next block and get rewards from people who submit transactions. A more reasonable way to achieve this is to stake with others (via some protocol or pooled with your friends), and some machine will produce blocks on your behalf. However, you do not need to be able to produce blocks to contribute to Ethereum's security (consensus on latest block). (ii) Another method is to verify the correctness of new blocks, which is equally as important for Ethereum in achieving decentralization. State size on Ethereum is big and not every machine can be a block producer, because of how much pre-existing data is needed to execute new transactions. This is where stateless clients come in. If we could somehow verify that block producers are not misbehaving without making the block ourselves, then perhaps we can enable everyday personal devices to do so and increase our validator set. (iii) Currently, we have light clients that allow us to verify on the consensus layer, but this does not give us the same security as running the execution ourselves. To this end, we can make use of Verkle Trees, which enables us to verify on the execution layer, which does indeed give us the same guarantee as though we are running the transactions ourselves.
Components
| Execution Layer | In Ethereum, when someone wants to run a node, they will need to run two programs. One is called the execution client and the other is called the consensus client. The implementations of these clients are team-dependent.The execution client receives new transactions and executes them in an environment called Ethereum Virtual Machine (EVM). This also means that the client needs to keep some local state in a database (e.g. previous block data). The consensus client implements the proof of stake algorithm, i.e. it shares relevant data to the network and participates as an actor in proof of stake. This consensus client is also known as Beacon Node.So, the execution layer runs transactions and the consensus layer ensures the order and validity of these transactions. They communicate with each other via RPCs (Remote Procedure Calls). An example would be block proposal, where the consensus client is selected to produce a block. The consensus client will request the execution client to make a block, which would then be broadcasted by the consensus client once received. A natural question to raise is, if each team has a custom implementation of execution clients, how do we ensure that the EVM logic behaves the same? (*) Implementation teams are aligned through Ethereum Improvement Proposals (EIPs), and economic incentives/disincentives exist to make sure teams are motivated to adhere to a common consensus (note: application programming interface). Usually, these meetings and discussions are done publicly, so anyone can understand what the latest changes being proposed are. |
|---|---|
| Merkle Patricia Trees | Difference between Merkle Trees and Merkle Patricia Tries (MPT): (i) Merkle Trees: A simple tree where each leaf node contains data, and each parent node holds a hash of its children nodes (can be more than 2 if it's not a binary tree). The root hash summarizes all data, providing data integrity. (ii) MPT: Combines Merkle trees with Patricia tries. MPTs support quick key-based lookups and updates, along with some optimisations on disk storage. The details about the optimisations can be found here [REF 1]Tree VS Trie: A tree is a hierarchical data structure with nodes connected by edges, typically used to represent data with parent-child relationships. A trie, or prefix tree, is a specialized type of tree used to store strings where each path from the root to a node represents a prefix of some word, making it efficient for searching and auto-completing words.(i) What is MPT: A MPT is essentially a Radix Trie with some optimisations. Radix Tries combine all leaves down a branch into a single node. Here is an example of a radix trie. A MPT would look like this but with more optimisations.Radix tree(ii) Uses: Organizes and ensures the integrity of state data (like balances and transactions). (iii) Where it’s used: For every block, we keep track of 3 tries using their root hash: receiptsRoot: This root hash is the Merkle root of all transaction receipts in the block. Transaction receipts include details such as gas usage, logs, and the outcome of each transaction, stateRoot: This root hash represents the global state of all accounts after the transactions in the block are processed. It serves as a snapshot of account balances, smart contract data, and other key information and transactionsRoot: This root hash is the Merkle root of all transactions in the block. |
Team
Every execution client needs to implement the necessary changes before the hard fork. Consequently, most execution client teams have at least 1 person actively working on Verkle Trees and preparing for the transition.
Verkle Tree + Stateless Clients
| Verkle Trees | Verkle trees are key-value pairs where the keys are 32-byte elements composed of a 31-byte stem and a 1-byte suffix. They have the same interface as MPT, i.e. you can do the same things as a normal merkle tree, but the main difference involves the lookup process. For Ethereum specifically, one Verkle Tree will be used to store account + storage data, instead of using 2 MPT because we can use 32-byte keys.Instead of using keccak256 hashes, we make use of vector commitments (see section below) instead. These commitments are pieces of data which can prove up to 256 items, each 252 bits in size. The path to leaf is determined by splitting the key into chunks, e.g. "abc" could be split to 3 levels, going from "a" -> "b" -> "c". Since each commitment is 252 bits (31 bytes), we would need to use 2 commitment to reference 32 bytes. This is done by splitting 32 bytes into 2 portion of 16 bytes, denoted as upper and lower segments.There are 2 types of nodes, extension and internal nodes (coloured gray and cyan above). Internal nodes branch up to 256 ways, guiding the search based on key prefixes. Once a path reaches an extension node, the last byte of the key identifies a specific suffix, pointing to one of 256 possible values committed in C₁ and C₂. Each value is split into upper and lower 128-bit segments to fit within field constraints, enabling compact and efficient lookups.Insertion example: 00 00 01 00 00...00 00 is inserted in a verkle tree containing only 00 00 00 00 00...00 00. Because the stems differ at the third byte, two internal nodes are added until the differing byte (C1 and C2) Then another extension node is inserted, with a full 31-byte stem. The initial node is untouched, and C²₀ has the same value as C⁰₀ before the insertion. |
|---|
| Vector Commitments | A commitment refers to some data (bytes) which can be used to prove you know some input value(s), which cannot be falsified (extremely unlikely possibility). Vector commitments would refer to a list of commitments.In the case of Merkle Trees, a commitment usually refers to the root hash of the tree. If you want to prove something exists using the root hash, you would re-generate the root hash with a list of sibling hashes.For Verkle Trees, a commitment refers to some point on a curve (elliptic curve), also known as a multiproof. Consider the leaf node in a Verkle Tree, which contains 2 commitments, called C1 and C2. Each commitment is the result of "grouping" 256 numbers into a single elliptic curve point. This grouping process is done through a commitment scheme, specifically KZG (Kate-Zaverucha-Goldberg) polynomial commitment scheme.A commitment scheme takes some large input data and tries to convince the verifier that it's valid data by sending comparatively smaller pieces of data to prove it, e.g. Merkle Trees and sibling node hashes.KZG polynomial commitment scheme: At a high level, a list of values is transformed into polynomial coefficients to make a polynomial, and we "commit" to this polynomial. This is done by generating some piece of data that proves that we are using a specific polynomial, which cannot be falsified (extremely unlikely possibility). In the case of Verkle Trees, the leaf node stores this polynomial commitment data, which means the leaf node is referring to a specific polynomial. Then, to check if something exists, we verify that passing some value in the polynomial gives the expected output, i.e. f(input) = expected output where f is the polynomial. Each inner node also has its own polynomial, to prove the inclusion of their children inner nodes. So, we would need one proof for each level that we traverse down to the leaf, adding 1 for the leaf node. This actually requries logN number of proofs, but this can be compressed to a fixed size, also known as a multiproof [REF 12].This scheme is useful in zk-rollups and other applications requiring compact proofs for big datasets, though they require pairing-friendly curves, which can impose certain cryptographic constraints, e.g. Keccak hashing is more complex to implement than Pedersen hashing for some curves. | | Execution Clients | As mentioned above, execution clients are a piece of software that serve to run the EVM and handle blockchain state. Anyone can come up with their own implementation, as long as it follows the main specifications outlined in the whitepaper / yellow paper. Execution Layer (EL) Clients and Disk Requirements: Geth: ~1TB+ Nethermind: ~800GB+, Besu: ~1TB+, Erigon: ~600GBEthereum state trie is ~250-300GB currently, depending on client implementation. | | Stateless Clients | Stateless clients in Ethereum verify blocks by using a “witness” (some data) without needing the entire blockchain state, making it faster and require less disk space. By switching from MPT to Verkle Tree, the "witness" data we need is much smaller.Why We Don’t Have Stateless Clients Yet: Stateless client implementation is challenging because it requires efficient witness generation and management, which Ethereum’s current infrastructure and data structure don’t fully support. | | Light Clients | Currently in Ethereum, Light clients are lightweight nodes that serve as trustless RPC endpoints. They participate only in verifying the chain with RPC calls using Merkle roots from block headers, and requesting state proofs from full nodes. Light clients require reimplementation of every RPC method, and due to limitations of Merkle proofs and what is provable - light client development has been slow.Example: It is hard to verify the data returned for the eth_getLogs RPC since it is not supported by Merkle proofs, and the logs root can easily be spoofed in RPCs that return it.Examples: Helios and Lodestar are popular light clients that allow Ethereum interaction with minimal resource requirements. Relevant News: A new $500 device, Ethos, recently launched, allowing users to run the Helios light client, making Ethereum more accessible to individuals without high-end hardware. | | Transition | Why We Can’t Immediately Transition to Verkle Trees: Switching to Verkle trees isn’t straightforward because it would require a hard fork—a network-wide upgrade where all nodes must adopt the new protocol. What Needs to Change for Verkle Trees: (i) State Changes: Ethereum’s state structure would need to be modified to accommodate the new Verkle tree format, impacting data storage and retrieval methods. (ii) Database Changes: Node operators would need to update their databases to store Verkle tree commitments instead of Merkle-Patricia tries, likely requiring a full data migration. (iii) Node Operator Adaptations: For instance, Nethermind would need a new database table to keep track of preimages, which may increase storage reqeuirements. But this may not be the case for other clients.Possible Migration Plans:1. Overlay Tree: after the hard fork, add about 5000 entries from the MPT to the Verkle Tree when processing a new block, so the client would try and look up the Verkle Tree first, falling back to MPT if it does not exist.2. Conversion Node: some nodes will go offline and convert from MPT to Verkle Tree, then the other nodes will fetch the updated Verkle Tree state and use it 3. Local Bulk: every node starts converting while still processing blocks, which drastically increases disk space usage. To ensure there's no denial of service, a new gas model can be proposed during this transition4. State Expiry: create a new Verkle tree and all writes to the original MPT will be done to the Verkle Tree, and lookups will first check if it exists in Verkle Tree, if not then check if it exists in old MPT | | Progress | Preparation for Devnet - KaustinenFinalise EIPs: Review: 2935: Serve historical block hashes from stateDraft: 4762: Statelessness gas cost changesDraft: 6800: Ethereum state using a unified verkle treeDraft: 7612: Verkle state transition via an overlay treeDraft: 7709: Read BLOCKHASH from storage and update costDraft: 7748: State Conversion to Verkle TreeTimelineDevnetEstimated hard forkQuestion: brief summary of latest verkle implementors call | | Other Ways to achieve Stateless Clients | Quantum-resistant approaches: A STARK-ed binary tree uses STARK proofs to ensure quantum-resistant security for blockchain data. Each node contains a STARK proof, confirming data integrity without interactive verification and enabling fast lookups in a balanced binary structure.Advantages: (i) Quantum Resistance: Resistant to quantum attacks due to the lack of vulnerable cryptographic assumptions. (ii) Scalability: Efficient proofs without trusted setups, ideal for high-frequency blockchain operations. (iii) Transparency: Relies on publicly verifiable randomness, boosting security. (iv) Blockchain Applications: STARKed binary trees offer a future-proof, scalable alternative to Merkle and Verkle trees, protecting blockchain data against quantum threats while supporting efficient state and transaction storage. | | Stateless/Light Clients outside of Ethereum | Solana: Tinydancer (light client)Polkadot: substrate connect (light client)Notes: maybe talk about the progress for other chains |
References
- https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/#optimization
- https://ethereum.org/en/developers/docs/nodes-and-clients/
- https://docs.alchemy.com/docs/patricia-merkle-tries
- https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie
- https://ethereum.org/en/roadmap/verkle-trees/
- https://en.wikipedia.org/wiki/Radix_tree
- https://vitalik.eth.limo/general/2024/10/23/futures4.html
- https://github.com/ethereum/pm/issues?q=is:issue+%22verkle+implementers+call%22
- https://notes.ethereum.org/@parithosh/verkle-transition
- https://inevitableeth.com/home/concepts/verkle-tree
- https://github.com/o1-labs/verkle-tree + https://github.com/o1-labs/verkle-tree
- https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
Notes
Questions Covered:
-
what is the execution layer in ethereum?
-
what are some differences between execution layer and consensus layer?
-
what are some interactions between execution and consensus layer?
-
who decides what the execution layer code does?
-
who works on the execution layer?
Questions Covered:
-
what is a Verkle Tree?
-
what is the underlying cryptography of Verkle Trees?
-
why is it better than MPT?
-
what are some downsides?
Questions Covered:
- what are stateless clients?
-
why is this useful?
-
why can't we have it now?This is not a merkle patricia tree, looks like a radix treeYes, I think my wording here is confusing_Marked as resolved__Re-opened_
👌
EF stateless consensus team:
Guillaume Ballet
Ignacio Hagopian
Josh Rudolf
Kevaundray WedderburnAdding context here in case it is confusing later on: We have logsRoot in the transaction receipt. So we need to get the all receipts in the block and the receiptRoot, and generate a merkle proof to verify the receipt. Then we have to get every log in the receipt and verify the logsRoot.
Merkle proofs are very slow to construct and this single RPC call for the end user is actually 2 RPC calls + 2 proof generations, so it is very slow at scale.Good point on scalability!