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]
 Author Topic: merkle tree order of hashes  (Read 792 times)
TierNolan
Legendary

Offline

Activity: 1176
Merit: 1001

 June 24, 2011, 02:55:41 PM

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

Posts: 1527235033

Ignore
 1527235033

1527235033
 Report to moderator
kjj
Legendary

Offline

Activity: 1302
Merit: 1000

 June 24, 2011, 03:13:24 PM

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

Activity: 1176
Merit: 1001

 June 24, 2011, 03:17:18 PM

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]
 « previous topic next topic »