The Verge -Ethereum’s Efficient Verifiable Query Technique: Verkle Trees

1. Introduction

On the last day of 2023, Vitalik shared Ethereum’s roadmap for 2023 on Twitter, summarizing the progress of Ethereum over the year. The roadmap section “The Verge” described how Ethereum’s technology could verify blockchain states more simply and efficiently. A core concept mentioned there is the Verkle Trees. So, what are Verkle Trees, why Ethereum needs it, and how do Verkle Trees solve problems? The goal of this article is to answer these questions for readers without delving too deeply into cryptography and mathematics, helping those with some understanding of Ethereum quickly grasp the concept of Verkle Trees.

2. Verifiable Query

Verifiable query technology is widely researched in the field of traditional databases, primarily used to solve trust issues with external databases. In many scenarios, data owners might choose not to store data themselves but instead entrust their database needs to a third party to provide database services (such as cloud databases). However, because third parties are not always trustworthy, the credibility of the query results they return to users is difficult to guarantee. The current verifiable query solutions for traditional databases mainly fall into two categories: those based on ADS (Authenticated Data Structures) and those based on verifiable computation.

ADS is a verifiable query technique extensively used in traditional databases, mostly built upon structures like Merkle Trees or similar accumulative structures. With the evolution of cryptographic tools, many researchers have gradually begun to explore the use of verifiable computation techniques to address issues with untrustworthy queries. Some verifiable computation schemes based on Zero-Knowledge Proof protocols, such as SNARKs, can indirectly support verifiable queries for external databases. These schemes support a wide variety of query types and generate less verification information, but they have higher computational overheads.

Currently, Ethereum uses Merkle Trees to implement verifiable queries, and the Verkle Tree technology is also based on Merkle Tree technology. Therefore, let’s first introduce Merkle Trees to help readers understand the role of verifiable queries using them as an example.

3. Merkle Trees

3.1. Definition and Characteristics of Merkle Trees

Merkle Trees are a tree-like structure commonly used in cryptography, suitable for solving data integrity issues. Below is a typical Merkle Tree structure: the leaf nodes represent the original data or their hash values, and each non-leaf (internal) node contains the combined hash of its child nodes.

Merkle Trees have two important characteristics:

1. Tamper-Resistance: Merkle Trees are typically constructed using collision-resistant hash functions, making it computationally infeasible to find two different messages that produce the same hash value. From the structure of a Merkle Tree, it is apparent that any modification to transaction data within a leaf node will result in a change to the root hash of the tree.
2. Efficient Integrity Verification of Large Datasets: Verifiers only need to store the root hash of the Merkle Tree to verify the integrity of any data. This is achieved without transmitting the complete data set, but rather by using sibling nodes along the path from the leaf to the root, known as a Merkle Path. These sibling nodes can be used to reconstruct the root hash for verification purposes.

3.2. How to construct a Merkle proof?

In a common verifiable query scenario, there is a prover and a verifier. The prover needs to generate a proof and send it to the verifier. Corresponding to the Ethereum network, a typical application scenario is where a light node (a client that only stores block headers) queries transaction data from a full node or an archive node (clients with all data) and obtains a Merkle proof to locally verify whether the query result is correct.

The Merkle proof consists of the following three parts:

1. The root hash of the Merkle tree for the complete dataset.
2. The data block whose integrity needs to be proven.
3. The Merkle Path, which includes the values of all sibling nodes on the path from the leaf node to the root node.

Among these, the root hash of the Merkle tree needs to be sent to the verifier in advance through a trustworthy means, and the verifier must trust this value. In Ethereum, the trustworthiness of block data is ensured by the consensus algorithm, and the root hash of the Merkle tree is contained within the block header.

Below is a specific example: when the prover needs to prove to the verifier that “4” is a data block existing in the dataset, and the verifier holds the trusted root hash “1d25” of the complete dataset’s Merkle tree, then the prover only needs to provide all the data marked in blue. Assuming there are n pieces of data in the set, at most 𝘭𝘰𝘨₂(𝘯) hash computations are needed to verify the correctness of any data block.

