Verkle Trees
What Are Verkle Trees?
Verkle trees are an advanced cryptographic data structure that uses vector commitments and Merkle Trees to create more efficient blockchain verification systems (hence the portmanteau, “Verkle”).
These structures enable blockchain nodes to verify network states without having to download or store complete blockchain data. Instead, they use compact cryptographic “witnesses” or proofs that allow nodes to verify specific data points without compromising security.
Computer scientist John Kuszmaul introduced the Verkle tree concept in 2018 as a solution to bandwidth and storage limitations in blockchain networks.
Merkle Trees vs Verkle Trees
Both of these structures serve similar purposes, but they use different methods:
Merkle Trees work like a family tree where each “parent” contains a mathematical fingerprint (hash) of all its “children.” To prove a piece of data is authentic, you need to show the entire chain of fingerprints from a data point, all the way up to the top of the tree.
Verkle Trees use a more advanced mathematical technique called vector commitments. Think of it like creating a single, compact receipt that can prove multiple pieces of information at once, rather than needing separate receipts for each item. This allows Verkle trees to verify the same information with much smaller proofs.
The key difference: Merkle trees require you to show every step of the verification path, while Verkle trees can prove authenticity with a much shorter, more efficient proof.
While Merkle tree proofs require approximately 1 kilobyte to verify data in a tree containing a billion storage points, Verkle tree proofs accomplish the same verification with less than 150 bytes, even for much larger datasets. Additionally, Verkle trees offer significantly faster proof generation and verification times.
How Do They Work?
Each node in a Verkle Tree structure exhibits one of three key characteristics:
- It is empty
- It is an intermediate node representing multiple child nodes.
- It is a leaf node with actual key-value data pairs
The Verkle Tree architecture consists of two primary node types:
Extension nodes efficiently represent sequences of nodes with single children, compressing long chains of intermediate nodes into compact representations.
Inner nodes store vector commitments representing multiple child nodes, which can include other extension nodes, inner nodes, or leaf nodes.
The construction process involves a tradeoff: creating proofs for trees with larger widths (more children per node) requires more computational time initially, but results in dramatically shorter proof sizes. As the tree width increases, the proof lengths decrease substantially, making verification more efficient over time.
To summarize, Verkle proofs can significantly improve blockchain scalability by decreasing the bandwidth and storage needs for full nodes, resulting in faster transaction processing. This is achieved by reducing the size of the data that nodes need to process for each block, allowing for verification using what’s contained within that particular block.
