Altair hashing count for potential optimization in sync committee balance hashing

altair-sync-commitee-balance-hashing.ts

const d = 38; // Mainnet specs = 2**40 / 4
const chunkCount = 200_000 / 4; // Mainnet size, GWei = uint64, 4 on each 32 bytes chunk

const syncCommitteeSize = 2 ** 9; // Mainnet specs

const indexes: number[] = [];
for (let i = 0; i < syncCommitteeSize; i++) {
  // Does not consider the possibility of two indexes fiting in the same chunk. Tho this is very rare.
  indexes.push(Math.floor(chunkCount * Math.random()));
}

// Count number of nodes that would rehash
const nodes = new Set<number>();

for (const index of indexes) {
  const bitstring = toGindexBitstring(d, index);
  for (let i = 1; i <= bitstring.length; i++) {
    const gindex = parseInt(bitstring.slice(0, i), 2);
    nodes.add(gindex);
  }
}

const totalHashes = countTotalHashesIfAllChange(chunkCount);
console.log(totalHashes, nodes.size, nodes.size / totalHashes);

// console.log(toGindexBitstring(d, BigInt(0)));

/** Aprox total hashes to do if the entire tree is replaced. Slight under-estimation but good enough. */
function countTotalHashesIfAllChange(len: number): number {
  let lengthAtDepth = len;
  let totalHashes = 0;
  while (lengthAtDepth > 1) {
    totalHashes += lengthAtDepth;
    lengthAtDepth = Math.floor(lengthAtDepth / 2);
  }
  return totalHashes;
}

function toGindexBitstring(depth: number, index: number): string {
  const str = index ? index.toString(2) : "";
  if (str.length > depth) {
    throw new Error("index too large for depth");
  } else {
    return "1" + str.padStart(depth, "0");
  }
}