Constant-complexity dispatcher idea

[k06a]

Today I spent some time on prototyping and was managed to achieve O(1)-complexity dispatcher. Check out few my messages here: vyperlang/vyper#2386 (comment)

And find code prototype here: https://gist.github.com/k06a/737fd1f389bb6f2e66f0ef76ea73729b

Abstract

I believe dispatcher implementation initially was O(N), but now it may be tree-like O(log(n)). I assume having an O(1) dispatcher when some contract has 5+ methods is a cool achievement.

Motivation

Contracts with tens of methods could have really slow dispatcher for most of the methods. Computing keccak256 and 2 jumps is a relatively cheap way to dispatch.

Specification

We just need to brute-force magic values at compile time to achieve all selectors being mapped into 0..N-1 values. The complexity of such brute force should be N^N/N!. If the number of selectors is really huge we could, for example, find the first function for splitting into a few groups by 8, and then use different magic for each group. Having 1 magic number you could split 32 selectors into 4 groups by 8 and then find magic for each group. Finding magic for a group of 8 would take 8^8/8! = 416 iterations in average. Seems possible to do this in compile-time.

Pseudocode:

const index = keccak256(abi.encodePacked(selector + (magic << 32))) % selectors.length;
JUMP(READ(table_start + index));

Backwards Compatibility

The resulting dispatcher code should be fully compatible for external calls with any other versions of the dispatcher.

[k06a]

I will write detailed specification, hope you like the idea and have desire to implement it. I assume dispatching can cost 100-150 gas for up to 512 methods and bytecode size could be smaller than now.

[chriseth]

I actually spent some time months ago to do something similar.
I would say: Why not?
One problem is that we still need to do the final comparison in the end, but we already do that even in the binary search case.
Another problem might be if we want to get rid of dynamic jumps at some point. Oh and this won't be compatible with code generation via Yul unless...
we implement this for the yul to evm code generation for switch statements in general :)

[chriseth]

Ah, maybe I misread your algorithm: Why do you need keccak? Shouldn't the following also work:

let n := mod(byte(0, mul(X, calldataload(0))), N)
codecopy(0, add(start, mul(n, 4)))
let d := shr(240, mload(0))
jump(d)

Here, N is the number of selectors and X is a number that needs to be brute-forced. instead of multiplying by X we could also use some other strategy or more complicated formulas.

[k06a]

If 2 selectors are multiples of N, mulmod with any salt X will lead to a collision.

[chriseth]

If 2 selectors are multiples of N, mulmod with any salt X will lead to a collision.

Ok, then it looks like we need to throw some xor and add operations in to the mix :)

[k06a]

XOR could help in some cases. In general we don’t have any proof than solution will exist for some arbitrary form of hash function. I consider keccak as safe and reliable hash to use. But we should consider some other functions, maybe we can find something better.

Case in which XOR is not working:

Imagine we have 16 selectors and 2 of them are 0xZZZZZZZ5 and 0xYYYYYYY5. Modulus of 16 is 5 for both. XORing both selectors with any salt will keep division remainder equal for them.

[cameel]

What about fallback? This looks like it would map any other function to one of those N. I think this would need an extra check before the jump to ensure that the input selector actually matches the destination selector. If not, we should jump to fallback instead.

[k06a]

What we are trying to build is this: https://en.wikipedia.org/wiki/Perfect_hash_function

[frangio]

O(1) would be interesting, but what would be the magnitude of the constant cost? Would it be less than the current costs? It would be nice to see some numbers.

I played around a bit with @k06a's script yesterday. For ~10 selectors it works well but any more than that the brute forcing can take a long time. I think most contracts have more than 10 selectors, so splitting into buckets and doing multiple dispatches would likely be necessary. Not sure if it needs to be done with multiple keccak like @k06a suggested, perhaps the cheapest approach is combination of binary search until reaching small enough buckets that we can generate and use an O(1) dispatch table.

[k06a]

@frangio, yes and formula is n^n/n! of bad salts per good salt. I think we can have this parameter adjustable, and use 6-7 by default. I will provide implementation for buckets soon, it’s almost the same - just need to count min and max selectors per bucket and check (max - min) <= 1

[k06a]

@frangio I think we can one step solution for 50 gas, 2-step for 100, etc. Current dispatcher gas is around 150 for 10-method contract and 350 for 80-method contract, AFAIR.

[k06a]

