📘Understanding Merkle Trees

Book an audit with Zokyo

Understanding Merkle Trees: The foundation of blockchain security relies heavily on a peculiar data structure known as a Merkle Tree. Named after its inventor, Ralph Merkle, it is a binary tree comprised of a set of nodes, where each node represents a certain amount of data. But what makes it so crucial in the context of blockchain and smart contract security? Let's unravel this concept piece by piece.

What is a Data Structure: A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. Common types of data structures include arrays, linked lists, stacks, queues, hash tables, trees, and graphs. The choice of data structure often depends on the specific requirements of the task at hand, such as the need for fast access, large storage capacity, or maintaining relationships between data elements.

What is a Binary Tree: A binary tree is a type of tree data structure in which each node has at most two children, referred to as the left child and the right child. This characteristic makes it easier to search for data, insert new data, and delete data, as you only need to compare and potentially modify two child nodes at each step.

What is a Node: A node is each circle you see in the image above. In the context of data structures, a node is a basic unit of information. It can contain various data types, such as a number, a string, or a reference or pointer to another node. In more complex data structures like trees and graphs, a node often contains additional information to describe its relationship to other nodes, such as links to its child nodes and/or its parent node.

What is a Hash Function: A hash function is a function that takes an input (or 'message') and returns a fixed-size string of bytes. The output, often a 'digest', is unique to each unique input: a small change to the input will produce such a drastic change in output that the new hash value appears uncorrelated with the old hash value. In the context of blockchain and cryptography, hash functions are used to maintain data integrity and security. For Ethereum and its Merkle trees, the Keccak-256 hash function (a variant of SHA-3) is commonly used.

Merkle Tree

A Merkle Tree is a kind of data structure used in computing. A data structure is simply a way of organizing and storing data so it can be used efficiently.

Let's break down the definition of Merkle Tree into simpler parts:

1. What is a tree in computing? Imagine a family tree, with the "ancestors" at the top and "descendants" below. A tree in computing is similar. It starts with a single "root" node at the top, which branches out to "child" nodes, and each of those can have their own "child" nodes, and so on. The nodes at the very bottom that have no children are called "leaves".

2. What is a cryptographic hash? A hash is a way of taking any amount of input data (like a sentence, a document, or a whole book), and creating a fixed-size string of characters from it, which looks random. What's special about it is that any small change to the input will completely change the hash, and you can't go backwards from the hash to the original data. Cryptographic hash functions are special types of hash functions that are particularly secure, meaning they're very hard to reverse or find collisions (two different inputs producing the same hash).

3. How is a Merkle Tree built? You start with your data blocks at the bottom as the "leaves" of the tree. Each of these data blocks is turned into a hash. Then, each pair of these hashes is combined and hashed again to get the hash for the node above them. This process continues up the tree, until you get a single hash at the top, which is the "root" of the tree.

4. What is a Merkle Tree used for? Merkle Trees are used in places where you need to verify data quickly and securely. For example, they are used in blockchain technology (which underlies cryptocurrencies like Bitcoin) to ensure all transactions are valid without having to check every single one.

In essence, Merkle Trees allow you to check if a small piece of data is part of a large dataset very quickly and with a high degree of certainty. If you have the top hash and a way to move down the tree, you can check if a piece of data is included in the original dataset without needing to have the entire dataset.

1. Basic Terminology: In a Merkle tree:

• Leaf nodes are the lowest nodes in the tree (they have no children) and represent the data blocks.

• Parent nodes are labeled with a cryptographic hash of their child nodes.

• The root node (the top node of the tree) is known as the Merkle root.

2. Construction of a Merkle Tree:

Let's consider we have 4 data blocks - L1, L2, L3, and L4.

Step 1: We start by taking the cryptographic hashes of the data blocks.

• HL1 = Hash(L1)

• HL2 = Hash(L2)

• HL3 = Hash(L3)

• HL4 = Hash(L4)

Here, 'Hash' can be any cryptographic hash function like SHA256.

