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

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.