Structural hashing for pixel art: a 1024-byte key that answers 'is this the same artwork?' in 115 nanoseconds — and then tells you exactly what was edited.
Nine days, or one second. That is the real distance between the naive answer and the structural one — measured, on a single CPU core, for the same question asked of the same ten million images. This article is the story of that gap, and of the small Rust module that crosses it.
The best computation is the one you never repeat.
The problem: every mint is an accusation waiting to be checked
Pixagram is a pixel-art social network with an on-chain marketplace. Every artwork a user mints must be checked against every artwork that already exists — not for byte-equality, which is trivial, but for the whole taxonomy of near-theft: the recolor, the 2× export, the "original" with one pixel moved, the palette quietly reduced from six shades to five, the negative, the half-size repost.
Call it what it is: copy-detection, or near-duplicate retrieval. (Not "image recognition" in the classifier sense — no network here learns what a cat is. This is provenance, at marketplace scale.)
The naive method reads both images and compares pixels. The honest cost of that is worse than it looks, because a raw diff answers nothing — it breaks on the very first recolor. To answer the real question pixel-wise, you must search the invariances: try the plausible rescale factors, try the monotonic recolor normalizations, diff after each attempt. We measured the raw diff of two 512×512 images at 0.66 ms; multiply by a modest invariance search (~6 scale factors × ~20 recolor remaps ≈ 120 passes) and each pair costs on the order of 80 ms. Against a corpus of 10 million artworks, one incoming mint costs ~9 days of CPU. Per mint.
The structural method compares two precomputed 1024-byte keys in 115 ns. Same corpus, same core: ~1.1 seconds brute-force — sub-second once the keys live in a BK-tree. That ratio is ~700,000×, and it is where the title's "~million×" comes from — not from magic, but from a change of regime: every invariance the naive loop searches at query time, we pay for once, at hash time, for everyone, forever.
Why the usual hashes fail here
Two families of prior art, two distinct failures:
Cryptographic hashes are built for avalanche — one flipped pixel, a completely different digest. Perfect for integrity, useless for similarity: the property we need is the exact opposite, hash distance ≈ image distance.
Photographic perceptual hashes (aHash/dHash/pHash) blur, downsample, and run DCTs — machinery designed for continuous photographs. Pixel art is quantized: ≤256 flat colors, hard 1-px edges, meaning carried by exact index relationships. Gaussian blur does not summarize this medium; it destroys it.
So we wrote the hash the medium deserves.
Idea 1 — canonicalize until the edits disappear
Before hashing, the image is reduced to a canonical form: palette deduplicated, unused entries stripped, fully-transparent pixels collapsed to a single entry, then the palette sorted by luminance and every pixel remapped to its luminance rank.
Consequences, each one an entire attack class neutralized for free:
- Palette storage order is irrelevant — same art, same hash.
- Any monotonic recolor — brightness, contrast, most tints — preserves luminance order, so the entire index layer is bit-identical. The edit is confined to the palette signature, where we can read it.
- Nearest-neighbor integer exports (2×, 3×, 4× — how pixel art actually ships) are detected via the gcd of all run lengths and undone. A 2× export hashes identically to its source.
Idea 2 — Gray code makes palette surgery cost one bit
Remove or merge a palette entry and every rank above it shifts by exactly one. Stored in binary, a ±1 shift can flip many bits (7 → 8 flips four). Stored Gray-coded, a ±1 shift flips exactly one bit — always:
/// Binary-reflected Gray code: adjacent values differ by exactly one bit.
pub fn gray(b: u8) -> u8 { b ^ (b >> 1) }
So a merged shade costs Hamming distance proportional to how much of the image used it — a graceful, meaningful degradation instead of an avalanche.
Idea 3 — layers, so each edit class damages exactly one thing
The hash is not one digest but a stack of independent signatures — palette (plus log-quantized populations, so a merged workhorse shade is distinguishable from a dropped accent), 16×16 tile digests with an exact FNV-1a per tile (a single-pixel edit changes one tile, and we can name it), an edge layer of index-transition counts, 32×32 supertile average colors, and a fixed 1024-byte global signature that is resolution-independent — the DB key behind the 115 ns comparison.
A word on the edge layer, because we considered Canny and rejected it: Canny exists to find edges hiding in continuous images — blur, gradients, hysteresis thresholds. In quantized art the edges are not hiding. Every adjacent pixel pair with different ranks is an edge, exactly. Counting transitions gives us Canny's benefits with zero thresholds and zero blur — the native edge detector of the medium.
Idea 4 — two parts: the image analyser and the hash analyser
The architecture splits cleanly. compute() is the image analyser — the only place pixels are ever read. compare() answers how similar. And diagnose() — the hash analyser — answers what changed, from the two hashes alone:
darken 25% → Recolored brightness −0.08 contrast −0.25
tint +60 red → Recolored tint[r+0.19 g−0.05 b−0.05]
1 pixel edited → LocallyEdited tiles 1/24 bbox(2,1)–(2,1)
merge 6→5 shades → PaletteReduced colors −1 (1 heavily used)
negated → Inverted luminance order reversed
2× export → Rescaled overall 1.000
Look at the first line again. A ×0.75 darken is a contrast slope of −0.25 — the analyser recovered the filter's actual coefficient from palette alignment alone, without ever seeing either image. An embedding model gives you a cosine similarity of 0.93 and a shrug; the hash gives you a report a moderator can act on — and a court can read.
The receipts
Measured on a single container vCPU (Rust, -O; your hardware will do better):
| operation | cost | rate |
|---|---|---|
compute() — hash a 96×64 artwork |
153 μs | 6,500/s |
compute() — hash a 512×512 export |
6.4 ms | 157/s |
full compare() (all layers) |
966 ns | ~1M pairs/s |
full diagnose() (structured report) |
4.0 μs | 250k reports/s |
| 1024-byte global key, Hamming | 115 ns | ~9M pairs/s |
| naive 512×512 RGBA diff — one attempt, zero invariances | 0.66 ms | — |
Scalar code, no SIMD — AVX-512 popcount would multiply the key rate again. And for completeness against the neural route: an embedding model spends billions of operations per image encoded; our encoder spends ~10⁶ integer ops, and our comparison is a thousand. Embedding pipelines precompute too — the honest difference is that our encode is orders of magnitude cheaper on CPU, our key is 1024 inspectable bytes rather than an opaque float vector, and our comparator explains itself.
Try it — the whole lab is one HTML file
The entire pipeline is ported to dependency-free JavaScript and wrapped in a single-file browser lab: drop two artworks (or generate edit scenarios), read the verdict, and watch the analysis drawn on the artwork itself — changed tiles outlined, bounding box dashed, mirrored tiles flagged with glyphs.
The port is not "inspired by" the Rust — it is byte-identical: the JS engine serializes the test corpus to the same 1649 bytes, hex-diffed against the reference, and reproduces every verdict to three decimals. When the browser tells you PaletteReduced, production Rust will say the same.
- Live demo: {LIVE_DEMO_URL}
- Source (Rust + lab): {SOURCE_URL}
What it does not do — yet
Honesty is cheaper than refunds. Crops and translations are not aligned (tile shingling is the designed follow-up); luminance-order-breaking filters — negation aside, which is detected — scramble the rank layer while the color layers still match; the ≤256-color bound is a feature of the medium, not a bug of the method; and the verdict thresholds were tuned on synthetic edits — corpus tuning on real mint pairs is the next milestone.
License
MIT, © 2026 Pixagram SA — take it, break it, tell us what you find.
The moral, if a systems article may have one: speed was never in the comparison — it was in refusing to compare what canonicalization had already answered. Millions of times faster is what remains when you stop repeating yourself.
Matias Affolter is co-founder and chairman of Pixagram SA. The Pixa chain is a HIVE/STEEM fork storing pixel art fully on-chain — which is precisely why every byte of provenance machinery has to earn its place.
Top comments (0)