Bitcoin Forum
October 20, 2017, 08:18:37 PM
 News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: merkle tree order of hashes  (Read 774 times)
TierNolan
Legendary

Offline

Activity: 1120

 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
1508530717
Hero Member

Offline

Posts: 1508530717

Ignore
 1508530717

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

Offline

Posts: 1508530717

Ignore
 1508530717

1508530717
 Report to moderator
1508530717
Hero Member

Offline

Posts: 1508530717

Ignore
 1508530717

1508530717
 Report to moderator
1508530717
Hero Member

Offline

Posts: 1508530717

Ignore
 1508530717

1508530717
 Report to moderator
kjj
Legendary

Offline

Activity: 1302

 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

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

Activity: 1120

 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 »