Expand description
UNSTABLE / EXPERIMENTAL
Clubcard is a compact data-structure that solves the exact membership query problem.
Given some universe of objects U, a subset R of U, and two hash functions defined on U (as
described below), Clubcard outputs a compact encoding of the function f : U -> {0, 1} defined
by f(x) = 0 if and only if x ∈ R.
Clubcard is based on the Ribbon filters from
And some ideas from Mike Hamburg’s RWC 2022 talk
- https://rwc.iacr.org/2022/program.php#abstract-talk-39
- https://youtu.be/Htms5rNy7B8?list=PLeeS-3Ml-rpovBDh6do693We_CP3KTnHU&t=2357
The construction will be described in detail in a forthcoming paper.
At a high level, a clubcard is a pair of matrices (X, Y) defined over GF(2). The hash functions h and g map elements of U to vectors in the domain of X and Y respectively.
The matrix X is a solution to H * X = 0 where the rows of H are obtained by hashing the
elements of R with h. The number of columns in X is floor(lg(|U\R| / |R|)).
The matrix Y is a solution to G * Y = C where the rows of G are obtained by hashing, with g,
the elements u ∈ U for which h(u) * X = 0. The matrix Y has one column. The rows of C encode
membership in R.
Given (X, Y) and an element u ∈ U, we have that u ∈ R iff h(u) * X == 0 and g(u) * Y = 0.
Clubcard was developed to replace the use of Bloom cascades in CRLite. In a preliminary experiment using a real-world collection of 12.2M revoked certs and 789.2M non-revoked certs, the currently-deployed Bloom cascade implementation of CRLite produces a 19.8MB filter in 293 seconds (on a Ryzen 3975WX with 64GB of RAM). This Clubcard implementation produces an 8.5MB filter in 200 seconds.
Structs§
- Clubcard
- A queryable Clubcard
- Clubcard
Index Entry - Metadata needed to compute membership in a clubcard.
- Equation
- An Equation<W> is a representation of a GF(2) linear functional a(x) = b + sum_i a_i x_i where a_i is equal to zero except for i in a block of 64*W coefficients starting at i=s. We say an Equation is /aligned/ if a_s = 1. (Note: a_i above denotes the i-th bit, not the i’th 64-bit limb.)
Enums§
Traits§
- Approximate
Size Of - Helper trait for (approximate) heap memory usage analysis in Firefox
- AsQuery
- Filterable
- A Filterable is an item that can be inserted into a RibbonBuilder.
- Queryable
- A Queryable is an item that can be passed to Clubcard::contains.
Type Aliases§
- Clubcard
Index - Lookup table from block identifiers to block metadata.