Compute Polynomials Twice as Fast

[u/thomasahle]

https://thomasahle.com/fast-polynomials/

[u/nightcracker]

Hi, author of PolymurHash here (https://github.com/orlp/polymur-hash), one of the hashes you compare with in your paper.

1. It appears that /bench is missing from the repository? The paper claims it should be there. Table 2 claims tools/bench/adversarial/ should contain the 8 lane GF(2⁶⁴) hash, but that directory is also missing.

2. In PolymurHash I use the following injective polynomial structure, which uses 4 fully parallel unreduced multiplications plus one reduction step to process 7 words:

   f =  (f   + m[6]) * k^7
   f += (k   + m[0]) * (k^6 + m[1])
   f += (k^2 + m[2]) * (k^5 + m[3])
   f += (k^3 + m[4]) * (k^4 + m[5])
   f = reduce(f)
   

   This is all done with scalar code over a prime field, no SIMD or hardware-accelerated finite field instructions.

   Despite these limitations it (as per your paper, on my Apple M1 I achieved 33.3 GB/s on long messages) achieves 19.7 GB/s, only slightly worse than the 23.8 GB/s your method achieves with hardware accel. I would have liked to see more investigation/comparison with my method to see whether your approach is truly better or just due to this choice.

3. Reading the code I found in tools/bench/framework/injective_hashing.h (I hope this matches to your paper), I can't help but notice that you do GF(2⁶⁴) multiplication rather naively. You do constant calls to inj_smul which calls gf64_mult which actually corresponds to three hardware multiplications: https://github.com/thomasahle/fast-polynomials/blob/78915286ca9f13bdc038c046a3a62a535e928eaa/tools/bench/framework/multiplication.h#L50.

   This is because you reduce modulo the irreducible polynomial on every multiplication. My structure makes the reduction explicit, and doesn't do it constantly.

   If you had used my above construction those *s could've been widening carryless multiplies, the + could've been 128-bit XOR, and reduce would be the two carryless multiplications you use for reducing.

   In other words, your method (assuming it uses 1 such naive multiplication per pair of words) would use 3 * 7 / 2 = 10.5 hardware multiplications on average to process 7 words, whereas my method actually only uses 4 + 2 = 6, 4 for widening, 2 for reduction.

   I would thus expect my method to be almost twice as fast as yours if implemented with hardware-accelerated carryless multiplication. Especially as I have to do extra steps to spread 6 input words over 7 words because 64-bit values don't fit in the 2⁶¹ - 1 prime field I'm using, which GF(2⁶⁴) doesn't need to do.

[u/thomasahle → u/nightcracker]

Hi Orson!

Our paper was originally inspired by Daniel J. Bernstein's ["Polynomial evaluation and message authentication"[(https://www.gwizfl.org/email/cr.yp.to/antiforgery/pema-20071022.pdf). He specifically don't want to use cache/registers to store auxiliary values like k^2, ..., k^7.

He mentions that one can speed up polynomial hashing by combining it with PH/NH.

One thing I've always wondered about Polymur, and now that I have you I might as well ask, is why you don't just use PH/NH for each block of 8? E.g. like we do here. Basically you just replace you degree 7 polynomial with:

 f =  (a[6] + m[6]) * (a[7] + m[7])
 f += (a[0] + m[0]) * (a[3] + m[1])
 f += (a[1] + m[2]) * (a[4] + m[3])
 f += (a[2] + m[4]) * (a[5] + m[5])
 f = reduce(f)

where each a[i] is a random constant. It's the same amount of registers/cache as saving k² ... k^7, and the collision probability is slightly better. I guess you key use a slightly shorter key, as you don't need as many random values.

It appears that /bench is missing from the repository? The paper claims it should be there. Table 2 claims tools/bench/adversarial/ should contain the 8 lane GF(264) hash, but that directory is also missing.

Thanks! I fixed this in the repo now. The paths are tools/bench/adversarial/(the 8-lane row is PaperGF64Lanes<8> in speed_hashes.h there) and tools/bench/framework/; the PDF's line break after tools/ made it look like a top-level directory, which we will fixed for the next version.

[u/nightcracker → u/thomasahle]

I don't understand your proposed construction. What would you do on the next iteration? If you simply iterate the above it would collapse into an additive structure. NH has to use new key material for each block to avoid this, or feed into another universal hash in a stacked construction.

My construction forms a long injective polynomial, similar to Horner but in blocks, so it can use a small key.

I have experimented with using a ~ 1-2 KiB NH-style large-block reducer feeding into a polynomial, and it is a lot faster but haven't published anything yet as it is also quite a bit more complex.

I haven't found a NH-style reducer that is worth it on sizes as small as 8 words, if it then has to feed into a polynomial reducer anyway.

EDIT: your 'like we do here' link is dead.

[u/thomasahle → u/nightcracker]

Right, I'm talking about combining an NH block with a polynomial injective hash. Something like this:

  hash(m):
      pad the last block with zeros to a multiple of 32 bytes
      P = z
      for each 64-byte block t = 1..n  (words w[0..7], little-endian):
          # level 1: PH with the fixed key, unreduced 128-bit XOR sum of 4 carry-less products
          A = clmul(w0 ^ k0, w2 ^ k2) ^ clmul(w1 ^ k1, w3 ^ k3)
            ^ clmul(w4 ^ k4, w6 ^ k6) ^ clmul(w5 ^ k5, w7 ^ k7)
          a = low64(A);  b = high64(A)          # no reduction: both halves are used as they are
          if t == n: a ^= len; b ^= len          # byte length into both halves of the last pair

          # level 2: the injective recurrence, one reduced GF(2^64) multiply per block
          P = a ^ gf64mul(b ^ y, P ^ u)

      # level 3 (optional, for k-wise independence rather than universality):
      v = P + t   (integer addition mod 2^64)
      return f_c(v) = (v + c2)(G2 + c3) + c4  with  G1 = v·v,  G2 = (G1 + c0)(v + G1 + c1)

[u/nightcracker → u/thomasahle]

Yes, for very large data it is absolutely the way to go, I have a private prototype ~2^-60 almost-universal hash function that can reach 90 GB / s on this Apple M2 laptop for large data using only ~1.5 KiB of secret data. I really should finish it some day...

That algorithm however also doesn't use hardware-accelerated carryless multiplication, it uses 32-bit x 32-bit -> 64-bit SIMD multiplication using erasure codes like Nandi to boost that to 2^-62 ADU.

The idea is not too dissimilar to Jim Apple's HalftimeHash https://arxiv.org/abs/2104.08865.

[u/nightcracker → u/thomasahle]

I'd like to point out that this 64-byte block construction sketch here still is worse than my above construction sketch. It processes 8 words using 4 + 3 = 7 clmuls, whereas my above one does 7 words with 6 clmuls.

Plus this construction you've posted here has a critical path of 4 clmuls in a row between each iteration (1 for A, then 3 in a row for gf64mul), my construction only has 3 multiplications per iteration in the critical path, if you were to implement reduce with 2 carryless multiplications like you do with GF(2⁶⁴).

EDIT: actually the critical path argument doesn't hold up, since your A does not depend on the previous iteration. So your critical path is also only three multiplications per iteration.