iblt

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 12, 2019 License: LGPL-3.0 Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// BucketNum represents the number of total buckets
	BucketNumBits = 12
	BucketNum     = 1 << BucketNumBits

	// BucketKeyHashLength is the number of bytes taken from
	// the hash of inserted RLP key
	BucketKeyHashLength = 6

	// BucketSerNumLength is the number of bytes used as index
	// if modified, change uint16 to corresponding types
	BucketSerNumLength = 2

	// BucketKeyLength represents the length of bytes used by keys
	BucketKeyLength = BucketKeyHashLength + BucketSerNumLength

	// BucketValueLength represents the length fo bytes used by keys
	BucketValueLength = 8
	DataLength        = BucketKeyLength + BucketValueLength

	// Number of used buckets in BucketNum of buckets
	BucketUsed = 4

	// Number of byte used in key hash
	KeyHashLength = 4

	// BloomBitLength is the number of bits in a classical bloom filter
	BloomLengthBits = 18
	BloomBitLength  = 1 << BloomLengthBits

	// BloomByteLength is the number of bytes in a classical bloom filter
	BloomByteLength = BloomBitLength / 8

	// number of bits per Digest-ed element
	BloomUsedBits = 7
)

Constants left here for reference

Variables

View Source 
var (
	ErrNoOpFunc = errors.New("not set operated function")
	ErrNoData   = errors.New("not provide data")
)
View Source 
var (
	ErrKeyDuplicate = errors.New("insert key duplicated")
	ErrPtrEmpty     = errors.New("input nil pointer")
	ErrDecodeFailed = errors.New("decode IBLT failed")
)

Errors

View Source 
var (
	WorkMap = InitWorkMap(runtime.NumCPU())
)

Functions

This section is empty.

Types

type Bloom 

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

Struct of bloom comprises a bloom of byte slice and a config

func NewBloom 

func NewBloom(config BloomConfig) *Bloom

func (Bloom) Big 

func (b Bloom) Big() *big.Int

Big converts b to a big integer.

func (Bloom) BloomRLP 

func (b Bloom) BloomRLP() *BloomRLP

func (*Bloom) DecodeRLP 

func (b *Bloom) DecodeRLP(s *rlp.Stream) error

func (*Bloom) Digest 

func (b *Bloom) Digest(k []byte) *Bloom

For certain value k, execute the required hashes, and set the value of the corresponding bloom bit to 1

func (*Bloom) EncodeRLP 

func (b *Bloom) EncodeRLP(w io.Writer) error

func (Bloom) Hex 

func (b Bloom) Hex() string

func (Bloom) IsEqual 

func (b Bloom) IsEqual(B *Bloom) bool

IsEqual tests whether the caller Bloom object is identical to the parameter B.

func (*Bloom) LookAt 

func (b *Bloom) LookAt(idx uint32) bool

Return the value of the corresponding bloom bit

func (Bloom) LookUp 

func (b Bloom) LookUp(k []byte) bool

Find out whether an element k is in the set according to the bloom. Notice that there are possibilities of false positive.

func (*Bloom) Or 

func (b *Bloom) Or(x, y *Bloom) *Bloom

bitwise operation Or.

func (*Bloom) SetAt 

func (b *Bloom) SetAt(idx uint32)

SetAt sets certain bit to 1 in big-endian

func (*Bloom) SetBytes 

func (b *Bloom) SetBytes(d []byte)

SetBytes sets the content of b to the given bytes.

type BloomConfig 

type BloomConfig struct {
	// Length of bloom on byte (not en bit)
	BloomByteLength uint
	// Number of Hash functions
	BloomBits uint
}

Configuration of bloom

func DeriveBloomConfig 

func DeriveBloomConfig(count int) BloomConfig

Proposed config of Bloom according to the paper given the number of elements.

func NewBloomConfig 

func NewBloomConfig(len, bits uint) BloomConfig

Create a new BloomConfig where the input len is the log2 of the length of bloom on bit

type BloomRLP 

type BloomRLP struct {
	Bloom  []byte
	Config BloomConfig
}

The struct(s) end with -RLP are what actually transmitting on the networks. The conversion from original bloom to -RLP bloom is implemented, they are used in EncodeRLP and DecodeRLP functions which implicitly implements RLP encoder.

func (BloomRLP) CBloom 

