# Merkle root and tree of Bitcoin – How to build?

When you learn about encrypted currencies you will find the term Merkle Root or Merkle Tree, respectively. It is in Bitcoin used as elementary function to build Blocks. Knowing how to build the Merkle Tree is essential to develop software that need to build blocks, like a pool- or mining software.

## Fingerprints – secure data integrity:

A fingerprint or in this context rather hash is the result of a function and a sequence of bytes. The result of the same function and an equal sequence of bytes in the same order will always be the same, just the smallest change returns with very big properly a complete other hash.

### Usage of hashes:

There are three big usages of hashes:

• Since it is not possible to calculate such a hash back to the input byte sequence, systems with user authentication stores usual just the hash instead of a plain password for more security. The system compare on authentication just the stored hash with the hash of the password input.
• Hashes are used for very easy data comparative. Many Websites show a file hash on download pages. You just need to calculate the hash of your downloaded file and compare them with the hash on the website to be nearly absolutely sure, you have downloaded the right file, since just one bit change would likely produce any other hash.
• The hash of a sequence of bytes is except of calculating them not predictable, encrypted currencies use hashes as challenge for regulation.

## What is a Merkle Root?

A Merkle Root, named about Ralph Merkle who patented them, is a hash, calculated from a ordered sequence of hashes. Bitcoin stores a Merkle Root in the byte sequences called Block, this field is called Merkle Root too. They become calculated by a virtual construct, called Merkle Tree.

## What is a Merkle Tree?

The name Merkle Tree comes from binary trees as directed graphs, where each element except the most top has one pretender and at most two successors. The top element is called the root node, so the Merkle Root is just the root node of a Merkle Tree. The Tree is only build to get the root node and become thrown away afterward.

## How to build a Merkle Tree? – Step by step:

Just follow these simple steps to calculate a Merkle Tree from a sequence of hash:

2. Take the hashes ordered in groups of two. If you have an odd hashes count, the last group contains the last element two times.
3. Concatenate the hashes in little endian byte order, hence the least significant bit of the first hash is the least significant bit of the concatenation.
4. Hash the concatenation and store the result in last-in-last-out order, the result of the first two hashes is the first element of the next row.
5. Continue the previous three steps, until you have the single top root node.

This image describes the virtual Merkle Tree of the three hashes A, B and C in Bitcoin using the algorithm SHA-256 twice:

## Purpose of the Merkle Root in Bitcoin:

The Merkle Root in the Bitcoin block header field with the same name is calculated from the hashes of the transactions of this block.

### Ensuring data integrity:

The only connection between a Block header and the transactions is the stored Merkle Root. Nevertheless, the data integrity is ensured, a change of a transaction would change the transaction hash, this would change the Merkle Tree and this the hash of the block header.

The hashing time of a block header doesn’t depend on the transaction count stored in this block. That is for fair mining very important. The Merkle Tree needs just to get recalculated, each time the transactions change, but this is very fast, even compared with finding a block with the lowest possible difficulty. It would be otherwise a competition between the speed of generating and testing block headers and transaction count.

### Less internet traffic for miner and pools:

Big pools needs a very strong internet connection. Since miners need to build steadily block headers, a miner needs to know the Merkle Root. The pool transfers only with the method mining.notify the hashes of the transactions to build the tree local, a transfer of all transactions would cost a lot more traffic, most transactions are bigger than the block header.

### Less storage space needed:

It is possible to test a block for containing a transaction just by knowing the hashes. Lightweight Bitcoin clients use this fact to store just hashes instead of the full transactions to reduce the storage space of the global blockchain database.

## Java build Merkle Root example code:

The Java class MerkleRootBuilder below implements the calculation of a Merkle Root. It expects as constructor arguments an instance of a sorted `java.util.Collection` (for example `java.util.ArrayList`), containing the hashes as little endian byte arrays and an implement of the Interface `HashFunction`, properly an instance of the class `DoubleSha256HashFunction`. The first element of the byte arrays has to be the least significant byte of the hashes, the first element of the collection (element 0 on indexed collections) should be the coinbase transaction, element 1 the second transaction of the block and so on.

The method `build` starts at the bottom of the tree with two `Deque`s. One contains the hashes of the current row, the other one is the target of the results. If the source deque contain an odd count of elements, the last element is at the start of the next row uncopied added a second time. In a perfect binary tree grows the row element count exponential to the linear growing of rows, so adding the element a second times become on big element count faster than testing each element for being the last one. The arrays become never changed nor sent to outside the own class instances, so we doesn’t need to copy them. The inner loop gets the elements in pairs of two, concats them, hash them (for abstraction in two steps, it could be one step for more performance) and adds the result to the other deque. After the last two elements became handled, the source and target deques become swapped and the game start from scratch, along there is more than one hash left.

