2

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?)

  • Doesn't the image on the right show exactly one transaction? – user19510 Sep 18 '18 at 13:06
  • Yes, but it's Tx3, Does not it mean that we had 3 transactions (Tx0, Tx1, Tx2) before this one? – Questioner Sep 18 '18 at 13:36
  • 1
    As the caption says, that's the tree after pruning Tx0, Tx1, and Tx2. In any case, yes, merkle trees can store an odd number of things. – user19510 Sep 18 '18 at 13:41
4

The number of transactions will always be even in a merkle tree (even number of leafs). If you happen to have an uneven number of transactions, the last transaction will be doubled for the construction of the merkle tree.

  • 1
    That is one way to solve it but you can complete other ways with empty strings for example, or by cutting the branch if it is not preset (if tx2 is present but tx3 is missing then hash23 = hash2). – Ismael Sep 19 '18 at 3:40
  • Thanks for noticing this, @Ismael. The merkle trie itself is an abstract data structure which does not define how to handle an uneven number of nodes. Consequently, the actual implementation defines how to handle this case (e.g. Ismaels examples). Bitcoin uses merkle tries containing transactions and their procedure to handle an uneven number of nodes was described in my answer. Ethereum uses a modified merkle patricia trie, where an uneven number of transaction in the trie is possible, e.g. 1 tx: rootHash: [ hexPrefix(rlp(tx_index), rlp(tx) ] @sas – sea212 Sep 19 '18 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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