2

The Bitcoin client builds a merkle tree to represent the transactions, then includes the root of that tree in the block header.
merkle tree from bitcoin paper
But usually, the number of transactions is not a power of two. When that happens, how does the Bitcoin client represent the transactions in the tree?

If I wrote a custom mining client, which built a tree with a different "shape," (example below) what would happen?

custom merkle tree

3

When the number of transactions is not a power of two, how does the Bitcoin client represent the transactions?

Each time around, it hashes each transaction with the one next to it, until there's only one left.
2 transactions merkle tree example
If there's an odd number of transactions, the last one is hashed again. 3 transactions merkle tree example
In this example, we start out with 11, then 6, then 3, then 2, then 1. 11 transactions merkle tree example

What would happen if you made a differently-shaped merkle-tree?

When sending blocks around, there's no way to specify the shape of the merkle tree. If it's different, the standard client will just reject it.

  • 3
    Small correction: when there are an odd number of elements in a level, the last one is hashed after appending it to itself. So usually hash6 of one level is H(hash12+hash13) of the level below, but it can be H(hash12+hash12) if hash12 is the last one. – Pieter Wuille Sep 1 '14 at 9:21
  • @PieterWuille Huh. I hadn't noticed that. +1 – Nick ODell Sep 1 '14 at 15:15

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.