mmr

package
v0.4.10-alpha Latest Latest
Warning

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

 Go to latest Published: Nov 29, 2022 License: ISC Imports: 10 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

This section is empty.

Functions

func GenerateBlockNodeChain added in v0.4.9 

func GenerateBlockNodeChain(c *TreeContainer, n int64)

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)

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)

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

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

func (*TBlockNode) ActualMMRRoot added in v0.4.9 

func (tn *TBlockNode) ActualMMRRoot() chainhash.Hash

func (*TBlockNode) Ancestor added in v0.4.9 

func (tn *TBlockNode) Ancestor(height int32) blocknodes.IBlockNode

func (*TBlockNode) BVersion 

func (tn *TBlockNode) BVersion() wire.BVersion

func (*TBlockNode) Bits added in v0.4.9 

func (tn *TBlockNode) Bits() uint32

func (*TBlockNode) CalcMedianVoteK added in v0.4.9 

func (tn *TBlockNode) CalcMedianVoteK() uint32

func (*TBlockNode) CalcPastMedianTime added in v0.4.9 

func (tn *TBlockNode) CalcPastMedianTime() time.Time

func (*TBlockNode) CalcPastMedianTimeForN added in v0.4.9 

func (tn *TBlockNode) CalcPastMedianTimeForN(nBlocks int) time.Time

func (*TBlockNode) ExpansionApproved added in v0.4.9 

func (tn *TBlockNode) ExpansionApproved() bool

func (*TBlockNode) GetHash added in v0.4.9 

func (tn *TBlockNode) GetHash() chainhash.Hash

func (*TBlockNode) Height added in v0.4.9 

func (tn *TBlockNode) Height() int32

func (*TBlockNode) K added in v0.4.9 

func (tn *TBlockNode) K() uint32

func (*TBlockNode) MergeMiningNumber 

func (tn *TBlockNode) MergeMiningNumber() uint32

func (*TBlockNode) MergedMiningTree 

func (tn *TBlockNode) MergedMiningTree() []byte

func (*TBlockNode) MergedMiningTreeSize 

func (tn *TBlockNode) MergedMiningTreeSize() uint32

func (*TBlockNode) NewHeader added in v0.4.9 

func (tn *TBlockNode) NewHeader() wire.BlockHeader

func (*TBlockNode) Parent added in v0.4.9 

func (tn *TBlockNode) Parent() blocknodes.IBlockNode

func (*TBlockNode) PowWeight added in v0.4.9 

func (tn *TBlockNode) PowWeight() *big.Int

func (*TBlockNode) PrevChainWeight 

func (tn *TBlockNode) PrevChainWeight() *big.Int

func (*TBlockNode) PrevHash added in v0.4.9 

func (tn *TBlockNode) PrevHash() chainhash.Hash

func (*TBlockNode) PrevMMRRoot added in v0.4.9 

func (tn *TBlockNode) PrevMMRRoot() chainhash.Hash

func (*TBlockNode) RelativeAncestor added in v0.4.9 

func (tn *TBlockNode) RelativeAncestor(distance int32) blocknodes.IBlockNode

func (*TBlockNode) SerialID added in v0.4.9 

func (tn *TBlockNode) SerialID() int64

func (*TBlockNode) SetActualMMRRoot added in v0.4.9 

func (tn *TBlockNode) SetActualMMRRoot(mmrRoot chainhash.Hash)

func (*TBlockNode) SetStatus added in v0.4.9 

func (tn *TBlockNode) SetStatus(status blocknodes.BlockStatus)

func (*TBlockNode) Shards 

func (tn *TBlockNode) Shards() uint32

func (*TBlockNode) Status added in v0.4.9 

func (tn *TBlockNode) Status() blocknodes.BlockStatus

func (*TBlockNode) Timestamp added in v0.4.9 

func (tn *TBlockNode) Timestamp() int64

func (*TBlockNode) Version added in v0.4.9 

func (tn *TBlockNode) Version() int32

func (*TBlockNode) VoteK added in v0.4.9 

func (tn *TBlockNode) VoteK() uint32

func (*TBlockNode) WorkSum added in v0.4.9 

func (tn *TBlockNode) WorkSum() *big.Int

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

type TreeNode added in v0.4.9 

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

func GenerateNLeafs added in v0.4.9 

func GenerateNLeafs(n int64) []TreeNode

GenerateNLeafs - function for testing which generates n leafs to insert in MMR tree, filled with realistic data

func (*TreeNode) Bytes added in v0.4.9 

func (node *TreeNode) Bytes() []byte

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.