gcs

README

gcs

(http://img.shields.io/badge/license-ISC-blue.svg)](http://copyfree.org)

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/l0k18/pod/util/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 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
• func Check(err error) bool
• func Debug(a ...interface{})
• func Debugc(fn func() string)
• func Debugf(format string, a ...interface{})
• func Debugs(a interface{})
• func Error(a ...interface{})
• func Errorc(fn func() string)
• func Errorf(format string, a ...interface{})
• func Errors(a interface{})
• func Fatal(a ...interface{})
• func Fatalc(fn func() string)
• func Fatalf(format string, a ...interface{})
• func Fatals(a interface{})
• func Info(a ...interface{})
• func Infoc(fn func() string)
• func Infof(format string, a ...interface{})
• func Infos(a interface{})
• func Trace(a ...interface{})
• func Tracec(fn func() string)
• func Tracef(format string, a ...interface{})
• func Traces(a interface{})
• func Warn(a ...interface{})
• func Warnc(fn func() string)
• func Warnf(format string, a ...interface{})
• func Warns(a interface{})
• 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) 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)

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

Inspired by https://github.com/rasky/gcs

Functions

func Check

func Check(err error) bool

func Debug

func Debug(a ...interface{})

func Debugc

func Debugc(fn func() string)

func Debugf

func Debugf(format string, a ...interface{})

func Debugs

func Debugs(a interface{})

func Error

func Error(a ...interface{})

func Errorc

func Errorc(fn func() string)

func Errorf

func Errorf(format string, a ...interface{})

func Errors

func Errors(a interface{})

func Fatal

func Fatal(a ...interface{})

func Fatalc

func Fatalc(fn func() string)

func Fatalf

func Fatalf(format string, a ...interface{})

func Fatals

func Fatals(a interface{})

func Info

func Info(a ...interface{})

func Infoc

func Infoc(fn func() string)

func Infof

func Infof(format string, a ...interface{})

func Infos

func Infos(a interface{})

func Trace

func Trace(a ...interface{})

func Tracec

func Tracec(fn func() string)

func Tracef

func Tracef(format string, a ...interface{})

func Traces

func Traces(a interface{})

func Warn

func Warn(a ...interface{})

func Warnc

func Warnc(fn func() string)

func Warnf

func Warnf(format string, a ...interface{})

func Warns

func Warns(a interface{})

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

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