How can I verify my merkle root function is correct?

Question

I've started playing with Bitcoin on a more technical level recently (I'm an experienced software developer but just a user of Bitcoin up until now). I'm trying to implement a function to calculate a merkle root, as described by the protocol documentation here. I think I have implemented a function as described, but I'm not too sure how to go about verifying what I've done. Ideally I'd like to write some unit tests, but I need some input values and an expect output.

Does anyone know where I might find a set of transaction hashes, along with the correct merkle root which should be produced from there? I'm really looking for example inputs & output which I can use to verify the correctness of my function.

I've tried copying & pasting the transaction hashes from Bitcoin block 96001, but the merkle root I'm calculating does not match what is displayed on blockchain.info. The strange thing is, when I feed the same transaction hashes into the merkle root function in BitcoinJS-lib, it produces the same merkle root as my function. Are my function and BitcoinJS-lib both wrong? Is blockchain.info wrong? Or is there something else going on here?

var sha256 = (buffer) => {
  return crypto.createHash('sha256')
    .update(buffer)
    .digest()
}

var doubleSha256 = (buffer) => sha256(sha256(buffer))

var merkleRoot = (hashes) => {
  if (hashes.length == 1)
    return hashes[0]

  return merkleRoot(
    _.chain(hashes)
      .chunk(2)
      .each(tuple => tuple[1] = tuple[1] || tuple[0])
      .map(tuple => Buffer.concat(tuple))
      .map(doubleSha256)
      .value()
  )
}

// Transaction hashes from block 96001:
var tx1 = Buffer.from('dcc95c8740525e27d87333558e5d0a288d0eac9062598c86c77e75dcde7178d2', 'hex')
var tx2 = Buffer.from('043cd1d9166cf16a4cc02d4385667657056cbe23f7058877c7fde09ef7de904a', 'hex')
var tx3 = Buffer.from('88b058d7e3e7b6d174d0f5a76a209a3107de65c01b010cda72ee64b22c980998', 'hex')

console.log(merkleRoot([tx1, tx2, tx3].sort()).toString('hex'));

// expected 'e7ae478c684e965d730e72b9cac644fd1ebeb1517fe69cc458d9d4070b9de8d8'
// output   'b2f52e4efbbab7653489b83d5ad331f1ada1b7e5959ac63b8aa45a786ae90279'

Answer 1

Most likely, you have some endian-ness issues. Remember that the merkle root published is in little-endian and so are the transaction hashes. You'll have to reverse them and then calculate merkle calculations.

You can take a look at the details of a block with the tx hashes here:

https://webbtc.com/block/00000000000000000375c25e5af8f3b2310585ad6a7c264d66398018ce4c6a41.json

There's a very helpful key in that json payload called "mrkl_tree" which tells you all nodes of the merkle tree (so the parent of two adjacent leaf nodes is in that set). It's probably easiest to build tests around that.