Node.js Merkle Tree[Node.js Home][Home]
The Merkle Tree is a method of producing a master hash from a hash tree. For input strings of 'Apple', 'Orange', 'Lemon', 'Lime', the SHA-1 hashes will be: '476432A3E85A0A ... 89B6820D63', '09FB6AABA7940A7 ... 03C1BAD', '4459B791A680 ... C21EDFCB9C' and '7E845D62D2F ... 03EB78640ABE0'. We will then take the 1st and 2nd hash and produce 33FE7D2212CB74 ... 07E7EB1, and the 3rd and 4th hash to produce A95D2B3B5F61A003 ... 3633FEC71B. We then take these two hashes and then produce a root hash.
|
Theory
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:
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]:
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: