Polynomial Hashing, in depth: evaluation at a random point, the n/p bound, length pitfalls, multiset and tree fingerprints, and Poly1305

The idea and its proof

Split the data into blocks m1, m2, ..., mn, each an integer below a prime p. Define H(m) = m1 r^(n−1) + m2 r^(n−2) + ... + mn mod p, evaluated by Horner's rule as one multiply and one add per block. Now suppose m and m' have the same length and differ. Their difference D(x) = H_m(x) − H_m'(x) is a nonzero polynomial of degree at most n − 1 over the field of integers mod p, so it has at most n − 1 roots. A collision happens only when r is one of those roots, so for r uniform over p values:

Pr[H(m) = H(m')] ≤ (n − 1) / p.

Three conditions make the bound true. The modulus must be prime, so the integers mod p form a field and a degree-d polynomial has at most d roots; mod 2^64 that fails, which is why overflowing 64-bit hashes can be broken by fixed inputs. The point r must be chosen after the inputs, or an adversary can pick inputs that collide on it. And blocks must be below p, so distinct data gives distinct coefficients.

The bound grows with length, unlike a cryptographic hash, so long inputs need a large p or two independent evaluations. Arithmetic mod 2^61 − 1 is fast because reduction is a shift and an add; see Modular Exponentiation for modular multiplication in general.

The length trap

The bound above assumed equal lengths, and the naive hash breaks without it. With Horner's rule, the inputs [0, 5] and [5] both hash to 5: a leading zero block contributes nothing. Similarly, if blocks come from bytes padded with zeros, "ab" and "ab\0" can collide. These collisions happen with probability 1, whatever r is.

Two separate fixes are needed, one per level. At the block level, add 1 to every block value so a zero block can never vanish. At the byte level, append a 0x01 byte to each chunk before reading it as an integer, so a short chunk and the same chunk followed by zero bytes become different numbers. That appended byte is exactly Poly1305's encoding. With both, different inputs give different polynomials, and the root-counting argument applies at the longer length. Prefixing the total length also works, but it breaks the range-combination rule used below.

P = (1 << 61) - 1

def poly_hash(blocks, r):
    # each block b must satisfy 0 <= b < P - 1; the +1 keeps zero blocks visible
    h = 0
    for b in blocks:
        h = (h * r + b + 1) % P
    return h

def blocks_of(data: bytes, size=7):
    # a 7-byte chunk plus the 0x01 marker is below 2^57, safely under P - 1
    return [int.from_bytes(data[i:i + size] + b"\x01", "little")
            for i in range(0, len(data), size)]

Each encoded value is at most 8 bytes with a top byte of 1, so it stays below 2^57 and below p. Reading raw 8-byte chunks instead would allow values up to 2^64, which are not below p, so two different chunks could map to the same coefficient.

Worked example: checking two replicas

Two nodes each hold a copy of a 10 GB file and want to know whether the copies are identical without sending the file. With 7-byte blocks, n is about 1.5 · 10^9. One node draws a fresh random r and sends it; both compute the hash in one pass and exchange 8 bytes. If the copies differ, the hashes agree with probability at most n/p, about 1.5 · 10^9 / 2.3 · 10^18, roughly one in 1.5 · 10^9. Run two independent r values and it drops below one in 10^18.

If the hashes differ, the copies certainly differ. To locate the difference, hash the two halves, recurse into the half that differs, and you find a differing block in about log2 n rounds of 16 bytes each. Hashes of adjacent ranges also combine: H(left + right) = H(left) · r^len(right) + H(right), so each node can precompute range hashes once and answer many queries.

Why not SHA-256? It is the right choice when an adversary may craft the data, or when the hash is stored and reused, because its security does not depend on a secret r. The polynomial fingerprint is cheaper, combinable and has a provable bound for honest data with a fresh r, which is exactly the replica-check setting.

Multisets and incremental updates

Sometimes order should not matter: two services hold the same set of IDs in different orders, or a stream of insertions and deletions should end with a checkable state. Use the polynomial whose roots are the elements:

H(S) = ∏ (r − x) mod p over x in S, with multiplicity.

Two multisets of size n are equal exactly when these polynomials are equal, and two different monic degree-n polynomials differ in a polynomial of degree below n, so a collision again has probability at most n/p. Adding an element is one multiplication, and removing one is a multiplication by the inverse of (r − x), which exists unless r happens to equal x.

def ms_hash(items, r):
    h = 1
    for x in items:
        h = h * ((r - x) % P) % P
    return h

def ms_add(h, x, r):
    return h * ((r - x) % P) % P

def ms_remove(h, x, r):
    return h * pow((r - x) % P, P - 2, P) % P   # Fermat inverse

Each service maintains its hash incrementally as rows change; a reconciliation job compares 8 bytes instead of shipping the sets. Like the sequence hash, it is only safe when r is secret from whoever controls the elements, because x = r makes the product zero.

Trees and the Schwartz-Zippel lemma

The same algebra hashes unordered rooted trees, so that isomorphic trees, ones that differ only in child order, get the same value. Draw one random value per depth, then define a node's hash as the product over its children of (r_depth + child hash). A leaf, which has no children, hashes to 1.

def tree_hash(children_of, node, depth, rs):
    h = 1
    for child in children_of[node]:
        h = h * ((rs[depth] + tree_hash(children_of, child, depth + 1, rs)) % P) % P
    return h

This one has several random variables, and the argument that covers it is the Schwartz-Zippel lemma: a nonzero polynomial of total degree d in any number of variables, evaluated at a point whose coordinates are drawn uniformly from a set of size p, is zero with probability at most d/p. For trees with n nodes the hash is a polynomial of degree at most n in the r values, so two non-isomorphic trees collide with probability at most n/p. The same lemma underlies randomised polynomial identity testing, matrix product checks and many verifiable-computation protocols. For deep trees, use an explicit stack instead of recursion. The same hashes power duplicate-subtree detection and canonical forms, alongside the suffix structures in Suffix Array Construction.

From fingerprints to MACs

If r is a secret key instead of a public random value, the polynomial hash becomes a universal hash in the Carter-Wegman sense: for any two messages fixed in advance, the collision probability over the key is small. Encrypting the hash with a one-time mask turns it into a message authentication code, and two widely deployed MACs are built exactly this way.

Poly1305 splits the message into 16-byte chunks, appends a 1 byte to each chunk (the length fix from earlier), reads them as little-endian integers, and evaluates the polynomial at a key-derived r modulo the prime 2^130 − 5, then adds a second key value s modulo 2^128. Some bits of r are cleared by clamping to speed up the arithmetic, which leaves 106 bits of key. GHASH in AES-GCM evaluates the same kind of polynomial over the binary field GF(2^128) with H derived from the cipher key.

In both, the key must never be reused across messages in a way that reveals the evaluation point. The known failure is GCM nonce reuse: two messages under the same key and nonce expose equations in H, and an attacker can then forge tags. The lesson carries back to the non-cryptographic uses: polynomial hashing is only as strong as the secrecy and freshness of r.

Choosing a field

Failure modes

• Fixed or published r. A constant in source code lets anyone who reads it build colliding inputs. Draw r at runtime from a good random source.
• Missing length handling. Leading or trailing zero blocks collide with probability 1.
• Blocks not below p. Reading 8-byte blocks under a 61-bit prime maps distinct chunks to the same residue.
• Composite modulus. Mod 2^64 or a composite number, the root-counting bound does not hold.
• Ignoring length growth. The bound is n/p per comparison and grows with the number of comparisons; for 10^9 comparisons of long inputs, a single 61-bit hash is not enough.
• Stored fingerprints. A hash saved and compared later lets an adversary who learns r plant collisions; persistent identifiers belong to a cryptographic hash.

Trade-offs

Polynomial hashing buys speed, a proof and algebraic structure: ranges combine, multisets update incrementally and trees hash canonically. It pays with a bound that grows with length and number of comparisons, and with security that depends entirely on keeping r random and private. Cryptographic hashes reverse the trade: no structure, no secret, a fixed output size and resistance to adversaries.

What to do next

1. Implement poly_hash mod 2^61 − 1 and test that [0, 5] and [5] now hash differently.
2. Write down n, the number of comparisons and p for your use, and compute the bound before choosing one or two hashes.
3. Use the range-combination rule to build a bisection protocol for locating a mismatch between two replicas.
4. Replace a sort-and-compare reconciliation job with an incremental multiset hash, and keep r secret from data producers.
5. For anything adversarial or persistent, switch to SHA-256 or BLAKE3, or a keyed MAC such as Poly1305 from a vetted library.
6. Review modular inverses and Fermat's little theorem in Number Theory Algorithms, then the substring uses in the string hashing article.