protocol/state/blockindex.go

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