SelectorTable

selector-table.js

const { toBN } = require('web3-utils');

function findBucket(iterations) {
    const selectors = [
        0x12345678,
        0x11223344,
        0xaabbccdd,
        0xabcdefff,
        0xabbcccdd,
        0xbbbbbbbb,
        0xaaaaaaaa,
        0xf2345678,
        0xf1223344,
        0xfabbccdd,
        0x1234567f,
        0x1122334f,
        0xaabbccdf,
        0xabcdefff,
        0xabbcccdf,
        0xbbbbbbbf,
        0xaaaaaaaf,
        0xf234567f,
        0xf122334f,
        0xfabbccdf,
        0xff345678,
        0xff223344,
        0xffbbccdd,
        0xffcdefff,
        0xffbcccdd,
        0xffbbbbbb,
        0xffaaaaaa,
        0xff345678,
        0xff223344,
        0xffbbccdd,
        0xff34567f,
        0xff22334f,
        0xffbbccdf,
        0xffcdefff,
        0xffbcccdf,
        0xffbbbbbf,
        0xffaaaaaf,
        0xff34567f,
        0xff22334f,
        0xffbbccdf
    ];
    return find(selectors, 5, 0, iterations);
}

function findExact(iterations) {
    const selectors = [
        0x12345678,
        0x11223344,
        0xaabbccdd,
        0xabcdefff,
        0xabbcccdd,
        0xbbbbbbbb,
        0xaaaaaaaa,
        0xf2345678,
        0xf1223344,
        0xfabbccdd
    ];
    return find(selectors, selectors.length, 0, iterations);
}

//
// N = number of selectors
// B = number of buckets
//
// All possible combinations: B^N
// Valid combinations: N! / ((N/B)!)^B
// Combinations per valid: B^N * ((N/B)!)^B / N!
// Combinations per valid when B=N: N^N / N!
//
// Splitting 6 selectors into 6 buckets: 64 combinations
// Splitting 7 selectors into 7 buckets: 163 combinations
// Splitting 8 selectors into 8 buckets: 416 combinations
// Splitting 9 selectors into 9 buckets: 1,067 combinations
// Splitting 10 selectors into 10 buckets: 2,755 combinations
// Splitting 11 selectors into 11 buckets: 7,147 combinations
// Splitting 12 selectors into 12 buckets: 18,000 combinations
// Splitting 13 selectors into 13 buckets: 48,000 combinations
// Splitting 13 selectors into 13 buckets: 127,000 combinations
// Splitting 15 selectors into 15 buckets: 334,000 combinations
//
// Splitting 40 selectors into 5 buckets of equal size: 1,187 combinations
// Splitting 40 selectors into 8 buckets of equal size: 70,000 combinations
// Splitting 100 selectors into 5 buckets of equal size: 7,204 combinations
// Splitting 100 selectors into 4 buckets of equal size: 996 combinations
// Splitting 100 selectors into 10 buckets of equal size: 42,000,000 combinations
//
function find(selectors, buckets, tolerance, iterations) {
    for (let magic = 1; magic < iterations; magic++) {
        if (magic % 1000 == 0) {
            console.log(`Testing magic ${magic}`);
        }

        const diff = calc(selectors, magic, buckets);
        if (diff <= tolerance) {
            console.log(`Result found after ${magic} combinations (diff = ${diff}):`);
            for (let i = 0; i < selectors.length; i++) {
                const magicStr = toBN(magic).toString('hex', 8);
                const result = toBN(web3.utils.keccak256(selectors[i] + magicStr)).modn(buckets).toString();
                console.log(`keccak256(0x${magicStr}${toBN(selectors[i]).toString('hex')}) = ${result}`);
            }
            return magic;
        }
    }
    throw "Not found";
}

function calc(selectors, magic, buckets) {
    let dict = {};
    let max = 0;
    for (let i = 0; i < selectors.length; i++) {
        const magicStr = toBN(magic).toString('hex', 8);
        const value = toBN(web3.utils.keccak256(selectors[i] + magicStr)).modn(buckets).toString();
        dict[value] = (dict[value] || 0) + 1;
        max = Math.max(max, dict[value]);
    }
    return max - Math.min(...Object.values(dict));
}

z.findBucket()

Testing magic 1000
Testing magic 2000
Testing magic 3000
Result found after 3442 combinations (diff = 0):
keccak256(0x00000d7212345678) = 1
keccak256(0x00000d7211223344) = 0
keccak256(0x00000d72aabbccdd) = 0
keccak256(0x00000d72abcdefff) = 2
keccak256(0x00000d72abbcccdd) = 3
keccak256(0x00000d72bbbbbbbb) = 3
keccak256(0x00000d72aaaaaaaa) = 0
keccak256(0x00000d72f2345678) = 2
keccak256(0x00000d72f1223344) = 1
keccak256(0x00000d72fabbccdd) = 3
keccak256(0x00000d721234567f) = 3
keccak256(0x00000d721122334f) = 2
keccak256(0x00000d72aabbccdf) = 4
keccak256(0x00000d72abcdefff) = 2
keccak256(0x00000d72abbcccdf) = 1
keccak256(0x00000d72bbbbbbbf) = 0
keccak256(0x00000d72aaaaaaaf) = 1
keccak256(0x00000d72f234567f) = 2
keccak256(0x00000d72f122334f) = 0
keccak256(0x00000d72fabbccdf) = 4
keccak256(0x00000d72ff345678) = 2
keccak256(0x00000d72ff223344) = 1
keccak256(0x00000d72ffbbccdd) = 0
keccak256(0x00000d72ffcdefff) = 4
keccak256(0x00000d72ffbcccdd) = 2
keccak256(0x00000d72ffbbbbbb) = 0
keccak256(0x00000d72ffaaaaaa) = 4
keccak256(0x00000d72ff345678) = 2
keccak256(0x00000d72ff223344) = 1
keccak256(0x00000d72ffbbccdd) = 0
keccak256(0x00000d72ff34567f) = 3
keccak256(0x00000d72ff22334f) = 1
keccak256(0x00000d72ffbbccdf) = 4
keccak256(0x00000d72ffcdefff) = 4
keccak256(0x00000d72ffbcccdf) = 3
keccak256(0x00000d72ffbbbbbf) = 4
keccak256(0x00000d72ffaaaaaf) = 3
keccak256(0x00000d72ff34567f) = 3
keccak256(0x00000d72ff22334f) = 1
keccak256(0x00000d72ffbbccdf) = 4

z.findExact()

Result found after 31 combinations (diff = 0):
keccak256(0x0000001f12345678) = 5
keccak256(0x0000001f11223344) = 4
keccak256(0x0000001faabbccdd) = 9
keccak256(0x0000001fabcdefff) = 1
keccak256(0x0000001fabbcccdd) = 4
keccak256(0x0000001fbbbbbbbb) = 3
keccak256(0x0000001faaaaaaaa) = 3
keccak256(0x0000001ff2345678) = 9
keccak256(0x0000001ff1223344) = 5
keccak256(0x0000001ffabbccdd) = 1