What is the formula to calculate the length of a merkle tree? What is the formula to calculate the length of a merkle tree, given the length of the leaf vector?
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 &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;
}


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 &gt; 1; i = ~~(i/2+.5)) len += i;
  return len &gt;= 2 ? ++len : 1;
}


Edit 2: And a C version for good measure.

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));
}