Get rid of SHA3 to calculate allowance slots

[Jorropo]

You can use an (spender << (16 * 8)) | (owner & 127) form instead.

In english, you truncate each address to 16 bytes and use the spender in the higher part of the word and the owner in the lower one.

I know that looks unsafe, this is basically dropping security from 160 bits to 128 bits.

However consider the fact that many wallets use BIP-39 (2048 big wordlist) with 12 word long passphrase that log2(2048**12) = 132 bits of security. We are in fact loosing 4 bits of security, which is only 16 times less secure.

EDIT: I'm not implementating that myself because editing JUMPI destinations by hand sounds like a hell.

[outdoteth]

Wow, nice.

This would save quit a bit I think - maybe 100 gas? There would be no need to store the address in memory either.

Instead of an | and an & wdyt about saving the | like this:

(spender << (20 * 8)) & owner

Does that still hold the same properties?

[Jorropo]

Correction and remarks

Why an OR is important

It must really be an OR, your AND just zeros out everything always: Think about it what you propose is:

OWNER_ADDRESS ZERO_BYTES
ZERO_BYTES    SPENDER_ADDRESS
AND
ZERO_BYTES    ZERO_BYTES

And so since they are miss-alligned they always have 0 matchings and your output is zeros everywhere always.

What it should be:

OWNER_ADDRESS ZERO_BYTES
ZERO_BYTES    SPENDER_ADDRESS
OR
OWNER_ADDRESS SPENDER_ADDRESS

Orders of spender and owner need to be swapped

In my first case it would have been possible to approve the zero address, that would clash with the balance slots (if you bruteforce an address with the first 4 bytes being zeros, approval of 0 and balance would map to the same slot and you would have been able to give you infinity many tokens).

Your idea:

(owner << (20 * 8)) | spender

(I have took the opportunity to swap the spender and owner case as well switch the & to an | for reasons explained earlier)

That change the thing, instead of having 128 bits on both sides, you know have 160 bits for the spender and only log2(2**(8*(32-20))) = 96 bits of security for the owner. That is very little (remember that bits are an logarithmic scale, so going up or down is multiplicative not additive in difficulty)

Personally I wouldn't take the risk of 96 bits security.

My final proposal:

The corrected expression is (owner << (16 * 8) | (spender & ((1 << 128) - 1)).

[Jorropo]

In solidity you would write that like this in case that helps implementing it:

uint256 slot = (uint256(owner) << (8 * 16)) | uint256(uint128(spender));

[outdoteth]

We know in the CALLDATA it's organised like this:

[function sig, owner, spender, amount] [4 bytes, 32 bytes, 32 bytes, 32 bytes]

We could load:

PUSH1 (0x04 + 0x10) 4 + 16 bytes CALLDATALOAD SLOAD

this takes everything from owner[4:] concat spender[:16]

what do you think of this? that saves the bitshifting which would need an additional couple of PUSH's It's not quite the same but i think it has the same properties? you are still taking 16 bytes from owner and 16 bytes from spender address.

[Jorropo]

what do you think of this? that saves the bitshifting which would need an additional couple of PUSH's

That would have worked if the abi was PACKED because you would fetch from the lower bytes of owner to the higher of spender (truly genius actually).

However the ABI is word (32 bytes) alligned as you know. So you in fact are replacing 12 bytes of spender for zeros.

That makes spender 4 bytes long, and if you browse 4byte.directory recreationally you would know how trivial thoses are to bruteforce.

[outdoteth]

Ah yeh of course

[outdoteth]

Ok. cool. I think it would look smth like this

// get the last 16 bytes of owner with 16 padded zeros PUSH1 (0x04) 4 bytes - 3 gas CALLDATALOAD - 3 gas PUSH1 (8 * 16) - 3 gas SHR - 3 gas

// get the last 16 bytes of spender PUSH1 (0x04 + 0x20) 4 + 32 bytes - 3 gas CALLDATALOAD - 3 gas PUSH1 ((1 << 128) - 1) - 3 gas AND - 3 gas

// combine OR - 3 gas

27 gas in total. That def beats the SHA3 version. Which is around ~50 gas I think.

[outdoteth]

This is really fkn neat. Thanks. 🔥

[Jorropo]

SGTM

[Jorropo]

Btw i have realised I forgot to include how you cant steal tokens from 0x0.

Often people send tokens to the zero address or 0xdEaD to burn them.

And if you brute force an address starting with 0x00000000 (4 bytes easy) your balance clashes with approval[0x0][you] so your balance is used as approval. You can use that to steal tokens from all 4bytes long address.

However in doing so your "approval" (in reality balance) gets decremented by how many tokens you take making the address net neutral (balance + stollen - stollen).

I guess that acts as free burn mechanism.

(Note 4bytes address cant be owned as it require brute forcing 128bits)

I've realised that put constrains in the order of sloads and stores in tranferFrom (you need to do load mutate store, load mutate store. Which is likely the best thing anyway.

That also require totalSupply < maxValue to never have a balance that would skip the subbing.

[yaronvel]

I would strongly recommend to reconsider. You think you have 128 bits security, where in fact you have 64 bits security. It would take only 2^64 attempts to generate a smart contract and an EOA who share the same first (or last) 16 bytes (sqrt(2^128)).

User will give an allowance to the "legit" smart contract, and the malicious EOA would rug pull him.

2^64 is still not negligible, but sounds like something a dedicated hardware can do (especially with CREATE2 where only sha3 calculation is needed).

[Jorropo]

You think you have 128 bits security, where in fact you have 64 bits security.

I know that applies to most hash results, but does that applies to ECC pub keys too ?

dedicated hardware can do (especially with CREATE2 where only sha3 calculation is needed).

I did overlooked that part (non ECC based addresses). 🤔

[yaronvel]

Idk if pub keys are uniformly distributed, would guess yes. But anw, with create2 it is a matter of finding two smart contracts with 16 bytes collision in their address. As it derrived from a sha3 calculation (of bunch of stuff, but also a 32 bytes that are free to play with), then the birthday attack is certainly applicable.

Btw, if the hash function is not uniformly distributed, then it is still applicable imo, only requires to find an applicable sub domain.