merkletree

Documentation

Overview

Package merkletree contains structs and functions required to enable Merkle Trees and Merkle Proofs.

Index

• func FindParents(nodeSlicePtr []*Node)
• func VerifyMerkleProof(targetHash hash.Hash, merkleProof []hash.LRHash) bool
• type MerkleTree
  • func NewMerkleTree(leafs []hash.Hash) MerkleTree
  • func (t MerkleTree) CalculateMerkleProof(targetHash hash.Hash) ([]hash.LRHash, error)
  • func (t MerkleTree) GetChildren(index int) (*Node, *Node, error)
  • func (t MerkleTree) GetNodeList() []*Node
  • func (t MerkleTree) GetRootHash() hash.Hash
  • func (t MerkleTree) GetSiblingHash(targetHash hash.Hash) (hash.Hash, error)
  • func (t MerkleTree) PrintRootHash()
  • func (t MerkleTree) PrintTree()
  • func (t MerkleTree) RecursivelyGetSiblingHashes(targetNode *Node, merkleProof []hash.LRHash) []hash.LRHash
• type Node
  • func RecursivePairCombination(inputSlice []*Node, permanentStorage []*Node, firstIter bool) []*Node

Functions

func FindParents

func FindParents(nodeSlicePtr []*Node)

FindParents is used to determine the parents of a slice of Node pointers.

func VerifyMerkleProof

func VerifyMerkleProof(targetHash hash.Hash, merkleProof []hash.LRHash) bool

VerifyMerkleProof takes a transaction id (which is a Hash) and a Merkle Proof and verifies that the given transaction is part of the Merkle Tree. It only verifies that this could be a correct Merkle Proof, but a node still needs to verify this by requesting from other nodes that the Merkle Tree root itself is correct.

Types

type MerkleTree

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

MerkleTree is a tree that is built bottom-up by combining two nodes and hashing them to form their parent.

func NewMerkleTree

func NewMerkleTree(leafs []hash.Hash) MerkleTree

NewMerkleTree is the constructor function of MerkleTree. It builds the tree from a provided slice of Hashes. Leafs are expected left-to-right assuming leafs are at the bottom.

func (MerkleTree) CalculateMerkleProof

func (t MerkleTree) CalculateMerkleProof(targetHash hash.Hash) ([]hash.LRHash, error)

CalculateMerkleProof calculatess the Merkle Proof for a Node given its Hash. It returns the proof in the form of a slice of LRHash.

func (MerkleTree) GetChildren

func (t MerkleTree) GetChildren(index int) (*Node, *Node, error)

GetChildren is a method of MerkleTree that returns pointers to the children nodes of a node with index index.

func (MerkleTree) GetNodeList

func (t MerkleTree) GetNodeList() []*Node

GetNodeList is a method of MerkleTree that returns a slice that contains pointers to Nodes.

func (MerkleTree) GetRootHash

func (t MerkleTree) GetRootHash() hash.Hash

GetRootHash is a method of MerkleTree that returns the roothash (which is just a Hash) of a Merkle Tree.

func (MerkleTree) GetSiblingHash

func (t MerkleTree) GetSiblingHash(targetHash hash.Hash) (hash.Hash, error)

GetSiblingHash is a method of MerkleTree that gets the sibling hash of a node. This is useful for building Merkle Trees and making Merkle Proofs.

func (MerkleTree) PrintRootHash

func (t MerkleTree) PrintRootHash()

PrintRootHash is a method of MerkleTree that prints the roothash.

func (MerkleTree) PrintTree

func (t MerkleTree) PrintTree()

PrintTree is a method of MerkleTree that prints the entire tree.

func (MerkleTree) RecursivelyGetSiblingHashes

func (t MerkleTree) RecursivelyGetSiblingHashes(targetNode *Node, merkleProof []hash.LRHash) []hash.LRHash

RecursivelyGetSiblingHashes is a method of MerkleTree that is used to access sibling hashes of a node, which is needed for making Merkle Proofs.

type Node

type Node struct {
	Value  hash.Hash
	Left   *Node // pointer to left child (nullptr if it does not exist)
	Right  *Node // pointer to right child (nullptr if it does not exist)
	Parent *Node // pointer to parent (nullptr if it does not exist)
}

Node is a node in a tree. A node knows its left and right sibling and its parent node.

func RecursivePairCombination

func RecursivePairCombination(inputSlice []*Node, permanentStorage []*Node, firstIter bool) []*Node

RecursivePairCombination is used to build Merkle Trees bottom-up.