Updated gist with code to support buckets: https://gist.github.com/k06a/737fd1f389bb6f2e66f0ef76ea73729b
Added computations for some cases:

//
// 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
//

[chriseth]

What about fallback? This looks like it would map any other function to one of those N. I think this would need an extra check before the jump to ensure that the input selector actually matches the destination selector. If not, we should jump to fallback instead.

Whatever we do, we need at least one full equality comparison per function, even if the contract does not have a fallback function, because there are always "false positives".

[chriseth]

XOR could help in some cases. In general we don’t have any proof than solution will exist for some arbitrary form of hash function. I consider keccak as safe and reliable hash to use. But we should consider some other functions, maybe we can find something better.

Sure, it's just that keccak is relatively expensive and if there is a cheaper option, I would use the cheaper option.

[k06a]

@chriseth I agree keccak256 is expensive especially on the host side, is Solidity it is relatively cheap. I will try to produce another function. But we can start with keccak256.

[k06a]

The probability of several selectors having the same remainders by multiple primary numbers is much lower. Moreover, we can select these primary numbers for a specific selector set exclusively. Maybe the following formula will work:

((selector % p1) * (selector % p2) * (selector % p3) * SALT) % N

[frangio]

At that point I don't know if it will be cheaper than keccak.

[k06a]

Just played with this idea of multiple remainders - it has so many collisions, not possible to find such SALT in practice for 5-10 selectors. I afraid multiplication of remainders produces more possibilities to have the same remainder after MOD N.

[ekpyron]

We could try dividing by the largest power of N that's a factor in any selector. I'd expect ((selector / powerOfN) * X) % N to usually work out for some random X (maybe checking random primes would even be enough). The division can of course collapse selectors in some cases, but we don't need to use the same schema for all cases, but can just fall back to something else if it doesn't work...

[k06a]

Found something interesting: http://stevehanov.ca/blog/?id=119

[frangio]

@k06a Great reference.

However, reading it made me realize that we're completely overthinking this. The function selector is already a random number. If we take selector % N we've got a pretty good hash function that splits in pretty small buckets. The cheapest dispatch function might be %N followed by linear if-else matches. It's not constant time, but it sounds like the difference would be up to a small constant with high probability.

[k06a]

@frangio we could bruteforce some simple formula to ensure distribution is good enough, for example, each bucket have max 2 selectors. I think this can be achieved pretty fast even for huge number of selectors.

[k06a]

@frangio splitting selectors onto N bucket by just using remainder works as following for some 78-selectors contract:

{
  '1': [ '0x28ffe6c8', '0xecc06c76' ],
  '4': [ '0x44467b82' ],
  '5': [ '0xbfe91734', '0x29fd9747' ],
  '6': [ '0x754e29c7' ],
  '7': [ '0xd1058e59', '0xf616a9c6', '0xd505accf' ],
  '8': [ '0x2733ff81' ],
  '9': [ '0x9cf9f4b1', '0xde00c0b4', '0x0b3b5df4', '0x70c86628' ],
  '13': [ '0xb6b55f25' ],
  '14': [ '0x70a08231' ],
  '16': [ '0xf00363fe', '0x18160ddd' ],
  '17': [ '0xc5ebeaec' ],
  '21': [ '0x1988513b' ],
  '22': [ '0x363eb6da', '0x4b75f54f', '0xe91f0ac6' ],
  '23': [ '0x9b648279', '0xeeb74c9a' ],
  '24': [ '0xc392f766' ],
  '25': [ '0x935a8b84', '0xf40fe2d2' ],
  '26': [ '0xfda0241d', '0xb1bd3517' ],
  '28': [ '0xea91c053', '0x6d10dd20' ],
  '30': [ '0x095ea7b3', '0x3fc8cef3' ],
  '33': [ '0x5fc11161', '0xd6d75f51' ],
  '34': [ '0xef1cd1cb' ],
  '35': [ '0xdd62ed3e' ],
  '37': [ '0x2f4f21e2', '0x3c968d3b' ],
  '38': [ '0x06fdde03' ],
  '39': [ '0xfe1195ec' ],
  '40': [ '0x3644e515', '0xfd52a774' ],
  '42': [ '0x3ba040c2' ],
  '44': [ '0xee77ffcf', '0xba3ff097' ],
  '47': [ '0x38c22694', '0x286e154d' ],
  '48': [ '0x6a6da61e' ],
  '49': [ '0xbe87321d', '0xa035b1fe' ],
  '51': [ '0x1e83409a' ],
  '52': [ '0x62273a93' ],
  '55': [ '0x2e1a7d4d' ],
  '56': [ '0x7ecebe00' ],
  '57': [ '0xfc0c546a' ],
  '58': [ '0x95d89b41' ],
  '59': [ '0x6496649c' ],
  '61': [ '0x35ec1a75', '0xd32b91dd', '0x371fd8e6', '0x9e4dec0c' ],
  '62': [ '0xa9059cbb' ],
  '65': [ '0x198f67ef', '0x23b872dd', '0x4774c812' ],
  '66': [ '0x32d323a5' ],
  '67': [ '0x39509351', '0xc8f56839' ],
  '69': [ '0x313ce567', '0xa457c2d7', '0x205c2878' ],
  '70': [ '0x23a27622' ],
  '71': [ '0xa9355827' ],
  '75': [ '0x1a686502' ],
  '76': [ '0x555e7f4a' ],
  '78': [ '0x4484bf97', '0xe0227cc5' ]
}