Ethereum’s light nodes synchronize only the block headers, which contain the roots of Merkle Trees for various sets of data (state tree, transaction tree, receipt tree). When a light node queries a full node for a particular leaf node’s data in the tree, the full node returns the original data along with the corresponding Merkle proof path. This allows the light node to trust the correctness of the query result.

3.3. Variants of Merkle Trees

Building upon the foundation of Merkle Trees, they can be combined and modified with other data structures to achieve new characteristics based on different objectives. To cater to various verifiable query scenarios, Merkle Trees can be extended to various indexed data structures, such as Merkle-B Trees (MBT). For efficient execution of operations like insertion, deletion, and querying, the Ethereum team proposed the Merkle Patricia Tree (MPT).

3.3.1. Merkle-B Tree

The Merkle-B Tree (MBT) is mainly used for handling verifiable range queries. Let 𝑓 be the fan-out of the MBT (the number of child nodes for each node). Based on the B+ tree structure, each internal node of the MBT, besides storing 𝑓 — 1 index keys and pointers to 𝑓 child nodes, also maintains the hash values of all its child nodes in a summarized form. Below is a representation of the structure of leaf nodes and internal nodes in an MBT.

When it is necessary to prove that the data returned from a certain range query conforms to the specified range, the server that computes the Verification Object (VO) must first perform two top-down search operations to find the left and right boundaries. It must also return all the data within this boundary as well as the hashes of all the branches needed to construct the path to the root hash.

The drawback of this data structure is that the returned VO can only prove that the query results are within the requested query range, but it cannot prove that the returned results are complete.

3.3.2. Merkle Patricia Tree

If a naive Merkle Tree is used to provide verifiable queries, the time-consuming process of regenerating the Merkle tree root after each data insertion or deletion can become significant. In addition, it necessitates the maintenance of additional data search trees for storage. The Merkle Patricia Tree (MPT) combines attributes of a Radix Tree (compact prefix tree) and a Merkle Tree, allowing it to perform insertions, deletions, and queries in O(log(N)) time. For a complete understanding of MPT, readers can refer to detailed technical articles on the subject. This article will only introduce some basic definitions and provide examples to help readers quickly understand MPT.

Ethereum’s underlying structure employs a key-value database for storage, meaning data is stored in the form of key-value pairs. The MPT is also decomposed into key-value pairs for storage. We define the logical structure of MPT nodes as follows:

• index
• path
• data

In the context of the Merkle Patricia Tree (MPT), the “index” refers to the key of a key-value pair, while the “path” combined with the “data” constitutes the value of the key-value pair. The index actually stores the hash of the Merkle tree node, and the path corresponds to the path string used in the prefix tree to find the target node. Ethereum uses hexadecimal strings as path strings, and therefore the width of the MPT is 16. The data is the target data corresponding to the path.

Below is an example of an MPT that has been optimized with compressed prefixes, storing the following key-value pair data:

{

‘cab8’: ‘dog’,

‘cabe’: ‘cat’,

‘39’: ‘chicken’,

‘395’: ‘duck’,

‘56f0’: ‘horse’

}

To find the data “duck” using the path “395,” you would start at the root hash and proceed through hashA, hashC, and hashD to ultimately reach the target data. Here’s a step-by-step guide:

1. Root Hash: This is the entry point of the Merkle Patricia Tree (MPT), and you would use it to find the first node.
2. hashA: Based on the root hash, you would retrieve the node or content identified by hashA. Since the path is “395,” you’re looking for the part of the tree that will lead you to “3”.
3. hashC: After accessing the content of hashA, you continue to follow the path. The next segment, “9”, leads you to hashC.
4. hashD: Finally, continuing down the path, the last segment “5” points you to hashD, which contains the value “duck”.

