regulated-finance

The Verhoeff algorithm: validating Aadhaar numbers at the ingestion edge

published
reading
5 min
tags
data-engineering, data-quality, python, spark, algorithms
On this page
  1. Why Verhoeff and not Luhn
  2. The Aadhaar layer
  3. The quarantine pattern
  4. What this does not prove

Somewhere in most Indian data platforms there is a customer feed with a column of 12-digit Aadhaar numbers, and somewhere downstream there is a join that silently fails because some of those numbers are wrong — a typo at a branch counter, an OCR misread from a scanned form, a leading zero eaten by an Excel export. You cannot call UIDAI to verify each row, and you should not want to: it is slow, it is rate-limited, and it means shipping PII out of your platform to answer a data-quality question.

What you can do is exploit a property of the number itself. The 12th digit of every Aadhaar number is a check digit computed by the Verhoeff algorithm over the first 11. Validating it is pure arithmetic — offline, free, and fast enough to run on every row of every load.

#Why Verhoeff and not Luhn

Check digits are old technology; your credit card uses the Luhn algorithm from 1954. But Luhn has a known blind spot: it is built on ordinary mod-10 arithmetic, which is commutative, and a commutative scheme cannot distinguish every pair of swapped digits — Luhn famously misses the transposition of 09 to 90. Since transposing adjacent digits is one of the most common human data-entry errors, that gap matters.

Jacobus Verhoeff closed it in 1969. His scheme was the first to detect all single-digit errors and all adjacent transpositions with a single decimal check digit. The trick is to abandon ordinary arithmetic and compute in the dihedral group D5 — the ten symmetries of a pentagon — where the group operation is non-commutative: a·b ≠ b·a, so swapped digits genuinely produce a different result.

In practice the group theory collapses into three fixed lookup tables, published in 1969 and frozen ever since: a 10×10 multiplication table d, a position-dependent permutation table p that cycles every 8 digits, and an inverse table inv used only when generating a check digit. The algorithm folds the digits, rightmost first, through the tables; a number with a correct check digit folds to exactly 0:

python
def compute_checksum(digits: str) -> int:
    """Fold the digits, rightmost first, through the D5 tables."""
    checksum = 0
    for position_from_right, char in enumerate(reversed(digits)):
        digit = int(char)
        permuted_digit = PERMUTATION_TABLE[position_from_right % 8][digit]
        checksum = MULTIPLICATION_TABLE[checksum][permuted_digit]
    return checksum
 
 
def validate(number: str) -> bool:
    return number.isdigit() and len(number) > 1 and compute_checksum(number) == 0

To see the transposition detection working, take the synthetic number 234123412346 — structurally valid, check digit and all — and swap its fourth and fifth digits, an error a human hand makes constantly:

python
>>> validate("234123412346")
True
>>> validate("234132412346")   # adjacent digits swapped
False

A Luhn-style scheme would catch most such swaps; Verhoeff catches all of them, and every single-digit error besides — not probably, not usually, but as a proven property of the group structure.

The tables themselves are in the companion repo. And yes, there are pip packages for this — I would still put the thirty lines in my own repo. The tables are constants that have not changed in fifty years; a dependency whose entire job is to hide them buys nothing and costs one more thing on the supply-chain audit.

#The Aadhaar layer

Aadhaar adds two structural rules on top of the checksum: the number is exactly 12 digits, and issued numbers never start with 0 or 1. Feeds also deliver the number formatted as 1234 5678 9012, so normalise before you judge. The important design decision is that validation returns a reason code, not a bare boolean:

python
def validate_aadhaar(raw: str) -> tuple[bool, str]:
    candidate = normalise(raw)
 
    if not candidate.isdigit():
        return False, REASON_NOT_NUMERIC
    if len(candidate) != AADHAAR_LENGTH:
        return False, REASON_WRONG_LENGTH
    if candidate[0] not in VALID_FIRST_DIGITS:
        return False, REASON_BAD_FIRST_DIGIT
    if not verhoeff_validate(candidate):
        return False, REASON_CHECKSUM_FAILED
    return True, REASON_OK

Each reason code diagnoses a different upstream disease. wrong_length usually means a numeric cast somewhere stripped digits — the classic Excel-ate-my-identifier failure. checksum_failed means a typo or an OCR misread of an otherwise plausible number. bad_first_digit or a run of 111111111111 (which fails the checksum) points at fabricated placeholder data. A boolean tells you you have a problem; the reason code tells you which system to go shout at.

#The quarantine pattern

Where does this run? At the ingestion edge, as a split into two streams — clean rows flow on, rejects land in a quarantine table with their reason code. In Spark:

python
checked = incoming.withColumn("check", check_aadhaar(F.col("aadhaar")))
 
clean = checked.filter(F.col("check.is_valid") == "true").drop("check")
 
quarantine = (
    checked.filter(F.col("check.is_valid") == "false")
    .withColumn("reject_reason", F.col("check.reason"))
    .withColumn("aadhaar_masked", F.col("check.masked"))
    .drop("check", "aadhaar")  # the raw value stops here
)

Note the last line. An Aadhaar number is sensitive PII under the Aadhaar Act, and the reject path is exactly where engineers get sloppy — raw values dumped into error logs and quarantine tables that nobody ever purges. The quarantine row carries only the masked form, XXXX XXXX 9012, which is enough for a human to chase the source record without your reject table becoming a breach.

The algorithm earns its keep a second time in the other direction. Because the check digit is computable, you can generate structurally valid numbers on demand — and that is exactly what dev and test environments need. Instead of masking production Aadhaar numbers (and praying the masking job never misses a copy), seed your test fixtures with synthetic numbers built by generate_check_digit: they pass every structural gate in the pipeline, exercise every code path, and correspond to nobody. Every test vector in the companion repo is produced this way; no real identity appears anywhere in it.

#What this does not prove

One caveat, and it is the one that keeps this honest: a passing checksum proves a number is well-formed, not that it is real. 999999999999 sails through every structural check — twelve digits, starts with 9, valid Verhoeff check digit. This gate is data-quality tooling, not KYC verification; actual verification is UIDAI's authentication APIs, with consent, through the front door. What the gate gives you is the other direction: every number that fails is certainly wrong, and you learn it for free, at ingestion time, before it poisons a customer dimension.

The repo contains the full implementation, the Spark job, and — my favourite part — tests that verify the algorithm's actual claim: for a sample of generated numbers, every single-digit corruption and every adjacent transposition is exhaustively mutated and must fail validation. Thirty lines of 1969 group theory, quietly doing data-quality work on a billion identities.

Share

Related