Merkle root and tree of Bitcoin – How to build?

Follow and share now!

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:

  1. In cases, you start with just one hash, this one is already the Merkle Root.
  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:

How to build a merkle tree

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.

Faster block header hashing:

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 Deques. 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;
	public byte[] build() {
		// Just one hash? We have the root already =)
		if(elements.size() == 1) {
			// Get the single element
			for(final byte[] once:elements) {
		Deque<byte[]> now = new LinkedList<byte[]>(elements);
		Deque<byte[]> nxt = new LinkedList<byte[]>();
		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);
	 * @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);
public final class DoubleSha256HashFunction implements HashFunction {
	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.update(firstTurn, 0, 32); // 256 Bit = 32 Byte
		} 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:






Example 1:



(Source: Block #1)




Example 2:



(Source: Block #80000)







Example 3:



(Source: Block #99960)






Example 4:



(Source: Block #100000)






Example 5:



(Source: Block #99974)





(Click/Tip to enlarge)

Post Your Comment Here

Your email address will not be published. Required fields are marked *