At each step in the path, the MPT leverages the properties of both the Radix Tree, for finding the correct path based on the key, and the Merkle Tree, for ensuring the integrity of the data through hash links. The “paths” in the tree are typically represented with a hexadecimal encoding, which corresponds with the tree’s branching factor of 16. Each node in the path includes enough hash pointers (to children nodes) and values to verify the integrity of the data and to navigate through the tree.

Please note that in a real MPT, the paths and the data would be encoded and stored in a specific format, and additional types of nodes (such as extension nodes and leaf nodes) help to optimize the structure for efficiency in different scenarios.

4. Vector Commitment

Commitment[1] schemes are cryptographic primitives that ensure data privacy and integrity. They are widely used in scenarios such as zero-knowledge proofs and secure multiparty computation. A basic commitment scheme is divided into two stages: the commit phase and the reveal (or open) phase.

1. Commit Phase: In this phase, the committer uses a cryptographic algorithm to bind a message to a commitment value and sends this commitment value to the recipient. At this stage, the commitment possesses two properties: hiding and binding. Hiding ensures that the content of the committed message is unknown to everyone except the committer. Binding ensures that once a commitment has been made, it cannot be altered by anybody, including the committer.
2. Reveal (Open) Phase: During this phase, the committer can prove to the recipient that the commitment value they received is a valid commitment to the original message. The commitment has the property of correctness, meaning that if both the committer and the recipient follow the protocol correctly, the recipient will be convinced that the commitment value they received during the commit phase is a valid commitment to the original message.

Vector Commitment is a special type of commitment scheme proposed by Catalano et al. [2] that allows a committer to make a commitment to an ordered set of messages 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ and to reveal (open) at any specified position to prove that message 𝑚𝑖 is the ith committed message. In vector commitments, binding means that no one can open the same position to reveal different messages.

A vector commitment scheme typically consists of the following algorithms:

5. Verkle Trees

5.1. Definition and Characteristics of Verkle Trees

Definition：Verkle Trees = Vector Commitments + Merkle Trees。

Please note：Vitalik Buterin, the co-founder of Ethereum, has a blog post specifically dedicated to introducing Verkle trees. This chapter adds some background and mathematical knowledge based on his blog. Some of the data and illustrations in the following text are derived from his blog.

Verkle Trees (VTs) are characterized by providing smaller proofs compared to Merkle Trees. For data on the scale of billions of entries, a Merkle tree might generate proofs around 1KB in size, whereas Verkle tree proofs can be less than 150 bytes. This compact proof size is advantageous for implementing “stateless clients”.

The structure of a Verkle tree is somewhat similar to that of the Merkle Patricia Tree (MPT). Here’s an example of its structure. The nodes of a Verkle tree can be: (i) Empty, (ii) Leaf nodes containing a key and its corresponding value, or (iii) Internal nodes with a fixed number of child nodes. This number of children is also referred to as the “width” of the tree.

The difference between VT (Verkle Trees) and MPT (Merkle Patricia Trees) lies primarily in how the tree width (or fan-out, which refers to the number of child nodes a node in the tree has) affects their efficiency. In the case of MPT, if the width is larger, it tends to be less efficient because a greater width means more sibling nodes, which could lead to longer update times for the MPT and larger proof sizes. Conversely, for VT, a wider tree width results in smaller proofs. The only restriction is that if the width is too high, the time it takes to generate a proof can become longer.

In Ethereum’s @vbuterin/verkle_tree_eip">design proposals for VTs, a width of 256 is suggested, which is significantly larger than the current 16 for MPT. Such a large width is feasible in VTs because of the use of advanced cryptographic techniques, such as vector commitments, that enable compact proofs regardless of the tree’s width. This compression technique allows Verkle Trees to scale more efficiently in terms of proof size. The subsequent text will explain the features mentioned above in more detail.

5.2. Commitment and Proof of Verkle Trees

Let’s see how proofs are generated in an MPT: The proof needs to include the hash values of all the side nodes (or sister nodes) on the path from the root node to the target leaf node. Taking “4ce” as an example, the parts marked in red in the diagram below are the nodes that need to be included in the returned proof.

In Verkle trees, you do not need to provide sibling nodes; instead, you only need to provide the path along with some additional data as evidence.

So how to generate commitments for a VT? The hash function used for computation is not a conventional hash but uses vector commitments.

After replacing the hash function with a commitment generation algorithm from vector commitments, the so-called root hash is now a root commitment. If any node’s data is tampered with, it will ultimately affect the root commitment.

How to generate a proof? As shown in the diagram below, you only need to provide three sub-proofs, each of which can prove that a node on the path exists at a certain position within its parent node. The wider the width, the fewer the layers, and consequently, the fewer sub-proofs are required.

In practical implementations, polynomial commitments are utilized (which can be implemented simply and efficiently for vector commitments), allowing for a commitment to a polynomial. The two most user-friendly polynomial commitment schemes are “KZG commitments” and “bulletproof-style polynomial commitments (the former has a commitment size of 48 bytes, while the latter is 32 bytes).

If you employ KZG commitments and proofs, the proof for each intermediate node is merely 96 bytes, which represents a space saving of nearly three times compared to a basic Merkle tree (assuming a width of 256).

The theoretical time complexity for operations on Merkle trees and Verkle trees is as follows:

The Verkle proof scheme introduced so far is quite basic; in fact, there are further advanced optimization strategies available.

5.3. Optimization: Merging the Proofs

5.3.1. idea

Compared to generating a proof for each layer of commitments on a path, the characteristic of polynomial commitments can be utilized to achieve “proving the parent-child relationship between all commitments on the path with a proof of fixed size, which can include an unlimited number of elements.” To understand specifically how this is accomplished, it is necessary to introduce some mathematical knowledge for explanation. This article will involve some mathematical formulas but will not cover the cryptographic part of the proof in principle. For the specific method, please refer to scheme that implements multiproofs through random evaluation.

5.3.2. Mathematical derivation

First, let’s introduce some basic concepts about polynomials in mathematics: how do we perform polynomial reduction, also known as degree reduction of a polynomial?

Assuming that we know a polynomial 𝑃(𝑥) and its value 𝑦₁ at 𝑥₁，that is 𝑃(𝑥₁) = 𝑦₁ .

Now, consider a new polynomial 𝑃(𝑥) - 𝑦₁ , which has a value of zero at (𝑥 = 𝑥₁) , because 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.

Tererfore, The polynomial 𝑃(𝑥) - 𝑦₁ has a root at 𝑥 = 𝑥₁ ，which means that (𝑥 - 𝑥₁ ) is a factor of 𝑃(𝑥) - 𝑦₁ .

In other words, we can express it in the following form: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) is another polynomial whose degree is one less than that of 𝑃(𝑥). This is beacuse (𝑥 -𝑥₁ ) is a first-degree factor, which reduces the total degree of the polynomial.

How to use KZG to prove a single value in a vector?

Take the KZG10 commitment as an example, for the polynomial 𝑃(𝑥) , suppose its polynomial commitment is [ 𝑃(𝑠) ]₁ .

As previously explained, for the polynomial 𝑃(𝑥) , if 𝑃(𝑧) = 𝑦 , then we have 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)

Now, the prover can generate a proof that the polynomial 𝑃(𝑥) satisfies 𝑃(𝑧) = 𝑦 : compute [ 𝑄(𝑠) ]₁ and send it to the verifier.

The verifier needs to verify 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

How to use KZG to prove multiple values in a vector?

We can construct a proof to demonstrate multiple values in a vector as follows:

By using this method, regardless of the number of data points in the same vector that need to be verified, only a proof of constant size is required.

Now let’s look at the Verkle Tree scheme without optimization from the perspective of the KZG commitment algorithm.

Using the construction method from the section “How to use KZG to prove a single value in a vector,” the verifier can construct commitments for the original and quotient polynomials for each polynomial 𝑓ᵢ(𝑥) , resulting in a total of 𝟐﹡𝑚 KZG commitments. The verifier sends all these commitments as proof for verification.

