bloom

README

bloom

Package bloom provides an API for dealing with bitcoin-specific bloom filters. A comprehensive suite of tests is provided to ensure proper functionality. See test_coverage.txt for the gocov coverage report. Alternatively, if you are running a POSIX OS, you can run the cov_report.sh script for a real-time report.

Installation and Updating

$ go get -u github.com/cybriq/p9/bloom

Examples

• NewFilter Example
  Demonstrates how to create a new bloom filter, add a transaction hash to it, and check if the filter matches the transaction.

License

Package bloom is licensed under the copyfree ISC License.

Documentation

Index

• Variables
• func MurmurHash3(seed uint32, data []byte) uint32
• func NewMerkleBlock(block *block.Block, filter *Filter) (*wire.MsgMerkleBlock, []uint32)
• type Filter
  • func LoadFilter(filter *wire.MsgFilterLoad) *Filter
  • func NewFilter(elements, tweak uint32, fprate float64, flags wire.BloomUpdateType) *Filter
  • func (bf *Filter) Add(data []byte)
  • func (bf *Filter) AddHash(hash *chainhash.Hash)
  • func (bf *Filter) AddOutPoint(outpoint *wire.OutPoint)
  • func (bf *Filter) IsLoaded() bool
  • func (bf *Filter) MatchTxAndUpdate(tx *util.Tx) bool
  • func (bf *Filter) Matches(data []byte) bool
  • func (bf *Filter) MatchesOutPoint(outpoint *wire.OutPoint) bool
  • func (bf *Filter) MsgFilterLoad() *wire.MsgFilterLoad
  • func (bf *Filter) Reload(filter *wire.MsgFilterLoad)
  • func (bf *Filter) Unload()

Examples

• NewFilter

Variables

var F, E, W, I, D, T log.LevelPrinter = log.GetLogPrinterSet(subsystem)

Functions

func MurmurHash3

func MurmurHash3(seed uint32, data []byte) uint32

MurmurHash3 implements a non-cryptographic hash function using the MurmurHash3 algorithm. This implementation yields a 32-bit hash value which is suitable for general hash-based lookups. The seed can be used to effectively randomize the hash function. This makes it ideal for use in bloom filters which need multiple independent hash functions.

func NewMerkleBlock

func NewMerkleBlock(block *block.Block, filter *Filter) (*wire.MsgMerkleBlock,
	[]uint32,
)

NewMerkleBlock returns a new *wire.MsgMerkleBlock and an array of the matched transaction index numbers based on the passed block and filter.

Types

type Filter

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

Filter defines a bitcoin bloom filter that provides easy manipulation of raw filter data.

func LoadFilter

func LoadFilter(filter *wire.MsgFilterLoad) *Filter

LoadFilter creates a new Filter instance with the given underlying wire.MsgFilterLoad.

func NewFilter

func NewFilter(elements, tweak uint32, fprate float64,
	flags wire.BloomUpdateType,
) *Filter

NewFilter creates a new bloom filter instance, mainly to be used by SPV clients. The tweak parameter is a random value added to the seed value. The false positive rate is the probability of a false positive where 1.0 is "match everything" and zero is unachievable.

Thus, providing any false positive rates less than 0 or greater than 1 will be adjusted to the valid range. For more information on what values to use for both elements and fprate, see https://en.wikipedia.org/wiki/Bloom_filter.

Example

This example demonstrates how to create a new bloom filter, add a transaction hash to it, and check if the filter matches the transaction.

package main

import (
	"fmt"
	"math/rand"
	"time"

	"github.com/cybriq/p9/pkg/bloom"
	"github.com/cybriq/p9/pkg/chainhash"
	"github.com/cybriq/p9/pkg/wire"
)

func main() {
	rand.Seed(time.Now().UnixNano())
	tweak := rand.Uint32()
	// Create a new bloom filter intended to hold 10 elements with a 0.01% false positive rate and does not include any
	// automatic update functionality when transactions are matched.
	filter := bloom.NewFilter(10, tweak, 0.0001, wire.BloomUpdateNone)
	// Create a transaction hash and add it to the filter. This particular trasaction is the first transaction in block
	// 310,000 of the main bitcoin block chain.
	txHashStr := "fd611c56ca0d378cdcd16244b45c2ba9588da3adac367c4ef43e808b280b8a45"
	txHash, e := chainhash.NewHashFromStr(txHashStr)
	if e != nil {
		fmt.Println(e)
		return
	}
	filter.AddHash(txHash)
	// Show that the filter matches.
	matches := filter.Matches(txHash[:])
	fmt.Println("Filter Matches?:", matches)
}

Output:

Filter Matches?: true

func (*Filter) Add

func (bf *Filter) Add(data []byte)

Add adds the passed byte slice to the bloom filter.

This function is safe for concurrent access.

func (*Filter) AddHash

func (bf *Filter) AddHash(hash *chainhash.Hash)

AddHash adds the passed chainhash.Hash to the Filter.

This function is safe for concurrent access.

func (*Filter) AddOutPoint

func (bf *Filter) AddOutPoint(outpoint *wire.OutPoint)

AddOutPoint adds the passed transaction outpoint to the bloom filter.

This function is safe for concurrent access.

func (*Filter) IsLoaded

func (bf *Filter) IsLoaded() bool

IsLoaded returns true if a filter is loaded, otherwise false.

This function is safe for concurrent access.

func (*Filter) MatchTxAndUpdate

func (bf *Filter) MatchTxAndUpdate(tx *util.Tx) bool

MatchTxAndUpdate returns true if the bloom filter matches data within the passed transaction, otherwise false is returned. If the filter does match the passed transaction, it will also update the filter depending on the bloom update flags set via the loaded filter if needed. This function is safe for concurrent access.

func (*Filter) Matches

func (bf *Filter) Matches(data []byte) bool

Matches returns true if the bloom filter might contain the passed data and false if it definitely does not.

This function is safe for concurrent access.

func (*Filter) MatchesOutPoint

func (bf *Filter) MatchesOutPoint(outpoint *wire.OutPoint) bool

MatchesOutPoint returns true if the bloom filter might contain the passed outpoint and false if it definitely does not.

This function is safe for concurrent access.

func (*Filter) MsgFilterLoad

func (bf *Filter) MsgFilterLoad() *wire.MsgFilterLoad

MsgFilterLoad returns the underlying wire.MsgFilterLoad for the bloom filter. This function is safe for concurrent access.

func (*Filter) Reload

func (bf *Filter) Reload(filter *wire.MsgFilterLoad)

Reload loads a new filter replacing any existing filter.

This function is safe for concurrent access.

func (*Filter) Unload

func (bf *Filter) Unload()

Unload unloads the bloom filter. This function is safe for concurrent access.