Bitcoin Forum
May 25, 2018, 07:57:13 AM *
News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: merkle tree order of hashes  (Read 792 times)
TierNolan
Legendary
*
Offline Offline

Activity: 1176
Merit: 1001


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
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1527235033
Hero Member
*
Offline Offline

Posts: 1527235033

View Profile Personal Message (Offline)

Ignore
1527235033
Reply with quote  #2

1527235033
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1000



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

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
TierNolan
Legendary
*
Offline Offline

Activity: 1176
Merit: 1001


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!