The Verge will work to enhance Ethereum's scalability and optimize storage utilizing Verkle Trees, a type of mathematical proof improving upon the currently used Merkle proofs. By decreasing the amount of data that validators must store on their computers in order to execute operations, node sizes will decrease, and more users will be able to serve as validators. This will boost network decentralization and security.
Verkle Trees
Verkle trees are a more advanced data structure for state commitments in blockchain technology. These trees offer increased efficiency by reducing the size of proofs and lowering verification costs on-chain. Essentially, Merkle and Verkle trees are similar in structure but have distinct features that set them apart as data structures for state commitments.
In the Tendermint/Cosmos SDK structure, Merkle trees are utilized to share transaction data between nodes, specifically between full nodes and light nodes for the purpose of block verification. In this context, a light node receives a commitment from a full node and acquires a witness, allowing it to construct the root in the block header. In Ethereum, Merkle trees are utilized in the Execution layer, in which block headers consist of three roots of Merkle trees: the state root, the transaction root, and the receipt root. Additionally, Ethereum has a global state tree that updates over time, which increases in size as time goes on. This is one of the reasons why Ethereum is exploring the use of Verkle trees in future releases, as they can minimize the amount of state that full nodes are required to hold, which is referred to as statelessness (weak).
The primary difference between Verkle and Merkle trees is in how they organize their witnesses and, as a result, their sizes. In Verkle trees, instead of providing all the nodes that share a parent, you only need to provide the path to the root. This means that in a wide tree, the path will be much smaller compared to all the sister nodes that would have to be provided in a Merkle tree commitment. Another added commitment that is needed in Verkle trees is vector commitments, which replace the functionality of the sister nodes in Merkle trees. This means that they provide verification that a certain child node is the correct node in the tree while only providing the path itself. This eliminates the need for sister nodes in proof construction, making Verkle trees more efficient than Merkle trees.
Simple Verkle Tree Implementation. Source: Coffee and Rain
Verkle trees are instrumental in transitioning Ethereum clients towards a stateless design. In a stateless environment, clients can validate blocks without retaining the entire state database. Verkle trees facilitate this by generating compact witnesses, which are essentially smaller subsets of necessary state data, required for executing a transaction block, along with cryptographic proof confirming their authenticity. A witness in this context refers to a selection of specific state data needed to execute and validate a block's transactions. It serves as a testament to the accuracy and legitimacy of the transactions and the state alterations they cause. Witnesses are crucial in achieving statelessness for Ethereum clients. They enable these clients to verify block transactions without depending on a full, local copy of the state trie, a substantial data structure representing Ethereum's state.
The adoption of witnesses is key in enabling stateless clients to validate blocks with only the essential data, rather than maintaining a complete local copy of the state. This shift dramatically lowers storage demands for clients, contributing to a more lightweight and scalable system. However, the challenge lies in ensuring that these witnesses are sufficiently compact to be rapidly and efficiently transmitted across the network within the tight confines of a typical 12-second slot.
Verkle trees are adept at creating these small witnesses. They are a hybrid of "Vector commitment" and "Merkle Trees," hence the name "Verkle." Their design allows for efficient and secure data representation, paving the way for stateless clients that can validate blocks without a local state database. This advancement leads to better scalability, reduced storage needs, and increased overall network efficiency.
Verkle trees enable the creation of more compact witnesses compared to Merkle tries by optimizing data structure and representation. In a Merkle Trie, the witness must include the entire path from the leaf nodes (which hold specific state data) to the root hash, encompassing all intermediate hashes and sibling nodes needed for verification. This leads to a bulky witness size.
Conversely, Verkle trees simplify this path, effectively reducing the witness size. They organize data to minimize the required intermediate nodes for proving the inclusion of a leaf node in the tree and eliminate the necessity of including sibling nodes in the witness. This streamlines the witness significantly.
Moreover, Verkle trees incorporate a potent polynomial commitment scheme, enhancing their space efficiency. This scheme ensures that the size of the witness remains constant, regardless of the number of leaves in the tree. The polynomial commitment offers a compact way to represent the witness data, facilitating its transmission across the peer-to-peer network.
This feature of Verkle trees is key to their efficiency and effectiveness in the Ethereum ecosystem. By providing a more space-efficient approach to representing state data, they enable faster and more streamlined block validation by stateless clients, contributing to the overall scalability and performance of the Ethereum network.
