# What a universal hash family guarantees

A collision bound can hold for every fixed pair even though one input always
has the same output. The order of choices also matters: fixing a pair before
drawing a function is different from choosing a pair after inspecting it.

## Exact finite example

Let x be a three-bit column vector and let A be a two-by-three binary matrix.
All arithmetic is over GF(2): addition is XOR. Enumerate all 64 matrices with
equal weight, including singular matrices and the zero matrix. Set h_A(x)=Ax.

| Event | Numerator | Denominator | Exact fraction |
| --- | ---: | ---: | ---: |
| A particular fixed distinct pair collides, for each of 28 pairs | 16 | 64 matrices | 1/4 |
| Zero input maps to zero | 64 | 64 matrices | 1 |
| A pair selected after the full matrix is revealed collides | 64 | 64 matrices | 1 |
| A particular ordered pair of outputs under Ax XOR b, for each distinct input pair | 16 | 256 matrix/offset seeds | 1/16 |

For the last row, b is an independent uniform two-bit offset. Each of the
16 ordered output pairs has the same count. The code records all counts, not
just the minimum or maximum.

For any fixed nonzero difference d=x XOR y, choose a nonzero coordinate of d.
After the other matrix columns are fixed, that column makes Ad uniform over
four values. Thus Pr[Ax=Ay]=1/4. Yet A0=0 always, so this family is not strongly
universal. With an offset, Ax XOR b is uniform even after A is fixed; together
with uniform A(x XOR y), this yields uniform paired outputs.

Every mapping from eight inputs into four outputs has a collision. The
adaptive selector records the lexicographically first colliding pair for each
matrix. Its success is not a violation of the fixed-pair guarantee: it changes
which pair is tested depending on the selected function. No practical attack
on a hash-table implementation is being claimed.

## Why the distinction matters for storage indexes

Bucket matches identify candidates. Exact indexes still need key comparisons
or another exact verification step. A digest match, an approximate-membership
answer and a bucket match have different meanings.

The zero-key example also shows why a collision bound alone is insufficient
to justify uniform hash-threshold sampling. For this linear family, zero is
always selected by a positive threshold. Strong universality supplies uniform
marginals and pairwise independence; it is not the same as full independence.

## Reproduce

Python 3.10 or newer, standard library only. Run in this directory:

```sh
python3 -B model.py --check
python3 -B -m unittest -v test_model.py
python3 -O -B -m unittest -v test_model.py
```

[model.py](model.py) implements enumeration; [test_model.py](test_model.py)
checks it against a row-wise matrix-product implementation.
[example.json](example.json) contains all pair counts and adaptive witnesses.
To regenerate the JSON, use `python3 -B model.py --write`.

This is exhaustive finite arithmetic, not a sampled experiment, device
measurement, benchmark replication or new hashing algorithm. Confidence
intervals do not apply to complete enumeration. The construction is educational
and is not a cryptographic primitive. Code and generated data: CC0-1.0.

## Primary sources

- [Carter and Wegman, Universal Classes of Hash Functions, JCSS 18(2), 1979](https://doi.org/10.1016/0022-0000(79)90044-8).
- [Thorup, High Speed Hashing for Integers and Strings, arXiv v9, 2020](https://arxiv.org/pdf/1504.06804v9), sections 2, 2.1, 3 and 6.

[Universal hashing](https://hesela.dev/terms/universal-hashing/) connects this
example to the corpus. See also [hash collisions](https://hesela.dev/terms/hash-collision/).