func (b BloomRLP) CBloom(res *Bloom) *Bloom

type Bucket 

type Bucket struct {
	Count    int32
	DataSum  Data
	DataHash DataHash
}

IBLT are made of buckets. The construction of bucket is slightly different from what the paper says, as there is no key here.

func NewBucket 

func NewBucket(config BucketConfig) (b *Bucket)

Create a new bucket according to its configuraion.

func (Bucket) IsEmpty 

func (b Bucket) IsEmpty() bool

Return whether a bucket is empty.

func (*Bucket) Put 

func (b *Bucket) Put(d Data) *Bucket

To add an element d in an empty bucket.

func (Bucket) String 

func (b Bucket) String() string

func (*Bucket) Subtract 

func (z *Bucket) Subtract(a, b *Bucket) *Bucket

Call method subtract

func (*Bucket) Xor 

func (z *Bucket) Xor(a, b *Bucket) *Bucket

Bitwise XOR operation between two buckets.

type BucketConfig 

type BucketConfig struct {
	//length of data by bytes
	DataLen uint
	//length of hash by bytes
	HashLen uint
}

Configuration of bucket in IBLT.

func NewBucketConfig 

func NewBucketConfig(dataLen, hashLen uint) BucketConfig

Create a new bucket configuration

func (BucketConfig) String 

func (config BucketConfig) String() string

type BucketRLP 

type BucketRLP struct {
	Idx     uint
	Count   uint
	KeySum  Data
	KeyHash DataHash
}

type Data 

type Data []byte

Defined data types used in IBLT

func NewData 

func NewData(size uint) Data

func (Data) Big 

func (k Data) Big() *big.Int

func (Data) Bytes 

func (k Data) Bytes() []byte

func (Data) Hash 

func (k Data) Hash() common.Hash

func (Data) Hex 

func (k Data) Hex() string

func (Data) IsEmpty 

func (k Data) IsEmpty() bool

func (Data) IsEqual 

func (k Data) IsEqual(K Data) bool

func (Data) Less 

func (k Data) Less(comp Data) bool

Less returns true if caller is less then argument compare is byte wise

func (Data) SetBytes 

func (k Data) SetBytes(b []byte)

func (Data) Xor 

func (k Data) Xor(a, b Data) Data

Xor performs exclusive Or operation on a and b c = a ^ b, equivalent to c = b ^ a a, b, c are assumed to be the same length

type DataHash 

type DataHash []byte

func NewDataHash 

func NewDataHash(size uint) DataHash

func (DataHash) Big 

func (d DataHash) Big() *big.Int

func (DataHash) Bytes 

func (d DataHash) Bytes() []byte

func (DataHash) Hex 

func (d DataHash) Hex() string

func (DataHash) IsEmpty 

func (d DataHash) IsEmpty() bool

func (DataHash) IsEqual 

func (d DataHash) IsEqual(K DataHash) bool

func (DataHash) Less 

func (d DataHash) Less(comp DataHash) bool

Less returns true if callee is less then argument compare is byte wise

func (DataHash) Lsb 

func (d DataHash) Lsb() bool

func (DataHash) Lsh 

func (d DataHash) Lsh(n int) DataHash

func (DataHash) SetBytes 

func (d DataHash) SetBytes(b []byte)

func (DataHash) Xor 

func (d DataHash) Xor(a, b DataHash) DataHash

type EstimatorConfig 

type EstimatorConfig struct {
	// number of layers of strata
	StrataNum uint
	// Configuration of IBLT for each layer
	IBLTConfig InvBloomConfig
}

func NewEstimatorConfig 

func NewEstimatorConfig(n uint) EstimatorConfig

Create a new estimator config according to the default setting of IBLT

func (EstimatorConfig) String 

func (config EstimatorConfig) String() string

type Graphene 

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

Graphene are made of a bloom and an invBloom

func NewGraphene 

func NewGraphene(i InvBloomConfig, b BloomConfig) *Graphene

Create a new Graphene with the configurations of bloom and invBloom.

func (Graphene) Bloom 

func (g Graphene) Bloom() *Bloom

Return the Bloom of the Graphene

func (Graphene) BloomConfig 

func (g Graphene) BloomConfig() BloomConfig

Return the config of the Bloom in the Graphene

func (*Graphene) DecodeRLP 

func (g *Graphene) DecodeRLP(s *rlp.Stream) error

