merkle

package
v0.0.0-...-7c12c5a Latest Latest
Warning

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

Go to latest
Published: Oct 21, 2015 License: GPL-2.0, GPL-3.0 Imports: 10 Imported by: 0

README

There are two types of merkle trees in this module.

  • IAVL+ Tree: A snapshottable (immutable) AVL+ tree for persistent data
  • A simple merkle tree for static data

IAVL+ Tree

The purpose of this data structure is to provide persistent storage for key-value pairs (say to store account balances) such that a deterministic merkle root hash can be computed. The tree is balanced using a variant of the AVL algortihm so all operations are O(log(n)).

Nodes of this tree are immutable and indexed by its hash. Thus any node serves as an immutable snapshot which lets us stage uncommitted transactions from the mempool cheaply, and we can instantly roll back to the last committed state to process transactions of a newly committed block (which may not be the same set of transactions as those from the mempool).

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Whenever this condition is violated upon an update, the tree is rebalanced by creating O(log(n)) new nodes that point to unmodified nodes of the old tree. In the original AVL algorithm, inner nodes can also hold key-value pairs. The AVL+ algorithm (note the plus) modifies the AVL algorithm to keep all values on leaf nodes, while only using branch-nodes to store keys. This simplifies the algorithm while keeping the merkle hash trail short.

In Ethereum, the analog is Patricia tries. There are tradeoffs. Keys do not need to be hashed prior to insertion in IAVL+ trees, so this provides faster iteration in the key space which may benefit some applications. The logic is simpler to implement, requiring only two types of nodes -- inner nodes and leaf nodes. On the other hand, while IAVL+ trees provide a deterministic merkle root hash, it depends on the order of transactions. In practice this shouldn't be a problem, since you can efficiently encode the tree structure when serializing the tree contents.

Simple Merkle Tree

For smaller static data structures that don't require immutable snapshots or mutability, use the functions provided in simple_tree.go. The transactions and validation signatures of a block are hashed using this simple merkle tree logic.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func PrintIAVLNode

func PrintIAVLNode(node *IAVLNode)

Prints the in-memory children recursively.

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 IAVLNode

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

func NewIAVLNode

func NewIAVLNode(key interface{}, value interface{}) *IAVLNode

func ReadIAVLNode

func ReadIAVLNode(t *IAVLTree, r io.Reader, n *int64, err *error) *IAVLNode

NOTE: The hash is not saved or set. The caller should set the hash afterwards. (Presumably the caller already has the hash)

type IAVLProof

type IAVLProof struct {
	LeafNode   IAVLProofLeafNode
	InnerNodes []IAVLProofInnerNode
	RootHash   []byte
}

func (*IAVLProof) Verify

func (proof *IAVLProof) Verify(keyBytes, valueBytes, rootHash []byte) bool

type IAVLProofInnerNode

type IAVLProofInnerNode struct {
	Height int8
	Size   int
	Left   []byte
	Right  []byte
}

func (IAVLProofInnerNode) Hash

func (branch IAVLProofInnerNode) Hash(childHash []byte) []byte

type IAVLProofLeafNode

type IAVLProofLeafNode struct {
	KeyBytes   []byte
	ValueBytes []byte
}

func (IAVLProofLeafNode) Hash

func (leaf IAVLProofLeafNode) Hash() []byte

type IAVLTree

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

Immutable AVL Tree (wraps the Node root) This tree is not goroutine safe.

func NewIAVLTree

func NewIAVLTree(keyCodec, valueCodec wire.Codec, cacheSize int, db dbm.DB) *IAVLTree

func (*IAVLTree) ConstructProof

func (t *IAVLTree) ConstructProof(key interface{}) *IAVLProof

Returns nil if key is not in tree.

func (*IAVLTree) Copy

func (t *IAVLTree) Copy() Tree

The returned tree and the original tree are goroutine independent. That is, they can each run in their own goroutine.

func (*IAVLTree) Get

func (t *IAVLTree) Get(key interface{}) (index int, value interface{})

func (*IAVLTree) GetByIndex

func (t *IAVLTree) GetByIndex(index int) (key interface{}, value interface{})

func (*IAVLTree) Has

func (t *IAVLTree) Has(key interface{}) bool

func (*IAVLTree) Hash

func (t *IAVLTree) Hash() []byte

func (*IAVLTree) HashWithCount

func (t *IAVLTree) HashWithCount() ([]byte, int)

func (*IAVLTree) Height

func (t *IAVLTree) Height() int8

func (*IAVLTree) Iterate

func (t *IAVLTree) Iterate(fn func(key interface{}, value interface{}) bool) (stopped bool)

func (*IAVLTree) Load

func (t *IAVLTree) Load(hash []byte)

Sets the root node by reading from db. If the hash is empty, then sets root to nil.

func (*IAVLTree) Remove

func (t *IAVLTree) Remove(key interface{}) (value interface{}, removed bool)

func (*IAVLTree) Save

func (t *IAVLTree) Save() []byte

func (*IAVLTree) Set

func (t *IAVLTree) Set(key interface{}, value interface{}) (updated bool)

func (*IAVLTree) Size

func (t *IAVLTree) Size() int

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 {
	Index       int      `json:"index"`
	Total       int      `json:"total"`
	LeafHash    []byte   `json:"leaf_hash"`
	InnerHashes [][]byte `json:"inner_hashes"` // Hashes from leaf's sibling to a root's child.
	RootHash    []byte   `json:"root_hash"`
}

func SimpleProofsFromHashables

func SimpleProofsFromHashables(items []Hashable) (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(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) FlattenInnerHashes

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

Starting from a leaf SimpleProofNode, FlattenInnerHashes() 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 interface{}) (has bool)
	Get(key interface{}) (index int, value interface{})
	GetByIndex(index int) (key interface{}, value interface{})
	Set(key interface{}, value interface{}) (updated bool)
	Remove(key interface{}) (value interface{}, removed bool)
	HashWithCount() (hash []byte, count int)
	Hash() (hash []byte)
	Save() (hash []byte)
	Load(hash []byte)
	Copy() Tree
	Iterate(func(key interface{}, value interface{}) (stop bool)) (stopped bool)
}

Jump to

Keyboard shortcuts

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