What actually lets Firefox check revocation for the entire Web Public Key Infrastructure in a few megabytes?

What actually lets Firefox check revocation for the entire Web Public Key Infrastructure in a few megabytes?

The answer is CRLite, and the mechanism is a worked example of probabilistic data structures meeting a real security need.

Revocation at web scale is a data problem. Certificate Revocation Lists (CRLs, RFC 5280) are large and stale; OCSP (RFC 6960) is per-query and privacy-leaking. CRLite, from a 2017 IEEE S&P paper by Larisch et al. and now shipping in Firefox, asks: can we push the full revocation state of every publicly-trusted certificate to the client?

The enabling insight is Certificate Transparency. Because CT logs (RFC 6962) enumerate essentially all issued certificates, the universe of certificates is knowable. CRLite encodes the revoked subset against that known universe using a cascade of Bloom filters. A single Bloom filter has false positives; a cascade layers additional filters trained only on the items the previous layer got wrong, driving the aggregate false-positive rate to zero over the known set.

The result compresses hundreds of millions of certificates' revocation status into roughly 1–10 MB, with daily delta updates. Lookups are local, instant, and leak nothing to the CA.

The constraint: it only works for certificates the client's filter knows about, so it depends on comprehensive CT coverage and timely updates.

Further reading: Larisch et al., "CRLite" (IEEE S&P 2017); RFC 6962; Mozilla's CRLite rollout posts.

Bottom line: CRLite turns revocation into a local lookup by exploiting CT's complete certificate census plus a zero-false-positive Bloom filter cascade.