bloomtree

README

The Bloom Tree

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.

Install

go get github.com/labbloom/bloom-tree

Usage

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

Example

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")))
	}
}

License

Apache-2.0

Documentation

Index

• func CheckProofType(proofType uint8) bool
• func SetChunkSize(v int) error
• func VerifyCompactMultiProof(element, seedValue []byte, multiproof *CompactMultiProof, root [32]byte, ...) (bool, error)
• type BloomFilter
• type BloomTree
  • func NewBloomTree(b BloomFilter) (*BloomTree, error)
  • func (bt *BloomTree) GenerateCompactMultiProof(elem []byte) (*CompactMultiProof, error)
  • func (bt *BloomTree) GetBloomFilter() BloomFilter
  • func (bt *BloomTree) Root() [32]byte
• type CompactMultiProof

Functions

func CheckProofType

func CheckProofType(proofType uint8) bool

func SetChunkSize

func SetChunkSize(v int) error

func VerifyCompactMultiProof

func VerifyCompactMultiProof(element, seedValue []byte, multiproof *CompactMultiProof, root [32]byte, bf BloomFilter) (bool, error)

VerifyCompactMultiProof return whether the multi proof provided is true or false. The proof type can be absence or presence

Types

type BloomFilter

type BloomFilter interface {
	Proof([]byte) ([]uint64, bool)
	BitArray() *bitset.BitSet
	MapElementToBF([]byte, []byte) []uint
	NumOfHashes() uint
	GetElementIndices([]byte) []uint
}

type BloomTree

type BloomTree struct {
	// contains filtered or unexported fields
}

BloomTree represents the bloom tree struct.

func NewBloomTree

func NewBloomTree(b BloomFilter) (*BloomTree, error)

NewBloomTree creates a new bloom tree.

func (*BloomTree) GenerateCompactMultiProof

func (bt *BloomTree) GenerateCompactMultiProof(elem []byte) (*CompactMultiProof, error)

GenerateCompactMultiProof returns a compact multiproof to verify the presence, or absence of an element in a bloom tree.

func (*BloomTree) GetBloomFilter

func (bt *BloomTree) GetBloomFilter() BloomFilter

func (*BloomTree) Root

func (bt *BloomTree) Root() [32]byte

Root returns the Bloom Tree root

type CompactMultiProof

type CompactMultiProof struct {
	// Chunks are the leaves of the bloom tree, i.e. the bloom filter values for given parts of the bloom filter.
	Chunks [][32]byte
	// Proof are the hashes needed to reconstruct the bloom tree root.
	Proof [][32]byte
	// ProofType is 255 if the element is present in the bloom filter. it returns the index of the index if the element is not present in the bloom filter.
	ProofType uint8
}