Complete Binary Merkle Tree

A Binary Merkle Tree must have exactly $2^n$ leaves. If we have, say, 5 values to commit to, we must pad them with 3 more to reach 8, which wastes space and hashes. A Complete Binary Merkle Tree solves this: it works with any number of leaves $N$, using exactly $2N-1$ nodes. It is used by Nervos CKB, for example.

The idea is to fill the tree level by level, just like a binary heap. The nodes are stored in an array where the root is at position 0, the children of the node at position $k$ are at $2k+1$ and $2k+2$, and the leaves are the last $N$ nodes. Here is the tree with 5 leaves:

graph BT
  n0["0 (root)"]
  n1["1"] --> n0
  n2["2"] --> n0
  n3["3"] --> n1
  n4["4 = H(leaf 0)"] --> n1
  n5["5 = H(leaf 1)"] --> n2
  n6["6 = H(leaf 2)"] --> n2
  n7["7 = H(leaf 3)"] --> n3
  n8["8 = H(leaf 4)"] --> n3

Notice that the leaves are on the last two levels: leaves 0, 1 and 2 are at depth 2, while leaves 3 and 4 are at depth 3. This is the same layout as our BinaryMerkleTree, which is simply the special case $N=2^n$, where all leaves are at the same depth.

CompleteBinaryMerkleTree

template CompleteBinaryMerkleTree(N) {
  assert(N > 0);
  signal input leafs[N];
  signal output root;

  // nodes are stored as in a binary heap: the root is at 0,
  // the children of node `i` are `2i + 1` and `2i + 2`, and the leaves are the last `N` nodes
  signal nodes[2 * N - 1];
  for (var i = 0; i < N; i++) {
    nodes[N - 1 + i] <== Poseidon(1)([leafs[i]]);
  }
  for (var i = N - 2; i >= 0; i--) {
    nodes[i] <== Poseidon(2)([nodes[2 * i + 1], nodes[2 * i + 2]]);
  }

  root <== nodes[0];
}

Computing the root is exactly as in BinaryMerkleTree, only with $N$ leaves: hash the leaves into the last $N$ positions, then fill in the internal nodes backwards from position $N-2$ down to the root. Our tests check that CompleteBinaryMerkleTree(4) gives the same root as BinaryMerkleTree(2).

CompleteBinaryMerkleProof

function cbmtDepth(N) {
  var depth = 0;
  while ((1 << (depth + 1)) <= 2 * N - 1) {
    depth++;
  }
  return depth;
}

template CompleteBinaryMerkleProof(N) {
  assert(N > 1);
  var D = cbmtDepth(N);
  signal input leaf;
  signal input index;
  signal input siblings[D];
  signal output root;

  // the index must be within the leaves; `N <= 2^D`, so both fit in `D + 1` bits
  _ <== Num2Bits(D + 1)(index);
  signal isValid <== LessThan(D + 1)([index, N]);
  isValid === 1;

  // position of the leaf in the tree, counting from 1 at the root, level by level;
  // the leaf is at the deepest level `D` if its position is at least `2^D`, otherwise at `D - 1`
  var position = N + index;
  signal isShallow <== LessThan(D + 1)([position, 1 << D]);
  var depth = D - isShallow;

  // the index of the leaf within its level, whose bits give the path from the leaf to the root
  var levelIndex = position - (1 << D) + isShallow * (1 << (D - 1));

  signal leafHash <== Poseidon(1)([leaf]);
  root <== BinaryMerkleRoot(D)(leafHash, depth, levelIndex, siblings);
}

A proof for a leaf is again its siblings from the leaf up to the root, but now the leaves can be at two different depths, so the number of siblings depends on the leaf. We use zk-kit’s BinaryMerkleRoot for this, which supports a variable depth up to a maximum: the maximum is the deepest level $D=\lfloor {\log }_2(2N-1)\rfloor$, and the siblings of a shallower leaf are padded with a 0.

The interesting part is to find the depth and the path of a leaf from its index, and it turns out that this is mostly linear. Number the nodes from 1 instead of 0, i.e. the root is 1, and the children of $j$ are $2j$ and $2j+1$. In this numbering:

• The leaf with index $i$ is at position $j=N+i$.
• A node at depth $d$ has a position in range $[2^d,2^{d+1})$. So the leaf is at the deepest level $D$ if $j\ge 2^D$, and at level $D-1$ otherwise. A single LessThan finds out which one.
• The bits of $j$ describe the path from the root: after the leading 1, each bit is 0 for a left child and 1 for a right child. So $j-2^d$, the index of the node within its level, has exactly the bits of the path, which is what BinaryMerkleRoot takes as its index.

For example, with $N=5$, leaf 4 is at position $j=9=(1001{)}_2$, which is $\ge 2^3$, so it is at depth 3. Its index within the level is $9-8=1=(001{)}_2$: from the root it goes left, left, then right, which is node 8 in the 0-based numbering of the figure above.

Since the depth is computed from the index instead of being given by the prover, the prover can not present an internal node as a leaf by choosing a smaller depth. We also make sure that the index is less than $N$, otherwise an index like $N$ would point to some other node of the tree.

Constraint Count

A proof for a million leaves has a depth of 20, and it costs about the same as a proof in a Binary Merkle Tree of depth 20, but without having to pad the leaves to $2^{20}=1048576$.

See Also

• Nervos Network’s CBMT implementation: https://github.com/nervosnetwork/merkle-tree