3

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'
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.