4 ms·

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 filte

by 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.

by wiml 6y ago

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.