bmt

Documentation

Overview

Package bmt provides a binary merkle tree implementation

simple nonconcurrent reference implementation for hashsize segment based Binary Merkle tree hash on arbitrary but fixed maximum chunksize

This implementation does not take advantage of any paralellisms and uses far more memory than necessary, but it is easy to see that it is correct. It can be used for generating test cases for optimized implementations. see testBMTHasherCorrectness function in bmt_test.go

Index

• Constants
• type BaseHasher
• type EOC
  • func NewEOC(hash []byte) *EOC
  • func (e *EOC) Error() string
• type Hasher
  • func New(p *TreePool) *Hasher
  • func (hr *Hasher) BlockSize() int
  • func (hr *Hasher) Hash() []byte
  • func (hr *Hasher) ReadFrom(r io.Reader) (m int64, err error)
  • func (hr *Hasher) Reset()
  • func (hr *Hasher) ResetWithLength(l []byte)
  • func (hr *Hasher) Size() int
  • func (hr *Hasher) Sum(b []byte) (r []byte)
  • func (hr *Hasher) Write(b []byte) (int, error)
• type Node
  • func NewNode(level, index int, parent *Node) *Node
• type RefHasher
  • func NewRefHasher(hasher BaseHasher, count int) *RefHasher
  • func (rh *RefHasher) Hash(d []byte) []byte
• type Tree
  • func NewTree(hasher BaseHasher, segmentSize, segmentCount int) *Tree
  • func (t *Tree) Draw(hash []byte, d int) string
• type TreePool
  • func NewTreePool(hasher BaseHasher, segmentCount, capacity int) *TreePool
  • func (tp *TreePool) Drain(n int)
  • func (tp *TreePool) Release(t *Tree)
  • func (tp *TreePool) Reserve() *Tree

Constants

const (
	// DefaultSegmentCount is the maximum number of segments of the underlying chunk
	DefaultSegmentCount = 128 // Should be equal to storage.DefaultBranches
	// DefaultPoolSize is the maximum number of bmt trees used by the hashers, i.e,
	// the maximum number of concurrent BMT hashing operations performed by the same hasher
	DefaultPoolSize = 8
)

Types

type BaseHasher

type BaseHasher func() hash.Hash

BaseHasher is a hash.Hash constructor function used for the base hash of the BMT.

type EOC

type EOC struct {
	Hash []byte // read the hash of the chunk off the error
}

EOC (end of chunk) implements the error interface

func NewEOC

func NewEOC(hash []byte) *EOC

NewEOC creates new end of chunk error with the hash

func (*EOC) Error

func (e *EOC) Error() string

Error returns the error string

type Hasher

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

Hasher a reusable hasher for fixed maximum size chunks representing a BMT implements the hash.Hash interface reuse pool of Tree-s for amortised memory allocation and resource control supports order-agnostic concurrent segment writes as well as sequential read and write can not be called concurrently on more than one chunk can be further appended after Sum Reset gives back the Tree to the pool and guaranteed to leave the tree and itself in a state reusable for hashing a new chunk

func New

func New(p *TreePool) *Hasher

New creates a reusable Hasher implements the hash.Hash interface pulls a new Tree from a resource pool for hashing each chunk

func (*Hasher) BlockSize

func (hr *Hasher) BlockSize() int

BlockSize returns the block size

func (*Hasher) Hash

func (hr *Hasher) Hash() []byte

Hash waits for the hasher result and returns it caller must call this on a BMT Hasher being written to

func (*Hasher) ReadFrom

func (hr *Hasher) ReadFrom(r io.Reader) (m int64, err error)

ReadFrom reads from io.Reader and appends to the data to hash using Write it reads so that chunk to hash is maximum length or reader reaches EOF caller must Reset the hasher prior to call

func (*Hasher) Reset

func (hr *Hasher) Reset()

Reset needs to be called before writing to the hasher

func (*Hasher) ResetWithLength

func (hr *Hasher) ResetWithLength(l []byte)

ResetWithLength needs to be called before writing to the hasher the argument is supposed to be the byte slice binary representation of the legth of the data subsumed under the hash

func (*Hasher) Size

func (hr *Hasher) Size() int

Size returns the size

func (*Hasher) Sum

func (hr *Hasher) Sum(b []byte) (r []byte)

Sum returns the hash of the buffer hash.Hash interface Sum method appends the byte slice to the underlying data before it calculates and returns the hash of the chunk

func (*Hasher) Write

func (hr *Hasher) Write(b []byte) (int, error)

Write fills the buffer to hash with every full segment complete launches a hasher go routine that shoots up the BMT

type Node

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

Node is a reuseable segment hasher representing a node in a BMT it allows for continued writes after a Sum and is left in completely reusable state after Reset

func NewNode

func NewNode(level, index int, parent *Node) *Node

NewNode constructor for segment hasher nodes in the BMT

type RefHasher

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

RefHasher is the non-optimized easy to read reference implementation of BMT

func NewRefHasher

func NewRefHasher(hasher BaseHasher, count int) *RefHasher

NewRefHasher returns a new RefHasher

func (*RefHasher) Hash

func (rh *RefHasher) Hash(d []byte) []byte

Hash returns the BMT hash of the byte slice implements the SwarmHash interface

type Tree

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

Tree is a reusable control structure representing a BMT organised in a binary tree Hasher uses a TreePool to pick one for each chunk hash the Tree is 'locked' while not in the pool

func NewTree

func NewTree(hasher BaseHasher, segmentSize, segmentCount int) *Tree

NewTree initialises the Tree by building up the nodes of a BMT segment size is stipulated to be the size of the hash segmentCount needs to be positive integer and does not need to be a power of two and can even be an odd number segmentSize * segmentCount determines the maximum chunk size hashed using the tree

func (*Tree) Draw

func (t *Tree) Draw(hash []byte, d int) string

Draw draws the BMT (badly)

type TreePool

type TreePool struct {
	SegmentSize  int
	SegmentCount int
	Capacity     int
	// contains filtered or unexported fields
}

TreePool provides a pool of Trees used as resources by Hasher a Tree popped from the pool is guaranteed to have clean state for hashing a new chunk Hasher Reset releases the Tree to the pool

func NewTreePool

func NewTreePool(hasher BaseHasher, segmentCount, capacity int) *TreePool

NewTreePool creates a Tree pool with hasher, segment size, segment count and capacity on GetTree it reuses free Trees or creates a new one if size is not reached

func (*TreePool) Drain

func (tp *TreePool) Drain(n int)

Drain drains the pool uptil it has no more than n resources

func (*TreePool) Release

func (tp *TreePool) Release(t *Tree)

Release gives back a Tree to the pool. This Tree is guaranteed to be in reusable state does not need locking

func (*TreePool) Reserve

func (tp *TreePool) Reserve() *Tree

Reserve is blocking until it returns an available Tree it reuses free Trees or creates a new one if size is not reached