bmt

package
v0.3.3 Latest Latest
Warning

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

Go to latest
Published: Aug 1, 2018 License: GPL-3.0 Imports: 5 Imported by: 0

Documentation

Overview

Package bmt provides a binary merkle tree implementation used for swarm chunk hash

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

View Source
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

This section is empty.

Types

type AsyncHasher

type AsyncHasher struct {
	*Hasher // extends the Hasher
	// contains filtered or unexported fields
}

AsyncHasher extends BMT Hasher with an asynchronous segment/section writer interface AsyncHasher is unsafe and does not check indexes and section data lengths it must be used with the right indexes and length and the right number of sections

behaviour is undefined if * non-final sections are shorter or longer than secsize * if final section does not match length * write a section with index that is higher than length/secsize * set length in Sum call when length/secsize < maxsec

  • if Sum() is not called on a Hasher that is fully written a process will block, can be terminated with Reset
  • it will not leak processes if not all sections are written but it blocks and keeps the resource which can be released calling Reset()

func (*AsyncHasher) SectionSize

func (sw *AsyncHasher) SectionSize() int

SectionSize returns the size of async section unit to use

func (*AsyncHasher) Sum

func (sw *AsyncHasher) Sum(b []byte, length int, meta []byte) (s []byte)

Sum can be called any time once the length and the span is known potentially even before all segments have been written in such cases Sum will block until all segments are present and the hash for the length can be calculated.

b: digest is appended to b length: known length of the input (unsafe; undefined if out of range) meta: metadata to hash together with BMT root for the final digest

e.g., span for protection against existential forgery

func (*AsyncHasher) Write

func (sw *AsyncHasher) Write(i int, section []byte)

Write writes the i-th section of the BMT base this function can and is meant to be called concurrently it sets max segment threadsafely

type BaseHasherFunc

type BaseHasherFunc func() hash.Hash

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 and section (double segment) writes 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

func New(p *TreePool) *Hasher

New creates a reusable BMT Hasher that pulls a new tree from a resource pool for hashing each chunk

func (*Hasher) BlockSize

func (h *Hasher) BlockSize() int

BlockSize returns the block size

func (*Hasher) NewAsyncWriter

func (h *Hasher) NewAsyncWriter(double bool) *AsyncHasher

NewAsyncWriter extends Hasher with an interface for concurrent segment/section writes

func (*Hasher) Reset

func (h *Hasher) Reset()

Reset needs to be called before writing to the hasher

func (*Hasher) ResetWithLength

func (h *Hasher) ResetWithLength(span []byte)

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

func (*Hasher) Size

func (h *Hasher) Size() int

Size returns the size

func (*Hasher) Sum

func (h *Hasher) Sum(b []byte) (s []byte)

Sum returns the BMT root hash of the buffer using Sum presupposes sequential synchronous writes (io.Writer interface) hash.Hash interface Sum method appends the byte slice to the underlying data before it calculates and returns the hash of the chunk caller must make sure Sum is not called concurrently with Write, writeSection

func (*Hasher) Write

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

Write calls sequentially add to the buffer to be hashed, with every full segment calls writeSection in a go routine

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

func (*RefHasher) Hash

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

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

type SectionWriter

type SectionWriter interface {
	Reset()                                       // standard init to be called before reuse
	Write(index int, data []byte)                 // write into section of index
	Sum(b []byte, length int, span []byte) []byte // returns the hash of the buffer
	SectionSize() int                             // size of the async section unit to use
}

SectionWriter is an asynchronous segment/section writer interface

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
	Size         int // the total length of the data (count * size)
	// contains filtered or unexported fields
}

TreePool provides a pool of trees used as resources by the BMT Hasher. A tree popped from the pool is guaranteed to have a clean state ready 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

func (*TreePool) Drain

func (p *TreePool) Drain(n int)

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL