Constant-time Solidity dispatcher MVP

sodis.js

const { BN } = require('bn.js');
const { keccak256 } = require('ethereumjs-util');
const { toBN } = require('web3-utils');

const numberOfSelectors = 1000;
const tableSizeKoef = 1.5;
const maxBucketSize = 2;

function hash (selector, salt, m) {
    return new BN(selector, 'hex').xor(toBN(salt)).toNumber() % 65537 % m;
}

// function hash2 (selector, salt, m) {
//     const saltStr = toBN(salt).toString('hex', 64);
//     const hash = keccak256(Buffer.from(selector + saltStr, 'hex'));
//     return toBN(hash).modn(m);
// }

function checkForExactMatch (selectors, salt) {
    for (let i = 0; i < selectors.length; i++) {
        if (hash(selectors[i], salt, selectors.length) != i) {
            return false;
        }
    }
    return true;
}

function checkForNonCollision (selectors, m, salt) {
    const set = new Set();
    for (let i = 0; i < selectors.length; i++) {
        const h = hash(selectors[i], salt, m);
        if (set.has(h)) {
            return false;
        }
        set.add(h);
    }
    return true;
}

const checkForBuckets = (max) => (selectors, m, salt) => {
    const map = new Map();
    for (let i = 0; i < selectors.length; i++) {
        const h = hash(selectors[i], salt, m);
        if (map[h] > max) {
            return false;
        }
        map[h] = map[h] + 1 || 1;
    }
    return true;
}

function findSalt (selectors, m, iterations, func) {
    for (let salt = 1; salt < iterations; salt++) {
        if (func(selectors, m, salt)) {
            return salt;
        }
    }
}

// const selectors = [
//     'or(uint256,bytes)',
//     'and(uint256,bytes)',
//     'eq(uint256,bytes)',
//     'lt(uint256,bytes)',
//     'gt(uint256,bytes)',
// ].map(Buffer.from).map(keccak256).map(s => s.toString('hex').substring(0, 8));

// const selectors = [
//     '12345678',
//     '11223344',
//     'aabbccdd',
//     'abcd0fff',
//     'eeeeeeee',
// ];

const selectors = Array.from(
    { length: numberOfSelectors },
    () => Math.floor(Math.random() * 2**31).toString(16).padStart(8, '0')
);

if ((new Set(selectors)).size !== selectors.length) {
    throw new Error('Duplicates found in selectors');
}

console.log('Selectors =', selectors);

const salt = findSalt(
    selectors,
    Math.round(selectors.length * tableSizeKoef),
    10000000,
    checkForBuckets(maxBucketSize)
);
console.log('Found salt =', salt);

if (salt) {
    console.log('Indexes =', selectors.map(s => hash(s, salt, selectors.length)));
}