3 ms·

The proof of almost-universality won't apply to subsets of bits, and many applications of hashes only use a subset of bits. The construction techniques used to

by nullc 3y ago

The proof of almost-universality won't apply to subsets of bits, and many applications of hashes only use a subset of bits. The construction techniques used to get almost-universality might even make some subset of bits very poor in their performance: or at least my experience with designing linear codes for error detection/correction has been that strong codes often have some bits that are surprisingly weak. So hopefully people have tested this empirically that the collision rates for the top and bottom n bits are all reasonable looking for varrious values of n (and might be useful to know which bits are the strongest, assuming you get a choice). Assuming there are no hidden gotchas like that, this looks pretty great.

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 nullc 3y ago

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.