func (*Graphene) EncodeRLP 

func (g *Graphene) EncodeRLP(w io.Writer) error

func (Graphene) Filter 

func (g Graphene) Filter(bob map[common.Hash]Data)

Filter filters out the keys in bob that are impossible in Alice by the filtering of bloom in Graphene. Remember there is still false positive.

func (*Graphene) FilterDecode 

func (g *Graphene) FilterDecode(bob map[common.Hash]Data) map[common.Hash]Data

FilterDecode returns the unique elements of Alice not existing in Bob. It modified the callee.

func (*Graphene) FilterListRLP 

func (g *Graphene) FilterListRLP(i interface{}) (Alice [][]byte, err error)

FilterListRLP returns the slice of RLP coded slices that are uniquely in caller's bloom lookup table.

func (Graphene) FilterRLP 

func (g Graphene) FilterRLP(i interface{}) map[interface{}]interface{}

FilterRLP filters out the keys that are impossible in the map's keys it will not modify the input interface. it panics if the input is not an valid map.

func (*Graphene) Insert 

func (g *Graphene) Insert(x Data)

Insert inserts the key-value pair into certain bucket in the bloom. This operation always succeeds, assuming that all keys are distinct.

func (*Graphene) InsertMap 

func (g *Graphene) InsertMap(m map[common.Hash]Data) *Graphene

Put the elements in the IBLT of Graphene.

func (*Graphene) InsertRLP 

func (g *Graphene) InsertRLP(k, v interface{})

call the InsertRLP method of invBloom

func (Graphene) InvBloom 

func (g Graphene) InvBloom() *InvBloom

Return the InvBloom of the Graphene

func (Graphene) InvBloomConfig 

func (g Graphene) InvBloomConfig() InvBloomConfig

Return the config of the IBLT in the Graphene

func (Graphene) ListRLP 

func (g Graphene) ListRLP() (Alice, Bob [][]byte, err error)

Call the ListRLP method of the IBLT in the Graphene

func (Graphene) LookUp 

func (g Graphene) LookUp(x Data) bool

Check the existence of data in the bloom. Note that there is still false positive

func (*Graphene) Recover 

func (g *Graphene) Recover(i interface{}) (alice [][]byte, err error)

Recover recovers the slice of RLP coded slices that are in caller's bloom

type GrapheneRLP 

type GrapheneRLP struct {
	Bloom    *BloomRLP
	InvBloom *InvBloomRLP
}

type HashPool 

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

HashPool stores sorted hashes, the first K hashes will be selected for comparison in order to estimate the set difference

func NewHashPool 

func NewHashPool(config HashPoolConfig) *HashPool

Create an empty HashPool

func (HashPool) Comp 

func (p HashPool) Comp(pp *HashPool) int

Comp returns the number of common hashes among K hashes

func (HashPool) Decode 

func (p HashPool) Decode(pp *HashPool) uint

Decode calculates the set difference based on the value of similarity

func (*HashPool) DecodeRLP 

func (p *HashPool) DecodeRLP(s *rlp.Stream) error

func (*HashPool) Encode 

func (p *HashPool) Encode(d Data)

Add the hash of a new data in the hashpool

func (*HashPool) EncodeRLP 

func (p *HashPool) EncodeRLP(w io.Writer) error

func (HashPool) GetK 

func (p HashPool) GetK() int

Get the minimum between the number of hashes in the pool and K

func (HashPool) MinHash 

func (p HashPool) MinHash(k uint) SortDataHash

MinHash chooses and returns K smallest hashes

func (*HashPool) String 

func (p *HashPool) String() string

type HashPoolConfig 

type HashPoolConfig struct {
	// length of Hash by bytes
	HashLen uint

	// K is the number of elements with smallest hash values
	// chosen for the estimation of difference
	K uint
}

The configuration of HashPool

func NewHashPoolConfig 

func NewHashPoolConfig(l, k uint) HashPoolConfig

Create a new hashpool

type HashPoolRLP 

type HashPoolRLP struct {
	Hashes SortDataHash
	Config HashPoolConfig
}

type HybridEstimator 

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

HybridEstimator combines strata estimator and min-hash estimator to estimate the set difference between two parties.

func NewHybridEstimator 

func NewHybridEstimator(config HybridEstimatorConfig) *HybridEstimator

Create a new hybrid estimator using the hybridEstimator config

