0

I've been trying to understand this for a few days now.

I understand that the hashmerkleroot is the root node of a fully perfect binary tree. I also understand that the sha256d hashes would be the non-leaf/parent nodes of the tree and the sha256d hashes of the transactions would be the leaf nodes.

I also know that a fully perfect binary tree with 'x' leaves has 2x-1 nodes.

The question I'm trying to answer is what is the formula for the number of SHA256d hashes required to obtain the hashmerkleroot if the number of transactions to be hashed is 'x'? Is any of my understanding above incorrect?

2

If the number of leaves is exactly a power of two (i.e., n = 2k), then the number of hashes performed is exactly n-1. This is easy to see: every hash operation takes two inputs, and reduces them to a single one. After n-1 operations, that means n nodes are reduced to 1, and that one is the Merkle root.

When the number of leaves is not a power of two, it's a bit more complicated. Whenever a "level" of the Merkle tree has an odd number of leaves, a hash operation is still performed for the last one, but it only takes one input. So every time this happens, it means an addition hash operation on top of the n-1 that are expected otherwise.

How often does that happen? Let's look at the level sizes for n=9..16 leaves:

  • 9 → 5 → 3 → 2 → 1: 11 hashes (n - 1 + 3 odd levels)
  • 10 → 5 → 3 → 2 → 1: 11 hashes (n - 1 + 2 odd levels)
  • 11 → 6 → 3 → 2 → 1: 12 hashes (n - 1 + 2 odd levels)
  • 12 → 6 → 3 → 2 → 1: 12 hashes (n - 1 + 1 odd level)
  • 13 → 7 → 4 → 2 → 1: 14 hashes (n - 1 + 2 odd levels)
  • 14 → 7 → 4 → 2 → 1: 14 hashes (n - 1 + 1 odd level)
  • 15 → 8 → 4 → 2 → 1: 15 hashes (n - 1 + 1 odd level)
  • 16 → 8 → 4 → 2 → 1: 15 hashes (n - 1 + 0 odd levels)

The number of odd levels is exactly equal to the number of 1 bits set in the binary representation of the difference between the number of leaves and the next power of two. For example, for n=11 leaves, the next power of two is 16, the difference between those is 5, which is written in binary as 1012, which has two 1s. Thus, the number of hashing operations is 11-1 + 2 = 12 hashes.

Without knowing anything about the structure of the number of leaves, a lower bound on the number of hashing operations is n-1, and an upper bound is n-1+log2(n-1).

3
  • Thanks. Most of it makes sense. 2 quick clarifications: 1. Wouldn't the total number of hashes be 2n-1 (when txs are a power of 2) as all the transactions need to be hashed to form the leaves? 2. I'm not sure I follow the log2(n-1) part in n-1+log2(n-1) Sep 5 at 21:57
  • I wasn't counting the transaction hashes. If you include those, add n to all results, but it's not entirely comparable, as transaction hashes are also more expensive (transactions are larger than 64 bytes). This is all also excluding all the witness hashes and the witness Merkle tree added by BIP141 (which roughly doubles things). Sep 6 at 0:18
  • Thanks. Good point n the witness hashes and the transaction hashes being more expensive. Much appreciated! Sep 6 at 21:02

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.