I see it have only 49 non-empty slots

I also tried to spend 1000 iterations to find SALT XORing which leads to a good distribution among N/2 slots:

  '0': [ '0x3644e515', '0x6496649c', '0x28ffe6c8' ],
  '1': [ '0x095ea7b3', '0x2f4f21e2' ],
  '2': [ '0x95d89b41' ],
  '3': [ '0xfe1195ec', '0x18160ddd' ],
  '5': [ '0xe0227cc5', '0x9e4dec0c', '0x3c968d3b' ],
  '6': [ '0x4b75f54f', '0x1988513b' ],
  '7': [ '0xfda0241d', '0x44467b82', '0x754e29c7' ],
  '8': [ '0xdd62ed3e', '0x5fc11161', '0xa035b1fe' ],
  '9': [ '0x3ba040c2', '0xa9355827' ],
  '10': [ '0x06fdde03', '0x4774c812' ],
  '11': [ '0xd505accf', '0xc8f56839', '0xf40fe2d2' ],
  '12': [ '0x23b872dd' ],
  '13': [ '0x555e7f4a', '0x2e1a7d4d' ],
  '14': [ '0x35ec1a75', '0xd6d75f51', '0xfd52a774' ],
  '16': [ '0xe91f0ac6', '0x1a686502' ],
  '17': [ '0xea91c053' ],
  '18': [ '0xb6b55f25', '0xd32b91dd' ],
  '19': [ '0x935a8b84', '0xeeb74c9a' ],
  '20': [ '0xc5ebeaec', '0xee77ffcf', '0x2733ff81' ],
  '21': [ '0x70c86628', '0xfc0c546a', '0x3fc8cef3' ],
  '22': [ '0x1e83409a', '0xb1bd3517', '0x363eb6da' ],
  '24': [ '0x70a08231', '0xde00c0b4', '0xa9059cbb' ],
  '26': [ '0xef1cd1cb' ],
  '27': [ '0x313ce567', '0x0b3b5df4' ],
  '28': [ '0xbe87321d' ],
  '29': [ '0xf616a9c6', '0xf00363fe', '0x38c22694' ],
  '30': [ '0x32d323a5', '0x9cf9f4b1', '0x205c2878' ],
  '31': [ '0xd1058e59', '0xa457c2d7', '0x39509351' ],
  '32': [ '0xba3ff097', '0xecc06c76' ],
  '33': [ '0xbfe91734', '0x29fd9747', '0x23a27622' ],
  '34': [ '0x371fd8e6' ],
  '35': [ '0xc392f766', '0x6a6da61e', '0x6d10dd20' ],
  '37': [ '0x4484bf97', '0x9b648279', '0x62273a93' ],
  '38': [ '0x198f67ef', '0x7ecebe00', '0x286e154d' ]

Script used:

let min = selectors.length;
for (let salt = 1; salt < 10000; salt++) {
    let dict = {};
    let max = 0;
    for (let s of selectors) {
        let key = ((s ^ salt) >>> 0) % Math.trunc(selectors.length / 2);
        dict[key] = (dict[key] || []).concat([s]);
        max = Math.max(max, dict[key].length);
    }
    min = Math.min(min, max);

    if (max <= 3) {
        console.log('Found salt =', salt, ' max =', max, ' dict =', dict);
        break;
    }
}
console.log('min =', min);

[frangio]