func (*HybridEstimator) Config 

func (e *HybridEstimator) Config() HybridEstimatorConfig

Return the configuration of the two estimators

func (*HybridEstimator) Decode 

func (e *HybridEstimator) Decode(r *HybridEstimator) uint

Calculate the difference of the two hybridEstimators

func (*HybridEstimator) DecodeRLP 

func (e *HybridEstimator) DecodeRLP(s *rlp.Stream) error

func (HybridEstimator) DeriveConfig 

func (e HybridEstimator) DeriveConfig(r *HybridEstimator) InvBloomConfig

According to the estimator of the sender, the receiver determines the configuration of the IBLT used for later transmission

func (*HybridEstimator) Encode 

func (e *HybridEstimator) Encode(d Data)

Put a data in the hybridEstimator Whether we should deal with it by strata or by minHash depends on its number of layer

func (*HybridEstimator) EncodeByte 

func (e *HybridEstimator) EncodeByte(b []byte)

Equivalent to Encode

func (*HybridEstimator) EncodeRLP 

func (e *HybridEstimator) EncodeRLP(w io.Writer) error

func (HybridEstimator) NewData 

func (e HybridEstimator) NewData() Data

Create a new byte slice with length equal to the length of data

func (HybridEstimator) NewDataHash 

func (e HybridEstimator) NewDataHash() DataHash

func (*HybridEstimator) String 

func (e *HybridEstimator) String() string

type HybridEstimatorConfig 

type HybridEstimatorConfig struct {
	StrataConfig  EstimatorConfig
	MinWiseConfig HashPoolConfig
}

The configuration of both the Strata Estimator and the HashPool

func NewHybridEstimatorConfig 

func NewHybridEstimatorConfig() HybridEstimatorConfig

Create a new hybrid estimatorConfig with the suggested configuration

type HybridEstimatorRLP 

type HybridEstimatorRLP struct {
	Strata  *StrataEstimatorRLP
	MinWise *HashPoolRLP
	Config  HybridEstimatorConfig
}

type IBloomStrataRLP 

type IBloomStrataRLP struct {
	Buckets []*BucketRLP
	Salt    uint8
}

This is different from InvBloomRLP, we have to drop the config field since it's unnecessary to carry the same config for different strata. They are saved under strata's config field.

type InvBloom 

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

The structure of IBLT

func NewInvBloom 

func NewInvBloom(config InvBloomConfig) *InvBloom

Create a new IBLT

func (InvBloom) Config 

func (b InvBloom) Config() InvBloomConfig

Return the configuration of IBLT

func (*InvBloom) Decode 

func (b *InvBloom) Decode(alice, bob map[common.Hash]Data) bool

Decode should be called after InvBloom subtraction alice stores the KV pairs that b, the caller has, bob stores the KV pairs that b, the caller has not.

Example: A: {"foo":"a1", "bar":"a2", "foo1":"common1", "bar1":"common2"} B: {"baz":"b1", "qux":"b2", "foo1":"common1", "bar1":"common2"}

C := A - B

C.Decode(alice, bob)

alice: {"foo":"a1", "bar":"a2"} bob: {"baz":"b1", "qux":"b2"}

Their common KV pairs are canceled, only when it returns true could their distinct pairs be Decode-ed. If it returns false, the partial pairs are not guaranteed to be correct.

Attention: Decode modifies the callee object. If one needs a non-corrupted version of decode, call Decode by a copy of that. TODO, optimize to use queue

func (*InvBloom) DecodeRLP 

func (b *InvBloom) DecodeRLP(s *rlp.Stream) error

DecodeRLP implements rlp.Decoder

func (*InvBloom) Delete 

func (b *InvBloom) Delete(k Data) bool

Delete a data from the corresponding buckets

func (*InvBloom) EncodeRLP 

func (b *InvBloom) EncodeRLP(w io.Writer) error

EncodeRLP implements rlp.Encoder

func (*InvBloom) Insert 

func (b *InvBloom) Insert(x Data)

Call the insert function

func (*InvBloom) InsertMap 

func (b *InvBloom) InsertMap(m map[common.Hash]Data) *InvBloom

For each element call the Insert function

func (*InvBloom) InsertRLP 

func (b *InvBloom) InsertRLP(k, v interface{})

InsertRLP inserts any k, v to IBLT using RLP coding it prints error if input is invalid or encode throws error

