4

According to definition and structure of the Merkle Tree, apparently, the number of transactions in a block that inserted in a Merkle Tree structure must be even (and not odd), is not it?

Please see the following figure which shows a Merkle Tree:

enter image description here

All the examples that I have seen, are like this one, meaning that apparently always number of transactions in a Merkle Tree are even (ex. in the example above there are four transactions). Is there an example in which number of transactions would be odd? And what happens if number of transaction are odd? (ex. how to insert 5 transactions in above example?)

Improve this question

1 Answer 1

Reset to default
13

If there are an odd number of nodes on any level of the merkle tree, the last node is duplicated and hashed with itself.n

If there were a Tx4, the diagram would look like this

                  Root (Hash01234444)
               /                      \
        Hash0123                 Hash4444
        /      \                    /     \
   Hash01      Hash23           Hash44     Hash44
   /   \        /   \             /   \
Hash0  Hash1  Hash2  Hash3     Hash4   Hash4
Improve this answer
6
  • Thank you, but does not this approach cause "overlapping" for storing transactions in a block? (Regarding to the space limitation we logically need to saving space and decreasing the size of data, isn't it?)
    – Questioner
    Commented Sep 20, 2018 at 9:02
  • 1
    Transactions are not stored like that. This duplication is only done at calculation time. There is no duplicated transaction stored in the block. It is simply part of the merkle root computation algorithm that the duplication is done.
    – Ava Chow ♦
    Commented Sep 20, 2018 at 13:59
  • @Thank you, It's OK. However, I mean "duplication of hash" and not duplication of transactions. However, since in a hash algorithm like SHA256 the size of output is always fix, so ex. in your example, size of Hash01234444 is equal to size of Hash01234, so we do not need any more space for Hash01234444. Hope I am right.
    – Questioner
    Commented Sep 20, 2018 at 14:40
  • The hashes aren't stored.
    – Ava Chow ♦
    Commented Sep 20, 2018 at 14:56
  • 2
    The merkle root (root hash in the diagram) is stored. That is the only hash stored. It is a fixed size, regardless of the rest of the merkle tree. The hashes in the merkle tree are not stored.
    – Ava Chow ♦
    Commented Sep 20, 2018 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.