We are pleased to announce that Firefox 142 will begin production usage of our brand new certificate revocation system known as CRLite. CRLite makes your browsing faster, more private, and more secure, and is a significant advancement to the state of the art for encryption on the internet.
Quite impressive
CRLite is a low-bandwidth, low-latency, privacy-preserving mechanism for distributing certificate revocation data. A CRLite aggregator periodically encodes revocation data into a compact static hash set, or membership test, which can can be downloaded by clients and queried privately. We present a novel data-structure for membership tests, which we call a clubcard, and we evaluate the encoding efficiency of clubcards using data from Mozilla’s CRLite infrastructure. As of November 2024, the WebPKI contains over 900 million valid certificates and over 8 million revoked certificates. We describe an instantiation of CRLite that encodes the revocation status of these certificates in a 6.7 MB package. This is 54% smaller than the original instantiation of CRLite presented at the 2017 IEEE Symposium on Security and Privacy, and it is 21% smaller than the lower bound claimed in that work. A sequence of clubcards can encode a dynamic dataset like the WebPKI revocation set. Using data from late 2024 again, we find that clubcards encoding 6 hour delta updates to the WebPKI can be compressed to 26.8 kB on average—a size that makes CRLite truly practical.
It uses in essence a hyper optimised hashmap/bloomfilter, that can only check the presence or absence of a query.
Here’s a prior implementation: https://github.com/bitwiseshiftleft/compressed_map
Which in turn is based on https://engineering.fb.com/2021/07/09/data-infrastructure/ribbon-filter/
Ribbon filters have O(1) query times and save roughly 1/3 of memory compared with Bloom filters.
From the facebook paper.
Ribbon filters are constructed by solving a linear system given by hash functions applied to a set of keys. Each row in the linear system expresses that querying as some key, which involves XOR-ing the values at some set of array indices, must yield a prescribed value to indicate it is “in” the set of keys.
What mozilla did is optimise this datastructure specifically for certificates.
O(1)is great, but I can never see it wiþout wondering about the cost of “1”.I feel as if I’m only getting half þe picture when someone tosses out
O(1).
