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
- type Hasher
- func (self *Hasher) BlockSize() int
- func (self *Hasher) Hash() []byte
- func (self *Hasher) ReadFrom(r io.Reader) (m int64, err error)
- func (self *Hasher) Reset()
- func (self *Hasher) ResetWithLength(l []byte)
- func (self *Hasher) Size() int
- func (self *Hasher) Sum(b []byte) (r []byte)
- func (self *Hasher) Write(b []byte) (int, error)
- type Node
- type RefHasher
- type Tree
- type TreePool
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 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BaseHasher ¶
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
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 ¶
New creates a reusable Hasher implements the hash.Hash interface pulls a new Tree from a resource pool for hashing each chunk
func (*Hasher) Hash ¶
Hash waits for the hasher result and returns it caller must call this on a BMT Hasher being written to
func (*Hasher) ReadFrom ¶
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 (self *Hasher) Reset()
Reset needs to be called before writing to the hasher
func (*Hasher) ResetWithLength ¶
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
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
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
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
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
Source Files