We introduce a data structure that allows for efficient (probabilistic) presence proofs and non-probabilistic absence proofs in a bandwidth efficient and secure way. The Bloom tree combines the idea of Bloom filters with that of Merkle trees. Bloom filters are used to verify the presence, or absence of elements in a set. In the case of the Bloom tree, we are interested to verify and transmit the presence, or absence of an element in a secure and bandwidth efficient way to another party. Instead of sending the whole Bloom filter to check for the presence, or absence of an element, the Bloom tree achieves efficient verification by using a compact Merkle multiproof. For more information on the bloom tree, please refer to the original paper.
go get github.com/labbloom/bloom-treebloom-tree generates a Merkle tree from a BloomFilter interface which implements the methods: Proof, BitArray, MapElementToBF, NumOfHashes, and GetElementIndicies (The DBF package implements all of the mentioned methods). To construct a Bloom tree, a given bloom filter gets first split into pre-defined chunks. Those chunks become then leaves of a Merkle tree. The default chunk size is 64 bytes. To change the chunk size, one must use the SetChunkSize method. Chunks must be divisible by 64.
After construction of the tree, compact Merkle multiproofs can be generated and verified.
package main
import (
"fmt"
"log"
"github.com/labbloom/DBF"
bloomtree "github.com/labbloom/bloom-tree"
)
func main() {
// Data for the bloom filter
data := [][]byte{
[]byte("Foo"),
[]byte("Bar"),
[]byte("Baz"),
}
seed := []byte("secret seed")
dbf := DBF.NewDbf(200, 0.2, seed)
for _, d := range data {
dbf.Add(d)
}
// specify the chunk size, the value must be divisible by 64
bloomtree.SetChunkSize(64)
// Create the bloom tree
bt, err := bloomtree.NewBloomTree(dbf)
if err != nil {
panic(err)
}
// Generate compact multiproof for element "Foo"
multiproof, err := bt.GenerateCompactMultiProof([]byte("Foo"))
if err != nil {
panic(err)
}
// if ProofType is equal to 255, it is a presence proof. Any other value means that it is an absence proof.
if multiproof.ProofType == 255 {
log.Printf("the proof type for element %s is a presence proof\n", []byte("Foo"))
} else {
log.Printf("the proof type for element %s is an absence proof\n", []byte("Foo"))
}
verified, err := bloomtree.VerifyCompactMultiProof([]byte("Foo"), seed, multiproof, bt.Root(), bt.GetBloomFilter())
if err != nil {
panic(err)
}
if !verified {
panic(fmt.Sprintf("failed to verify proof for %s", []byte("Foo")))
}
}