Read the docs here
A Bloom filter is a space-efficient probabilistic data strucuture invented by Burton Bloom. They provide probabilistic set membership where elements can be checked if they exist in the bloom filter. There are no false negatives, but there are false positives that are dependent on size of filter, number of entries, and number of hashes. The math is described here. Inserting an element is: filter = hash(ele) | filter. Checking for existance is: filter == hash(ele) | filter. Bloom filters have many applications including cache filtering and P2P networks. For example, SPV nodes use bloom filters to help conceal their addresses. They do this by constructing a filter that will match transactions that are associated to their addresses and other transactions that are not associated to their addresses. Then they send this bloom filter to connected full nodes and recieve the transactions that match it. Full nodes can not be confident in which transactions are related to addresses of the SPV node.
A mock-up of the SPV functionality using this package!
$ go get "github.com/nettijoe96/bloom"
package main
import (
"fmt"
"github.com/nettijoe96/bloom"
)
func main() {
b, err := bloom.NewBloomFromCap(100) // a 512-bit bloom filter made to fit 100 elements
if err != nil {
fmt.Println("issue making bloom filter")
return
}
b.PutStr("hello")
exists, acc := b.ExistsStr("hello")
fmt.Printf("'hello' exists: %t, accuracy of result: %f\n", exists, acc)
}
- Possibly merge Bloom and BigBloom into one type