<p>The length of a merkle tree is the sum of a series starting with the number of leaves, halving (rounded up) on every step and ending with 1.</p>

<p>Here is the algorithm for calculating the length of a merkle tree from the number of leaves in JavaScript.</p>

<pre><code>function getMerkleLength(leafCount) {
  // Input must be a positive integer or zero
  leafCount = Math.abs(parseInt(leafCount));

  var merkleLength = 0, currentLevel = leafCount;

  // Most merkle tree implementations return a null hash for empty lists, so the
  // length in that case would still be one.
  if (leafCount &lt;= 1) return 1;

  // Loop
  for (;;) {
    // Add the current level to the length
    merkleLength += currentLevel;

    // If the current level is the root, we are done
    if (currentLevel == 1) return merkleLength;

    // Each level contains half the hashes of the last one and if there is an
    // odd number of leafs, the last hash is duplicated
    currentLevel = Math.ceil(currentLevel / 2);
  }
  return merkleLength;
}
</code></pre>

<p><strong>Edit:</strong> I like readable code, but just for fun, here's the equivalent short version:</p>

<pre><code>function getMerkleLength(leafCount) {
  for (var len = 0, i = ~~leafCount; i &gt; 1; i = ~~(i/2+.5)) len += i;
  return len &gt;= 2 ? ++len : 1;
}
</code></pre>

<p><strong>Edit 2:</strong> And a <a href="http://codepad.org/xfvhtwXn" rel="nofollow">C version</a> for good measure.</p>

<pre><code>typedef unsigned int uint;

uint getMerkleLength(uint leafCount)
{
  uint len = 0, i;
  for (i = leafCount; i &gt; 1; i = (i+1)&gt;&gt;1) {
    len += i;
  }
  return len &gt;= 2 ? ++len : 1;
}

void main() {
  uint i;
  for (i = 0; i &lt;= 100; i++) {
    printf("%u: %u\n", i, getMerkleLength(i));
  }
  printf("%u: %u\n", 5000, getMerkleLength(5000));
  printf("%u: %u\n", 99999999, getMerkleLength(99999999));
}
</code></pre>

CC BY-SA 3.0
2011-12-10T11:51:48.243Z
Well yes, recursively, it is not a problem, I was thinking about calculating it without recursion, if it is at all possible.
ThePiachu
CC BY-SA 3.0
2011-12-10T16:52:36.480Z
@ThePiachu If you're content with a very good approximation, it's simply twice the number of leaves.
Meni Rosenfeld
CC BY-SA 3.0
2011-12-10T19:58:13.603Z
@MeniRosenfeld Hmm, approximation, maybe, but one can't count on it being enough with memory allocation. The approximation is one short for 5 (5+3+2+1=11) and 10 (10+5+3+2+1=21).
ThePiachu
CC BY-SA 3.0
2011-12-10T23:04:23.770Z
Not sure I get your point, this loop will execute about once per bit. So for a merkle tree with 1 million transactions, you'll need about 20 iterations of the loop, maybe 300 cycles. That's about the cost of a 2-3 memory accesses. I can't imagine a scenario where it would be worth optimizing this function or using a heuristic. If you plan on allocating the memory for that merkle tree, you'll spend several orders of magnitude longer doing that.
justmoon
CC BY-SA 3.0
2011-12-11T05:57:44.020Z
@ThePiachu Then use an upper bound. The value of the function is always at most 2n + (log(n)/log(2)) - 1.
Meni Rosenfeld
CC BY-SA 3.0
2011-12-10T01:55:27.610Z
2012-04-04T16:44:43.917Z
2012-04-04T16:44:43.917Z
justmoon
<p>It's not clear exactly what you're asking. The 'Merkle Tree' is a notional structure consisting of a number of different objects used in the process of generating a hash. It's not an object with a standard binary format whose length is well-defined.</p>

<p>In other words, the Merkle Tree is an algorithm. You put in an ordered list of N 256-bit hashes, and you get out a single 256-bit hash. There really is no "Merkle Tree" <em>itself</em> that has any length. To reconstruct the entire process, you need all and only the input hashes in order.</p>

CC BY-SA 3.0
2011-12-10T00:53:45.497Z
Well, Block Explorer for example lists all the hashes of the merkle tree as a list - http://blockexplorer.com/rawblock/0000000000000086f8bf1ddf9d45ecb0fb3405b4a203fb7c84a8624b5e447e95 - I am wondering how one would pre-calculate the length of the array given the number of the leaf nodes.
ThePiachu
CC BY-SA 3.0
2011-12-10T02:54:24.353Z
I believe there's one 256-bit entry for each transaction. The top one is the hash of the first transaction, which is what the hash would be if only the first transaction were included. The last one is the final hash, the one with all transactions included (and it matches the hash in the header).
David Schwartz
CC BY-SA 3.0
2011-12-09T22:52:11.363Z
2011-12-10T00:00:12.973Z
2011-12-10T00:00:12.973Z
David Schwartz
<p>What is the formula to calculate the length of a merkle tree, given the length of the leaf vector?</p>

