Massif blob pre-calculated offsets

Lookup tables for navigating the dynamic, but computable, offsets into the Merkle log binary format

This page provides lookup tables for navigating the dynamic, but computable, offsets into the Merkle log binary format. The algorithms to reproduce this are relatively simple. DataTrails provides open-source implementations, but in many contexts it is simpler to use these pre-calculations. These tables can be made for any log configuration at any time, in part or in whole, without access to any specific log.

This is a quick review of the log format. We explain this in more detail at Navigating the Merkle Log

Each Log Is Comprised of Many Blobs, Each Containing a Fixed Number of Leaves#

    +----------+ +----------+ .. +----------+
    | massif 0 | | massif 1 |    | massif n
    +----------+ +----------+ .. +----------+

New leaves are added to the last blob in the log.

Each Individual Blob Has a Fixed Size Portion and Two Variably Sized Sections#

    |--------.----------.----------.---------|
    |  fixed  size      | computable size    |
    |--------.----------.----------.---------|
    | header | trieData |peak stack| mmrData |
    |--------.----------.----------.---------|

The Peak Stack and MMR Data Sizes Are Computable#

…but it is not always convenient to do so.

Using veracity, the following command line can reproduce a canonical “illustrative” log from Navigating the Merkle Log

veracity --height 2 massifs --count 6

generates:

                       14
                          \
                6           13             21
                  \            \              \
    h=2 1 |  2  |  5  |   9  |  12   |  17   | 20  |
          |     |     |      |       |       |     |
        0 |0   1| 3  4| 7   8|10   11|15   16|18 19| MMR INDICES
        0 |0   1| 2  3| 4   5|6     7|8     9|10 11| LEAF INDICES

The following table Stack Start and mmr Start are byte offsets from the start of the file. Stack Start is the end of the fixed header information, the relevant parts of which are described in Navigating the Merkle Log.

The leaf values are indices into the trie fields (not considered further in this page) and the node values are indices into the array of 32-byte nodes starting at mmr Start

It is fairly easy to validate the leaves and nodes by hand. Reproducing the Stack Start needs details from Navigating the Merkle Log.

Pre-computes for Your First Million Events#

DataTrails production logs currently have a massif height of 14, which is results in 8129 leaves, which is $$1^{14-1}$$

The Algorithms Backing the Table Generation#

In combination with the format information at Navigating the Merkle Log the pre-computed tables above can be generated using these examples using the DataTrails open source, go-lang based veracity tooling.

• Leaf Count and Massif Index
• mmrIndex from leafIndex
• Peak Stack Length

function massifIndex(mmrIndex, massifHeight) {
  const nl =  Number(leafCount(mmrIndex + 1n));
  const f = Number(1n << massifHeight);
  const massifIndex = Math.floor(nl / f);
  return massifIndex;
}

// returns the number of leaves in the largest mmr whose size is <= the supplied size
function leafCount(mmrSize) {
  let pos = BigInt(mmrSize);
  if (pos == BigInt(0)) return 0n;
  let peakSize = ((1n << 64n) - 1n) >> BigInt(clz64(mmrSize));
  let peakMap = 0n;
  for (; peakSize > 0n;) {
    peakMap <<= 1n
    if (pos >= peakSize) {
      pos -= peakSize;
      peakMap |= 1n;
    }
    peakSize >>= 1n;
  }
  return peakMap;
}

function clz64(num) {
  if (!typeof num === 'bigint') throw new Error(`num must be bigint not ${typeof num}`);
  num = BigInt.asUintN(64, num);

  const hi = num >> 32n;
  let lz = Math.clz32(Number(hi));
  if (lz !== 0) return lz;
  const lo = Number((num & ((1n << 32n) - 1n)));
  return 32 + Math.clz32(lo);
}

function treeIndex(iLeaf) {
  let sum = 0n; // Assuming iLeaf can be very large, use BigInt for accuracy.
  let i = BigInt(iLeaf); // Ensure iLeaf is treated as BigInt

  while (i > 0n) {
      const height = log2Uint64(i) + 1n;
      sum += spurSumHeight(height) + BigInt(height);
      const half = 1n << (height - 1n);
      i -= half;
  }

  return sum;
}

// spurSumHeight counts the interior 'spur' nodes required for the given height
function spurSumHeight(height) {
  height = BigInt(height); // Ensure height is treated as BigInt

  if (height === BigInt(0)) {
      return BigInt(0);
  }

  let sum = BigInt(0);
  for (let i = BigInt(1); i <= height - BigInt(1); i += BigInt(1)) {
      sum += (BigInt(1) << (height - BigInt(1) - i)) * i;
  }
  return sum;
}

function log2Uint64(num) {
  if (typeof num === 'bigint') {
      if (num <= 1n) return 0n; // log2(1) = 0 and log2(0) is undefined, handled as 0 for simplicity
      let log = 0n;
      while (num > 1n) {
          num >>= 1n;
          log += 1n;
      }
      return log;
  }

  if (num <= 1) return 0; // Similarly, handle log2(1) = 0 and log2(0) as 0
  return Math.floor(Math.log2(num));
}

/** Calculate the size of a massifs peak stack by passing the massifIndex in place of iLeaf */
function leafMinusSpurSum(iLeaf) {
  let sum = BigInt(iLeaf);
  iLeaf = sum >> BigInt(1);

  while (iLeaf > 0) {
      sum -= iLeaf;
      iLeaf >>= BigInt(1);
  }
  return sum;
}