Step 2: The hashes are paired and concatenated, and the hash of the resulting strings are calculated.

• HL12 = Hash(HL1 + HL2)

• HL34 = Hash(HL3 + HL4)

Here, '+' represents concatenation.

Step 3: These hashes are again concatenated and hashed to form the root.

• ROOT = Hash(HL12 + HL34)

This ROOT is the Merkle Root of our Merkle Tree.

Just like before, you can use this tree for efficient and secure verification of the contents of these data blocks. The process is exactly the same, but with the updated block names.

Real use case

let's delve into a practical example of how Merkle Trees are utilized in blockchain technology for handling transactions.

Let's say we have a set of Bitcoin transactions:

• Transaction 1 (T1): Alice sends 1 BTC to Bob

• Transaction 2 (T2): Bob sends 0.5 BTC to Charlie

• Transaction 3 (T3): Charlie sends 0.2 BTC to Dave

• Transaction 4 (T4): Dave sends 0.1 BTC to Alice

These four transactions form our "data blocks". Now we will form a Merkle Tree from these transactions just like we did before.

Step 1: We hash each transaction (this is equivalent to HL1 = Hash(L1) and so on):

• HT1 = Hash(T1)

• HT2 = Hash(T2)

• HT3 = Hash(T3)

• HT4 = Hash(T4)

Step 2: Pair and concatenate the hashes, then hash the resulting strings (equivalent to HL12 = Hash(HL1 + HL2) and so on):

• HT12 = Hash(HT1 + HT2)

• HT34 = Hash(HT3 + HT4)

Step 3: Concatenate and hash the pair hashes to form the root:

• ROOT = Hash(HT12 + HT34)

The resulting ROOT is our Merkle Root, which provides a "fingerprint" or summary of all the transactions.

Now let's say a new participant, Eve, joins the Bitcoin network and wants to verify Transaction 3 (T3). Instead of downloading the whole blockchain, she can download just the Merkle Path, or the shortest path to T3, which includes HT4 (T3's pair) and HT12 (the sibling of T3's parent). Eve can now compute:

• HT34 = Hash(HT3 + HT4)

• ROOT = Hash(HT12 + HT34)

If this computed ROOT matches the actual Merkle Root of the blockchain, Eve can be sure that T3 is indeed part of the block. This is how the use of Merkle Trees makes verification of transactions efficient and secure in the blockchain.

Properties and Advantages of Merkle Trees:

1. Efficiency: In a Merkle Tree, each leaf node represents a block of data, and each non-leaf node is a hash of its child nodes. The most important aspect of this structure is the Merkle root, a single hash at the top of the tree that represents all the data underneath it. To verify whether a specific block of data is part of the dataset, you don't need to look at every piece of data. You only need to look at a specific path from the root to the leaf node representing that data, along with some additional nodes (known as siblings) along the way. This path, known as a Merkle proof, is significantly smaller than the entire dataset, which makes the verification process very efficient, even for large datasets.

2. Security: The Merkle root changes if any part of the data it represents changes. That's because a small change in any block of data will change its hash, which will change the hashes of nodes above it in the tree, all the way up to the root. This means that it's practically impossible to change the data without also changing the Merkle root. This feature makes Merkle Trees very secure - any tampering with the data would be immediately noticeable when comparing the Merkle root.

3. Proof of Integrity: If two parties have the same Merkle root, they know they have the exact same version of the data. That's because it's practically impossible to have two different datasets produce the same Merkle root, due to the properties of cryptographic hash functions. This means that Merkle Trees provide a very strong assurance of data integrity. If the Merkle roots match, the datasets match.

Understanding these properties is crucial for understanding systems that use Merkle Trees. These include blockchain systems, where Merkle Trees are used to efficiently verify transactions; torrent systems, where they're used to ensure file integrity; and other distributed systems, where they're used to synchronize data across multiple nodes. The security and efficiency provided by Merkle Trees are essential to the functioning of these systems.