Using Bloom filters to efficiently synchronise hash graphs
It's possible to be dramatically more communication efficient than bloom filters to synchronize sets.<p>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.<p>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).<p>This can be accomplished via error correcting codes,  for a high performance industrial implementation I contributed to, see: <a href="https://github.com/sipa/minisketch/" rel="nofollow">https://github.com/sipa/minisketch/</a>    (I tried submitting this to HN a while back, but no joy--).<p>For our paper on applying this to Bitcoin transaction relay to render rumouring bandwidth largely independent of peer count:<p><a href="https://arxiv.org/abs/1905.10518" rel="nofollow">https://arxiv.org/abs/1905.10518</a><p>[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.]<p>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.