|
Title: merkle tree order of hashes Post by: TierNolan on 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. Title: Re: merkle tree order of hashes Post by: kjj on 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 (https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees) Title: Re: merkle tree order of hashes Post by: TierNolan on June 24, 2011, 03:17:18 PM Double the unpaired one. https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees (https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees) Ahh right. I read that to mean that the "c" input was used twice rather than saying how the tree is constructed. Thanks. |