How a patricia trie made RPKI validation 500× faster.

RPKI — the Resource Public Key Infrastructure — is the closest thing the Internet has to a source of truth about who's allowed to announce which prefixes. The TAL files publish hundreds of thousands of signed ROAs (Route Origin Authorizations). Each ROA says: this origin ASN is allowed to announce this prefix, up to this length. If a BGP announcement's (origin, prefix) pair doesn't match any covering ROA, it's RPKI invalid — and a hijack is suddenly very loud.

NetPulse's job is to listen to a BGP feed (the RIPE RIS live stream) and, for each UPDATE, decide if the announcement is a hijack or a leak. The detector ensembles three signals; rpki_invalid is the cheapest and most informative one. So that signal has to be fast — line-rate fast.

The slow version

My first cut was the obvious one. Load all 859,043 VRPs into a flat list. For each announcement, linear-scan the list looking for any ROA that covered the prefix and matched the origin. Roughly:

# the slow version
def validate(announce, vrps):
    for vrp in vrps:
        if announce.prefix.subnet_of(vrp.prefix) \
           and announce.prefix.prefixlen <= vrp.maxlen \
           and announce.origin == vrp.asn:
            return Validation.VALID
    return Validation.UNKNOWN

The benchmark on my laptop: 43.2 ms / call recorded · BENCHMARK.md. Fine for offline analysis. Useless at line rate — RIPE RIS pushes BGP UPDATEs faster than that, and you can't miss any.

The insight

VRPs are prefixes. The natural lookup over prefixes is longest-prefix-match — exactly what every Internet router does for forwarding decisions. The data structure that's been doing this in routing tables for forty years is a patricia trie: a binary trie keyed on network bits, compressed to skip identical stretches.

Build once. Walk it bit-by-bit on lookup. O(prefix_length) — roughly 32 hops for IPv4. The trie is also a perfect fit for “is there a covering ROA at any length up to maxlen?” — the trie walk naturally surfaces every ancestor.

The fix

# longest-prefix-match index: 500× faster than linear
class RPKIIndex:
    def __init__(self, vrps: Iterable[VRP]):
        self.trie = PatriciaTrie()
        for vrp in vrps:
            self.trie.insert(vrp.prefix, vrp)

    def validate(self, a: Announce) -> Validation:
        cov = self.trie.longest_prefix(a.prefix)
        if not cov: return Validation.UNKNOWN
        if a.origin in cov.allowed_origins:
            return Validation.VALID
        return Validation.INVALID

The numbers

New benchmark, same machine, same 859k-VRP dataset, same 1,000-call workload:

500× speedup. Suddenly RPKI validation isn't a bottleneck; it's free. The detector can run live against the RIS Live WebSocket and still have ~99.99% of its time budget left for the other two signals.

Lessons I keep relearning

1. Data structures matter more than language. Rewriting the linear scan in Rust would have bought maybe 5×. The trie bought 500× in Python.
2. The right structure is often the boring one. A patricia trie isn't novel — routers have used them since the eighties. The novelty was admitting that this lookup was equivalent to BGP forwarding and that the same tool applied.
3. Profile before optimising, then again after. After the trie, RPKI dropped off the flamegraph entirely and a previously-invisible path-validation step became the new hot spot. Optimisation reshapes the bottleneck list.

The detector is open source at github.com/pauti04/netpulse. The benchmark methodology is documented in BENCHMARK.md in the repo — happy to walk through it if you're curious.