4 ms·

Using Bloom filters to efficiently synchronise hash graphs

171 points by ignoramous 6y ago

wiml 6y ago
This is nice. How does it compare to something like a polynomial based representation like in [1] (used by the old keyserver gossip network)? I find Bloom filters more intuitive to reason about, but [1] does mention them as prior work and seems to think its scheme outperforms them. [1] http://dx.doi.org/10.1109/TIT.2003.815784 http://dx.doi.org/10.1109/TIT.2003.815784 http://ipsit.bu.edu/documents/ieee-it3-web.pdf http://ipsit.bu.edu/documents/ieee-it3-web.pdf
- thomasahle 6y ago
  I think the approaches based on invertible bloom filters are generally more efficient. https://dl.acm.org/doi/abs/10.1145/2043164.2018462 https://dl.acm.org/doi/abs/10.1145/2043164.2018462 (What's the difference?: efficient set reconciliation without prior context) 2011 https://link.springer.com/article/10.1007/s00446-017-0316-0 https://link.springer.com/article/10.1007/s00446-017-0316-0 (Simple Multi-Party Set Reconciliation) 2015 They both briefly mention the Minsky paper.
  - nullc 6y ago
    > I think the approaches based on invertible bloom filters are generally more efficient. More computationally efficient for sure, but their communications efficiency is only good asymptotically. For "small" cases such as where the set difference has a few hundred or thousand entries and especially where the set members are small (e.g. <=64-bit hashes) there is a pretty large constant factor needed to get a low failure rate from invertible bloom filters. E.g. for a set difference of size 128 we measured that you need 32x communications overhead to get a 1 in 10,000 failure rate. 8x overhead for 2048 items. The issue is that iblt decodability depends on the non-existence of cycles in a random graph and this only holds for sufficiently large graphs. For applications (such as Bitcoin transaction relay or -- I think -- SCM commits) which frequently synchronize a small number of items these communications overheads take that approach entirely out of the running. Fortunately, at these sizes the quadratic computation of communications efficient approaches is not a big deal. Interestingly, it is completely unambiguous that IBLT and dense code based reconciliation can be combined (sort of the dual to Raptor codes, which combine sparse fountain codes and dense RS-like codes for block erasure recovery)-- but it's an open question if the combination can capture the advantages of both approaches (linear time decode and concrete communications efficiency (as opposed to asymptotic)) for set reconciliation as is the case for block erasure codes.
    - thomasahle 6y ago
      Interesting! I'm thinking even polynomial methods can "fail" if you underestimated the difference didn't send a big enough sketch. Won't you have to do some sort of exponential fallback anyway to cover that case? If so, you could also use a lower overhead in the IBT and just rely on the same fallback mechanism.
      - nullc 6y ago
        Depending on your communications cost model there is no reason to use an exponential backoff with pinsketch: you can just send one (or N) more sketch-entries at a time. At a cost of one or two extra entries total, you can tell if you have enough before doing the costly computation. [There are some utility functions in minisketch that tell you how much overhead you need to make all failures fast-detectable with a cryptographic level of certainty, it's typically a tiny amount] Your application may also know by construction that the symmetric difference won't be larger than expected. This is the case for e.g. biometric key generation-- if the difference larger than expected it just means the auth failed. Likewise for using pinsketch for anonymous communication. If you notice on our graphs IBLT never gets to particularly low overhead-- at least for small keys, even when you accept low reliability. Efficient fallback also doesn't work quite as well for iblt: For pinsketch when the sketch is too small you can send more entries (a shorter sketch is just a prefix of a longer sketch), which is perfectly efficient (+/- rtt costs). You can also bisect the sketch by splitting into two sketches with an arbitrary hash function and conserve your prior communication: you send the sketch of just the left half and the receiver can get the sketch of the right half by xoring the left with the parent sketch. Bisection has communications overhead because splitting will not distribute items perfectly equally. For pinsketch the only reason you'd do the bisection thing instead of extending the sketch is because decoding has O(N^2) computational cost, but for IBLT bisection is the only option on failure other than totally start over with a bigger sketch (and waste all the prior bandwidth). Unfortunately the bisection approach doesn't work as well on IBLT because while pinsketch will be successful in every split segment as soon as that segment is under capacity, IBLT will also continue to fail until the splitting removes all cycles from each segment. So you get inefficiency both from imbalance and from the need to eliminate cycles. Obviously, what trade-offs will make the most sense depends on the application. We've contemplated adding IBLT to minisketch as an option, particularly because the two approaches can be combined in several different ways: e.g. IBLTs where the buckets are small pinsketches just works(tm)) or e.g. when IBLTs fail they often decode most differences but have a few cycles, a small parallel pinsketch can have the known differences removed and resolve the cycles.
