orlp / polyxor

# PolyXOR128
PolyXOR128 is a 128-bit universal hash function
designed for fast file/data stream integrity checks with cryptographic strength.
It has some nice properties:
 - It is **mathematically proven** to have a low collision rate. When
 initialized with **a random key completely independent of the
 input**, the probability that two inputs `m`
 and `m'` of up to `n` bytes collide is at most `(n/4096 + 3) / 2^128`. This
 proof is fully formalized in Lean, see the `proofs` directory.
 - It is one of the fastest hash functions available for medium to large inputs,
 reaching throughputs of up to 130 GB/s on a Ryzen 9950X, and 60 GB/s on an
 Apple M2 Pro. It is to my knowledge the fastest 128-bit hash, even beating
 most 64-bit and insecure hashes. See the benchmarks below.
There are potential downsides to PolyXOR128 as well:
 - It essentially requires carryless
 multiplication
 to be hardware-accelerated. The portable reference implementation is unusably
 slow. Luckily every modern desktop and server CPU supports this, but this may
 be a blocker for embedded devices. Our implementation does dynamic
 dispatch to hardware-accelerated paths for AArch64 and x86-64, even if you do
 not compile with those feature flags enabled.
 - A key-expanded instance of PolyXOR128 takes about 5 KB of memory. This is
 not a problem for most use-cases, but on a server handling millions of secure
 connections each with separate hash instances this might be problematic.
 - It is not currently optimized for small strings (e.g. | | |
The full data can be found in `assets/`. Note that the drop of the Xeon 8488C
at 2 MiB is due to the hashed data no longer fitting in L2 cache.
## How it works and why it's fast
I have written a more in-depth design document, but the TL;DR is as
follows. We take 128-byte blocks and add key material before splitting it up into
four parts. We compute a fifth part by means of a parity check code expanding
our total to 160 bytes. Each part is then hashed using a carryless
multiplication version of NH (similar to CLHASH), resulting in five hashes.
These hashes are accumulated with XOR. This entire process is done in SIMD,
here's a visualization of the five hashes on a 128-byte block:
We continue this process until we exhaust our pre-computed buffer of key
material (4 KiB). Then we recombine these five hashes into two, which have a
combined 2^-128 collision probability, and absorb that into a polynomial hash.
If we ignore the recombination and polynomial hash reduction (which happens only
once every 4 KiB chunk), this processes 128 bytes using ten 64 x 64 -> 128-bit
carryless multiplications. With AVX-512 on a Ryzen 9950X we can execute one
`_mm512_clmulepi64_epi128` per two cycles, which does four of these
multiplications per instruction. Putting it all together this gives a maximum
throughput of 25.6 bytes / cycle which we get fairly close to.
## A note on the usage of LLMs
All the final code (and prose) written in this library has been written