Bitcoin Forum
April 29, 2017, 04:00:12 AM *
News: If the forum does not load normally for you, please send me a traceroute.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: merkel root  (Read 1837 times)
Geir
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 10, 2012, 12:35:44 PM
 #1

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.
1493438412
Hero Member
*
Offline Offline

Posts: 1493438412

View Profile Personal Message (Offline)

Ignore
1493438412
Reply with quote  #2

1493438412
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
March 10, 2012, 01:08:23 PM
 #2

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
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 10, 2012, 01:30:20 PM
 #3

Perfect answer, thanks Smiley
Geir
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 10, 2012, 04:27:15 PM
 #4

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
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
March 10, 2012, 04:41:50 PM
 #5

That's right. Be careful of endianness.
Geir
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 10, 2012, 04:51:51 PM
 #6

 Grin
Geir
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 10, 2012, 07:08:16 PM
 #7

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

Activity: 1428


Core Armory Developer


View Profile WWW
March 11, 2012, 04:48:08 PM
 #8

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.





Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
Geir
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 11, 2012, 08:21:46 PM
 #9

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

Activity: 1428


Core Armory Developer


View Profile WWW
March 11, 2012, 08:28:42 PM
 #10

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.   

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
Geir
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 12, 2012, 09:13:02 PM
 #11

Ok I'm still working on this, even after all your help Sad 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
Jr. Member
*
Offline Offline

Activity: 43


View Profile
March 13, 2012, 08:48:55 PM
 #12

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

Not meant to be easy this hehe Smiley
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!