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         */
  62         return node, nil
  63 }
  64
  65 // blockHeader convert a node to the header struct
  66 func (node *BlockNode) BlockHeader() *types.BlockHeader {
  67         previousBlockHash := bc.Hash{}
  68         if node.Parent != nil {
  69                 previousBlockHash = node.Parent.Hash
  70         }
  71         return &types.BlockHeader{
  72                 Version:           node.Version,
  73                 Height:            node.Height,
  74                 PreviousBlockHash: previousBlockHash,
  75                 Timestamp:         node.Timestamp,
  76                 BlockCommitment: types.BlockCommitment{
  77                         TransactionsMerkleRoot: node.TransactionsMerkleRoot,
  78                         TransactionStatusHash:  node.TransactionStatusHash,
  79                 },
  80         }
  81 }
  82
  83 func (node *BlockNode) CalcPastMedianTime() uint64 {
  84         timestamps := []uint64{}
  85         iterNode := node
  86         for i := 0; i < consensus.MedianTimeBlocks && iterNode != nil; i++ {
  87                 timestamps = append(timestamps, iterNode.Timestamp)
  88                 iterNode = iterNode.Parent
  89         }
  90
  91         sort.Sort(common.TimeSorter(timestamps))
  92         return timestamps[len(timestamps)/2]
  93 }
  94
  95 // CalcNextBits calculate the bits for next block
  96 func (node *BlockNode) CalcNextBits() uint64 {
  97         if node.Height%consensus.BlocksPerRetarget != 0 || node.Height == 0 {
  98                 return node.Bits
  99         }
 100
 101         compareNode := node.Parent
 102         for compareNode.Height%consensus.BlocksPerRetarget != 0 {
 103                 compareNode = compareNode.Parent
 104         }
 105         return difficulty.CalcNextRequiredDifficulty(node.BlockHeader(), compareNode.BlockHeader())
 106 }
 107
 108 // CalcNextSeed calculate the seed for next block
 109 func (node *BlockNode) CalcNextSeed() *bc.Hash {
 110         if node.Height == 0 {
 111                 return consensus.InitialSeed
 112         }
 113         if node.Height%consensus.SeedPerRetarget == 0 {
 114                 return &node.Hash
 115         }
 116         return node.Seed
 117 }
 118
 119 // BlockIndex is the struct for help chain trace block chain as tree
 120 type BlockIndex struct {
 121         sync.RWMutex
 122
 123         index     map[bc.Hash]*BlockNode
 124         mainChain []*BlockNode
 125 }
 126
 127 // NewBlockIndex will create a empty BlockIndex
 128 func NewBlockIndex() *BlockIndex {
 129         return &BlockIndex{
 130                 index:     make(map[bc.Hash]*BlockNode),
 131                 mainChain: make([]*BlockNode, 0, approxNodesPerDay),
 132         }
 133 }
 134
 135 // AddNode will add node to the index map
 136 func (bi *BlockIndex) AddNode(node *BlockNode) {
 137         bi.Lock()
 138         bi.index[node.Hash] = node
 139         bi.Unlock()
 140 }
 141
 142 // GetNode will search node from the index map
 143 func (bi *BlockIndex) GetNode(hash *bc.Hash) *BlockNode {
 144         bi.RLock()
 145         defer bi.RUnlock()
 146         return bi.index[*hash]
 147 }
 148
 149 func (bi *BlockIndex) BestNode() *BlockNode {
 150         bi.RLock()
 151         defer bi.RUnlock()
 152         return bi.mainChain[len(bi.mainChain)-1]
 153 }
 154
 155 // BlockExist check does the block existed in blockIndex
 156 func (bi *BlockIndex) BlockExist(hash *bc.Hash) bool {
 157         bi.RLock()
 158         _, ok := bi.index[*hash]
 159         bi.RUnlock()
 160         return ok
 161 }
 162
 163 // TODO: THIS FUNCTION MIGHT BE DELETED
 164 func (bi *BlockIndex) InMainchain(hash bc.Hash) bool {
 165         bi.RLock()
 166         defer bi.RUnlock()
 167
 168         node, ok := bi.index[hash]
 169         if !ok {
 170                 return false
 171         }
 172         return bi.nodeByHeight(node.Height) == node
 173 }
 174
 175 func (bi *BlockIndex) nodeByHeight(height uint64) *BlockNode {
 176         if height >= uint64(len(bi.mainChain)) {
 177                 return nil
 178         }
 179         return bi.mainChain[height]
 180 }
 181
 182 // NodeByHeight returns the block node at the specified height.
 183 func (bi *BlockIndex) NodeByHeight(height uint64) *BlockNode {
 184         bi.RLock()
 185         defer bi.RUnlock()
 186         return bi.nodeByHeight(height)
 187 }
 188
 189 // SetMainChain will set the the mainChain array
 190 func (bi *BlockIndex) SetMainChain(node *BlockNode) {
 191         bi.Lock()
 192         defer bi.Unlock()
 193
 194         needed := node.Height + 1
 195         if uint64(cap(bi.mainChain)) < needed {
 196                 nodes := make([]*BlockNode, needed, needed+approxNodesPerDay)
 197                 copy(nodes, bi.mainChain)
 198                 bi.mainChain = nodes
 199         } else {
 200                 i := uint64(len(bi.mainChain))
 201                 bi.mainChain = bi.mainChain[0:needed]
 202                 for ; i < needed; i++ {
 203                         bi.mainChain[i] = nil
 204                 }
 205         }
 206
 207         for node != nil && bi.mainChain[node.Height] != node {
 208                 bi.mainChain[node.Height] = node
 209                 node = node.Parent
 210         }
 211 }