func (*InvBloom) ListRLP 

func (b *InvBloom) ListRLP() (Alice, Bob [][]byte, err error)

b is already the subtraction of two IBLTs, if the decode succeeds, reconstruct the two original sets

func (*InvBloom) NewBucket 

func (b *InvBloom) NewBucket() *Bucket

func (InvBloom) NewData 

func (b InvBloom) NewData() Data

Create a new data with the length of value in buckets

func (InvBloom) String 

func (b InvBloom) String() string

func (*InvBloom) Subtract 

func (z *InvBloom) Subtract(a, b *InvBloom) *InvBloom

Since this style of operator should support syntax like a.Subtract(a, b), attention should be paid to the value change when then are assigned, consider all the situations

with the help of Linxin Liu at 2018-08-03

subtract sets z to the difference of a-b and returns z

type InvBloomConfig 

type InvBloomConfig struct {
	// The configuration of buckets of IBLT
	BktConfig BucketConfig

	// BucketNum represents the number of total buckets
	BucketNum uint

	// Number of used buckets in BucketNum of buckets
	BucketUsed uint

	// Number of bytes reserved to record the key
	KeyLen uint

	// Number of bytes reserved to record the value
	ValLen uint

	// Number of bytes reserved to record the section number
	SerNumLen uint
}

Configuration of IBLT

func NewInvBloomConfig 

func NewInvBloomConfig(bkt uint, used uint) InvBloomConfig

Create a new InvBloom Config according two the config of buckets in the context of transmission of transactions

func (InvBloomConfig) String 

func (config InvBloomConfig) String() string

type InvBloomRLP 

type InvBloomRLP struct {
	Buckets []*BucketRLP
	Config  InvBloomConfig
	Salt    uint8
}

type MapWork 

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

func InitWorkMap 

func InitWorkMap(tNum int) *MapWork

func (*MapWork) AbortWorks 

func (work *MapWork) AbortWorks()

func (*MapWork) SetOperation 

func (work *MapWork) SetOperation(task Operation)

func (*MapWork) StartWorks 

func (work *MapWork) StartWorks(items []interface{}) (chan interface{}, error)

func (*MapWork) StopWorks 

func (work *MapWork) StopWorks()

type Operation 

type Operation interface {
	DoTask(i interface{}) interface{}
}

type SortData 

type SortData []Data

func (SortData) Len 

func (k SortData) Len() int

func (SortData) Less 

func (k SortData) Less(i, j int) bool

func (SortData) Swap 

func (k SortData) Swap(i, j int)

type SortDataHash 

type SortDataHash []DataHash

func (SortDataHash) Len 

func (k SortDataHash) Len() int

func (SortDataHash) Less 

func (k SortDataHash) Less(i, j int) bool

func (SortDataHash) Swap 

func (k SortDataHash) Swap(i, j int)

type StrataEstimator 

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

StrataEstimator is a strata estimator consists of an array of IBLT, each element is inserted to an IBLT corresponding to its level of key

func NewEstimator 

func NewEstimator(config EstimatorConfig) *StrataEstimator

Create a new estimator according to estimatorConfig

func (*StrataEstimator) DecodeData 

func (e *StrataEstimator) DecodeData(r *StrataEstimator) uint

Calculate the difference of two StrataEstimator

func (*StrataEstimator) DecodeRLP 

func (e *StrataEstimator) DecodeRLP(s *rlp.Stream) error

func (*StrataEstimator) EncodeData 

func (e *StrataEstimator) EncodeData(d Data)

Add a new data into the strata estimator

func (*StrataEstimator) EncodeRLP 

func (e *StrataEstimator) EncodeRLP(w io.Writer) error

func (StrataEstimator) NewDataHash 

func (e StrataEstimator) NewDataHash() DataHash

Create an empty byte slice with the setting of hash length

func (StrataEstimator) String 

func (e StrataEstimator) String() string

func (StrataEstimator) TrailingZeros 

func (e StrataEstimator) TrailingZeros(h DataHash) uint

Determine the layer of IBLT the data should be inserted into by calculating the number of preceding zeros

type StrataEstimatorRLP 

type StrataEstimatorRLP struct {
	Count  uint
	Strata []*IBloomStrataRLP
	Config EstimatorConfig
}

type WorkReq 

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

type WorkResp 

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.