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());
		this.elements.addAll(elements);
		
		// 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);
			}
		}
		
		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) {
				now.addLast(now.getLast());
			}
						
			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);
				nxt.addLast(hash);
			}
			// 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:

Input:


 

Output:

<error>

 

Example 1:

Input:

982051fd1e4ba744bbbe680e1fee14677ba1a3c3540bf7b1cdb606e857233e0e

(Source: Block #1)

Output:

982051fd1e4ba744bbbe680e1fee14677ba1a3c3540bf7b1cdb606e857233e0e

 

Example 2:

Input:

252bf9d75c4f481ebb6278d708257d1f12beb6dd30301d26c623f789b2ba6fc0
e2d32adb5f8ca820731dff234a84e78ec30bce4ec69dbd562d0b2b8266bf4e5a

(Source: Block #80000)

Output:

190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f

 

Tree:

 

 

Example 3:

Input:

c6f2ba9c82a506b634cea1047e0993c0d7205f08561262cc4a5e69cdbd659cf8
4f21bb697bf3d5293fc6e137440855358b86f2b599d90ede09edaec6f9be1818
0d02210b9177cfc8193b95254473ff7bd986ed1179c276d12bad5bdba2403ad4

(Source: Block #99960)

Output:

f94b61259c7e9af3455b277275800d0d6a58b929eedf9e0153a6ef2278a5d534

 

Tree:

 

Example 4:

Input:

876dd0a3ef4a2816ffd1c12ab649825a958b0ff3bb3d6f3e1250f13ddbf0148c
c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff
c46e239ab7d28e2c019b6d66ad8fae98a56ef1f21aeecb94d1b1718186f05963
1d0cb83721529a062d9675b98d6e5c587e4a770fc84ed00abc5a5de04568a6e9

(Source: Block #100000)

Output:

6657a9252aacd5c0b2940996ecff952228c3067cc38d4885efb5a4ac4247e9f3

 

Tree:

 

Example 5:

Input:

3658837f39d3c6e170726ebccde47edaf5340ac830991ea7b3aaffee453f5ddc
48cc12597887c93dc161f82d8b0adf4166cc169c7be8b1cf78bfbf29448bd90e
eaaee2b601061be3fd3a547c8bbdab5658fdcd0fb633de09b06059be17da0881
d968b21afa85d6fab016c39176604fed99487f98975dc295b2139bf28fa4ffec
e7f42d1556feef839d84257262435be1417baa4048a39594990e1dedef797fb5
66d7577163c932b4f9690ca6a80b6e4eb001f0a2fa9023df5595602aae96ed8d

(Source: Block #99974)

Output:

cce3697d67c0fe334b1c0040be1368c5ffb2c563f2486fbbe28ecf0c47662027

 

Tree:

(Click/Tip to enlarge)

Post Your Comment Here

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

Free Demo!

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

Join the Calloway Crypto Soft now!

Read now the whole review!

If you have additional questions or stumble, please email immediate to earnmoneytodayblog@gmail.com or use the simple contact form.

 

earn-money.today successful challenge: 1041/2000 successful trader. Test now Calloway Crypto System or other verified trading systems for free and send us how successful you are and how much profit you made, and may what we can do for you.

52%

Last successful trader:
Antje B.
Be the next!