Repository: bitcoinjs/bitcoinjs-lib
Pull request #580 (2016-05-04 14:44:09)

Block: add checkMerkleRoot/calculateMerkleRoot

fanatid: @dcousens I think this intersects with https://github.com/ethers/bitcoin-proof
maybe we should move `bitcoin-proof` to bitcoinjs org? if @ethers don't mind :)
dcousens: @fanatid perhaps `NULL_HASH` should just be `null`?  It doesn't really make sense as a `Buffer` now that I think about it...
A merkle root of nothing is nothing,  not `0000000000000000000000000000...`


dcousens: @fanatid the implementation in `bitcoin-proof` is very convoluted by comparison,  mixed encodings etc.
It also has completely different data structure expectations.

I don't think it'd be reasonable to use that package without major changes tbh.
fanatid: > @fanatid perhaps `NULL_HASH` should just be `null`?  It doesn't really make sense as a `Buffer` now that I think about it...
A merkle root of nothing is nothing,  not `0000000000000000000000000000...`

Maybe throw error when `transactions.length` equal to zero? It's impossible situation.
fanatid: @dcousens we can change `bitcoin-proof` for one style with `bitcoinjs` :) There isn't much changes should be.
jprichardson: > @dcousens we can change bitcoin-proof for one style with bitcoinjs :) There isn't much changes should be.

If we can avoid NIH, the better IMHO.
dcousens: > Maybe throw error when transactions.length equal to zero? It's impossible situation.

Agreed,  will change.

@jprichardson I don't consider this a NIH issue,  it was simply a matter of concise code.
`bitcoin-proof` also seems quite an odd name for something that should probably just be just a generic merkle tree package.
dcousens: >  If we can avoid NIH, the better IMHO.

I don't think this is a NIH issue tbh,  I'm not against using external/pre-written modules?
I'd just rather not have to 'adapt' to them via unnecessary allocations of objects/data structures. 
fanatid: @dcousens I know yet one module for merkle proof: https://github.com/mappum/bitcoin-merkle-proof (supports proof for bip37)
dcousens: @fanatid but why is it `bitcoin-` at all,  merkle trees are nothing new,  and if we don't use a `bitcoin-` specific package, just one that operates purely on `Buffer`,  we can avoid any hazards in API wrappers/adapters.
ethers: @fanatid @dcousens FWIW If relevant, I do not mind moving bitcoin-proof to here, and whatever style, name, and other changes desired.  (It was named that way to help make it more discoverable.)
dcousens: @ethers nothing against your package mate!  It's great,  I'm just thinking out loud that we should probably generalize the concept and then use that instead.

I'd love to use merkle trees and proofs for other applications too.   Maybe even in `common-blockchain` @jprichardson 
dcousens: ping @fanatid check 007d2a7,  reworked from yours,  thanks for the hint :)
dcousens: @fanatid if you're happy with latest, please merge :)
(making a new issue for extracting this logic)
dcousens: @fanatid will squash if needed
fanatid: LGTM, please squash and I merge

Patch:
diff --git a/src/block.js b/src/block.js
index 75a7980d..9356c898 100644
--- a/src/block.js
+++ b/src/block.js
@@ -1,3 +1,4 @@
+var createHash = require('create-hash')
 var bufferutils = require('./bufferutils')
 var bcrypto = require('./crypto')
 var bufferCompare = require('buffer-compare')
@@ -133,6 +134,35 @@ Block.calculateTarget = function (bits) {
   return target
 }
 
+Block.calculateMerkleRoot = function (transactions) {
+  var length = transactions.length
+  if (length === 0) throw TypeError('Cannot compute merkle root for zero transactions')
+
+  var hashes = transactions.map(function (transaction) { return transaction.getHash() })
+
+  while (length > 1) {
+    var j = 0
+
+    for (var i = 0; i < length; i += 2, ++j) {
+      var hasher = createHash('sha256')
+      hasher.update(hashes[i])
+      hasher.update(i + 1 !== length ? hashes[i + 1] : hashes[i])
+      hashes[j] = bcrypto.sha256(hasher.digest())
+    }
+
+    length = j
+  }
+
+  return hashes[0]
+}
+
+Block.prototype.checkMerkleRoot = function () {
+  if (!this.transactions) return false
+
+  var actualMerkleRoot = Block.calculateMerkleRoot(this.transactions)
+  return bufferCompare(this.merkleRoot, actualMerkleRoot) === 0
+}
+
 Block.prototype.checkProofOfWork = function () {
   var hash = bufferReverse(this.getHash())
   var target = Block.calculateTarget(this.bits)


Test patch:
diff --git a/test/block.js b/test/block.js
index 7dd653fb..97cb7003 100644
--- a/test/block.js
+++ b/test/block.js
@@ -97,6 +97,44 @@ describe('Block', function () {
     })
   })
 
+  describe('calculateMerkleRoot', function () {
+    it('should throw on zero-length transaction array', function () {
+      assert.throws(function () {
+        Block.calculateMerkleRoot([])
+      }, /Cannot compute merkle root for zero transactions/)
+    })
+
+    fixtures.valid.forEach(function (f) {
+      if (f.hex.length === 160) return
+
+      var block
+
+      beforeEach(function () {
+        block = Block.fromHex(f.hex)
+      })
+
+      it('returns ' + f.merkleRoot + ' for ' + f.id, function () {
+        assert.strictEqual(Block.calculateMerkleRoot(block.transactions).toString('hex'), f.merkleRoot)
+      })
+    })
+  })
+
+  describe('checkMerkleRoot', function () {
+    fixtures.valid.forEach(function (f) {
+      if (f.hex.length === 160) return
+
+      var block
+
+      beforeEach(function () {
+        block = Block.fromHex(f.hex)
+      })
+
+      it('returns ' + f.valid + ' for ' + f.id, function () {
+        assert.strictEqual(block.checkMerkleRoot(), true)
+      })
+    })
+  })
+
   describe('checkProofOfWork', function () {
     fixtures.valid.forEach(function (f) {
       var block
diff --git a/test/fixtures/block.json b/test/fixtures/block.json
index a18fca5a..c7aa5f7a 100644
--- a/test/fixtures/block.json
+++ b/test/fixtures/block.json
@@ -101,6 +101,20 @@
       "timestamp": 1439710609,
       "valid": false,
       "version": 3
+    },
+    {
+      "description": "Genesis Block",
+      "bits": 486604799,
+      "hash": "6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000",
+      "height": 0,
+      "hex": "0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a29ab5f49ffff001d1dac2b7c0101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff0100f2052a01000000434104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac00000000",
+      "id": "000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f",
+      "merkleRoot": "3ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a",
+      "nonce": 2083236893,
+      "prevHash": "0000000000000000000000000000000000000000000000000000000000000000",
+      "timestamp": 1231006505,
+      "valid": true,
+      "version": 1
     }
   ],
   "invalid": [