Earlier quoted context omitted.
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. (I'm one of the authors of CRLite in Firefox: https://insufficient…
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…
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.)