---
title: The Bots That Almost Match
date: '2026-07-10'
description: 'Exact-match blocklists are blind to a bot farm that mutates its fingerprint by one field per request. This is how MinHash and locality-sensitive hashing turn "have I seen this exact client" into "have I seen something shaped like this", and catch the farm in sublinear time.'
author: Pablo Fernandez
tags:
  - MinHash
  - LSH
  - Fingerprinting
  - Bot Detection
  - Near-Duplicate Detection
source: 'https://www.pablofr.com/blog/minhash-lsh-bot-fingerprinting'
---
You ban a fingerprint, and three minutes later the same farm is back. Not the same fingerprint: this time one TLS extension is in a different order, the accept-language is `en-GB` instead of `en-US`, one font is missing from the list. Your blocklist is a hash set, and to a hash set that is a brand new client it has never seen. So it waves through a thousand requests that are, to any honest reading, the exact same bot you just blocked, wearing a slightly different coat each time.

This is the failure mode that separates a toy blocklist from a real one. The interesting adversary does not send you the same request twice. It sends you a thousand requests that are ninety-eight percent identical and never once byte-for-byte the same. The question this post is built around is narrow and, I think, genuinely hard: how do you catch a client you have technically never seen, because it makes sure you never see the same one twice?

The answer is a pair of old ideas from the search-engine world, [MinHash](https://en.wikipedia.org/wiki/MinHash) and [locality-sensitive hashing](https://en.wikipedia.org/wiki/Locality-sensitive_hashing), pointed at fingerprints instead of web pages. Together they turn the question from "have I seen this exact client" into "have I seen something shaped like this", and they answer it without comparing the new request against everything you have ever stored.

## The blocklist that sees a thousand strangers

A cryptographic hash is built to do the opposite of what we want here. Flip one bit of the input and roughly half the output bits flip: that avalanche is the whole point of a good hash, and it is exactly why a hash set cannot see a near-duplicate. Two fingerprints that differ in one reordered header produce two outputs with nothing visible in common. The structure that makes exact-match lookups fast is the structure that makes fuzzy matching impossible.

```
   fingerprint A  ──▶  sha256  ──▶  9f2a … c1e4
   fingerprint B  ──▶  sha256  ──▶  4e7b … 8003     one header reordered

   to a hash lookup:   two total strangers
   to the traffic:     the same client, barely touched
```

*A cryptographic hash erases similarity by design: one reordered header makes two near-identical fingerprints look like total strangers to a hash set.*

You cannot fingerprint your way out of this by picking better fields. Whatever you measure, TLS ciphers and extensions, a [JA4](https://github.com/FoxIO-LLC/ja4) string, header names and their order, the `navigator` object, the font list, a canvas hash, the attacker can jitter one of them per request and stay under an exact-match ban forever. The mutation is cheap for them and invisible to a hash set. What you actually want to ask is a similarity question: not "is this fingerprint in my list", but "is this fingerprint close to a lot of things in my list". That is a different kind of lookup, and naively it is far more expensive.

## Why the obvious fix does not scale

The obvious fix is to store every fingerprint and, for each new request, measure how similar it is to the ones you have. Define similarity however you like, share of overlapping features, edit distance on the raw string, and the problem is the same: you are comparing one new item against every stored item, and across a stream you are comparing everything against everything. That is O(n squared) pairwise work, and n here is your request rate. At a few thousand requests a second, with a rolling window of millions of fingerprints, it is not a tuning problem. It is off the table.

```
   naive:   compare each new fingerprint with every stored one
            ┌─────────────────────────────────┐
            │   n x n  comparisons per window │
            └─────────────────────────────────┘
                       off the hot path

   what we want:  a lookup that returns only the near-duplicates
            new fingerprint  ──▶  one bucket  ──▶  a short candidate list
```

*Pairwise similarity is quadratic: every new fingerprint compared against every stored one is the cost you cannot pay on the hot path.*

So we need two things that sound almost contradictory. A cheap, fixed-size summary of a fingerprint whose closeness to another summary tells us how similar the originals were. And a way to retrieve only the near-duplicates of a new fingerprint without scanning the rest. MinHash gives us the first. LSH gives us the second. They were designed together, by [Andrei Broder](https://cs.brown.edu/courses/cs253/papers/nearduplicate.pdf) at AltaVista in the late nineties, to de-duplicate a web the size of the whole web, and the shape of that problem is the shape of ours.

## Turn a fingerprint into a set

The first move is to stop thinking of a fingerprint as a string and start thinking of it as a set of features. You break it into tokens, one per observable property, and namespace each token so a cipher can never accidentally collide with a font. This is the fingerprinting version of [shingling](https://en.wikipedia.org/wiki/W-shingling), the trick Broder used to turn a document into the set of its overlapping word-runs.

```typescript:shingle.ts
// Turn one client fingerprint into a set of namespaced feature tokens.
// The namespace prefix keeps a cipher from ever colliding with a font.
function shingle(fp: Fingerprint): Set<string> {
  const s = new Set<string>()
  for (const c of fp.tlsCiphers) s.add(`tls:${c}`)
  for (const e of fp.tlsExtensions) s.add(`ext:${e}`)
  fp.headerOrder.forEach((h, i) => s.add(`hdr:${i}:${h}`))
  for (const f of fp.fonts) s.add(`font:${f}`)
  s.add(`ja4:${fp.ja4}`)
  s.add(`ua:${fp.userAgent}`)
  return s
}
```

```
   one fingerprint
        │  split into namespaced feature tokens
        ▼
   ┌───────────────────────────────────────────────────┐
   │ ja4:t13d…  tls:0x1301  tls:0x1302  ext:0x0000     │
   │ hdr:0:host  hdr:1:accept  font:Arial  ua:Mozilla… │
   └───────────────────────────────────────────────────┘
        │
        ▼
   a set of tokens   ──▶   ready to compare by overlap
```

*Shingling: a fingerprint becomes a set of namespaced tokens, so similarity between two clients is just the overlap between two sets.*

Once a fingerprint is a set, "how similar are two clients" has an exact, boring answer: the [Jaccard similarity](https://en.wikipedia.org/wiki/Jaccard_index), the size of the intersection over the size of the union. Two clients sharing every feature score 1. Two sharing nothing score 0. A farm member that jittered one field out of two hundred scores around 0.99. That number is precisely the signal a hash set throws away, and computing it directly still means intersecting two sets, which is still too slow to do against everything. Jaccard is the right question. MinHash is how you stop paying full price to ask it.

## The trick that makes MinHash work

Here is the one idea the whole technique rests on, and it is worth slowing down for. Take a set, hash every element, and keep only the single smallest hash value. Now do the same for a second set, using the same hash function, and ask a simple question: how often do the two minimums come out equal?

> The answer is the surprise the whole method rests on: the two minimums match exactly as often as the two sets are alike. Put formally, the probability that two sets share the same MinHash value equals their Jaccard similarity, with nothing approximated in that statement. Similarity you would otherwise get by intersecting two full sets, you now read off by comparing two single numbers.

The reason is almost too simple. The minimum comes from whichever element, across the union of both sets, happened to hash smallest. That winning element lands in both sets exactly when it sits in their intersection, and it is equally likely to be any element of the union. So the chance the minimums match is the chance the smallest-hashing element is a shared one, which is the intersection over the union. That is Jaccard, falling straight out of a minimum.

One minimum is a coin weighted by similarity, so you throw many. Use k independent hash seeds, keep k minimums, and you have a fixed-length signature. Compare two signatures position by position: the fraction that agree is an unbiased estimate of the Jaccard similarity, with a standard error of about one over the square root of k. At k of 128 that is under nine percent error from a signature of 128 numbers, a few hundred bytes, regardless of whether the original fingerprint had ten features or ten thousand.

```typescript:minhash.ts
// k independent hashes; keep the smallest image of the set under each seed.
// P(sig A[i] === sig B[i]) === Jaccard(A, B), by construction.
function minhash(set: Set<string>, seeds: number[]): Uint32Array {
  const sig = new Uint32Array(seeds.length).fill(0xffffffff)
  for (const token of set) {
    for (let i = 0; i < seeds.length; i++) {
      const h = hash32(token, seeds[i])
      if (h < sig[i]) sig[i] = h
    }
  }
  return sig
}
```

```
   set A = {a,b,c,d}          set B = {a,b,c,e}          Jaccard = 3/5 = 0.60

   seed 1   min(A) = 12       min(B) = 12                agree
   seed 2   min(A) = 07       min(B) = 41                differ
   seed 3   min(A) = 33       min(B) = 33                agree
   seed 4   min(A) = 18       min(B) = 18                agree
     ⋮
   ───────────────────────────────────────────────────────────────
   fraction of agreeing rows   ≈   0.60   =   estimated Jaccard
```

*MinHash in miniature: each row keeps one minimum; the fraction of rows where two signatures agree estimates their Jaccard similarity.*

We have solved half the problem. Any two fingerprints can now be compared in k cheap integer comparisons instead of a set intersection. But k comparisons times every stored signature is still linear per request, and linear per request is still quadratic across the stream. We compressed the comparison. We have not yet avoided doing it against everything.

## From signatures to buckets

The second move is what makes the whole thing sublinear, and it is a lovely piece of engineering. Cut each k-length signature into b bands of r rows, so that b times r equals k. Hash each band on its own into a bucket. Two clients that are identical across all r rows of any single band land in the same bucket for that band, and become candidates. You never compare a fingerprint against the whole store: you look it up in b hash tables and collect whoever shares a bucket.

```typescript:lsh.ts
// Split the 128-value signature into 32 bands of 4 rows each.
// Two clients that agree on ALL 4 rows of ANY band share that bucket.
function bandKeys(sig: Uint32Array, bands = 32, rows = 4): string[] {
  const keys: string[] = []
  for (let b = 0; b < bands; b++) {
    const slice = sig.subarray(b * rows, b * rows + rows)
    keys.push(`${b}:${hash32(slice.join(','), 0)}`)
  }
  return keys
}
```

```
   signature (128 values)   =   32 bands   x   4 rows

   band 0    [ v0   v1   v2   v3  ]   ─hash─▶   "0:3f1a"
   band 1    [ v4   v5   v6   v7  ]   ─hash─▶   "1:9c02"
   band 2    [ v8   v9   v10  v11 ]   ─hash─▶   "2:7e55"
     ⋮
   band 31   [ …                 ]   ─hash─▶   "31:a0b8"

   match ALL 4 rows of ANY one band   ──▶   candidate pair
```

*Banding: the signature is chopped into bands, each hashed to one bucket key, so a single matching band is enough to make two clients candidates.*

The elegant part is that the probability of two clients becoming candidates is a tunable function of how similar they are. If their true Jaccard is s, then any given band matches with probability s to the power r, and they collide in at least one of the b bands with probability 1 minus the quantity (1 minus s-to-the-r), all to the power b. Plot that against s and you get an S-curve: near-flat and low for dissimilar pairs, near-flat and high for similar ones, with a steep cliff in between at a threshold of roughly (1 over b) to the power (1 over r). More rows per band raises the threshold and sharpens the cliff; more bands lowers it. You are dialling in exactly how alike two clients must be before you bother looking.

```
   P(become candidates)
   1.0 │                              ·   ·   ·   ·
       │                       ·
       │                  ·
   0.5 │               ·
       │            ·
       │        ·
   0.0 │ ·  ·  ·
       └──────────────────────────────────────────────
        0.0     0.2     0.4     0.6     0.8     1.0
                    Jaccard similarity  s

        steep threshold ≈ 0.42     (b = 32 bands, r = 4 rows)
```

*The S-curve for 32 bands of 4 rows: pairs below Jaccard 0.3 almost never surface, pairs above 0.6 almost always do, with a sharp threshold near 0.42.*

Retrieval, then, is a query into b buckets followed by an exact MinHash check to throw out the weak candidates the S-curve let through. The bucket lookup is what makes it fast, turning a scan of the whole store into a handful of hash-table probes. The verify step is what makes it honest, because bucketing gives you likely-similar, not certainly-similar.

```typescript:query.ts
// Buckets give cheap candidates; confirm with the real estimate before acting.
function neighbours(sig: Uint32Array, index: LshIndex): string[] {
  const seen = new Set<string>()
  for (const key of bandKeys(sig)) {
    for (const id of index.bucket(key)) seen.add(id)
  }
  return [...seen].filter((id) => estimateJaccard(sig, index.sig(id)) >= 0.5)
}
```

## The farm lights up one bucket

Put the two pieces together against a real bot farm and the payoff is direct. The farm is trying to look like a crowd: many IPs, spread across residential and mobile ranges, each request a little different from the last. But the whole economy of a farm is sameness. They share a request template, a TLS stack, a header-construction routine, a font-poor headless environment. That shared skeleton is most of the feature set, and the per-request jitter is a thin coat of paint on top. High Jaccard is not an accident of the attack. It is the attack's cost structure.

```
   many sources, near-identical signatures

   203.0.113.9     sig ●●●●●○●●   ┐
   198.51.100.2    sig ●●●●●●●●   │
   203.0.113.44    sig ●●●○●●●●   ├──▶   bucket "7:a91f"
   198.51.100.7    sig ●●●●●●○●   │
   192.0.2.15      sig ●●●●●●●●   ┘

   one dense cluster · many IPs · one shape   ──▶   a farm
```

*A farm cannot escape its own sameness: many IPs, per-request jitter, yet the shared skeleton drives them all into the same LSH bucket.*

Now the buckets are not just a retrieval index, they are a detector. A bucket that suddenly holds forty signatures from thirty-eight different IP addresses, all within a whisker of each other in Jaccard, is not forty users. It is one actor wearing forty coats. You did not need a labelled dataset or a model to see it. You needed the structure that makes near-duplicates collide, and then you watched what collided. Datamuro treats a dense, IP-diverse cluster as evidence to feed the score, the same way the [cross-signal consistency check](/blog/anti-bot-architecture-2026) treats a JA4 that disagrees with a User-Agent as evidence: not a verdict, but a strong finger pointing at coordinated automation.

## MinHash or SimHash

MinHash is not the only near-duplicate hash, and picking the wrong one wastes the technique. The other one you will meet is [SimHash](https://en.wikipedia.org/wiki/SimHash), Charikar's method, which Google put into production for [de-duplicating the crawl](https://research.google/pubs/detecting-near-duplicates-for-web-crawling/). The difference is which similarity each one preserves, and that decides which signal each one fits.

MinHash preserves Jaccard over sets: presence and absence of features, every feature weighted the same. SimHash preserves cosine similarity over weighted vectors, and it collapses a whole item into one short bit-string whose Hamming distance tracks similarity. If your fingerprint is naturally a set of discrete capabilities, ciphers, extensions, fonts, header names, MinHash is the native fit. If you are comparing something more like a weighted bag of tokens, a raw header block or a request body where some fields matter more than others, SimHash is the sharper tool.

| | MinHash + LSH | SimHash |
|---|---|---|
| Preserves | Jaccard over sets | Cosine over weighted vectors |
| Item becomes | k minimums (a signature) | one n-bit string |
| Near-duplicate test | shared LSH band, then verify | small Hamming distance |
| Natural fit here | capability sets: TLS, fonts, headers | payloads, header blocks, bodies |
| Weighting | uniform (unless weighted MinHash) | built in per dimension |

In practice a mature pipeline runs both: MinHash and LSH to cluster clients by their capability fingerprint, SimHash to catch requests minted from the same server-side template even when the capability set is identical. They answer near-duplicate for two different views of the same request.

## The hard part is time

Everything above is the easy half. The structures are elegant and the code is short. What actually breaks in production is that all of this is stateful and the state has to decay, and getting the decay right is most of the real work.

A fingerprint that was a farm member an hour ago is noise now. If your LSH tables never forget, every bucket slowly fills with a year of history, the clusters blur, and the S-curve you tuned so carefully drowns in stale collisions. So the index has to be a sliding window: entries expire, buckets thin out, and a farm that goes quiet leaves an empty bucket behind within the window. This is the same lesson every approximate structure teaches, the same one behind a windowed [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog) or a decaying [count-min sketch](https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch): the estimator is the easy part, the windowing is the engineering.

```
   now  ───────────────────────────────────────▶  time

   [        active window: last 30 min          ]
        new signatures inserted here
   ┌───────────────────────────────────────────────┐
   │   LSH buckets, entries expire by TTL          │
   └───────────────────────────────────────────────┘
        an hour later the farm's bucket is empty again
```

*The LSH index is a sliding window: signatures enter, buckets expire by TTL, and a farm that goes quiet leaves an empty bucket behind.*

Then it gets worse, because you rarely run on one node. A farm hitting ten edge locations puts one signature in each, and if each node keeps its own LSH tables, no single node ever sees the cluster. The near-duplicate structure only pays off when the buckets are shared, which means the hot path is now touching a networked store. You end up leaning on a shared, expiry-aware backend, [Redis probabilistic structures](https://redis.io/docs/latest/develop/data-types/probabilistic/) or something like them, and paying a round trip to keep the bucket global. The algorithm stays sublinear. The system around it is where the difficulty moved.

## Where it clusters the wrong people

Here is the honest bit, because this technique fails in specific, nameable ways.

The first is that dense clusters of near-identical fingerprints are not always farms. A big corporate NAT sends thousands of genuinely different people out behind a handful of IPs on a locked-down, identical browser build, and their fingerprints are near-duplicates because their laptops are near-duplicates. The single most common device-plus-browser-plus-locale combination on the internet forms a huge, legitimate cluster on its own. MinHash cannot tell coordinated from merely uniform. It hands you a cluster; the IP diversity, the request cadence, the rest of your signals have to decide whether that cluster is a company or an attack.

The second is that the shingling choice dominates everything, and it is easy to get wrong. Shingle on features that every Chrome user shares and you will cluster the entire Chrome population into one bucket and call it a farm. The features have to carry enough entropy that similarity means something, which usually means down-weighting the ubiquitous tokens, the exact problem uniform Jaccard is blind to and [weighted MinHash](https://ekzhu.github.io/datasketch/minhash.html) exists to fix. Garbage shingles produce confident nonsense.

The third is that a patient adversary can read this post too. If they know the threshold is near 0.42, they can mutate aggressively enough to drop each request below it, and slip through as genuine strangers. But that is the good kind of problem, because the cost lands on them. To fall under the Jaccard threshold they have to vary real capabilities, ciphers, extensions, fonts, not just cosmetic fields, and the moment they do that at volume they start contradicting themselves across the other layers: a TLS stack that no longer matches the claimed browser, a font set no real build ships. Near-duplicate clustering does not have to be un-evadable. It has to make evasion expensive enough that it surfaces somewhere else.

> The parameters here are illustrative, not tuned for your traffic. k of 128, 32 bands of 4 rows, a 0.42 threshold: these are starting points to reason about, not settings to ship. The right values depend on your feature entropy, your window length, and how much you are willing to trade false positives against missed clusters. Measure the S-curve on your own labelled clusters before you trust a threshold.

## What it actually buys you

Strip it back and the whole thing is a change of question. An exact-match blocklist asks "have I seen this exact client before", and a farm answers by simply never being the exact same client twice. MinHash and LSH ask "have I seen something shaped like this", and that question does not have a cheap dodge, because the shape is the farm's whole reason for existing. The template, the shared stack, the headless environment: those are the things that make it a farm instead of a thousand real people, and they are exactly the things that survive the jitter.

That is why this belongs in the toolbox next to the structural defenses rather than the clever tricks. It is not a single tell that a vendor can patch out from under you, the way a [DevTools leak](/blog/anti-bot-architecture-2026) can vanish in a Chrome release. It is a property of how coordinated automation has to work. You will still misfire on the corporate NAT and the world's most popular laptop, you will still owe all the windowing and state-sharing work, and it is still evidence rather than a verdict. But it turns the attacker's greatest efficiency, running one bot ten thousand times, into the signal that gives them away. Make them all a little different, and they are all, unmistakably, the same.

## References

- [Andrei Broder: Identifying and Filtering Near-Duplicate Documents (the MinHash / resemblance paper)](https://cs.brown.edu/courses/cs253/papers/nearduplicate.pdf)
- [Wikipedia: MinHash](https://en.wikipedia.org/wiki/MinHash)
- [Wikipedia: Locality-sensitive hashing](https://en.wikipedia.org/wiki/Locality-sensitive_hashing)
- [Wikipedia: Jaccard index](https://en.wikipedia.org/wiki/Jaccard_index)
- [Wikipedia: w-shingling](https://en.wikipedia.org/wiki/W-shingling)
- [Leskovec, Rajaraman, Ullman: Mining of Massive Datasets, ch. 3 on finding similar items (LSH banding)](http://infolab.stanford.edu/~ullman/mmds/ch3.pdf)
- [Mining of Massive Datasets (book home)](http://www.mmds.org/)
- [Manku, Jain, Das Sarma: Detecting Near-Duplicates for Web Crawling (SimHash in production)](https://research.google/pubs/detecting-near-duplicates-for-web-crawling/)
- [Wikipedia: SimHash](https://en.wikipedia.org/wiki/SimHash)
- [datasketch: MinHash, LSH and weighted MinHash in Python](https://github.com/ekzhu/datasketch)
- [datasketch docs: MinHash LSH](https://ekzhu.github.io/datasketch/lsh.html)
- [FoxIO: JA4+ network fingerprinting suite](https://github.com/FoxIO-LLC/ja4)
- [Redis: probabilistic data structures](https://redis.io/docs/latest/develop/data-types/probabilistic/)