Mermaid Mountain Range

figure.md

graph TD;
  3 --> 1((1))
  3 --> 2((2))
  6 --> 4((4))
  6 --> 5((5))
  10 --> 8((8))
  10 --> 9((9))
  13 --> 11((11))
  13 --> 12((12))
  18 --> 16((16))
  18 --> 17((17))
  21 --> 19((19))
  21 --> 20((20))
  25 --> 23((23))
  25 --> 24((24))
  28 --> 26((26))
  28 --> 27((27))
  34 --> 32((32))
  34 --> 33((33))
  37 --> 35((35))
  37 --> 36((36))
  41 --> 39((39))
  41 --> 40((40))
  44 --> 42((42))
  44 --> 43((43))
  49 --> 47((47))
  49 --> 48((48))
  52 --> 50((50))
  52 --> 51((51))
  56 --> 54((54))
  56 --> 55((55))
  59 --> 57((57))
  7 --> 3((3))
  7 --> 6((6))
  14 --> 10((10))
  14 --> 13((13))
  22 --> 18((18))
  22 --> 21((21))
  29 --> 25((25))
  29 --> 28((28))
  38 --> 34((34))
  38 --> 37((37))
  45 --> 41((41))
  45 --> 44((44))
  53 --> 49((49))
  53 --> 52((52))
  15 --> 7((7))
  15 --> 14((14))
  30 --> 22((22))
  30 --> 29((29))
  46 --> 38((38))
  46 --> 45((45))
  31 --> 15((15))
  31 --> 30((30))

mmr_test.ts

// Copyright 2024 Carson Farmer
// Copyright 2021-2023 Triton Software AG
// SPDX-License-Identifier: GPL-2.0
// Typescript code ported from original Rust code
// @see {https://github.com/Neptune-Crypto/twenty-first}

/**
 * Get (index, height) of leftmost ancestor
 * This ancestor does *not* have to be in the MMR
 * This algorithm finds the closest $2^n - 1$ that's bigger than
 * or equal to `node_index`.
 */
function leftmostAncestor(nodeIndex: bigint): [bigint, bigint] {
  if (nodeIndex < 1n) {
    throw new Error("invalid node index");
  }
  let h = 0n;
  for (let i = 0n; i < 64n; i++) {
    if ((nodeIndex & (1n << (63n - i))) !== 0n) {
      h = i;
      break;
    }
  }
  h = 63n - h;
  const ret = (1n << (h + 1n)) - 1n;
  return [ret, h];
}

/**
 * Calculate the index of the left child of a node.
 */
function leftChild(nodeIndex: bigint, height: bigint): bigint {
  return nodeIndex - (1n << height);
}

/**
 * Calculate the index of the right child of a node.
 */
function rightChild(nodeIndex: bigint): bigint {
  return nodeIndex - 1n;
}

/**
 * Traversing from this node upwards, count how many of the ancestor (including itself)
 * is a right child. Also returns node's height.
 */
function rightLineageLengthAndOwnHeight(nodeIndex: bigint): [number, number] {
  let [candidate, candidateHeight] = leftmostAncestor(nodeIndex);
  let rightAncestorCount = 0;

  while (true) {
    if (candidate === nodeIndex) {
      return [rightAncestorCount, Number(candidateHeight)];
    }

    const leftChildNode = leftChild(candidate, candidateHeight);
    const candidateIsRightChild = leftChildNode < nodeIndex;
    if (candidateIsRightChild) {
      candidate = rightChild(candidate);
      rightAncestorCount += 1;
    } else {
      candidate = leftChildNode;
      rightAncestorCount = 0;
    }

    candidateHeight -= 1n;
  }
}

/**
 * Get the node_index of the parent
 */
function parent(nodeIndex: bigint): bigint {
  const [rightAncestorCount, height] = rightLineageLengthAndOwnHeight(
    nodeIndex,
  );

  if (rightAncestorCount !== 0) {
    return nodeIndex + 1n;
  } else {
    return nodeIndex + (1n << (BigInt(height) + 1n));
  }
}

/**
 * Convert from leaf index to node index
 */
function leafIndexToNodeIndex(leafIndex: bigint): bigint {
  const hammingWeight = countOnes(leafIndex);
  return 2n * leafIndex - hammingWeight + 1n;
}

/**
 * Count the number of 1s in the binary representation of `n`
 */
function countOnes(n: bigint): bigint {
  let count = 0n;
  while (n) {
    count += n & 1n;
    n >>= 1n;
  }
  return count;
}
      
Deno.test("create mmr tree", () => {
  const set = new Set<bigint>();
  const max = 31;
  console.log("graph TD;");
  for (let i = 0; i < max; i++) {
    const nodeIndex = leafIndexToNodeIndex(BigInt(i));
    const p = parent(nodeIndex);
    set.add(p);
    console.log(`${p} --> ${nodeIndex}((${nodeIndex}))`);
  }
  const big = leafIndexToNodeIndex(BigInt(max)) - 1n;
  for (const nodeIndex of set) {
    const p = parent(nodeIndex);
    if (p <= big) {
      set.add(p);
      console.log(`${p} --> ${nodeIndex}((${nodeIndex}))`);
    }
  }
});

Just a handy little deno "script" that logs a mermaid diagrams useful for explaining and exploring merkle mountain ranges (or binary numeral trees, or history trees, or functional scan trees, or whatever you want to call them). It is then quite handy to just include these diagrams in Notion, or GitHub content/posts.