merkle

README

Simple Merkle Tree

For smaller static data structures that don't require immutable snapshots or mutability; for instance the transactions and validation signatures of a block can be hashed using this simple merkle tree logic.

Documentation

Index

• func SimpleHashFromBytes(bz []byte) []byte
• func SimpleHashFromByteslices(bzs [][]byte) []byte
• func SimpleHashFromHashers(items []Hasher) []byte
• func SimpleHashFromHashes(hashes [][]byte) []byte
• func SimpleHashFromMap(m map[string]Hasher) []byte
• func SimpleHashFromTwoHashes(left []byte, right []byte) []byte
• type Hasher
• type KVPair
  • func (kv KVPair) Hash() []byte
• type SimpleMap
  • func NewSimpleMap() *SimpleMap
  • func (sm *SimpleMap) Hash() []byte
  • func (sm *SimpleMap) KVPairs() cmn.KVPairs
  • func (sm *SimpleMap) Set(key string, value Hasher)
  • func (sm *SimpleMap) Sort()
• type SimpleProof
  • func SimpleProofsFromHashers(items []Hasher) (rootHash []byte, proofs []*SimpleProof)
  • func SimpleProofsFromMap(m map[string]Hasher) (rootHash []byte, proofs []*SimpleProof)
  • func (sp *SimpleProof) String() string
  • func (sp *SimpleProof) StringIndented(indent string) string
  • func (sp *SimpleProof) Verify(index int, total int, leafHash []byte, rootHash []byte) bool
• type SimpleProofNode
  • func (spn *SimpleProofNode) FlattenAunts() [][]byte
• type Tree

Functions

func SimpleHashFromBytes

func SimpleHashFromBytes(bz []byte) []byte

func SimpleHashFromByteslices

func SimpleHashFromByteslices(bzs [][]byte) []byte

func SimpleHashFromHashers

func SimpleHashFromHashers(items []Hasher) []byte

func SimpleHashFromHashes

func SimpleHashFromHashes(hashes [][]byte) []byte

func SimpleHashFromMap

func SimpleHashFromMap(m map[string]Hasher) []byte

func SimpleHashFromTwoHashes

func SimpleHashFromTwoHashes(left []byte, right []byte) []byte

Types

type Hasher

type Hasher interface {
	Hash() []byte
}

type KVPair

type KVPair cmn.KVPair

A local extension to KVPair that can be hashed.

func (KVPair) Hash

func (kv KVPair) Hash() []byte

type SimpleMap

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

func NewSimpleMap

func NewSimpleMap() *SimpleMap

func (*SimpleMap) Hash

func (sm *SimpleMap) Hash() []byte

Merkle root hash of items sorted by key (UNSTABLE: and by value too if duplicate key).

func (*SimpleMap) KVPairs

func (sm *SimpleMap) KVPairs() cmn.KVPairs

Returns a copy of sorted KVPairs.

func (*SimpleMap) Set

func (sm *SimpleMap) Set(key string, value Hasher)

func (*SimpleMap) Sort

func (sm *SimpleMap) Sort()

type SimpleProof

type SimpleProof struct {
	Aunts [][]byte `json:"aunts"` // Hashes from leaf's sibling to a root's child.
}

func SimpleProofsFromHashers

func SimpleProofsFromHashers(items []Hasher) (rootHash []byte, proofs []*SimpleProof)

proofs[0] is the proof for items[0].

func SimpleProofsFromMap

func SimpleProofsFromMap(m map[string]Hasher) (rootHash []byte, proofs []*SimpleProof)

func (*SimpleProof) String

func (sp *SimpleProof) String() string

func (*SimpleProof) StringIndented

func (sp *SimpleProof) StringIndented(indent string) string

func (*SimpleProof) Verify

func (sp *SimpleProof) Verify(index int, total int, leafHash []byte, rootHash []byte) bool

Verify that leafHash is a leaf hash of the simple-merkle-tree which hashes to rootHash.

type SimpleProofNode

type SimpleProofNode struct {
	Hash   []byte
	Parent *SimpleProofNode
	Left   *SimpleProofNode // Left sibling  (only one of Left,Right is set)
	Right  *SimpleProofNode // Right sibling (only one of Left,Right is set)
}

Helper structure to construct merkle proof. The node and the tree is thrown away afterwards. Exactly one of node.Left and node.Right is nil, unless node is the root, in which case both are nil. node.Parent.Hash = hash(node.Hash, node.Right.Hash) or hash(node.Left.Hash, node.Hash), depending on whether node is a left/right child.

func (*SimpleProofNode) FlattenAunts

func (spn *SimpleProofNode) FlattenAunts() [][]byte

Starting from a leaf SimpleProofNode, FlattenAunts() will return the inner hashes for the item corresponding to the leaf.

type Tree

type Tree interface {
	Size() (size int)
	Height() (height int8)
	Has(key []byte) (has bool)
	Proof(key []byte) (value []byte, proof []byte, exists bool) // TODO make it return an index
	Get(key []byte) (index int, value []byte, exists bool)
	GetByIndex(index int) (key []byte, value []byte)
	Set(key []byte, value []byte) (updated bool)
	Remove(key []byte) (value []byte, removed bool)
	HashWithCount() (hash []byte, count int)
	Hash() (hash []byte)
	Save() (hash []byte)
	Load(hash []byte)
	Copy() Tree
	Iterate(func(key []byte, value []byte) (stop bool)) (stopped bool)
	IterateRange(start []byte, end []byte, ascending bool, fx func(key []byte, value []byte) (stop bool)) (stopped bool)
}