Documentation
¶
Overview ¶
Package bmt provides a binary merkle tree implementation
Package bmt is a 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. There is extra check on reference hasher correctness in bmt_test.go * TestRefHasher * testBMTHasherCorrectness function
Index ¶
Constants ¶
const ( // SegmentCount is the maximum number of segments of the underlying chunk // Should be equal to max-chunk-data-size / hash-size SegmentCount = 128 // PoolSize 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 PoolSize = 8 )
Variables ¶
This section is empty.
Functions ¶
Types ¶
type BaseHasherFunc ¶
BaseHasherFunc is a hash.Hash constructor function used for the base hash of the BMT. implemented by Keccak256 SHA3 sha3.NewKeccak256
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
- reuses a pool of trees for amortised memory allocation and resource control
- supports order-agnostic concurrent segment writes (TODO:) as well as sequential read and write
- the same hasher instance must not be called concurrently on more than one chunk
- the same hasher instance is synchronously reuseable
- Sum gives back the tree to the pool and guaranteed to leave the tree and itself in a state reusable for hashing a new chunk
- generates and verifies segment inclusion proofs (TODO:)
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) DataLength ¶
Datalength returns the maximum data size that is hashed by the hasher = segment count times segment size
func (*Hasher) Reset ¶
func (h *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 length of the data subsumed under the hash, i.e., span
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 BaseHasherFunc, count int) *RefHasher
NewRefHasher returns a new RefHasher
type TreePool ¶
type TreePool struct {
SegmentSize int // size of leaf segments, stipulated to be = hash size
SegmentCount int // the number of segments on the base level of the BMT
Capacity int // pool capacity, controls concurrency
Depth int // depth of the bmt trees = int(log2(segmentCount))+1
Datalength int // the total length of the data (count * size)
// 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
func NewTreePool ¶
func NewTreePool(hasher BaseHasherFunc, segmentCount, capacity int) *TreePool
NewTreePool creates a tree pool with hasher, segment size, segment count and capacity on Hasher.getTree it reuses free trees or creates a new one if capacity is not reached
Source Files