merkel root

[Geir]

Hi

I've been trying to understand more about how bitcoin works. But I can't find much information on how the merkel root is calculated. I understand it's a coinbase script and the transactions from this block, but not much more. Any one know of some place I can read up on this.

[1714871845]

1714871845

[Mike Hearn]

See here:

  http://en.wikipedia.org/wiki/Hash_tree

The leaves of the tree are transaction hashes. See also the buildMerkleTree function in BitCoinJ:

http://code.google.com/p/bitcoinj/source/browse/src/com/google/bitcoin/core/Block.java#582

[Geir]

Perfect answer, thanks

[Geir]

Is this really as simple as:
* Get transactions with getmemorypool, gives:
   "blabla" = tx1
   "blabla" = tx2
   "blabla" = tx3
   "blabla" = tx4
   and so on

* Do A = sha256(tx1 | tx2), B = sha256(tx3 | tx4)
* do sha256(A | B) = merkel root

Am I on to something???

[Mike Hearn]

That's right. Be careful of endianness.

[Geir]

 

[Geir]

Should i be able to make the merkel root I'm making now match the one i get from "getwork"??

[etotheipi]

Here's a diagram I created a long time ago when I was starting to illustrate BTC concepts for a presentation that I ended up not giving.

The parent of two nodes (in the diagram) is created by concatenating the two child nodes (such as "0f3e32d0af34332d") and then hashing that.

If a level has an odd number of nodes, you copy the last node. to make it even:  i.e. if a level has 3 nodes:  A, B, C, you just make it A,B,C,C and then carry on.

[Geir]

Thanks, nice illustration. I think I've got it more or less working. Only struggling with the endians.

[etotheipi]

Thanks, nice illustration. I think I've got it more or less working. Only struggling with the endians.

Endianness is a royal PITA in Bitcoin.  I don't know if it helps at all, but I have a working implementation of merkle-root calculation here in C++ and here in Python.   There doesn't appear to be any endianness switching in the calculations, so you just need to make sure the endianness is correct on the input and everything else show work out.   

[Geir]

Ok I'm still working on this, even after all your help I've figured out that to hash the transaction you actually do a sha256(sha256(tx)), the was my first problem.
Now the problem is:

I'm looking at the merkle root in http://blockexplorer.com/rawblock/000000000000030de89e7729d5785c4730839b6e16ea9fb686a54818d3860a8d

Taking the last three hashes you should think that:
sha256(e2d23adf5c86b1266a6abb9a471eaa05bf233dc66245e36a82bb14392fb36c4713f0f97659ccb96 f0f6abd4cda25894463dec0cf3deb626acfc60d506bfd3650) = acb5aeb11e2a607e610b90f2722cf68aec719af2a2fd6a6af179764e90169af4

But no, I cant get this to work. Am i missing something again??

PS I am converting from hex to byte[]

[Geir]

After some brute force reverse engineering I figured it out First off its sha256(sha256 and then the hex string is used in reverse.

Not meant to be easy this hehe