gcs

README

gcs

[] (https://travis-ci.org/brsuite/bronutil) ![ISC License] (http://img.shields.io/badge/license-ISC-blue.svg) [] (http://godoc.org/github.com/brsuite/bronutil/gcs)

Package gcs provides an API for building and using a Golomb-coded set filter similar to that described here.

A comprehensive suite of tests is provided to ensure proper functionality.

Installation and Updating

$ go get -u github.com/brsuite/bronutil/gcs

License

Package gcs is licensed under the copyfree ISC License.

Documentation

Overview

Package gcs provides an API for building and using a Golomb-coded set filter.

Golomb-Coded Set

A Golomb-coded set is a probabilistic data structure used similarly to a Bloom filter. A filter uses constant-size overhead plus on average n+2 bits per item added to the filter, where 2^-n is the desired false positive (collision) probability.

GCS use in Brocoin

GCS filters are a proposed mechanism for storing and transmitting per-block filters in Brocoin. The usage is intended to be the inverse of Bloom filters: a full node would send an SPV node the GCS filter for a block, which the SPV node would check against its list of relevant items. The suggested collision probability for Brocoin use is 2^-20.

Index

• Constants
• Variables
• type Filter
  • func BuildGCSFilter(P uint8, M uint64, key [KeySize]byte, data [][]byte) (*Filter, error)
  • func FromBytes(N uint32, P uint8, M uint64, d []byte) (*Filter, error)
  • func FromNBytes(P uint8, M uint64, d []byte) (*Filter, error)
  • func (f *Filter) Bytes() ([]byte, error)
  • func (f *Filter) HashMatchAny(key [KeySize]byte, data [][]byte) (bool, error)
  • func (f *Filter) Match(key [KeySize]byte, data []byte) (bool, error)
  • func (f *Filter) MatchAny(key [KeySize]byte, data [][]byte) (bool, error)
  • func (f *Filter) N() uint32
  • func (f *Filter) NBytes() ([]byte, error)
  • func (f *Filter) NPBytes() ([]byte, error)
  • func (f *Filter) P() uint8
  • func (f *Filter) PBytes() ([]byte, error)
  • func (f *Filter) ZipMatchAny(key [KeySize]byte, data [][]byte) (bool, error)

Constants

const (
	// KeySize is the size of the byte array required for key material for
	// the SipHash keyed hash function.
	KeySize = 16
)

Variables

var (
	// ErrNTooBig signifies that the filter can't handle N items.
	ErrNTooBig = fmt.Errorf("N is too big to fit in uint32")

	// ErrPTooBig signifies that the filter can't handle `1/2**P`
	// collision probability.
	ErrPTooBig = fmt.Errorf("P is too big to fit in uint32")
)

Types

type Filter

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

Filter describes an immutable filter that can be built from a set of data elements, serialized, deserialized, and queried in a thread-safe manner. The serialized form is compressed as a Golomb Coded Set (GCS), but does not include N or P to allow the user to encode the metadata separately if necessary. The hash function used is SipHash, a keyed function; the key used in building the filter is required in order to match filter values and is not included in the serialized form.

func BuildGCSFilter

func BuildGCSFilter(P uint8, M uint64, key [KeySize]byte, data [][]byte) (*Filter, error)

BuildGCSFilter builds a new GCS filter with the collision probability of `1/(2**P)`, key `key`, and including every `[]byte` in `data` as a member of the set.

func FromBytes

func FromBytes(N uint32, P uint8, M uint64, d []byte) (*Filter, error)

FromBytes deserializes a GCS filter from a known N, P, and serialized filter as returned by Bytes().

func FromNBytes

func FromNBytes(P uint8, M uint64, d []byte) (*Filter, error)

FromNBytes deserializes a GCS filter from a known P, and serialized N and filter as returned by NBytes().

func (*Filter) Bytes

func (f *Filter) Bytes() ([]byte, error)

Bytes returns the serialized format of the GCS filter, which does not include N or P (returned by separate methods) or the key used by SipHash.

func (*Filter) HashMatchAny

func (f *Filter) HashMatchAny(key [KeySize]byte, data [][]byte) (bool, error)

HashMatchAny returns checks whether any []byte value is likely (within collision probability) to be a member of the set represented by the filter faster than calling Match() for each value individually.

NOTE: This method should outperform MatchAny if the number of query entries approaches the number of filter entries, len(data) >= f.N().

func (*Filter) Match

func (f *Filter) Match(key [KeySize]byte, data []byte) (bool, error)

Match checks whether a []byte value is likely (within collision probability) to be a member of the set represented by the filter.

func (*Filter) MatchAny

func (f *Filter) MatchAny(key [KeySize]byte, data [][]byte) (bool, error)

MatchAny returns checks whether any []byte value is likely (within collision probability) to be a member of the set represented by the filter faster than calling Match() for each value individually.

func (*Filter) N

func (f *Filter) N() uint32

N returns the size of the data set used to build the filter.

func (*Filter) NBytes

func (f *Filter) NBytes() ([]byte, error)

NBytes returns the serialized format of the GCS filter with N, which does not include P (returned by a separate method) or the key used by SipHash.

func (*Filter) NPBytes

func (f *Filter) NPBytes() ([]byte, error)

NPBytes returns the serialized format of the GCS filter with N and P, which does not include the key used by SipHash.

func (*Filter) P

func (f *Filter) P() uint8

P returns the filter's collision probability as a negative power of 2 (that is, a collision probability of `1/2**20` is represented as 20).

func (*Filter) PBytes

func (f *Filter) PBytes() ([]byte, error)

PBytes returns the serialized format of the GCS filter with P, which does not include N (returned by a separate method) or the key used by SipHash.

func (*Filter) ZipMatchAny

func (f *Filter) ZipMatchAny(key [KeySize]byte, data [][]byte) (bool, error)

ZipMatchAny returns checks whether any []byte value is likely (within collision probability) to be a member of the set represented by the filter faster than calling Match() for each value individually.

NOTE: This method should outperform HashMatchAny when the number of query entries is smaller than the number of filter entries.