protocol/blockindex.go

   1 package protocol
   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 )
  15
  16 // approxNodesPerDay is an approximation of the number of new blocks there are
  17 // in a week 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 seed 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%consensus.SeedPerRetarget == 0 {
 112                 return &node.Hash
 113         }
 114         return node.seed
 115 }
 116
 117 // BlockIndex is the struct for help chain trace block chain as tree
 118 type BlockIndex struct {
 119         sync.RWMutex
 120
 121         index     map[bc.Hash]*BlockNode
 122         mainChain []*BlockNode
 123 }
 124
 125 // NewBlockIndex will create a empty BlockIndex
 126 func NewBlockIndex() *BlockIndex {
 127         return &BlockIndex{
 128                 index:     make(map[bc.Hash]*BlockNode),
 129                 mainChain: make([]*BlockNode, 0, approxNodesPerDay),
 130         }
 131 }
 132
 133 // AddNode will add node to the index map
 134 func (bi *BlockIndex) AddNode(node *BlockNode) {
 135         bi.Lock()
 136         bi.index[node.Hash] = node
 137         bi.Unlock()
 138 }
 139
 140 // GetNode will search node from the index map
 141 func (bi *BlockIndex) GetNode(hash *bc.Hash) *BlockNode {
 142         bi.RLock()
 143         defer bi.RUnlock()
 144         return bi.index[*hash]
 145 }
 146
 147 func (bi *BlockIndex) BestNode() *BlockNode {
 148         bi.RLock()
 149         defer bi.RUnlock()
 150         return bi.mainChain[len(bi.mainChain)-1]
 151 }
 152
 153 // BlockExist check does the block existed in blockIndex
 154 func (bi *BlockIndex) BlockExist(hash *bc.Hash) bool {
 155         bi.RLock()
 156         _, ok := bi.index[*hash]
 157         bi.RUnlock()
 158         return ok
 159 }
 160
 161 // TODO: THIS FUNCTION MIGHT BE DELETED
 162 func (bi *BlockIndex) InMainchain(hash bc.Hash) bool {
 163         bi.RLock()
 164         defer bi.RUnlock()
 165
 166         node, ok := bi.index[hash]
 167         if !ok {
 168                 return false
 169         }
 170         return bi.nodeByHeight(node.height) == node
 171 }
 172
 173 func (bi *BlockIndex) nodeByHeight(height uint64) *BlockNode {
 174         if height >= uint64(len(bi.mainChain)) {
 175                 return nil
 176         }
 177         return bi.mainChain[height]
 178 }
 179
 180 // NodeByHeight returns the block node at the specified height.
 181 func (bi *BlockIndex) NodeByHeight(height uint64) *BlockNode {
 182         bi.RLock()
 183         defer bi.RUnlock()
 184         return bi.nodeByHeight(height)
 185 }
 186
 187 // SetMainChain will set the the mainChain array
 188 func (bi *BlockIndex) SetMainChain(node *BlockNode) {
 189         bi.Lock()
 190         defer bi.Unlock()
 191
 192         needed := node.height + 1
 193         if uint64(cap(bi.mainChain)) < needed {
 194                 nodes := make([]*BlockNode, needed, needed+approxNodesPerDay)
 195                 copy(nodes, bi.mainChain)
 196                 bi.mainChain = nodes
 197         } else {
 198                 i := uint64(len(bi.mainChain))
 199                 bi.mainChain = bi.mainChain[0:needed]
 200                 for ; i < needed; i++ {
 201                         bi.mainChain[i] = nil
 202                 }
 203         }
 204
 205         for node != nil && bi.mainChain[node.height] != node {
 206                 bi.mainChain[node.height] = node
 207                 node = node.parent
 208         }
 209 }