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