Last active
August 5, 2021 12:11
-
-
Save dapplion/1d354becbd65f9db1b213a8ebe7653d7 to your computer and use it in GitHub Desktop.
Numerical simulation to estimate hashing cost of balance updates on altair block processing, only for sync committee indexes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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"); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment