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 SimpleHashFromBinaries(items []interface{}) []byte
• func SimpleHashFromBinary(item interface{}) []byte
• func SimpleHashFromHashables(items []Hashable) []byte
• func SimpleHashFromHashes(hashes [][]byte) []byte
• func SimpleHashFromMap(m map[string]interface{}) []byte
• func SimpleHashFromTwoHashes(left []byte, right []byte) []byte
• type Hashable
  • func MakeSortedKVPairs(m map[string]interface{}) []Hashable
• type KVPair
  • func (kv KVPair) Hash() []byte
• type KVPairs
  • func (kvps KVPairs) Len() int
  • func (kvps KVPairs) Less(i, j int) bool
  • func (kvps KVPairs) Sort()
  • func (kvps KVPairs) Swap(i, j int)
• type SimpleProof
  • func SimpleProofsFromHashables(items []Hashable) (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 SimpleHashFromBinaries

func SimpleHashFromBinaries(items []interface{}) []byte

Convenience for SimpleHashFromHashes.

func SimpleHashFromBinary

func SimpleHashFromBinary(item interface{}) []byte

General Convenience

func SimpleHashFromHashables

func SimpleHashFromHashables(items []Hashable) []byte

Convenience for SimpleHashFromHashes.

func SimpleHashFromHashes

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

func SimpleHashFromMap

func SimpleHashFromMap(m map[string]interface{}) []byte

Convenience for SimpleHashFromHashes.

func SimpleHashFromTwoHashes

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

Types

type Hashable

type Hashable interface {
	Hash() []byte
}

func MakeSortedKVPairs

func MakeSortedKVPairs(m map[string]interface{}) []Hashable

type KVPair

type KVPair struct {
	Key   string
	Value interface{}
}

Convenience struct for key-value pairs.

A list of KVPairs is hashed via `SimpleHashFromHashables`. NOTE: Each `Value` is encoded for hashing without extra type information, so the user is presumed to be aware of the Value types.

func (KVPair) Hash

func (kv KVPair) Hash() []byte

type KVPairs

type KVPairs []KVPair

func (KVPairs) Len

func (kvps KVPairs) Len() int

func (KVPairs) Less

func (kvps KVPairs) Less(i, j int) bool

func (KVPairs) Sort

func (kvps KVPairs) Sort()

func (KVPairs) Swap

func (kvps KVPairs) Swap(i, j int)

type SimpleProof

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

func SimpleProofsFromHashables

func SimpleProofsFromHashables(items []Hashable) (rootHash []byte, proofs []*SimpleProof)

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

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)
}