Merkle tree structure for 9 transactions

Question

I've been reading the developers documentation, other sources and the good books about Bitcoin. But none of the resources shows a merkle tree with 5 or more leafs. I'm confused, does the bitcoin core make a merkle tree of transactions (a,b,c,d,e,f,g,h,i) like:

H( H( H( H(a,b), H(c,d) ), H( H(e,f), H(g,h) ) ), H(i,i) )

or It's wrong?

I'm asking, because the structure of this one is not close to a complete binary tree, as every example I've found in the resources. If I'm right, the structure would be something like:

               _____/\______
             / \           / \
            /   \         i   i
           /     \
          /       \
         /         \
        /           \
      /   \       /   \
    / \   / \   / \   / \ 
   a   b c   d e   f g   h 

Thanks

Answer 1

That's not exactly right. It's more 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

At each level of the tree, if it's odd, then you just copy the last element onto the back of the tree, and then you hash the pairs to produce a new list at about half the size. Then you do the same thing with that list, in a recursive algorithm, repeating until you have just one element left (Note that if you only have 1 transaction in the block, the merkle root is just the TXID of that transaction). The result is not always a binary tree, it just happens to be when the number of transactions is a power of 2.

It's also interesting to note that the fact that i is hashed with itself introduces a vulnerability (CVE-2012-2459). Basically, I could publish a block that actually listed the transaction with i as the TXID twice at the end of the block. Obviously that block would be invalid, as it has the same transaction twice in the block. But the merkle root would be the same as a block that had a valid list of transactions, with i listed only once. But since you think you have already seen the block with with that header and merkle root, you would deny it. This is fixed by marking all blocks that have duplicate values in the merkle tree structure as having invalid merkle roots.