Matching 90,000 tracker domains with a reverse-label trie

For every DNS lookup, Vigil has to answer one question fast: is this a known tracker? The list it checks against is StevenBlack/hosts, an open-source hosts file of about 90,000 entries that the community maintains. I didn't build that list; Vigil bundles a copy. What I did build is how it's stored and matched, because the answer is needed on every query, on a phone, without making the app feel slow.

Why not a set

A plain set of strings answers "is this exact name on the list?" quickly. But trackers don't stay on one name. If ads.example.com is listed, so is x.y.ads.example.com for the purposes of this app. A set would need a lookup for every parent of the name, or a pass over the whole list.

Read the name from the right

Domains get more specific from right to left: com, then example, then ads. So the trie stores each domain's labels in reverse, one node per label. Inserting ads.example.com walks com, example, ads and marks the last node as the end of an entry.

fun insert(domain: String) {
    val labels = domain.split('.').filter { it.isNotEmpty() }
    if (labels.isEmpty()) return
    var node = root
    for (label in labels.reversed()) {
        node = node.children.getOrPut(label) { TrieNode() }
    }
    if (!node.isEnd) {
        node.isEnd = true
        _size++
    }
}

Lookup uses the same walk, with one extra line that does the real work: if any node along the path is marked as an end, the domain matches. That single check is how a listed domain automatically covers every subdomain beneath it.

fun matches(domain: String): Boolean {
    val labels = domain.split('.').filter { it.isNotEmpty() }
    if (labels.isEmpty()) return false
    var node = root
    for (label in labels.reversed()) {
        if (node.isEnd) return true
        node = node.children[label] ?: return false
    }
    return node.isEnd
}

The cost of a lookup is the number of labels in the name, a handful, no matter whether the list has a thousand entries or ninety thousand.

Loading it without lying

The bundled hosts file is parsed on a background dispatcher: comment lines are skipped, the address column is dropped, and entries like localhost and the ip6- names are ignored. Until loading finishes, classify() returns Unknown instead of Clean. The app has three verdicts, Tracker, Clean and Unknown, so a query that arrives before the list is ready is never wrongly shown as safe.