CRLite builds a cascade of Bloom filters to ensure no false positives.
For Firefox end users, a certificate only gets tested against the filter cascade if it is known to have been included in its creation (by examining the embedded SCT timestamps). If it's not definite that the certificate was used to generate the filter, then Firefox reverts to OCSP.
Ahh thanks for the link and sorry for the snark; the finite universe optimization is cool! [0]
# Why is CRLite able to compress so much data?
Bloom filters are probabilistic data structures with an error rate due to data collisions. However, if you know the whole range of data that might be tested against the filter, you can compute all the false positives and build another layer to resolve those. Then you keep going until there are no more false positives. In practice, this happens in 25 to 30 layers, which results in substantial compression.
EDIT: Is there any risk of filter blow up (think 1000's of layers) if a CA did a mass revocation (maybe some root key leak)?
Mozilla worked with some researchers to analyze a bunch of degenerate cases like that and basically the answer is 'no', that the CRLite paper's calculation of an optimal false positive rate per layer works out quite well.
What does happen in CRLite is that you can't keep shipping the tiny "stash" updates to clients, you have to mint a whole new .mlbf filter file, which is about a megabyte. [Edit:] Then you can resume the "stash" updates from there, but the ecosystem 'shock' requires a regeneration of the filter.
(There was supposed to be a blogpost on the Mozilla blog from the research teams; I don't know if it was ever written.)
J.C. has already answered for Firefox; for Apple's system (valid.apple.com), if there's a bloom filter hit, the client double checks via OCSP before failing the connection.
Source: a WWDC 2017 talk which unfortunately I can't find online anymore
A concern is: Does it fail closed? It's easy to imagine an Apple engineer finds this fails sometimes for crap-CA whose OCSP server is kinda-sorta maybe working, in Bremen at least, usually, although not on weekends, and they go "Oh, I can fix this, just ignore if it fails" and now we've got our old friend the "Seatbelt that snaps when you crash" back.
Mozilla's choice here avoids that problem coming up which means nobody needs to push back when it gets "solved" in this regressive way.
That is a very good question and I don't know the answer, but if you want to go source code spelunking, you can probably find the answer on https://opensource.apple.com/
For Firefox end users, a certificate only gets tested against the filter cascade if it is known to have been included in its creation (by examining the embedded SCT timestamps). If it's not definite that the certificate was used to generate the filter, then Firefox reverts to OCSP.
(I'm one of the authors of CRLite in Firefox: https://insufficient.coffee/2020/12/01/crlite-part-4-infrast... )