since we don't need the hash to be cryptographically secure for this, we'd be better off using a high quality regular hash function like xxh3_64 from https://pypi.org/project/xxhash/, about 10x faster:

# built-in sha3_256, not keccak
$ python -m timeit --setup="from hashlib import sha3_256" "sha3_256(b'').digest()"
500000 loops, best of 5: 892 nsec per loop

# xxh64, requires `pip install xxhash`
$ python -m timeit --setup="from xxhash import xxh64_digest" "xxh64_digest(b'')"
2000000 loops, best of 5: 101 nsec per loop

# xxh3_64, requires `pip install xxhash`
$ python -m timeit --setup="from xxhash import xxh3_64_digest" "xxh3_64_digest(b'')"
5000000 loops, best of 5: 98.3 nsec per loop

thanks for suggestion!

wdyt? 7d08e7a

for consistency I think it would be better to avoid xxh3_128 and use xxh3_64 only. Plus that way we have an extra 64 bit reserved for some future use!

I was considering 128 bits for storages to be more conservative. (Storages are more frequently updated than code and balances.) With 64 bits, the hash collision probability exceeds 10^-12 when generating 6,000 hashes (which is large, but not unrealistic when running halmos in cloud several days.) With 128 bits, however, it would take 20 trillion hashes to reach the 10^-12 collision probability.

That said, 64 bits might still be good enough for our use case. But, in that case, I'm not sure what's the benefit of using xxhash vs the builtin hash(). The builtin hash() can take arbitrary objects as input, and also doesn't seem slower than xxhash:

$ python -m timeit --setup="from xxhash import xxh3_64_digest" "xxh3_64_digest(b'')"
5000000 loops, best of 5: 54.2 nsec per loop

$ python -m timeit "hash(b'')"
20000000 loops, best of 5: 12.6 nsec per loop

One concern with the builtin hash() is that it returns 32-bit hashes on 32-bit machines, but I guess 32-bit machines are rare these days, so it might not be a real concern? Another concern is that it's not deterministic across runs, which could be an issue if we want to support resume features. What do you think?

let me merge this as is, and we can discuss hash functions separately.