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

2 Answers 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 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));
  • Well yes, recursively, it is not a problem, I was thinking about calculating it without recursion, if it is at all possible.
    – ThePiachu
    Commented Dec 10, 2011 at 11:51
  • @ThePiachu If you're content with a very good approximation, it's simply twice the number of leaves. Commented Dec 10, 2011 at 16:52
  • @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
    Commented Dec 10, 2011 at 19:58
  • 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
    Commented Dec 10, 2011 at 23:04
  • @ThePiachu Then use an upper bound. The value of the function is always at most 2n + (log(n)/log(2)) - 1. Commented Dec 11, 2011 at 5:57

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.

  • Well, Block Explorer for example lists all the hashes of the merkle tree as a list - blockexplorer.com/rawblock/… - I am wondering how one would pre-calculate the length of the array given the number of the leaf nodes.
    – ThePiachu
    Commented Dec 10, 2011 at 0:53
  • 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). Commented Dec 10, 2011 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.