8

Merkle Tree pairs transactions and hashes them and the process continues till we get to the root. But how would this pairing process work if the number of transactions were odd?

Merkle tree illustration with 8 transactions

1 Answer 1

12

Ethereum uses Modified Merkle Patricia Tries for transactions (as well as for state and transaction receipts). The key for a transaction in the trie is its RLP encoded index in the transaction list of a block. See a good explanation of how Patricia Tries are constructed ELI5 How does a Merkle-Patricia-trie tree work?

Here is an example of how the state trie looks like (for transactions just replace Simplified World State on the top-right with Simplified Transactions where Keys are transaction_index and Values are transaction_content. It's simplified since some details are omitted such as RLP encoding). The number of nibbles for state trie is always 64, for transactions trie it varies.

enter image description here

For the case of Bitcoin, where Merkle Tree is used, in case the number of transactions is odd at some level of the tree then you just copy the element onto the right to form a pair. So the tree may look something like this:

                            ROOT
                            /  \   
                         /        \  
                      /              \
                   /                    \
               z1                            z2
             /  \                           / \
           /      \                       /     \
        /            \                /            \
      y1              y2             y3             y3
     /  \            /  \           / \
   /      \        /      \       /     \
  x1      x2      x3      x4     x5    x5
 / \     / \     / \     / \     / \ 
a   b   c   d   e   f   g   h   i   i

As you can see i, x5, y3 are duplicated in the tree.

To answer your questions:

Can a mined block have odd number of transactions?

Yes

How merkle root works in that case?

Whether there is an even or odd number of transactions doesn't matter since in Patricia Merkle Trie there is no pairing of nodes like in Merkle Tree case.

3
  • Shouldn't a key contain 8 nibble (32 bytes)? In your example it contains 7 nibbles, which is 28 bytes. @medvedev1088
    – alper
    Dec 15, 2017 at 6:53
  • Got it, 16 nibbles on state-trie. Is the key size on transaction trie is fixed? As I know each Tx is 64 bytes. Sorry I didn't get the RLP(1) example. @medvedev1088
    – alper
    Dec 15, 2017 at 7:23
  • 1
    No, the key size on transaction trie is not fixed. The key for a transaction in the trie is its RLP encoded index in the transaction list of a block. For example if there are only 3 transactions in a block then the transactions trie will have 3 keys: RLP(0), RLP(1), RLP(2). github.com/ethereum/wiki/wiki/Patricia-Tree#transactions-trie Dec 15, 2017 at 7:28

Your Answer

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

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