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