# What is a Merkle Tree?

A **Merkle Tree** is a special **data structure** that uses **hash functions** to efficiently verify whether a single piece of data is part of a larger dataset.

Think of it like a digital “family tree” of data, where every branch depends on the ones below it. Each leaf (the lowest layer) represents a **hashed version** of an original data item (TX 1 - 8) — such as a file, message, or transaction.

<figure><img src="/files/FCZnKhlriZZMgFGjgf0A" alt=""><figcaption></figcaption></figure>

#### **Hash Functions: The Foundation of Merkle Trees**

To understand Merkle Trees, it helps to first recall how **hash functions** work. A hash function converts any input—text, image, or file—into a **fixed-length digital fingerprint**.

Modern cryptographic hash functions (like **SHA-256**) have three key properties:

1. **Pre-image resistance (One-way):** It’s practically impossible to determine the original input from the hash.
2. **Second pre-image resistance (Deterministic):** The same input always produces the same output.
3. **Collision resistance:** It’s extremely unlikely for two different inputs to create the same hash.
   * For SHA-256, the chance of a collision is around **4.3 × 10⁻⁶⁰** — effectively zero.

&#x20;

<figure><img src="/files/1XWrsJLxsId5B0PYzWcS" alt=""><figcaption></figcaption></figure>

#### **Building a Merkle Tree**

A Merkle Tree begins with multiple **data elements** (labeled A through H).

1. Each element is passed through a **hash function** to produce **leaf nodes** (AB–GH).
2. Pairs of these hashes are then **concatenated** (joined together) and **hashed again** to form the next layer up.
3. This process repeats layer by layer until a **single hash value**—the **Merkle Root**—is produced at the top.

<figure><img src="/files/0vCCDRF6XbPIsxGAlokk" alt=""><figcaption></figcaption></figure>

Each leaf node corresponds to one piece of data. So, if you have *n* data entries, you’ll have *n* leaf nodes. The **bottom layer** is called **Layer 0**, and each subsequent layer above it is numbered until the top root is reached.

***

#### **Handling Odd Numbers of Nodes**

Merkle Trees work best with pairs. But what happens if there’s an **odd number of nodes** in a layer?

If a layer has an **unpaired (widow) node**, that last hash is **duplicated** and **hashed with itself** to make a complete pair.

For example:

* A 16-leaf tree produces 8 nodes on the next layer.
* A 17-leaf tree produces 9 nodes, where the ninth is created by hashing the final leaf twice (HQQ).

In general, if *n/2* isn’t an integer, the number of nodes in the next layer will be **rounded up** to the next whole number.

***

#### **Layer Growth and Tree Depth**

Every time the number of data entries **doubles**, a new layer is added to the Merkle Tree:

* 4 entries → 3 layers
* 8 entries → 4 layers
* 16 entries → 5 layers\
  …and so on.

This structure allows Bitcoin and other systems to verify data efficiently, even when dealing with **massive datasets**.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hub.bsvblockchain.org/higher-learning/bsv-academy/bitcoin-primitives-merkle-trees/the-merkle-tree/what-is-a-merkle-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.