5 ms·

According to the UMAC paper, the 32x32=>64 multiplication only contains 32-bit of entropy, even though it uses 64-bit space. That's understandable : most of the

According to the UMAC paper, the 32x32=>64 multiplication only contains 32-bit of entropy, even though it uses 64-bit space. That's understandable : most of the entropy will be in the middle of the register. That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy.

dragontamer 8y ago
But there's 64-bits of input (32-bit A x 32-bit B). So if you have 64-bits of input, but only result in 32-bits of output entropy, then you've lost information. I realize you have to compress data down in a Hash function somehow, but ideally you want to minimize the loss of entropy / information from the input bits. The ideal mixing function would have 512-bits of internal state, with 512-bits of entropy starting off... and ending with 512-bits of entropy once all the mixing were done. If your factoid is correct, then we're starting with 512-bits of entropy, but only 256-bits of entropy after the multiply. > That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy. Why not optimize the function, and aim for only 256-bits of internal state (with 256-bits of entropy) ?? See: you can cut down on state and possibly improve performance. Maybe not on Intel Skylake, but probably on ARM Neon / AMD Zen (which have 128-bit SIMD registers internally). Hmmmm... 512-bit (aka 2x AVX2 registers) is probably needed to get good ILP on Intel processors. So there probably wouldn't be much improvement for Intel. ----------- Again though: I'm not sure if its losing information yet. Its just something I'm thinking about... (32-bit XOR would be 32-bit + 32-bit input, with only 32-bits of entropy output. But unlike multiply, you only have 32-bits of state) 32-bit multiplication with a constant, keeping only the bottom 32-bits, keeps all 32-bits of entropy without being forced to expand to 64-bits. I definitely like the bit-mixing properties of multiply, its just difficult to find configurations of multiplication that saves every bit of entropy.
- Cyan4973 8y ago
  It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. In the resulting 64-bit register, bit-0 can only be contributed by the first bit-0 of each 32-bit input. So it's only representative of these 2 bits. Same at the other end, bit-63 mostly depending on bit-31 of each 32-bit input, and also on carry over from previous bits (making things more complex). In the middle, many more bits participate, so that's where they are "well mixed". This question of bit distribution becomes critical if the 64-bit accumulator was used "as is" to produce a hash, but fortunately it's not. Accumulators will get mixed before that stage. When the mixing function is done correctly, every bit will get redistributed to the point of saturation. After which point, it does not matter that initially one accumulator's bit had less contributions than another : all source bits contributes fully. This can be easily verified with SMHasher's Avalanche test. Finally, XXH3 does not follow UMAC too closely, and adds an operation which ensures that all bits are necessarily present at least once in the accumulator. This compensate from the risk of multiplying by zero, which _is_ dangerous for checksumming, as it would nullify a contribution.
  - dragontamer 8y ago
    > It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. I agree. But entropy is a great concept that helps allow us to calculate whether or not "input bits" can affect "output bits". Lets look at XXH3_scrambleAcc: __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); __m256i const dk2 = _mm256_mul_epu32 (d2,k2); xacc[i] = _mm256_xor_si256(dk, dk2); Assume you start with 512-bits of input entropy (that is: assume that all 512-bits of state are uniformly random). Will you have 512-bits of uniformly random output after the above operations? Or to put it in your words: are you 100% sure that the above steps allow every input bit to affect every output bit? It appears not. My counter-example (not that I've debugged your code... but based on my reading) is as follows: key[2] is 0x7c01812c, and key[3] is 0xf721ad1c. This means that key[2] AND key[3] are even numbers. Which means dk.int64[1] bit0 will always be zero. And dk2.int64[1] bit0 will ALSO always be zero (on iteration 0, i=0) I bet you, at least... if I did my math correctly... that xacc[0].int64[1].bit0 will ALWAYS be zero, no matter what state you start with (bit#64 of xacc[0] == 0) This is because xacc[0].int64[1].bit0 = dk.int64[1].bit0 XOR dk2.int64[1].bit0 And both of those component parts seem to always be zero. Which means you're at LEAST wasting the 64th bit of state each time you perform XXH3_scrambleAcc. It certainly seems like a weakness of the XXH3_scrambleAcc function to me. That's a lot of operations you do, to literally throw away half your bits. There's probably an optimization you can do here to get better mixing.
    - Cyan4973 8y ago
      Well, if you believe a better scrambling operation is possible, you are certainly welcomed to suggest one. Considering feedbacks on the algorithm is one of the objectives of the test phase. If the issue is about the default keys, it's also possible to change them, though one will also have to consider what happens with custom keys and if it implies ensuring some conditions (custom keys is a long-term objective of XXH3). At the end, XXH3 is only generating 64 and 128 bit hashes, and maybe 256 in the future, so compression necessarily happens somewhere. I believe the issue would be more pressing if the intention was to generate a 512-bit hash, but that has never been an objective.
- Cyan4973 8y ago
  > Why not optimize the function, and aim for only 256-bits of internal state (with 256-bits of entropy) ?? It's a lot more difficult to ensure that accumulators contain full-width entropy at all times. The trade-off in this algorithm is that we intentionally use bigger accumulators and don't even try to maintain the entropy at full level all the time. All it needs is to ensure that the level of entropy is _at least_ 32 bits per accumulator, which is much easier. This leads to better speed.

dragontamer 8y ago

But there's 64-bits of input (32-bit A x 32-bit B). So if you have 64-bits of input, but only result in 32-bits of output entropy, then you've lost information. I realize you have to compress data down in a Hash function somehow, but ideally you want to minimize the loss of entropy / information from the input bits. The ideal mixing function would have 512-bits of internal state, with 512-bits of entropy starting off... and ending with 512-bits of entropy once all the mixing were done. If your factoid is correct, then we're starting with 512-bits of entropy, but only 256-bits of entropy after the multiply. > That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy. Why not optimize the function, and aim for only 256-bits of internal state (with 256-bits of entropy) ?? See: you can cut down on state and possibly improve performance. Maybe not on Intel Skylake, but probably on ARM Neon / AMD Zen (which have 128-bit SIMD registers internally). Hmmmm... 512-bit (aka 2x AVX2 registers) is probably needed to get good ILP on Intel processors. So there probably wouldn't be much improvement for Intel. ----------- Again though: I'm not sure if its losing information yet. Its just something I'm thinking about... (32-bit XOR would be 32-bit + 32-bit input, with only 32-bits of entropy output. But unlike multiply, you only have 32-bits of state) 32-bit multiplication with a constant, keeping only the bottom 32-bits, keeps all 32-bits of entropy without being forced to expand to 64-bits. I definitely like the bit-mixing properties of multiply, its just difficult to find configurations of multiplication that saves every bit of entropy.

Cyan4973 8y ago
It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. In the resulting 64-bit register, bit-0 can only be contributed by the first bit-0 of each 32-bit input. So it's only representative of these 2 bits. Same at the other end, bit-63 mostly depending on bit-31 of each 32-bit input, and also on carry over from previous bits (making things more complex). In the middle, many more bits participate, so that's where they are "well mixed". This question of bit distribution becomes critical if the 64-bit accumulator was used "as is" to produce a hash, but fortunately it's not. Accumulators will get mixed before that stage. When the mixing function is done correctly, every bit will get redistributed to the point of saturation. After which point, it does not matter that initially one accumulator's bit had less contributions than another : all source bits contributes fully. This can be easily verified with SMHasher's Avalanche test. Finally, XXH3 does not follow UMAC too closely, and adds an operation which ensures that all bits are necessarily present at least once in the accumulator. This compensate from the risk of multiplying by zero, which _is_ dangerous for checksumming, as it would nullify a contribution.
- dragontamer 8y ago
  > It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. I agree. But entropy is a great concept that helps allow us to calculate whether or not "input bits" can affect "output bits". Lets look at XXH3_scrambleAcc: __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); __m256i const dk2 = _mm256_mul_epu32 (d2,k2); xacc[i] = _mm256_xor_si256(dk, dk2); Assume you start with 512-bits of input entropy (that is: assume that all 512-bits of state are uniformly random). Will you have 512-bits of uniformly random output after the above operations? Or to put it in your words: are you 100% sure that the above steps allow every input bit to affect every output bit? It appears not. My counter-example (not that I've debugged your code... but based on my reading) is as follows: key[2] is 0x7c01812c, and key[3] is 0xf721ad1c. This means that key[2] AND key[3] are even numbers. Which means dk.int64[1] bit0 will always be zero. And dk2.int64[1] bit0 will ALSO always be zero (on iteration 0, i=0) I bet you, at least... if I did my math correctly... that xacc[0].int64[1].bit0 will ALWAYS be zero, no matter what state you start with (bit#64 of xacc[0] == 0) This is because xacc[0].int64[1].bit0 = dk.int64[1].bit0 XOR dk2.int64[1].bit0 And both of those component parts seem to always be zero. Which means you're at LEAST wasting the 64th bit of state each time you perform XXH3_scrambleAcc. It certainly seems like a weakness of the XXH3_scrambleAcc function to me. That's a lot of operations you do, to literally throw away half your bits. There's probably an optimization you can do here to get better mixing.
  - Cyan4973 8y ago
    Well, if you believe a better scrambling operation is possible, you are certainly welcomed to suggest one. Considering feedbacks on the algorithm is one of the objectives of the test phase. If the issue is about the default keys, it's also possible to change them, though one will also have to consider what happens with custom keys and if it implies ensuring some conditions (custom keys is a long-term objective of XXH3). At the end, XXH3 is only generating 64 and 128 bit hashes, and maybe 256 in the future, so compression necessarily happens somewhere. I believe the issue would be more pressing if the intention was to generate a 512-bit hash, but that has never been an objective.
Cyan4973 8y ago
> Why not optimize the function, and aim for only 256-bits of internal state (with 256-bits of entropy) ?? It's a lot more difficult to ensure that accumulators contain full-width entropy at all times. The trade-off in this algorithm is that we intentionally use bigger accumulators and don't even try to maintain the entropy at full level all the time. All it needs is to ensure that the level of entropy is _at least_ 32 bits per accumulator, which is much easier. This leads to better speed.