```public final class MerkleRootBuilder implements Factory<byte[]> {
private final Collection<byte[]> elements;
private final HashFunction hashFunc;

/**
*
* @param elements A sorted collection of hashes, each in little endian order. (elements.get(x)[0] = the least significant byte)
* @param hashFunc
*/
public MerkleRootBuilder(final Collection<byte[]> elements,
final HashFunction hashFunc) {
if(elements == null) {
throw new IllegalArgumentException("elements == null");
} else if(elements.size() == 0) {
throw new IllegalArgumentException("elements.size() == 0");
} else if(hashFunc == null) {
throw new IllegalArgumentException("hashFunc == null");
}

this.elements = new ArrayList<byte[]>(elements.size());

// Check from field to avoid race manipulation
for(final byte[] bs:this.elements) {
if(bs == null) {
throw new IllegalArgumentException("elements contains null");
}
}
this.hashFunc = hashFunc;
}
@Override
public byte[] build() {
// Just one hash? We have the root already =)
if(elements.size() == 1) {
// Get the single element
for(final byte[] once:elements) {
return(once);
}
}

do {
// If the current row of the Merkle Tree contains
// an even element count, the last hash become
// concatted by itself.
// Doesn't copy it, we won't change it!
if((now.size() & 1) != 0) {
}

while(now.size() > 0) {
final byte[] h0 = now.removeFirst();
final byte[] h1 = now.removeFirst();
final byte[] cat = concatBytes(h0, h1);
final byte[] hash = hashFunc.hash(cat);
}
// Triangle swap of source and destination for the next
// level.
final Deque<byte[]> tri = now;
now = nxt;
nxt = tri;
} while(now.size() > 1);
return(now.getFirst());
}
/**
*
* @param a
* @param b
* @return (a[0],a[1],a[2]...a[n-1],b[0],b[1],b[2]...)
*/
private byte[] concatBytes(final byte[] a, final byte[] b) {
final int aLen = a.length;
final int bLen = b.length;

final byte[] c = Arrays.copyOf(a, aLen + bLen);
System.arraycopy(b, 0, c, aLen, bLen);
return(c);
}
}```
```public final class DoubleSha256HashFunction implements HashFunction {
@Override
public byte[] hash(final byte[] in) {
try {
final MessageDigest d = MessageDigest.getInstance("SHA-256");
d.update(in, 0, in.length);
final byte[] firstTurn = d.digest();
d.reset();
d.update(firstTurn, 0, 32); // 256 Bit = 32 Byte
return(d.digest());
} catch (final NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
}
}```
```public interface HashFunction {
public byte[] hash(byte[] in);
}```
```public interface Factory<T> {
T build();
}```

## Merkle Root examples:

Here are some examples to test your software and play with. The hex strings are little endian, but convert it back to real bytes before hashing.

### Example 0:

#### Output:

`<error>`

### Example 1:

#### Input:

`982051fd1e4ba744bbbe680e1fee14677ba1a3c3540bf7b1cdb606e857233e0e`

(Source: Block #1)

#### Output:

`982051fd1e4ba744bbbe680e1fee14677ba1a3c3540bf7b1cdb606e857233e0e`

### Example 2:

#### Input:

```252bf9d75c4f481ebb6278d708257d1f12beb6dd30301d26c623f789b2ba6fc0

(Source: Block #80000)

#### Output:

`190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f`

### Example 3:

#### Input:

```c6f2ba9c82a506b634cea1047e0993c0d7205f08561262cc4a5e69cdbd659cf8
4f21bb697bf3d5293fc6e137440855358b86f2b599d90ede09edaec6f9be1818

(Source: Block #99960)

#### Output:

`f94b61259c7e9af3455b277275800d0d6a58b929eedf9e0153a6ef2278a5d534`

### Example 4:

#### Input:

```876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148c
c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff
1d0cb83721529a062d9675b98d6e5c587e4a770fc84ed00abc5a5de04568a6e9```

(Source: Block #100000)

#### Output:

`6657a9252aacd5c0b2940996ecff952228c3067cc38d4885efb5a4ac4247e9f3`

### Example 5:

#### Input:

```3658837f39d3c6e170726ebccde47edaf5340ac830991ea7b3aaffee453f5ddc
eaaee2b601061be3fd3a547c8bbdab5658fdcd0fb633de09b06059be17da0881
d968b21afa85d6fab016c39176604fed99487f98975dc295b2139bf28fa4ffec
e7f42d1556feef839d84257262435be1417baa4048a39594990e1dedef797fb5
66d7577163c932b4f9690ca6a80b6e4eb001f0a2fa9023df5595602aae96ed8d```

(Source: Block #99974)

#### Output:

`cce3697d67c0fe334b1c0040be1368c5ffb2c563f2486fbbe28ecf0c47662027`

#### Tree:

(Click/Tip to enlarge)

# Free Demo!

Join the Calloway Crypto System now,
to get a free demo account: