A Bloom-Filter is a datastructure which helps to find differences in a set. The datastructure is probabilistic and was invented by Burton Howard Bloom in 1970. The most important building block is a good fitting hash function (number of collisions should be low enough for the use case).
This repo contains simple implementations for the Bloom Filters specified in RFC-Draft about Byzantine Fault Tolerant Set Reconciliation
Three different level of the Bloom-Filter datastructure are implemented:
- Basic Bloom Filter: Most basic
- Counting Bloom Filter: Counts number of elements
- Invertible Bloom Filter: Most advanced implementation allowing decoding and set differences
More information on Wikipedia about Bloom filter
Be aware that I implemented the structure to get a grasp of how bloom filters work and that I made some simplifications. This could lead to inaccuracies regarding the spec or simply lead to bugs ;)