gcs

README

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.

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 Bitcoin

GCS filters are a proposed mechanism for storing and transmitting per-block filters in Bitcoin. 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 Bitcoin use is 2^-20.

Index

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

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, er.R)

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, er.R)

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, er.R)

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, er.R)

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, er.R)

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, er.R)

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, er.R)

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, er.R)

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) 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) ZipMatchAny

func (f *Filter) ZipMatchAny(key [KeySize]byte, data [][]byte) (bool, er.R)

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.