That's great! I wasn't considering that empty buckets are a problem. Using xor for salting makes a lot of sense.

[k06a]

Got advice from @snjax that (selector XOR salt) % n could match for any salt if n is some power of 2 like 2**k.

It makes much more sense to use:

((selector XOR salt) % prime) % n

And I would not suggest to use MUL instead of XOR, because it could keep remainder the same in some cases.

[chriseth]

Has there been any progress on this in the last days? :)

[snjax]

I suppose, number of all states for keccak256(...)%m and n picks is m^n, and number of states without collisions is m!/(m-n)!, so P:=m!/((m-n)!m^n), for m = 115 and n=100 P=1.9e-30

[k06a]

@snjax I agree that adding m^(m-n) was wrong and this leads to m^n / (m! / (m-n)!) and the result is much worse than I expected: n=100, m=500 requires brute-forcing 40k salts in keccak256(selector + salt) % m

[k06a]

I suspect the best solution we have right now for N selectors is the following:

1. Determine M > N for the result table dimension, for example M = N*3/2
2. Bruteforce SALT for keccak256(concat(selector, SALT)) % M until all buckets have <=3 elements
3. Use the result as an index in jump table to get into code checking up to 3 selectors in a row

I am trying to compute a number of cases that are suitable for the conditions to compute the probability and complexity of the bruteforcing task.

[aathan]

This conversation reminds me of the dispatcher in Objective-C, which has to solve some similar issues. In Objective-C methods are invoked dynamically by runtime lookup using "selectors" which are themselves essentially based on the function signature. Obviously method dispatch in a raw CPU context vs dispatch in the EVM is very different. However, the dispatcher has been worked on since the 90s and may contain relevant prior art.

Just in case it's of interest, here's where you can find the source code for the message dispatch function:

https://github.com/apple-oss-distributions/objc4/tree/main/runtime/Messengers.subproj

Extracts from a related conversation (I'd credit the contributors but it's a private email list):

• https://dl.acm.org/doi/10.1145/217838.217851 "Minimizing row displacement dispatch tables"
• https://mjtsai.com/blog/2020/07/06/optimizing-the-objective-c-runtime-in-big-sur/
• https://twitter.com/pedantcoder/status/1277795696855277568
• "since [Solidity] selectors are hash substrings ... [sort] the selectors and then in dispatch [estimate] a starting index of (sel*count)>>32, and [search] up or down linearly from there" (i.e., similar to the opening idea of this thread, I think).

EDIT: Included some items from conversation on a private email list I pinged.

[k06a]

Checked the following numbers:

• Number of selectors: up to 1000
• Table size: 1.5 * number of selectors
• Max bucket size: 2

Hash function:

(selector XOR salt) MOD 65537 MOD m

After brute-forcing salts for 10k different sets of 1000 random generated selectors I have the following stats:

• 99th percentile of sets find salt after 11726 iterations
• 95th percentile of sets find salt after 7129 iterations
• 90th percentile of sets find salt after 5343 iterations
• 50th percentile of sets find salt after 1552 iterations

I believe we could use something like this:

let ptr := mod(mod(xor(selector, SALT), PRIME), TABLE_SIZE)
codecopy(0, add(TABLE_OFFSET_IN_BYTECODE, mul(ptr, 2)), 2)
jump(shr(240, mload(0)))

and on destinations we can have 3 variations:

1. Check 0 combinations

   mstore(0, UNKNOWN_SELECTOR_ERROR)
   revert(0, 4)

2. Check 1 combination

   if eq(selector, SELECTOR_X) {
       jmp(SELECTOR_X_OFFSET_IN_BYTECODE)
   }
   mstore(0, UNKNOWN_SELECTOR_ERROR)
   revert(0, 4)

3. Check 2 combination

   if eq(selector, SELECTOR_Y) {
       jmp(SELECTOR_Y_OFFSET_IN_BYTECODE)
   }
   if eq(selector, SELECTOR_Z) {
       jmp(SELECTOR_Z_OFFSET_IN_BYTECODE)
   }
   mstore(0, UNKNOWN_SELECTOR_ERROR)
   revert(0, 4)

Or we could use the first table to point on 1-2 selectors in the second table. And use 1 code to check these selectors.

https://gist.github.com/k06a/5b6c06faa235e656cc391cb444ea71e8

[k06a]

Pseudocode of single dispatcher with 2 tables

