Merkle trees vs. Verkle trees, Explained

Merkle trees are employed in Bitcoin (BTC) and other cryptocurrencies to more effectively and securely encrypt blockchain data. Verkle trees allow for smaller proof sizes, particularly important for Ethereum’s upcoming scaling upgrades.

But, how do you identify a Merkle tree? Leaf nodes, non-leaf nodes and the Merkle root are the three essential parts of a Merkle tree in the context of blockchains. Transaction hashes or transaction IDs (TXIDs) reside in leaf nodes, which can be viewed on a block explorer. Then, above the leaf nodes, a layer of non-leaf nodes is hashed together in pairs. Non-leaf nodes keep the hash of the two leaf nodes they represent below them. 

Related: What is blockchain technology? How does it work?

As the tree narrows as it ascends, half as many nodes per layer are formed when non-leaf node levels continue to be hashed together in pairs. Two nodes will be present in the final non-leaf node layer, which establishes the Merkle root (used to verify the leaf nodes) and is the location of the last hashing in a Merkle tree.

The Merkle root stored in the data portion of a block can be compared to the Merkle root stored in the header, allowing the miner to identify any manipulation quickly. A Merkle proof combines the value being proved and the hashing values needed to recover the Merkle root. In addition, they support simple Payment Verification (SPV), which can be used to authenticate a transaction without downloading a complete block or blockchain. This allows using a crypto wallet or light-client node to send and receive transactions.

Verkle trees enable significantly reduced proof sizes for a large amount of data compared to Merkel trees. The proof length, typically logarithmic in the state size, impacts network communication. But, what is a Verkle proof? A Verkle proof is evidence of a large amount of data stored, which could easily be verified by anyone with the tree’s root.

The prover must offer a single proof demonstrating all parent-child links between all commitments along the paths from each leaf node to the root instead of presenting all “sister nodes” at every level in Verkle trees. Compared to ideal Merkle trees, proof sizes can be reduced by a factor of six–eight and by a factor of more than 20–30 compared to Ethereum’s current hexary Patricia trees.