However, as mentioned earlier, this approach requires generating multiple proofs, and the verifier also needs to perform multiple verification computations. We need to find a way to compress multiple commitment proofs.

Merging the Proofs

The prover sends the proof [ 𝑞( 𝑠 )]₁ to the verifier for verification.

The evidence produced by this scheme consists of one commitment, two proofs, and one value, with constant data size. Eventually, after the proof merging optimization in the Verkle tree, the verifiable data object sent to the verifier includes the following:

1. Constant size evidence
2. The data of the leaves to be proven (key-value pairs)
3. The commitment values of all nodes on the path from the leaf to the root (assuming a tree width of 256 with 2³² nodes, then the average depth is 4, requiring only 3 commitment values)

Note that 𝑥ᵢ and 𝑦ᵢ do not need to be explicitly provided; they can all be computed.

5.3.3. performance

Regarding the proof merging scheme for Verkle trees, the specific size of the generated proof is as follows（The unit of the row is billion.）:

The above data assumes the usage of a tree of width 256, employing the KZG commitment scheme (with a commitment size of 48 bytes), and maximizes the utilization of the tree. In practice, for completely random distributions of information, the tree depth would increase by about 60%, and the size of each element would increase by 30 bytes. If the bulletproof scheme is used, then the commitment size would be 32 bytes.

5.4. Prover and verifier computation load

1. Proof Generation: The cost of generating proofs by the prover is related to the tree’s width, but each atomic operation requires a relatively low computational cost, so Verkle trees with widths between 256 and 1024 perform well in terms of algorithms.
2. Proof Verification: Vitalik has indicated that the verification algorithm is very fast and can typically be completed within 100ms, even when there are several thousand values to verify.
3. When Updating Verkle Trees: Updating the tree requires recalculating all the intermediate commitment values along the path due to changes in values or structure. However, Vitalik mentioned that, thanks to some properties of the polynomial commitment algorithm, it is possible to design a method that precomputes alternative commitment values and stores them, thereby reducing the computational time cost during updates, which essentially trades space for time.

6. Conclusions

The following is the original words of vitalik blog, we added a paragraph at the end as a supplement。

Verkle trees are a powerful upgrade to Merkle proofs that allow for much smaller proof sizes. Instead of needing to provide all “sister nodes” at each level, the prover need only provide a single proof that proves all parent-child relationships between all commitments along the paths from each leaf node to the root. This allows proof sizes to decrease by a factor of ~6–8 compared to ideal Merkle trees, and by a factor of over 20–30 compared to the hexary Patricia trees that Ethereum uses today (!!).

They do require more complex cryptography to implement, but they present the opportunity for large gains to scalability. In the medium term, SNARKs can improve things further: we can either SNARK the already-efficient Verkle proof verifier to reduce witness size to near-zero, or switch back to SNARKed Merkle proofs if/when SNARKs get much better (eg. through GKR, or very-SNARK-friendly hash functions, or ASICs). Further down the line, the rise of quantum computing will force a change to STARKed Merkle proofs with hashes as it makes the linear homomorphisms that Verkle trees depend on insecure. But for now, they give us the same scaling gains that we would get with such more advanced technologies, and we already have all the tools that we need to implement them efficiently.

At present, many Ethereum clients have provided the implementation of the Verkle tree and related test networks. The community is still discussing the time when the Verkle Trees will be launched on the main network. It is likely to be implemented in a hard fork upgrade in 2024 or 2025. For detailed information about Verkle trees on Ethereum, see https://verkle.info/ .

7. Reference

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Minimum disclosure proofs of knowledge[J]. Journal of computer and system sciences, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Vector commitments and their applications[C]//Public-KeyCryptography–PKC 2013: 16th International Conference on Practice and Theory in Public- Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16. Springer, 2013: 55–72.

Disclaimer：

1. This article is reprinted from [ZAN], All copyrights belong to the original author [AntChain Open Labs and ZAN]. If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.