<protocol><academic-research>
What is the formula to calculate the length of a merkle tree?
ThePiachu
# What is the formula to calculate the length of a merkle tree?

(Asked by: username_0 on 2011-12-09)

What is the formula to calculate the length of a merkle tree, given the length of the leaf vector?

**Tags:** protocol, academic-research


---

## 2 answers

### Answer by username_1 on 2011-12-10. Score: 2

The length of a merkle tree is the sum of a series starting with the number of leaves, halving (rounded up) on every step and ending with 1.

Here is the algorithm for calculating the length of a merkle tree from the number of leaves in JavaScript.

```
function getMerkleLength(leafCount) {
  // Input must be a positive integer or zero
  leafCount = Math.abs(parseInt(leafCount));

  var merkleLength = 0, currentLevel = leafCount;

  // Most merkle tree implementations return a null hash for empty lists, so the
  // length in that case would still be one.
  if (leafCount <= 1) return 1;

  // Loop
  for (;;) {
    // Add the current level to the length
    merkleLength += currentLevel;

    // If the current level is the root, we are done
    if (currentLevel == 1) return merkleLength;

    // Each level contains half the hashes of the last one and if there is an
    // odd number of leafs, the last hash is duplicated
    currentLevel = Math.ceil(currentLevel / 2);
  }
  return merkleLength;
}

```

**Edit:** I like readable code, but just for fun, here's the equivalent short version:

```
function getMerkleLength(leafCount) {
  for (var len = 0, i = ~~leafCount; i > 1; i = ~~(i/2+.5)) len += i;
  return len >= 2 ? ++len : 1;
}

```

**Edit 2:** And a [C version](http://codepad.org/xfvhtwXn) for good measure.

```
typedef unsigned int uint;

uint getMerkleLength(uint leafCount)
{
  uint len = 0, i;
  for (i = leafCount; i > 1; i = (i+1)>>1) {
    len += i;
  }
  return len >= 2 ? ++len : 1;
}

void main() {
  uint i;
  for (i = 0; i <= 100; i++) {
    printf("%u: %u\n", i, getMerkleLength(i));
  }
  printf("%u: %u\n", 5000, getMerkleLength(5000));
  printf("%u: %u\n", 99999999, getMerkleLength(99999999));
}

```

> **Comments:**
> **username_0**: Well yes, recursively, it is not a problem, I was thinking about calculating it without recursion, if it is at all possible.  
> **username_2**: @username_0 If you're content with a very good approximation, it's simply twice the number of leaves.  
> **username_0**: @username_2 Hmm, approximation, maybe, but one can't count on it being enough with memory allocation. The approximation is one short for 5 (5+3+2+1=11) and 10 (10+5+3+2+1=21).  
> **username_1**: Not sure I get your point, this loop will execute about once per bit. So for a merkle tree with 1 million transactions, you'll need about 20 iterations of the loop, maybe 300 cycles. That's about the cost of a 2-3 memory accesses. I can't imagine a scenario where it would be worth optimizing this function or using a heuristic. If you plan on allocating the memory for that merkle tree, you'll spend several orders of magnitude longer doing that.  
> **username_2**: @username_0 Then use an upper bound. The value of the function is always at most 2n + (log(n)/log(2)) - 1.  

---

### Answer by username_3 on 2011-12-09. Score: -1

It's not clear exactly what you're asking. The 'Merkle Tree' is a notional structure consisting of a number of different objects used in the process of generating a hash. It's not an object with a standard binary format whose length is well-defined.

In other words, the Merkle Tree is an algorithm. You put in an ordered list of N 256-bit hashes, and you get out a single 256-bit hash. There really is no "Merkle Tree" *itself* that has any length. To reconstruct the entire process, you need all and only the input hashes in order.

> **Comments:**
> **username_0**: Well, Block Explorer for example lists all the hashes of the merkle tree as a list - http://blockexplorer.com/rawblock/0000000000000086f8bf1ddf9d45ecb0fb3405b4a203fb7c84a8624b5e447e95 - I am wondering how one would pre-calculate the length of the array given the number of the leaf nodes.  
> **username_3**: I believe there's one 256-bit entry for each transaction. The top one is the hash of the first transaction, which is what the hash would be if only the first transaction were included. The last one is the final hash, the one with all transactions included (and it matches the hash in the header).  

---

