<p>If the number of leaves is exactly a power of two (i.e., <em>n = 2<sup>k</sup></em>), then the number of hashes performed is exactly <em>n-1</em>. This is easy to see: every hash operation takes two inputs, and reduces them to a single one. After <em>n-1</em> operations, that means <em>n</em> nodes are reduced to <em>1</em>, and that one is the Merkle root.</p>
<p>When the number of leaves is not a power of two, it's a bit more complicated. Whenever a &quot;level&quot; 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 <em>n-1</em> that are expected otherwise.</p>
<p>How often does that happen? Let's look at the level sizes for <em>n=9..16</em> leaves:</p>
<ul>
<li><em>9 → 5 → 3 → 2 → 1</em>: <em>11</em> hashes (<em>n - 1</em> + <em>3</em> odd levels)</li>
<li><em>10 → 5 → 3 → 2 → 1</em>: <em>11</em> hashes (<em>n - 1</em> + <em>2</em> odd levels)</li>
<li><em>11 → 6 → 3 → 2 → 1</em>: <em>12</em> hashes (<em>n - 1</em> + <em>2</em> odd levels)</li>
<li><em>12 → 6 → 3 → 2 → 1</em>: <em>12</em> hashes (<em>n - 1</em> + <em>1</em> odd level)</li>
<li><em>13 → 7 → 4 → 2 → 1</em>: <em>14</em> hashes (<em>n - 1</em> + <em>2</em> odd levels)</li>
<li><em>14 → 7 → 4 → 2 → 1</em>: <em>14</em> hashes (<em>n - 1</em> + <em>1</em> odd level)</li>
<li><em>15 → 8 → 4 → 2 → 1</em>: <em>15</em> hashes (<em>n - 1</em> + <em>1</em> odd level)</li>
<li><em>16 → 8 → 4 → 2 → 1</em>: <em>15</em> hashes (<em>n - 1</em> + <em>0</em> odd levels)</li>
</ul>
<p>The number of odd levels is exactly equal to the number of <em>1</em> bits set in the binary representation of the difference between the number of leaves and the next power of two. For example, for <em>n=11</em> leaves, the next power of two is <em>16</em>, the difference between those is <em>5</em>, which is written in binary as <em>101<sub>2</sub></em>, which has two <em>1</em>s. Thus, the number of hashing operations is <em>11-1 + 2 = 12</em> hashes.</p>
<p>Without knowing anything about the structure of the number of leaves, a lower bound on the number of hashing operations is <em>n-1</em>, and an upper bound is <em>n-1+log<sub>2</sub>(n-1)</em>.</p>

CC BY-SA 4.0
2021-09-05T21:57:40.143Z
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)
arikachimoaririki
CC BY-SA 4.0
2021-09-06T00:18:09.377Z
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).
Pieter Wuille
CC BY-SA 4.0
2021-09-06T21:02:58.927Z
Thanks. Good point n the witness hashes and the transaction hashes being more expensive. Much appreciated!
arikachimoaririki
CC BY-SA 4.0
2021-09-01T22:02:48.713Z
2021-09-01T22:02:48.713Z
Pieter Wuille
<p>I've been trying to understand this for a few days now.</p>
<p>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.</p>
<p>I also know that a fully perfect binary tree with 'x' leaves has 2x-1 nodes.</p>
<p>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?</p>

<hash><merkle-tree><sha256>
For a block containing 'x' number of unverified transactions, how many SHA256d hashes are performed to obtain the hashmerkleroot?
arikachimoaririki
# For a block containing 'x' number of unverified transactions, how many SHA256d hashes are performed to obtain the hashmerkleroot?

(Asked by: username_0 on 2021-09-01)

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?

**Tags:** hash, merkle-tree, sha256


---

## 1 answers

### Answer by username_1 on 2021-09-01. Score: 2 | Accepted answer

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 *1*s. 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)*.

> **Comments:**
> **username_0**: 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)  
> **username_1**: 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).  
> **username_0**: Thanks. Good point n the witness hashes and the transaction hashes being more expensive. Much appreciated!  

---

