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

Overview

Package merkle computes a deterministic minimal height Merkle tree hash. If the number of items is not a power of two, some leaves will be at different levels. Tries to keep both sides of the tree the same size, but the left may be one greater.

Use this for short deterministic trees, such as the validator list. For larger datasets, use IAVLTree.

Be aware that the current implementation by itself does not prevent second pre-image attacks. Hence, use this library with caution. Otherwise you might run into similar issues as, e.g., in early Bitcoin: https://bitcointalk.org/?topic=102395

              *
             / \
           /     \
         /         \
       /             \
      *               *
     / \             / \
    /   \           /   \
   /     \         /     \
  *       *       *       h6
 / \     / \     / \
h0  h1  h2  h3  h4  h5

TODO(ismail): add 2nd pre-image protection or clarify further on how we use this and why this secure.

Index

• func SimpleHashFromHashers(items []Hasher) []byte
• func SimpleHashFromMap(m map[string]Hasher) []byte
• func SimpleHashFromTwoHashes(left, right []byte) []byte
• func SimpleProofsFromMap(m map[string]Hasher) (rootHash []byte, proofs map[string]*SimpleProof, keys []string)
• type Hasher
• type KVPair
  • func (kv KVPair) Hash() []byte
• type SimpleProof
  • func SimpleProofsFromHashers(items []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 SimpleHashFromHashers

func SimpleHashFromHashers(items []Hasher) []byte

SimpleHashFromHashers computes a Merkle tree from items that can be hashed.

func SimpleHashFromMap

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

SimpleHashFromMap computes a Merkle tree from sorted map. Like calling SimpleHashFromHashers with `item = []byte(Hash(key) | Hash(value))`, sorted by `item`.

func SimpleHashFromTwoHashes

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

SimpleHashFromTwoHashes is the basic operation of the Merkle tree: Hash(left | right).

func SimpleProofsFromMap

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

SimpleProofsFromMap generates proofs from a map. The keys/values of the map will be used as the keys/values in the underlying key-value pairs. The keys are sorted before the proofs are computed.

Types

type Hasher

type Hasher interface {
	Hash() []byte
}

Hasher represents a hashable piece of data which can be hashed in the Tree.

type KVPair

type KVPair cmn.KVPair

A local extension to KVPair that can be hashed. Key and value are length prefixed and concatenated, then hashed.

func (KVPair) Hash

func (kv KVPair) Hash() []byte

type SimpleProof

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

SimpleProof represents a simple merkle proof.

func SimpleProofsFromHashers

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

SimpleProofsFromHashers computes inclusion proof for given items. proofs[0] is the proof for items[0].

func (*SimpleProof) String

func (sp *SimpleProof) String() string

String implements the stringer interface for SimpleProof. It is a wrapper around StringIndented.

func (*SimpleProof) StringIndented

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

StringIndented generates a canonical string representation of a SimpleProof.

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

SimpleProofNode is a 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

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

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

Tree is a Merkle tree interface.