1

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

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 Dec 10 '11 at 11:51
  • @ThePiachu If you're content with a very good approximation, it's simply twice the number of leaves. – Meni Rosenfeld Dec 10 '11 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 Dec 10 '11 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 Dec 10 '11 at 23:04
  • @ThePiachu Then use an upper bound. The value of the function is always at most 2n + (log(n)/log(2)) - 1. – Meni Rosenfeld Dec 11 '11 at 5:57
-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.

  • 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 Dec 10 '11 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). – David Schwartz Dec 10 '11 at 2:54

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.