mmr

package
v0.4.5 Latest Latest
Warning

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

 Go to latest Published: Dec 29, 2021 License: ISC Imports: 7 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func BuildMerkleTreeStoreNG added in v0.4.2 

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

Types

type BlocksMMRTree 

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

func NewTree 

func NewTree() *BlocksMMRTree

nolint: gomnd

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) AddBlockWithoutRebuild added in v0.4.3 

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

AddBlockWithoutRebuild adds block as latest leaf, increases height and weight, but without tree rebuild.

IMPORTANT! This function is not safe!

AddBlockWithoutRebuild should be used only for quick block adding.

Quick Block Adding must be done like this: 

tree := NewTree()
tree.AllocForFastAdd(n)
for _, block := range blocks {
   tree.AddBlockWithoutRebuild(....)
}
err := tree.RebuildTreeAndAssert()

func (*BlocksMMRTree) AllocForFastAdd added in v0.4.3 

func (t *BlocksMMRTree) AllocForFastAdd(blockCount uint64)

AllocForFastAdd allocates tree containers to hold expected number of blocks.

IMPORTANT! this function is not safe!

AllocForFastAdd should be used only on empty tree instances and only for quick block adding. Quick Block Adding must be done like this: 

tree := NewTree()
tree.AllocForFastAdd(n)
for _, block := range blocks {
   tree.AddBlockWithoutRebuild(....)
}
err := tree.RebuildTreeAndAssert()

func (*BlocksMMRTree) Block 

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

func (*BlocksMMRTree) CurrenWeight added in v0.4.2 

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) LeafByHash added in v0.4.2 

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

func (*BlocksMMRTree) LookupNodeByRoot 

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

func (*BlocksMMRTree) MarshalJSON added in v0.4.2 

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

func (*BlocksMMRTree) Parent 

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

func (*BlocksMMRTree) RebuildTreeAndAssert added in v0.4.3 

func (t *BlocksMMRTree) RebuildTreeAndAssert() error

RebuildTreeAndAssert just rebuild the whole tree and checks is root match with actual.

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 added in v0.4.2 

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) SetNodeQuick added in v0.4.3 

func (mmrTree *TreeContainer) SetNodeQuick(node blocknodes.IBlockNode)

func (*TreeContainer) SetNodeToMmrWithReorganization added in v0.4.2 

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

type TreeLeaf added in v0.4.2 

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 added in v0.4.2 

func (n *TreeLeaf) Clone() *TreeLeaf

func (*TreeLeaf) MarshalJSON added in v0.4.2 

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

type Value 

type Value []byte

func (Value) Block 

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

Source Files

View all Source files

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.