Bitcoin Forum
December 04, 2016, 08:17:11 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: merkle tree order of hashes  (Read 702 times)
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
June 24, 2011, 02:55:41 PM
 #1

According to the paper, if you have 4 transactions, then the procedure is

12 = Hash(1,2)
34 = Hash(3,4)
root = hash(12,34)

However, it doesn't say how to handle non-power of 2 trees.

For 5 transactions, it could be something like:

Pass 1:

12 = Hash(1,2)
34 = Hash(3,4)
5_ = 5

Pass 2:

1234 = Hash(12,34)
5___ = 5_

Pass 3

root = Hash(1234, 5___)

However, that gives an unbalanced tree. 

Another option would be

1,2,3,4,5

becomes

5,12,34

and then

512,34

and then

51234

Is there some flexibility?  I couldn't see how the tree was defined in block explorer.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
1480839431
Hero Member
*
Offline Offline

Posts: 1480839431

View Profile Personal Message (Offline)

Ignore
1480839431
Reply with quote  #2

1480839431
Report to moderator
1480839431
Hero Member
*
Offline Offline

Posts: 1480839431

View Profile Personal Message (Offline)

Ignore
1480839431
Reply with quote  #2

1480839431
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480839431
Hero Member
*
Offline Offline

Posts: 1480839431

View Profile Personal Message (Offline)

Ignore
1480839431
Reply with quote  #2

1480839431
Report to moderator
1480839431
Hero Member
*
Offline Offline

Posts: 1480839431

View Profile Personal Message (Offline)

Ignore
1480839431
Reply with quote  #2

1480839431
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
June 24, 2011, 03:13:24 PM
 #2

According to the paper, if you have 4 transactions, then the procedure is

12 = Hash(1,2)
34 = Hash(3,4)
root = hash(12,34)

However, it doesn't say how to handle non-power of 2 trees.

For 5 transactions, it could be something like:

Pass 1:

12 = Hash(1,2)
34 = Hash(3,4)
5_ = 5

Pass 2:

1234 = Hash(12,34)
5___ = 5_

Pass 3

root = Hash(1234, 5___)

However, that gives an unbalanced tree. 

Another option would be

1,2,3,4,5

becomes

5,12,34

and then

512,34

and then

51234

Is there some flexibility?  I couldn't see how the tree was defined in block explorer.

Double the unpaired one.  https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
TierNolan
Legendary
*
Offline Offline

Activity: 1036


View Profile
June 24, 2011, 03:17:18 PM
 #3


Ahh right.  I read that to mean that the "c" input was used twice rather than saying how the tree is constructed.

Thanks.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
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!