mmr

Documentation

Overview

Package mmr provides implementation of the Merkle Mountain Range.

Block Leaf is structure of that contains Block Hash and Block PowWeight aka weight:

block = { hash; weight }

How To calculate Root Leaf for two parents:

1. concat hash and weight for each parent

2. concat resulting values and hash them.

3. sum weights

   root = block1 + block2 where: bv1 = concat(block1.hash, block1.weight) bv2 = concat(block2.hash, block2.weight) root.hash = HASH( concat(bv1, bv2) ) root.weight = block1.weight+block2.weight

Tree Topology:

For 1 leaf:

0: root = block1

For 2 leaves:

1:      root = node12 = block1 + block2
       /       \
0:   block1   block2

For 3 leaves:

2:          root = node12 + block3
             /      \
1:       node12      \
        /     \       \
0:   block1  block2   block3

For 4 leaves:

2:            root = node12 + node34
              /           \
1:        node12         node34
         /     \        /      \
0:   block1  block2   block3   block4

For 5 leaves:

3:                    root = node12_34 + block5
                        /       \
2:              node12_34         \
               /         \          \
1:        node12         node34       \
         /     \        /      \        \
0:   block1  block2   block3   block4   block5

For 6 leaves:

3:                     root = node12_34 + node56
                        /              \
2:               node12_34               \
               /         \                 \
1:        node12         node34            node56
         /     \        /      \          /      \
0:   block1  block2   block3   block4   block5  block6

For 7 leaves:

3:                      root = node12_34 + node56_7
                        /                        \
2:               node12_34                      node56_7
               /         \                      /       \
1:        node12         node34            node56        \
         /     \        /      \          /      \        \
0:   block1  block2   block3  block4   block5  block6   block7

For 8 leaves:

3:                      root = node12_34 + node56_78
                        /                        \
2:              node12_34                         node56_78
               /         \                      /          \
1:        node12         node34            node56           node78
         /     \        /      \          /      \         /     \
0:   block1  block2   block3  block4   block5  block6   block7  block8

Index

• func BuildMerkleTreeStoreNG(blocks []Leaf) (*Leaf, []*Leaf)
• type BlocksMMRTree
  • func NewTree() *BlocksMMRTree
  • func (t *BlocksMMRTree) AddBlock(hash chainhash.Hash, difficulty *big.Int)
  • func (t *BlocksMMRTree) Block(height int32) *TreeLeaf
  • func (t *BlocksMMRTree) CurrenWeight() *big.Int
  • func (t *BlocksMMRTree) Current() *TreeLeaf
  • func (t *BlocksMMRTree) CurrentRoot() chainhash.Hash
  • func (t *BlocksMMRTree) Fork() *BlocksMMRTree
  • func (t *BlocksMMRTree) LeafByHash(blockHash chainhash.Hash) (*TreeLeaf, bool)
  • func (t *BlocksMMRTree) LookupNodeByRoot(mmrRoot chainhash.Hash) (*TreeLeaf, bool)
  • func (t *BlocksMMRTree) MarshalJSON() ([]byte, error)
  • func (t *BlocksMMRTree) Parent(height int32) *TreeLeaf
  • func (t *BlocksMMRTree) ResetRootTo(hash chainhash.Hash, height int32)
  • func (t *BlocksMMRTree) RmBlock(hash chainhash.Hash, height int32)
  • func (t *BlocksMMRTree) RootForHeight(height int32) chainhash.Hash
  • func (t *BlocksMMRTree) SetBlock(hash chainhash.Hash, difficulty *big.Int, height int32)
• type Leaf
  • func BuildMerkleTreeStore(blocks []Leaf) []*Leaf
  • func HashMerkleBranches(left, right *Leaf) *Leaf
  • func (b *Leaf) Value() Value
• type TreeContainer
  • func (mmrTree *TreeContainer) SetNodeToMmrWithReorganization(node blocknodes.IBlockNode) bool
• type TreeLeaf
  • func (n *TreeLeaf) Clone() *TreeLeaf
  • func (n *TreeLeaf) MarshalJSON() ([]byte, error)
