Item — HN Reader

This sounds very interesting, so I tried reading some of the math in https://github.com/sipa/minisketch/blob/master/doc/math.md (I'm not great this kind of math).

In my understanding, a Bloom filter, while being O(set_size), nonetheless has a small multiplier for the linear factor (in the OP I think they mentioned using 10 bits). As I read the PinSketch setup, it looks like it would actually need the full bit size of the set members, so for SHA-256 you need the full 256 bits per set member. So while PinSketch would only need O(symmetric_difference_between_sets), the element size factor is ~25 times larger?

And also, in the example from the minisketch readme, it looks A still needs to send the full sketch (not just the symdiff) in the first message, right?

In other words, there are a bunch of trade-offs here that might very much depend on your application?

2 comments

You can make the hashes you as small as you like-- subject to the limitation that you'll get false positives if you make it too small ---- the same problem that small hashes get in bloom filters.

Bloom filters also have poor communications efficiencies for small numbers of entries: you have to oversize the filter a lot. This can be ameliorated by entropy coding the oversized bloom filter, but once you're going that far you're better off with using a golumb coded set or something more efficient.

I think the only case where an approximate set-filter approach will be more efficient is where you want to communicate a small set one way to someone whos set is much larger. The issue there is the the sketch needs one entry per item it removes, while a bloom filter can be smaller (assuming the difference is big enough to overcome the bloom overheads).

Information theoretically it should be possible to decode a minisketch 'beyond the limit' using knowledge of the specific items in the local set. ... but the only algorithm I know for this has exponential time (brute force remove items from your set and retry the reconstruction). This problem is mathematically pretty close to list-input decoding a error correcting code, so efficient algorithms may be possible-- but so far there hasn't been any research to that end.

[You can, of course, combine a filter with efficient reconciliation in cases where an set size differences are expected. The filter's FP rate just needs to be low enough to get the receivers set size close to the sender's]

> it looks A still needs to send the full sketch

The sketch is exactly the same size as the symdiff it can recover.

An interesting challenge is that you likely don't know in advance how big the symdiff is... If you're too conservative you waste bandwidth, but never more bandwidth then you use sending the whole set. You can reduce your waste at the expense of round-trips, in an obvious manner: fetching a little more of the sketch each time until you have enough.

In the erlay paper (bitcoin application of this stuff), we give a scheme to bisect when the difference is bigger than expected without wasting much bandwidth. The bisection loses a little communications efficiency but avoids quadratic computation costs which become problematic for big set differences.

It depends on the protocol requirements. If you have 256-bit data elements to reconcile, and want 100% guarantee that reconciliation will succeed with 1 round-trip, then you'll indeed need to use sketches with 256-bit elements.

However, if you're fine with more roundtrips, or probabilistic reconciliation, you can typically use far smaller elements. Have the parties agree on a random salt, and construct sketches of short salted hashes of your data elements (where the size of these hashes depends on your tolerance for failure due to collisions in your sets). Run the reconciliation algorithm to figure out the difference, and then send/request the real elements based on their short hashes.