mmr

package
v0.4.11 Latest Latest
Warning

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

 Go to latest Published: Sep 11, 2023 License: ISC Imports: 8 Imported by: 0

Documentation

Overview

Package mmr provides implementation of the Merkle Mountain Range.

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

block = { hash; weight }

How To calculate Root node 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

View Source 
var (
	ErrNodeNotFound          = errors.New("node not found")
	ErrNodeNoParent          = errors.New("node has no parent")
	ErrNodeDuplicate         = errors.New("node duplicate")
	ErrHeightMismatch        = errors.New("node height does not match")
	ErrHeightAndHashMismatch = errors.New("node height and hash do not match")
)

Functions

This section is empty.

Types

type BlocksMMRTree 

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

func NewTree 

func NewTree() *BlocksMMRTree

nolint: gomnd

func (*BlocksMMRTree) ActualRootForLeafByHash added in v0.4.9 

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

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.PreAllocateTree(n)
for _, block := range blocks {
   tree.AddBlockWithoutRebuild(....)
}
err := tree.RebuildTreeAndAssert()

func (*BlocksMMRTree) AppendBlock added in v0.4.9 

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

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

func (*BlocksMMRTree) Block 

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

func (*BlocksMMRTree) CurrenWeight added in v0.4.2 

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

func (*BlocksMMRTree) Current 

func (t *BlocksMMRTree) Current() *TreeNode

func (*BlocksMMRTree) CurrentRoot 

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

func (*BlocksMMRTree) LeafByHash added in v0.4.2 

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

func (*BlocksMMRTree) LookupNodeByRoot 

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

func (*BlocksMMRTree) MarshalJSON added in v0.4.2 

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

func (*BlocksMMRTree) Parent 

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

func (*BlocksMMRTree) PreAllocateTree added in v0.4.9 

func (t *BlocksMMRTree) PreAllocateTree(blockCount int)

PreAllocateTree allocates tree containers to hold expected number of blocks.

IMPORTANT! this function is not safe!

PreAllocateTree 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.PreAllocateTree(n)
for _, block := range blocks {
   tree.AddBlockWithoutRebuild(....)
}
err := tree.RebuildTreeAndAssert()

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

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

func (*BlocksMMRTree) RmBlock 

func (t *BlocksMMRTree) RmBlock(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 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(blockNode blocknodes.IBlockNode) (*chainhash.Hash, error)

type TreeNode added in v0.4.9 

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

func (*TreeNode) Clone added in v0.4.9 

func (node *TreeNode) Clone() *TreeNode

func (*TreeNode) MarshalJSON added in v0.4.9 

func (node *TreeNode) MarshalJSON() ([]byte, error)

Source Files

View all Source files

Directories

Path Synopsis

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.