protocol/state/blockindex.go

   1 package state
   2
   3 import (
   4         "errors"
   5         "math/big"
   6         "sort"
   7         "sync"
   8
   9         "github.com/vapor/common"
  10         "github.com/vapor/consensus"
  11         "github.com/vapor/consensus/difficulty"
  12         "github.com/vapor/protocol/bc"
  13         "github.com/vapor/protocol/bc/types"
  14 )
  15
  16 // approxNodesPerDay is an approximation of the number of new blocks there are
  17 // in a day on average.
  18 const approxNodesPerDay = 24 * 24
  19
  20 // BlockNode represents a block within the block chain and is primarily used to
  21 // aid in selecting the best chain to be the main chain.
  22 type BlockNode struct {
  23         Parent  *BlockNode // parent is the parent block for this node.
  24         Hash    bc.Hash    // hash of the block.
  25         Seed    *bc.Hash   // seed hash of the block
  26         WorkSum *big.Int   // total amount of work in the chain up to
  27
  28         Version                uint64
  29         Height                 uint64
  30         Timestamp              uint64
  31         Nonce                  uint64
  32         Bits                   uint64
  33         TransactionsMerkleRoot bc.Hash
  34         TransactionStatusHash  bc.Hash
  35 }
  36
  37 func NewBlockNode(bh *types.BlockHeader, parent *BlockNode) (*BlockNode, error) {
  38         if bh.Height != 0 && parent == nil {
  39                 return nil, errors.New("parent node can not be nil")
  40         }
  41
  42         node := &BlockNode{
  43                 Parent:                 parent,
  44                 Hash:                   bh.Hash(),
  45                 WorkSum:                difficulty.CalcWork(bh.Bits),
  46                 Version:                bh.Version,
  47                 Height:                 bh.Height,
  48                 Timestamp:              bh.Timestamp,
  49                 Nonce:                  bh.Nonce,
  50                 Bits:                   bh.Bits,
  51                 TransactionsMerkleRoot: bh.TransactionsMerkleRoot,
  52                 TransactionStatusHash:  bh.TransactionStatusHash,
  53         }
  54
  55         if bh.Height == 0 {
  56                 node.Seed = consensus.InitialSeed
  57         } else {
  58                 node.Seed = parent.CalcNextSeed()
  59                 node.WorkSum = node.WorkSum.Add(parent.WorkSum, node.WorkSum)
  60         }
  61         return node, nil
  62 }
  63
  64 // blockHeader convert a node to the header struct
  65 func (node *BlockNode) BlockHeader() *types.BlockHeader {
  66         previousBlockHash := bc.Hash{}
  67         if node.Parent != nil {
  68                 previousBlockHash = node.Parent.Hash
  69         }
  70         return &types.BlockHeader{
  71                 Version:           node.Version,
  72                 Height:            node.Height,
  73                 PreviousBlockHash: previousBlockHash,
  74                 Timestamp:         node.Timestamp,
  75                 Nonce:             node.Nonce,
  76                 Bits:              node.Bits,
  77                 BlockCommitment: types.BlockCommitment{
  78                         TransactionsMerkleRoot: node.TransactionsMerkleRoot,
  79                         TransactionStatusHash:  node.TransactionStatusHash,
  80                 },
  81         }
  82 }
  83
  84 func (node *BlockNode) CalcPastMedianTime() uint64 {
  85         timestamps := []uint64{}
  86         iterNode := node
  87         for i := 0; i < consensus.MedianTimeBlocks && iterNode != nil; i++ {
  88                 timestamps = append(timestamps, iterNode.Timestamp)
  89                 iterNode = iterNode.Parent
  90         }
  91
  92         sort.Sort(common.TimeSorter(timestamps))
  93         return timestamps[len(timestamps)/2]
  94 }
  95
  96 // CalcNextBits calculate the bits for next block
  97 func (node *BlockNode) CalcNextBits() uint64 {
  98         if node.Height%consensus.BlocksPerRetarget != 0 || node.Height == 0 {
  99                 return node.Bits
 100         }
 101
 102         compareNode := node.Parent
 103         for compareNode.Height%consensus.BlocksPerRetarget != 0 {
 104                 compareNode = compareNode.Parent
 105         }
 106         return difficulty.CalcNextRequiredDifficulty(node.BlockHeader(), compareNode.BlockHeader())
 107 }
 108
 109 // CalcNextSeed calculate the seed for next block
 110 func (node *BlockNode) CalcNextSeed() *bc.Hash {
 111         if node.Height == 0 {
 112                 return consensus.InitialSeed
 113         }
 114         if node.Height%consensus.SeedPerRetarget == 0 {
 115                 return &node.Hash
 116         }
 117         return node.Seed
 118 }
 119
 120 // BlockIndex is the struct for help chain trace block chain as tree
 121 type BlockIndex struct {
 122         sync.RWMutex
 123
 124         index     map[bc.Hash]*BlockNode
 125         mainChain []*BlockNode
 126 }
 127
 128 // NewBlockIndex will create a empty BlockIndex
 129 func NewBlockIndex() *BlockIndex {
 130         return &BlockIndex{
 131                 index:     make(map[bc.Hash]*BlockNode),
 132                 mainChain: make([]*BlockNode, 0, approxNodesPerDay),
 133         }
 134 }
 135
 136 // AddNode will add node to the index map
 137 func (bi *BlockIndex) AddNode(node *BlockNode) {
 138         bi.Lock()
 139         bi.index[node.Hash] = node
 140         bi.Unlock()
 141 }
 142
 143 // GetNode will search node from the index map
 144 func (bi *BlockIndex) GetNode(hash *bc.Hash) *BlockNode {
 145         bi.RLock()
 146         defer bi.RUnlock()
 147         return bi.index[*hash]
 148 }
 149
 150 func (bi *BlockIndex) BestNode() *BlockNode {
 151         bi.RLock()
 152         defer bi.RUnlock()
 153         return bi.mainChain[len(bi.mainChain)-1]
 154 }
 155
 156 // BlockExist check does the block existed in blockIndex
 157 func (bi *BlockIndex) BlockExist(hash *bc.Hash) bool {
 158         bi.RLock()
 159         _, ok := bi.index[*hash]
 160         bi.RUnlock()
 161         return ok
 162 }
 163
 164 // TODO: THIS FUNCTION MIGHT BE DELETED
 165 func (bi *BlockIndex) InMainchain(hash bc.Hash) bool {
 166         bi.RLock()
 167         defer bi.RUnlock()
 168
 169         node, ok := bi.index[hash]
 170         if !ok {
 171                 return false
 172         }
 173         return bi.nodeByHeight(node.Height) == node
 174 }
 175
 176 func (bi *BlockIndex) nodeByHeight(height uint64) *BlockNode {
 177         if height >= uint64(len(bi.mainChain)) {
 178                 return nil
 179         }
 180         return bi.mainChain[height]
 181 }
 182
 183 // NodeByHeight returns the block node at the specified height.
 184 func (bi *BlockIndex) NodeByHeight(height uint64) *BlockNode {
 185         bi.RLock()
 186         defer bi.RUnlock()
 187         return bi.nodeByHeight(height)
 188 }
 189
 190 // SetMainChain will set the the mainChain array
 191 func (bi *BlockIndex) SetMainChain(node *BlockNode) {
 192         bi.Lock()
 193         defer bi.Unlock()
 194
 195         needed := node.Height + 1
 196         if uint64(cap(bi.mainChain)) < needed {
 197                 nodes := make([]*BlockNode, needed, needed+approxNodesPerDay)
 198                 copy(nodes, bi.mainChain)
 199                 bi.mainChain = nodes
 200         } else {
 201                 i := uint64(len(bi.mainChain))
 202                 bi.mainChain = bi.mainChain[0:needed]
 203                 for ; i < needed; i++ {
 204                         bi.mainChain[i] = nil
 205                 }
 206         }
 207
 208         for node != nil && bi.mainChain[node.Height] != node {
 209                 bi.mainChain[node.Height] = node
 210                 node = node.Parent
 211         }
 212 }