The Wonder of Merkle Trees

The Wonder of Merkle Trees

I think that every child at school should read the Satoshi Nakamoto paper. In the paper, Satoshi lays out a more trusted world, and at its core is the usage of Merkle Trees. With this we create a tree of hashes and then it this to create a root hash. In blockchain, it is this root hash that we add to our blockchain, in order to create a chaining effect.

So let’s say we have the names of a few countries: ‘France’, ‘Germany’, ‘Denmark’, ‘Sweden’, ‘UK’, ‘Spain’, and ‘Italy’. We can then hash as [here]:

Input:		 [ 'France', 'Germany', 'Denmark', 'Sweden', 'UK', 'Spain', 'Italy' ]
Root hash:	 65C7C87E2731AE97D0BE89EA3299A544FD28DE6A
Tree depth	 3
Tree levels:	 4
Tree nodes:	 7

Level  0
[ '65C7C87E2731AE97D0BE89EA3299A544FD28DE6A' ]

Level  1
[ '8D832398ACABF7B669C023174169C8876F9764DC',
  '2BBB8E1E1D16671B763D0C026C9A2BA43FD73381' ]

Level  2
[ '0F705D70B6CF6FFE1FE570FC24947767438541FA',
  'A5D0D57347C4BE03B6E91E0176D5E53614AA861E',
  'F8A5C1FC111019BDCD2E6F7877299878F9699640',
  'AD79EF0F076D3A686AB9738925F4DD2C7E69D7D1' ]

Level  3
[ 'E3772AC4B4DB87B4A8DBFA59EF43CD1A8AD29515',
  '17D53E0E6A68ACDF80B78D4F9D868C8736DB2CEC',
  '89DA124E04DFE1AD9946CD37D91A119E1D028898',
  '72DDD2B619AF6D6A73FEBF80F7FCAD22495498CD',
  '7770D04C7BFB791E7C95959F12D6797BEE87A8D8',
  '20A8DF9B760336178FCA425339EC1C7E542A2463',
  'AD79EF0F076D3A686AB9738925F4DD2C7E69D7D1' ]

The root of the tree is then 65C7C87E2731…299A544FD28DE6A, and we have seven nodes and four levels. We can now draw the Merkle Tree:

The SHA-1 hash of ‘France’ is E3772AC4B4D…43CD1A8AD29515. Notice that because we have an odd number of nodes, the hash for ‘Italy’ is used for the next level. The following is some sample code for node.js:

var merkle = require('merkle');

const args = process.argv.slice(2);

const str= args[0];

var arr = str.split(',')

console.log("Input:\t\t",arr);

var tree = merkle('sha1').sync(arr);

console.log("Root hash:\t",tree.root());
console.log("Tree depth\t",tree.depth());
console.log("Tree levels:\t",tree.levels());
console.log("Tree nodes:\t",tree.nodes());

var i;
for (i = 0; i < tree.levels(); i++) {
	console.log("\nLevel ",i);
	console.log(tree.level(i));
}

If we create with no hashing method, we can clearly see the structure of the true. In this case we use ‘1’,’2',’3',’4' and ‘5’ for our data [here]:

var merkle = require('merkle');

Input: [ ‘1’, ‘2’, ‘3’, ‘4’, ‘5’ ]
Type: none
Root hash: 12345
Tree depth 3
Tree levels: 4
Tree nodes: 6

Level 0
[ ‘12345’ ]

Level 1
[ ‘1234’, ‘5’ ]

Level 2
[ ‘12’, ‘34’, ‘5’ ]

Level 3
[ ‘1’, ‘2’, ‘3’, ‘4’, ‘5’ ]

The great advantage of using a Merkle Tree is that we can easily check that a value is included in the root hash. In the diagram below, to test that ‘Germany’ (Node 2) is in the tree, we would need only need Node 1, Node 34 and Node 567 in order to generate the root (Node 1234567):

The reason we only need nodes 1, 34 and 567, is that we can regenerate Node 12 and Node 1234 from these values. Bitcoin, for example, uses this method in order to check the validity of a transaction within the block. We can then add our transactions into a Merkle Tree, and produce a root hash. Within the block we can then add the root hash of the previous block and the root hash of the next block, and thus interlock the blocks into a chain:

Conclusions

We live in an almost completely untrusted digital world. With Merkle Trees we can add strong levels of trust, and easily compute the validity of transactions. If you are interested, here is an outline of the greatness of Ralph Merkle: