3 ms·
I recently discovered a problem in this domain of modulo reduction. I'm looking for a way to create a smaller index for Ethereum accounts that are in the range
by timdaub 5y ago
I recently discovered a problem in this domain of modulo reduction. I'm looking for a way to create a smaller index for Ethereum accounts that are in the range of 0 to 2^160 [1]. It's mainly to reduce gas storage cost [3].
Most folks I asked about it, ended up concluding that I'll end up with this pidgeon hole effect where it'll become likely that an index is suggested multiple times [2].
It may not be super cryptographically-sophisticated: But what I want is a hash function that's (at least) somewhat aware of collisions without using too much storage. Bloomfilters were recommended - but it seems they need to much storage too. I need to be able to map Ethereum accounts to a smaller sized domain e.g. 0 to 2^32 to safe storage costs in smart contracts.
Since I asked on Stackexchange, the problem has become kind of stale and I stopped working on it. But it's fascinating and I should continue to dive deeper...
Interesting article! Thanks
- 1: https://crypto.stackexchange.com/questions/91742/can-there-be-an-injective-function-that-maps-a-large-set-of-integers-to-a-smalle https://crypto.stackexchange.com/questions/91742/can-there-b...
- 2: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle
- 3: https://github.com/rugpullindex/honeybatcher https://github.com/rugpullindex/honeybatcher
- FreakLegion 5y agoThere are smaller alternatives to Bloom filters, if size is the only issue. A few examples: - https://github.com/0xcb/Golomb-coded-map https://github.com/0xcb/Golomb-coded-map - https://github.com/efficient/cuckoofilter https://github.com/efficient/cuckoofilter - https://github.com/FastFilter/xor_singleheader/ https://github.com/FastFilter/xor_singleheader/
- timdaub 5y agoThanks, helpful links. I've looked into them and found them a great fit for my awesome-ethereum-rollups list [1]. - 1 https://github.com/rugpullindex/awesome-ethereum-rollups#membership-proof-data-structures https://github.com/rugpullindex/awesome-ethereum-rollups#mem...