• (2-bytes) table with top 2 bits indication on bucket size and 14-bit offset in the second table
• (4-bytes selector, 4 bytes dest offset) table of all selectors and function pointers

let ptr := mod(mod(xor(selector, SALT), PRIME), TABLE_SIZE)
codecopy(0, add(TABLE_OFFSET_IN_BYTECODE, mul(ptr, 2)), 2)
let idx := shr(240, mload(0))
if iszero(idx) {
    mstore(0, UNKNOWN_SELECTOR_ERROR)
    revert(0, 4)
}

codecopy(0, add(TABLE_2_OFFSET_IN_BYTECODE, mul(and(0x3FFF, idx), 8)), 16)

if and(0x8000, idx) {
    let s := shr(224, mload(0))
    if eq(selector, s) {
        jmp(shr(224, shl(32, mload(0))))
    }
}

mstore(0, shl(64, mload(0))

// Same code as previous, except mload(0) was shifted to the next 8-byte record
if and(0x8000, idx) {
    let s := shr(224, mload(0))
    if eq(selector, s) {
        jmp(shr(224, shl(32, mload(0))))
    }
}

[k06a]

Maybe you could introduce the dispatcher() function in Solidity in the addition to receive() and fallback() methods family? Which will be called before and instead of external methods, where Solidity engineers could put their own heavily optimized version of the dispatcher and perform internal calls?

[axic]

Maybe you could introduce the dispatcher() function in Solidity in the addition to receive() and fallback() methods family?
Which will be called before and instead of external methods, where Solidity engineers could put their own heavily optimized version of the dispatcher and perform internal calls?

This should be a separate issue for discussion, and I think there are a bunch of overlapping once already.

One (small) downside I see is that in that case a contract could not have any function marked external or public, as that would indicate those are reachable from the outside, and a result make visual inspection of contracts hard.

[aathan]

This discussion IMHO motivates a set of instructions that expect inputs assumed to come from a certain value distribution (hash based keccak prefix for now) plus well-formed data structures, and emit results ... in this case a computationally efficient lookup. I've been working on non EVM projects for a while now and don't recall, but I don't think the EVM has a "BIOS" and if not, maybe it should have. I.e., "long jumps" into functions that are actually implemented "outside" the EVM in a CPU and gas efficient manner as part of the EVM itself.

Clearly the keccak computation instructions are examples "in that direction"; but there's probably a family of functions that shouldn't require new instruction-set but can be implemented efficiently outside the EVM in a physical CPU efficient manner based on a calling ABI. I.e., an stdlib.

It doesn't make much sense to me that, structurally speaking, either miners or EVM users would want expensive functions like this to run in the most inefficient context possible. I.e. inside EVM. I imagine keccak is not run there for precisely the same reasons.

[axic]

@aathan "precompiled contracts" are effectively accomplishing what you are saying. They were opcodes initially, but moved out to reduce the surface area of the EVM, and keccak256 remained as an opcode because it is "supposed to be used more widely". There is a struggle around these, and I personally am against making the EVM more complicated and more CISC-like, as opposed to introducing useful primitives.

[k06a]

Having constant-time dispatcher as a precompile is a nice idea, but I afraid it is almost impossible to get it into consensus layer - this could took months or event years of discussions.

[k06a]

But using keccak256(abi.encodePackeg(selector, salt)) is much more reliable and predictable

[k06a]

It seems current dispatcher have O(log) execution complexity, but O(n) code size. I think it's possible to have table of function pointers in the code and have O(1) code size for this dispatcher. I discovered that 27 methods dispatcher size is 4Kb, which is pretty huge. WDYT @chriseth @cameel?

[k06a]

BTW I developed salt miner tool in rust: https://github.com/1inch/solidity-dispatcher-miner

Brute-forces almost 0.5 MSalts/s on a single core on my 8-core Mac Book M1 Max - works nice for up to 25-30 selectors. Estimate execution time as following: N^N/N! / 500000 / num_of_cores

[github-actions]

This issue has been marked as stale due to inactivity for the last 90 days.
It will be automatically closed in 7 days.

[github-actions]

Hi everyone! This issue has been automatically closed due to inactivity.
If you think this issue is still relevant in the latest Solidity version and you have something to contribute, feel free to reopen.
However, unless the issue is a concrete proposal that can be implemented, we recommend starting a language discussion on the forum instead.

[k06a]

Please reopen

[ZumZoom]

FYI vyperlang/vyper#3496