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.

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 Decred

GCS filters are a mechanism for storing and transmitting per-block filters. The usage is intended to be the inverse of Bloom filters: a consensus-validating full node commits to a single filter for every block and serves the filter to SPV clients that match against the filter locally to determine if the block is potentially relevant. The suggested collision probability for Decred use is 2^-20.

Index

• Constants
• Variables
• func MakeHeaderForFilter(filter *Filter, prevHeader *chainhash.Hash) chainhash.Hash
• type Filter
  • func FromBytes(N uint32, P uint8, d []byte) (*Filter, error)
  • func FromNBytes(P uint8, d []byte) (*Filter, error)
  • func FromNPBytes(d []byte) (*Filter, error)
  • func FromPBytes(N uint32, d []byte) (*Filter, error)
  • func NewFilter(P uint8, key [KeySize]byte, data [][]byte) (*Filter, error)
  • func (f *Filter) Bytes() []byte
  • func (f *Filter) Hash() chainhash.Hash
  • func (f *Filter) Match(key [KeySize]byte, data []byte) bool
  • func (f *Filter) MatchAny(key [KeySize]byte, data [][]byte) bool
  • func (f *Filter) N() uint32
  • func (f *Filter) NBytes() []byte
  • func (f *Filter) NPBytes() []byte
  • func (f *Filter) P() uint8
  • func (f *Filter) PBytes() []byte

Constants

const KeySize = 16

KeySize is the size of the byte array required for key material for the SipHash keyed hash function.

Variables

var (
	// ErrNTooBig signifies that the filter can't handle N items.
	ErrNTooBig = errors.New("N does not fit in uint32")

	// ErrPTooBig signifies that the filter can't handle `1/2**P`
	// collision probability.
	ErrPTooBig = errors.New("P is too large")

	// ErrNoData signifies that an empty slice was passed.
	ErrNoData = errors.New("no data provided")

	// ErrMisserialized signifies a filter was misserialized and is missing the
	// N and/or P parameters of a serialized filter.
	ErrMisserialized = errors.New("misserialized filter")
)

Functions

func MakeHeaderForFilter

func MakeHeaderForFilter(filter *Filter, prevHeader *chainhash.Hash) chainhash.Hash

MakeHeaderForFilter makes a filter chain header for a filter, given the filter and the previous filter chain header.

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 FromBytes

func FromBytes(N uint32, P uint8, 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, d []byte) (*Filter, error)

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

func FromNPBytes

func FromNPBytes(d []byte) (*Filter, error)

FromNPBytes deserializes a GCS filter from a serialized N, P, and filter as returned by NPBytes().

func FromPBytes

func FromPBytes(N uint32, d []byte) (*Filter, error)

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

func NewFilter

func NewFilter(P uint8, key [KeySize]byte, data [][]byte) (*Filter, error)

NewFilter 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 (*Filter) Bytes

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

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

func (f *Filter) Hash() chainhash.Hash

Hash returns the BLAKE256 hash of the filter.

func (*Filter) Match

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

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

MatchAny 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

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

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

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.