nullc 6y ago
It's possible to be dramatically more communication efficient than bloom filters to synchronize sets. Bloom filters require O(my_set_size) bandwidth, with a good constant factor. This work optimizes it somewhat by excluding members that existed at the time of last synchronization, but it still wastes bandwidth when those commits came in from another source. It's possible to instead realize O(symmetric_difference_between_sets) when synchronizing a pair. Applied to this kind of usage the bandwidth required would be reduced by whatever redundancy factor (e.g. number of different repos you'd learn the same commit from). This can be accomplished via error correcting codes, for a high performance industrial implementation I contributed to, see: https://github.com/sipa/minisketch/ https://github.com/sipa/minisketch/ (I tried submitting this to HN a while back, but no joy--). For our paper on applying this to Bitcoin transaction relay to render rumouring bandwidth largely independent of peer count: https://arxiv.org/abs/1905.10518 https://arxiv.org/abs/1905.10518 [Similar to the motivations of the post, we consider immunity to attackers to be critical-- and most prior efficient gossip work is extremely non-robust.] For the specific case of synchronizing the blockchain itself, these fancy techniques aren't needed because there is only a single best chain 'list'-- there is only one relevant tip-- and it can be efficiently synchronized with bisection. Bitcoin sends up to 100 hashes at once (though usually more like 30), the first few dense around the best tip and the rest exponentially spaced to extremely efficiently find the highest point of commonalty.
- dochtman 6y ago
  This sounds very interesting, so I tried reading some of the math in https://github.com/sipa/minisketch/blob/master/doc/math.md 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?

171 points by ignoramous 6y ago

wiml 6y ago

This is nice. How does it compare to something like a polynomial based representation like in [1] (used by the old keyserver gossip network)? I find Bloom filters more intuitive to reason about, but [1] does mention them as prior work and seems to think its scheme outperforms them. [1] http://dx.doi.org/10.1109/TIT.2003.815784 http://dx.doi.org/10.1109/TIT.2003.815784 http://ipsit.bu.edu/documents/ieee-it3-web.pdf http://ipsit.bu.edu/documents/ieee-it3-web.pdf

thomasahle 6y ago
I think the approaches based on invertible bloom filters are generally more efficient. https://dl.acm.org/doi/abs/10.1145/2043164.2018462 https://dl.acm.org/doi/abs/10.1145/2043164.2018462 (What's the difference?: efficient set reconciliation without prior context) 2011 https://link.springer.com/article/10.1007/s00446-017-0316-0 https://link.springer.com/article/10.1007/s00446-017-0316-0 (Simple Multi-Party Set Reconciliation) 2015 They both briefly mention the Minsky paper.
- nullc 6y ago
  > I think the approaches based on invertible bloom filters are generally more efficient. More computationally efficient for sure, but their communications efficiency is only good asymptotically. For "small" cases such as where the set difference has a few hundred or thousand entries and especially where the set members are small (e.g. <=64-bit hashes) there is a pretty large constant factor needed to get a low failure rate from invertible bloom filters. E.g. for a set difference of size 128 we measured that you need 32x communications overhead to get a 1 in 10,000 failure rate. 8x overhead for 2048 items. The issue is that iblt decodability depends on the non-existence of cycles in a random graph and this only holds for sufficiently large graphs. For applications (such as Bitcoin transaction relay or -- I think -- SCM commits) which frequently synchronize a small number of items these communications overheads take that approach entirely out of the running. Fortunately, at these sizes the quadratic computation of communications efficient approaches is not a big deal. Interestingly, it is completely unambiguous that IBLT and dense code based reconciliation can be combined (sort of the dual to Raptor codes, which combine sparse fountain codes and dense RS-like codes for block erasure recovery)-- but it's an open question if the combination can capture the advantages of both approaches (linear time decode and concrete communications efficiency (as opposed to asymptotic)) for set reconciliation as is the case for block erasure codes.
  - thomasahle 6y ago
    Interesting! I'm thinking even polynomial methods can "fail" if you underestimated the difference didn't send a big enough sketch. Won't you have to do some sort of exponential fallback anyway to cover that case? If so, you could also use a lower overhead in the IBT and just rely on the same fallback mechanism.
    - nullc 6y ago
      Depending on your communications cost model there is no reason to use an exponential backoff with pinsketch: you can just send one (or N) more sketch-entries at a time. At a cost of one or two extra entries total, you can tell if you have enough before doing the costly computation. [There are some utility functions in minisketch that tell you how much overhead you need to make all failures fast-detectable with a cryptographic level of certainty, it's typically a tiny amount] Your application may also know by construction that the symmetric difference won't be larger than expected. This is the case for e.g. biometric key generation-- if the difference larger than expected it just means the auth failed. Likewise for using pinsketch for anonymous communication. If you notice on our graphs IBLT never gets to particularly low overhead-- at least for small keys, even when you accept low reliability. Efficient fallback also doesn't work quite as well for iblt: For pinsketch when the sketch is too small you can send more entries (a shorter sketch is just a prefix of a longer sketch), which is perfectly efficient (+/- rtt costs). You can also bisect the sketch by splitting into two sketches with an arbitrary hash function and conserve your prior communication: you send the sketch of just the left half and the receiver can get the sketch of the right half by xoring the left with the parent sketch. Bisection has communications overhead because splitting will not distribute items perfectly equally. For pinsketch the only reason you'd do the bisection thing instead of extending the sketch is because decoding has O(N^2) computational cost, but for IBLT bisection is the only option on failure other than totally start over with a bigger sketch (and waste all the prior bandwidth). Unfortunately the bisection approach doesn't work as well on IBLT because while pinsketch will be successful in every split segment as soon as that segment is under capacity, IBLT will also continue to fail until the splitting removes all cycles from each segment. So you get inefficiency both from imbalance and from the need to eliminate cycles. Obviously, what trade-offs will make the most sense depends on the application. We've contemplated adding IBLT to minisketch as an option, particularly because the two approaches can be combined in several different ways: e.g. IBLTs where the buckets are small pinsketches just works(tm)) or e.g. when IBLTs fail they often decode most differences but have a few cycles, a small parallel pinsketch can have the known differences removed and resolve the cycles.

nullc 6y ago

It's possible to be dramatically more communication efficient than bloom filters to synchronize sets. Bloom filters require O(my_set_size) bandwidth, with a good constant factor. This work optimizes it somewhat by excluding members that existed at the time of last synchronization, but it still wastes bandwidth when those commits came in from another source. It's possible to instead realize O(symmetric_difference_between_sets) when synchronizing a pair. Applied to this kind of usage the bandwidth required would be reduced by whatever redundancy factor (e.g. number of different repos you'd learn the same commit from). This can be accomplished via error correcting codes, for a high performance industrial implementation I contributed to, see: https://github.com/sipa/minisketch/ https://github.com/sipa/minisketch/ (I tried submitting this to HN a while back, but no joy--). For our paper on applying this to Bitcoin transaction relay to render rumouring bandwidth largely independent of peer count: https://arxiv.org/abs/1905.10518 https://arxiv.org/abs/1905.10518 [Similar to the motivations of the post, we consider immunity to attackers to be critical-- and most prior efficient gossip work is extremely non-robust.] For the specific case of synchronizing the blockchain itself, these fancy techniques aren't needed because there is only a single best chain 'list'-- there is only one relevant tip-- and it can be efficiently synchronized with bisection. Bitcoin sends up to 100 hashes at once (though usually more like 30), the first few dense around the best tip and the rest exponentially spaced to extremely efficiently find the highest point of commonalty.

dochtman 6y ago
This sounds very interesting, so I tried reading some of the math in https://github.com/sipa/minisketch/blob/master/doc/math.md 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?