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?
Can a mined block have an odd number of transactions? If so, how does the Merkle root in that case?
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.
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?
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.
Shouldn't a key contain 8 nibble (32 bytes)? In your example it contains 7 nibbles, which is 28 bytes. @medvedev1088– alperDec 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– alperDec 15, 2017 at 7:23
1No, 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