3 ms·

I am working on a new hash that uses more memory (aiming around 4KiB that's shared in a process), but is a whole lot faster. The finalizer for that hash is a un

by orlp 3y ago

I am working on a new hash that uses more memory (aiming around 4KiB that's shared in a process), but is a whole lot faster. The finalizer for that hash is a universal hash which I believe is 2^(2-k) almost-delta universal mod 2^k for any k <= 64. So the bottom bits are always high quality. PolymurHash has no such guarantee, the claims are only over the full hash. That said, I don't expect problems in practice due to the Murmur style bit mixing at the end.

nullc 3y ago
> I am working on a new hash that uses more memory (aiming around 4KiB that's shared in a process), but is a whole lot faster. Though it's hard to imagine anything with 4kib of state being very fast! is it just a precomputed power table or something where the whole thing isn't even accessed for short inputs? > The finalizer for that hash is a universal hash which I believe is 2^(2-k) almost-delta universal mod 2^k for any k <= 64. So the bottom bits are always high quality. That's interesting! > PolymurHash has no such guarantee, the claims are only over the full hash. That said, I don't expect problems in practice due to the Murmur style bit mixing at the end. That mix at the end is just an addition with a secret constant, right? I'd expect then the least significant bits to not be improved much by it.
- orlp 3y ago
  > Though it's hard to imagine anything with 4kib of state being very fast! is it just a precomputed power table or something where the whole thing isn't even accessed for short inputs? Correct, it's a pregenerated table of random bits that, in essence, gets multiplied with the input. If the input is small, only a small portion gets accessed. > That mix at the end is just an addition with a secret constant, right? I'd expect then the least significant bits to not be improved much by it. No, the mix at the end is as follows: x ^= x >> 32; x *= 0xe9846af9b1a615dULL; x ^= x >> 32; x *= 0xe9846af9b1a615dULL; x ^= x >> 28; x += secret; The addition of secret at the end ensures that the permutation is not trivially invertible by an adversary. The rest is a Murmur-style permutation, which PolymurHash gets part of its name from.
  - nullc 3y ago
    Okay that should be pretty good-- at least no worse than an arbitrary well built (non-universal) hash function.

by orlp 3y ago

nullc 3y ago

> I am working on a new hash that uses more memory (aiming around 4KiB that's shared in a process), but is a whole lot faster. Though it's hard to imagine anything with 4kib of state being very fast! is it just a precomputed power table or something where the whole thing isn't even accessed for short inputs? > The finalizer for that hash is a universal hash which I believe is 2^(2-k) almost-delta universal mod 2^k for any k <= 64. So the bottom bits are always high quality. That's interesting! > PolymurHash has no such guarantee, the claims are only over the full hash. That said, I don't expect problems in practice due to the Murmur style bit mixing at the end. That mix at the end is just an addition with a secret constant, right? I'd expect then the least significant bits to not be improved much by it.

orlp 3y ago
> Though it's hard to imagine anything with 4kib of state being very fast! is it just a precomputed power table or something where the whole thing isn't even accessed for short inputs? Correct, it's a pregenerated table of random bits that, in essence, gets multiplied with the input. If the input is small, only a small portion gets accessed. > That mix at the end is just an addition with a secret constant, right? I'd expect then the least significant bits to not be improved much by it. No, the mix at the end is as follows: x ^= x >> 32; x *= 0xe9846af9b1a615dULL; x ^= x >> 32; x *= 0xe9846af9b1a615dULL; x ^= x >> 28; x += secret; The addition of secret at the end ensures that the permutation is not trivially invertible by an adversary. The rest is a Murmur-style permutation, which PolymurHash gets part of its name from.
- nullc 3y ago
  Okay that should be pretty good-- at least no worse than an arbitrary well built (non-universal) hash function.