Documentation
¶
Overview ¶
Package bmt implements Binary Merkle Tree hash. Binary Merkle Tree Hash is a hash function over arbitrary byte slices of limited size. The BMT hash is defined as H(header|bmt-root) where header is an 8-byte metadata prefix and bmt-root is the root hash of the binary merkle tree built over fixed size segments of the underlying chunk using any base hash function H (e.g., keccak 256 SHA3). The segment size is the same as the hash size of H. The number of segments on the base must be a power of 2 so that the resulting tree is balanced. Chunks with data shorter than the fixed size are hashed as if they had zero padding.
BMT hash is used as the chunk hash function in swarm which in turn is the basis for the 128 branching swarm hash used to represent files.
The BMT is optimal for providing compact inclusion proofs, i.e. prove that a segment is a substring of a chunk starting at a particular offset. The size of the underlying segments is fixed to the size of the base hash (called the resolution of the BMT hash), Using Keccak256 SHA3 hash is 32 bytes, the EVM word size to optimize for on-chain BMT verification as well as the hash size optimal for inclusion proofs in the merkle tree of the swarm hash.
Two implementations are provided:
RefHasher is optimized for code simplicity and meant as a reference implementation that is simple to understand
Hasher is optimized for speed taking advantage of concurrency with minimalistic concurrency control.
BMT Hasher implements the following interfaces:
- standard golang hash.Hash - synchronous, reusable
- io.Writer - synchronous left-to-right datawriter.
Index ¶
- Constants
- Variables
- func LengthFromSpan(span []byte) uint64
- func LengthToSpan(length int64) []byte
- func SetSIMDOptIn(b bool)
- type Conf
- type Hasher
- type Pool
- type Proof
- type Prover
- func (h Prover) BlockSize() int
- func (h Prover) Capacity() int
- func (h Prover) Proof(i int) Proof
- func (h Prover) Reset()
- func (h Prover) SetHeader(span []byte)
- func (h Prover) SetHeaderInt64(length int64)
- func (h Prover) Size() int
- func (p *Prover) Sum(b []byte) []byte
- func (h Prover) Verify(i int, proof Proof) (root []byte, err error)
- func (h Prover) Write(b []byte) (int, error)
- type ProverPool
Constants ¶
const SEGMENT_SIZE = 32
SEGMENT_SIZE is the keccak256 output size in bytes, also the BMT leaf segment size.
const (
SpanSize = 8
)
Variables ¶
var SIMDOptIn func() bool = func() bool { return false }
SIMDOptIn reports whether the SIMD hasher has been opted into.
Functions ¶
func LengthFromSpan ¶
LengthFromSpan returns length from span.
func LengthToSpan ¶
LengthToSpan creates a binary data span size representation. It is required for calculating the BMT hash.
func SetSIMDOptIn ¶
func SetSIMDOptIn(b bool)
SetSIMDOptIn sets the SIMD opt-in flag. Intended to be called once during startup before the first NewPool call (cmd/bee calls it after flag parsing).
Types ¶
type Conf ¶
Conf captures the user-facing configuration of a BMT hasher pool. Implementation-specific derived state (tree depth, batch width, etc.) is computed internally by each pool implementation.
func NewConfWithPrefix ¶
NewConfWithPrefix is like NewConf but with an optional prefix prepended to every hash operation.
type Hasher ¶
type Hasher interface {
hash.Hash
// SetHeaderInt64 sets the header bytes of BMT hash to the little endian binary representation of the int64 argument.
SetHeaderInt64(int64)
// SetHeader sets the header bytes of BMT hash by copying the first 8 bytes of the argument.
SetHeader([]byte)
// Capacity returns the maximum amount of bytes that will be processed by the implementation.
Capacity() int
}
Hasher provides the necessary extension of the hash interface to add the length-prefix of the BMT hash.
Any implementation should make it possible to generate a BMT hash using the hash.Hash interface only. However, the limitation will be that the Span of the BMT hash always must be limited to the amount of bytes actually written.
Inclusion-proof generation (Proof / Verify / zero-padded Sum) is NOT part of this interface — it lives on the Prover type, which is always goroutine-backed regardless of SIMDOptIn. See pkg/bmt/proof.go.
func NewPrefixHasher ¶
NewPrefixHasher returns a standalone BMT hasher with the given prefix.
type Pool ¶
type Pool interface {
// Get returns a BMT hasher, possibly reusing one from the pool.
Get() Hasher
// Put returns a hasher to the pool for reuse.
Put(Hasher)
}
Pool is the interface all BMT hasher pools satisfy.
type Prover ¶
type Prover struct {
// contains filtered or unexported fields
}
Prover adds Merkle-proof generation and verification on top of a BMT hasher.
Proof generation requires the tree to be fully populated, so Prover.Sum zero-pads any unwritten sections before hashing. Prover is always backed by the goroutine BMT implementation, independent of the SIMD opt-in flag: proofs are produced on a rare, redistribution-only code path where the well-tested goroutine implementation is preferred over the SIMD speedup.
The embedded *goroutineHasher is package-private, so callers outside pkg/bmt cannot bypass Sum to skip padding.
func NewPrefixProver ¶
NewPrefixProver is NewProver with an optional keccak prefix prepended to every BMT node hash. Also goroutine-backed regardless of SIMDOptIn.
func NewProver ¶
func NewProver() *Prover
NewProver returns a Prover backed by a freshly allocated goroutine-based BMT hasher, independent of the SIMD opt-in flag.
func (Prover) BlockSize ¶
func (h Prover) BlockSize() int
BlockSize returns the optimal write block size.
func (Prover) Capacity ¶
func (h Prover) Capacity() int
Capacity returns the maximum number of bytes this hasher can process.
func (Prover) SetHeader ¶
func (h Prover) SetHeader(span []byte)
SetHeader copies the span preamble from the argument.
func (Prover) SetHeaderInt64 ¶
func (h Prover) SetHeaderInt64(length int64)
SetHeaderInt64 sets the span preamble from an int64.
func (*Prover) Sum ¶
Sum zero-pads any unwritten sections (so every leaf section in the BMT is populated and Proof paths are reconstructible), then computes the BMT root and appends it to b. Shadows the promoted goroutineHasher.Sum.
type ProverPool ¶
ProverPool is a pool of goroutine-backed Provers. Ignores SIMDOptIn by design.
func NewProverPool ¶
func NewProverPool(c *Conf) ProverPool
NewProverPool returns a pool of goroutine-backed Provers, independent of SIMDOptIn. See Prover for the rationale.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package reference is a simple nonconcurrent reference implementation for hashsize segment based Binary Merkle tree hash on arbitrary but fixed maximum chunksize n where 0 <= n <= 4096
|
Package reference is a simple nonconcurrent reference implementation for hashsize segment based Binary Merkle tree hash on arbitrary but fixed maximum chunksize n where 0 <= n <= 4096 |