HashTower Simulation

10M_items.txt

Simulation of add() 10,000,000 items:
For each add() call:
average storage read = 2.33 slots
average storage write = 2.33 slots
average hash call = 0.33 times (PoseidonT5)


lv 19	                   _                       _                       _                       _
lv 18	                   _                       _                       _                       _
lv 17	                   _                       _                       _                       _
lv 16	                   _                       _                       _                       _
lv 15	                   _                       _                       _                       _
lv 14	                   _                       _                       _                       _
lv 13	                   _                       _                       _                       _
lv 12	                   _                       _                       _                       _
lv 11	           0,4194303         4194304,8388607 ↵                     _                       _
lv 10	     8388608,9437183 ↵       5242880,6291455         6291456,7340031         7340032,8388607
lv 9	     9437184,9699327 ↵       8650752,8912895         8912896,9175039         9175040,9437183
lv 8	     9699328,9764863         9764864,9830399         9830400,9895935         9895936,9961471 ↵
lv 7	     9961472,9977855         9977856,9994239 ↵       9928704,9945087         9945088,9961471
lv 6	     9994240,9998335 ↵       9981952,9986047         9986048,9990143         9990144,9994239
lv 5	     9998336,9999359 ↵       9995264,9996287         9996288,9997311         9997312,9998335
lv 4	     9999360,9999615         9999616,9999871 ↵       9998848,9999103         9999104,9999359
lv 3	     9999872,9999935 ↵       9999680,9999743         9999744,9999807         9999808,9999871
lv 2	     9999936,9999951         9999952,9999967         9999968,9999983 ↵       9999920,9999935
lv 1	     9999984,9999987         9999988,9999991         9999992,9999995 ↵       9999980,9999983
lv 0	     9999996,9999996         9999997,9999997         9999998,9999998         9999999,9999999 ↵


length: 10000000
profiling: r: 23333300 w: 23333325 h: 3333325
level lengths: 4,3,3,1,2,1,1,2,4,1,1,2,0,...
getPositions(0):  [ 11, 0, 0, 4194304 ]

HashTower.mjs

"use strict";
//import { poseidon } from "circomlibjs"; // for off-line computing

const prof = {
    read: 0, write: 0, hash: 0,
    r: function() { this.read++ },
    w: function() { this.write++ },
    h: function() { this.hash++ },
    toString: function() { return `r: ${this.read} w: ${this.write} h: ${this.hash}` }
};

const W = 4;
const H = 20; // 4^0 + 4^1 + ... + 4^19 = 366503875925
const DEBUG_RANGE = true;

// simulating a Solidity storage struct
class HashTowerData {
    constructor() {
        this.length = 0;
        this.buf = Array.from({length: H}, () => Array(W).fill('_')); // fill _ for visual affects only
    }
    getLength()        { prof.r(); return this.length; }
    setLength(l)       { prof.w(); this.length = l; }
    getBuf(lv, idx)    { prof.r(); return this.buf[lv][idx]; }
    setBuf(lv, idx, v) { prof.w(); this.buf[lv][idx] = v; }
}

// simulating a Solidity library
class HashTower {
    hash(arr) {
        prof.h();
        return !DEBUG_RANGE ? poseidon(arr) : [arr[0][0], arr[W - 1][1]];
    }
    add(self, item) {
        const len = self.getLength();
        const lvLengths = this.getLevelLengths(len);

        var toAdd = !DEBUG_RANGE ? BigInt(item) : [item, item];

        for (let lv = 0; lv < H; lv++) {
            const origLvLen = lvLengths[lv];
            if (origLvLen < W) {
                self.setBuf(lv, origLvLen, toAdd);
                break;
            } else {
                const bufOfLv = Array.from({length: W}, (v, i) => self.getBuf(lv, i));
                const hash = this.hash(bufOfLv);
                self.setBuf(lv, 0, toAdd);
                toAdd = hash; // to be added in the upper level
            }
        }
        self.setLength(len + 1);
    }
    getLevelLengths(len) {
        var lengths = [];
        var zeroIfLessThan = 0; // W^0 + W^1 + W^2 ... (1 + 4 + 16 + ...)
        var pow = 1; // pow = W^lv
        for (let lv = 0; lv < H; lv++) {
            zeroIfLessThan += pow;
            const lvLen = (len < zeroIfLessThan) ? 0 : Math.floor((len - zeroIfLessThan) / pow) % W + 1;
            lengths.push(lvLen); // zero-terminated
            if (lvLen == 0) break;
            pow *= W; // shift
        }
        return lengths;
    }
    // direct access without triggering profiling
    show(len, buf) {
        console.clear();
        var lvLengths = this.getLevelLengths(len);
        for (let lv = H - 1; lv >= 0; lv--) {
            var msg = "lv " + lv + "\t";
            for (let i = 0; i < W; i++) {
                const s = "" + buf[lv][i];
                msg += s.length > 20
                    ? s.substring(0, 17) + "..."
                    : s.padStart(20, " ");
                msg += (i == lvLengths[lv] - 1) ? " ↵  " + "\x1b[90m" : "    "; // ↵
            }
            msg += "\x1b[0m";
            console.log(msg);
        }
        console.log("\n");
        console.log("length: " + len);
        console.log("profiling:", prof.toString());
        console.log("level lengths: " + lvLengths + ",...");
        console.log("getPositions(0): ", ht.getPositions(0, len));
        const t0 = new Date().getTime(); while (new Date().getTime() < t0 + 1000);
    }
    // only for proving
    getPositions(idx, len) {
        if (idx < 0 || idx >= len) return undefined;
        const lvLengths = this.getLevelLengths(len);
        var start = len;
        var pow = 1;
        for (let lv = 0; lv < H; lv++) {
            for (let lvIdx = lvLengths[lv] - 1; lvIdx >= 0; lvIdx--) {
                start -= pow;
                if (start <= idx) {
                    return [lv, lvIdx, start, pow];
                }
            }
            pow *= W;
        }
        return undefined;
    }
}


const htd = new HashTowerData();
const ht = new HashTower();
ht.show(htd.length, htd.buf);
for (let i = 0; i < 10000000; i++) {
    ht.add(htd, i);
    //ht.show(htd.length, htd.buf);
}
ht.show(htd.length, htd.buf);