merkle

package module
v1.1.0 Latest Latest
Warning

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

 Go to latest Published: Aug 2, 2021 License: Apache-2.0 Imports: 10 Imported by: 3

README

Merkle Go Library

Documentation

Index

Constants

View Source 
const Version = "0.4.0" // benchmarking, update proof

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 MakeIAVLNode 

func MakeIAVLNode(buf []byte, t *IAVLTree) (node *IAVLNode, err error)

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

func NewIAVLNode 

func NewIAVLNode(key []byte, value []byte) *IAVLNode

type IAVLProof 

type IAVLProof struct {
	LeafHash   []byte
	InnerNodes []IAVLProofInnerNode
	RootHash   []byte
}

func ReadProof 

func ReadProof(data []byte) (*IAVLProof, error)

ReadProof will deserialize a IAVLProof from bytes

func (*IAVLProof) Root 

func (proof *IAVLProof) Root() []byte

Please leave this here! I use it in light-client to fulfill an interface

func (*IAVLProof) Verify 

func (proof *IAVLProof) Verify(key []byte, value []byte, root []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(cacheSize int, db dbm.DB) *IAVLTree

func (*IAVLTree) ConstructProof 

func (t *IAVLTree) ConstructProof(key []byte) (value []byte, proof *IAVLProof)

Returns nil, 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. However, upon Save(), any other trees that share a db will become outdated, as some nodes will become orphaned. Note that Save() clears leftNode and rightNode. Otherwise, two copies would not be goroutine independent.

func (*IAVLTree) Get 

func (t *IAVLTree) Get(key []byte) (index int, value []byte, exists bool)

func (*IAVLTree) GetByIndex 

func (t *IAVLTree) GetByIndex(index int) (key []byte, value []byte)

func (*IAVLTree) Has 

func (t *IAVLTree) Has(key []byte) 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 []byte, value []byte) bool) (stopped bool)

func (*IAVLTree) IterateRange 

func (t *IAVLTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)

IterateRange makes a callback for all nodes with key between start and end inclusive If either are nil, then it is open on that side (nil, nil is the same as Iterate)

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

func (t *IAVLTree) Proof(key []byte) (value []byte, proofBytes []byte, exists bool)

func (*IAVLTree) Remove 

func (t *IAVLTree) Remove(key []byte) (value []byte, removed bool)

func (*IAVLTree) Save 

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

func (*IAVLTree) Set 

func (t *IAVLTree) Set(key []byte, value []byte) (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 {
	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)
}

Source Files

View all Source files

Directories

Path Synopsis
cmd
merkleloadtest

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.