Further minimizing the redundancy in Neutrino filters (BIP158 / Golomb sets)
Last year saw the introduction of BIP158 and Neutrino wallet which use Golomb-coded sets to very efficiently encode which items are in bitcoin blocks.
The basic idea in BIP158 is that we have N items of interest (such as distinct scriptPubKeys) in a block, which we hash to integers in the interval [0,F-1] for some range F that is much larger than N. These are basically short hashes, but with an uneven number of bits. This set of hashes can be queried to check whether a candidate scriptPubKey might be in a block, by computing the hash for the candidate and checking if that integer is in the set. The false positive rate is approximately N/F, and can be therefore tuned by making F larger or smaller.
Golomb-Rice comes into play by providing a very size-efficient way of encoding the list of hashes (by sorting them and encoding just the differences with an entropy-optimized code), which is important for minimizing over