• type Value
  • func (v Value) Block() (b Leaf)

Functions

func BuildMerkleTreeStoreNG

func BuildMerkleTreeStoreNG(blocks []Leaf) (*Leaf, []*Leaf)

Types

type BlocksMMRTree

type BlocksMMRTree struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

func NewTree

func NewTree() *BlocksMMRTree

func (*BlocksMMRTree) AddBlock

func (t *BlocksMMRTree) AddBlock(hash chainhash.Hash, difficulty *big.Int)

AddBlock adds block as latest leaf, increases height and rebuild tree.

func (*BlocksMMRTree) Block

func (t *BlocksMMRTree) Block(height int32) *TreeLeaf

func (*BlocksMMRTree) CurrenWeight

func (t *BlocksMMRTree) CurrenWeight() *big.Int

func (*BlocksMMRTree) Current

func (t *BlocksMMRTree) Current() *TreeLeaf

func (*BlocksMMRTree) CurrentRoot

func (t *BlocksMMRTree) CurrentRoot() chainhash.Hash

func (*BlocksMMRTree) Fork

func (t *BlocksMMRTree) Fork() *BlocksMMRTree

func (*BlocksMMRTree) LeafByHash

func (t *BlocksMMRTree) LeafByHash(blockHash chainhash.Hash) (*TreeLeaf, bool)

func (*BlocksMMRTree) LookupNodeByRoot

func (t *BlocksMMRTree) LookupNodeByRoot(mmrRoot chainhash.Hash) (*TreeLeaf, bool)

func (*BlocksMMRTree) MarshalJSON

func (t *BlocksMMRTree) MarshalJSON() ([]byte, error)

func (*BlocksMMRTree) Parent

func (t *BlocksMMRTree) Parent(height int32) *TreeLeaf

func (*BlocksMMRTree) ResetRootTo

func (t *BlocksMMRTree) ResetRootTo(hash chainhash.Hash, height int32)

ResetRootTo sets provided block with <hash, height> as latest and drops all blocks after this.

func (*BlocksMMRTree) RmBlock

func (t *BlocksMMRTree) RmBlock(hash chainhash.Hash, height int32)

RmBlock drops all block from latest to (including) provided block with <hash, height>.

func (*BlocksMMRTree) RootForHeight

func (t *BlocksMMRTree) RootForHeight(height int32) chainhash.Hash

func (*BlocksMMRTree) SetBlock

func (t *BlocksMMRTree) SetBlock(hash chainhash.Hash, difficulty *big.Int, height int32)

SetBlock sets provided block with <hash, height> as latest. If block height is not latest, then reset tree to height - 1 and add AddBLock.

type Leaf

type Leaf struct {
	Hash   chainhash.Hash
	Weight *big.Int
	// contains filtered or unexported fields
}

func BuildMerkleTreeStore

func BuildMerkleTreeStore(blocks []Leaf) []*Leaf

func HashMerkleBranches

func HashMerkleBranches(left, right *Leaf) *Leaf

func (*Leaf) Value

func (b *Leaf) Value() Value

type TreeContainer

type TreeContainer struct {
	*BlocksMMRTree
	// RootToBlock stores all known pairs of the mmr_root and corresponding block,
	// which was the last leaf in the tree for this root.
	// Here is stored all roots for the main chain and orphans.
	RootToBlock map[chainhash.Hash]chainhash.Hash
}

func (*TreeContainer) SetNodeToMmrWithReorganization

func (mmrTree *TreeContainer) SetNodeToMmrWithReorganization(node blocknodes.IBlockNode) bool

type TreeLeaf

type TreeLeaf struct {
	Leaf

	Height     uint64
	ActualRoot chainhash.Hash // ActualRoot is a root of the MMR Tree when this node was latest
}

func (*TreeLeaf) Clone

func (n *TreeLeaf) Clone() *TreeLeaf

func (*TreeLeaf) MarshalJSON

func (n *TreeLeaf) MarshalJSON() ([]byte, error)

type Value

type Value []byte

func (Value) Block

func (v Value) Block() (b Leaf)