vendor/github.com/btcsuite/btcd/blockchain/process.go

   1 // Copyright (c) 2013-2017 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package blockchain
   6
   7 import (
   8         "fmt"
   9         "time"
  10
  11         "github.com/btcsuite/btcd/chaincfg/chainhash"
  12         "github.com/btcsuite/btcd/database"
  13         "github.com/btcsuite/btcutil"
  14 )
  15
  16 // BehaviorFlags is a bitmask defining tweaks to the normal behavior when
  17 // performing chain processing and consensus rules checks.
  18 type BehaviorFlags uint32
  19
  20 const (
  21         // BFFastAdd may be set to indicate that several checks can be avoided
  22         // for the block since it is already known to fit into the chain due to
  23         // already proving it correct links into the chain up to a known
  24         // checkpoint.  This is primarily used for headers-first mode.
  25         BFFastAdd BehaviorFlags = 1 << iota
  26
  27         // BFNoPoWCheck may be set to indicate the proof of work check which
  28         // ensures a block hashes to a value less than the required target will
  29         // not be performed.
  30         BFNoPoWCheck
  31
  32         // BFDryRun may be set to indicate the block should not modify the chain
  33         // or memory chain index.  This is useful to test that a block is valid
  34         // without modifying the current state.
  35         BFDryRun
  36
  37         // BFNone is a convenience value to specifically indicate no flags.
  38         BFNone BehaviorFlags = 0
  39 )
  40
  41 // blockExists determines whether a block with the given hash exists either in
  42 // the main chain or any side chains.
  43 //
  44 // This function is safe for concurrent access.
  45 func (b *BlockChain) blockExists(hash *chainhash.Hash) (bool, error) {
  46         // Check block index first (could be main chain or side chain blocks).
  47         if b.index.HaveBlock(hash) {
  48                 return true, nil
  49         }
  50
  51         // Check in the database.
  52         var exists bool
  53         err := b.db.View(func(dbTx database.Tx) error {
  54                 var err error
  55                 exists, err = dbTx.HasBlock(hash)
  56                 if err != nil || !exists {
  57                         return err
  58                 }
  59
  60                 // Ignore side chain blocks in the database.  This is necessary
  61                 // because there is not currently any record of the associated
  62                 // block index data such as its block height, so it's not yet
  63                 // possible to efficiently load the block and do anything useful
  64                 // with it.
  65                 //
  66                 // Ultimately the entire block index should be serialized
  67                 // instead of only the current main chain so it can be consulted
  68                 // directly.
  69                 _, err = dbFetchHeightByHash(dbTx, hash)
  70                 if isNotInMainChainErr(err) {
  71                         exists = false
  72                         return nil
  73                 }
  74                 return err
  75         })
  76         return exists, err
  77 }
  78
  79 // processOrphans determines if there are any orphans which depend on the passed
  80 // block hash (they are no longer orphans if true) and potentially accepts them.
  81 // It repeats the process for the newly accepted blocks (to detect further
  82 // orphans which may no longer be orphans) until there are no more.
  83 //
  84 // The flags do not modify the behavior of this function directly, however they
  85 // are needed to pass along to maybeAcceptBlock.
  86 //
  87 // This function MUST be called with the chain state lock held (for writes).
  88 func (b *BlockChain) processOrphans(hash *chainhash.Hash, flags BehaviorFlags) error {
  89         // Start with processing at least the passed hash.  Leave a little room
  90         // for additional orphan blocks that need to be processed without
  91         // needing to grow the array in the common case.
  92         processHashes := make([]*chainhash.Hash, 0, 10)
  93         processHashes = append(processHashes, hash)
  94         for len(processHashes) > 0 {
  95                 // Pop the first hash to process from the slice.
  96                 processHash := processHashes[0]
  97                 processHashes[0] = nil // Prevent GC leak.
  98                 processHashes = processHashes[1:]
  99
 100                 // Look up all orphans that are parented by the block we just
 101                 // accepted.  This will typically only be one, but it could
 102                 // be multiple if multiple blocks are mined and broadcast
 103                 // around the same time.  The one with the most proof of work
 104                 // will eventually win out.  An indexing for loop is
 105                 // intentionally used over a range here as range does not
 106                 // reevaluate the slice on each iteration nor does it adjust the
 107                 // index for the modified slice.
 108                 for i := 0; i < len(b.prevOrphans[*processHash]); i++ {
 109                         orphan := b.prevOrphans[*processHash][i]
 110                         if orphan == nil {
 111                                 log.Warnf("Found a nil entry at index %d in the "+
 112                                         "orphan dependency list for block %v", i,
 113                                         processHash)
 114                                 continue
 115                         }
 116
 117                         // Remove the orphan from the orphan pool.
 118                         orphanHash := orphan.block.Hash()
 119                         b.removeOrphanBlock(orphan)
 120                         i--
 121
 122                         // Potentially accept the block into the block chain.
 123                         _, err := b.maybeAcceptBlock(orphan.block, flags)
 124                         if err != nil {
 125                                 return err
 126                         }
 127
 128                         // Add this block to the list of blocks to process so
 129                         // any orphan blocks that depend on this block are
 130                         // handled too.
 131                         processHashes = append(processHashes, orphanHash)
 132                 }
 133         }
 134         return nil
 135 }
 136
 137 // ProcessBlock is the main workhorse for handling insertion of new blocks into
 138 // the block chain.  It includes functionality such as rejecting duplicate
 139 // blocks, ensuring blocks follow all rules, orphan handling, and insertion into
 140 // the block chain along with best chain selection and reorganization.
 141 //
 142 // When no errors occurred during processing, the first return value indicates
 143 // whether or not the block is on the main chain and the second indicates
 144 // whether or not the block is an orphan.
 145 //
 146 // This function is safe for concurrent access.
 147 func (b *BlockChain) ProcessBlock(block *btcutil.Block, flags BehaviorFlags) (bool, bool, error) {
 148         b.chainLock.Lock()
 149         defer b.chainLock.Unlock()
 150
 151         fastAdd := flags&BFFastAdd == BFFastAdd
 152         dryRun := flags&BFDryRun == BFDryRun
 153
 154         blockHash := block.Hash()
 155         log.Tracef("Processing block %v", blockHash)
 156
 157         // The block must not already exist in the main chain or side chains.
 158         exists, err := b.blockExists(blockHash)
 159         if err != nil {
 160                 return false, false, err
 161         }
 162         if exists {
 163                 str := fmt.Sprintf("already have block %v", blockHash)
 164                 return false, false, ruleError(ErrDuplicateBlock, str)
 165         }
 166
 167         // The block must not already exist as an orphan.
 168         if _, exists := b.orphans[*blockHash]; exists {
 169                 str := fmt.Sprintf("already have block (orphan) %v", blockHash)
 170                 return false, false, ruleError(ErrDuplicateBlock, str)
 171         }
 172
 173         // Perform preliminary sanity checks on the block and its transactions.
 174         err = checkBlockSanity(block, b.chainParams.PowLimit, b.timeSource, flags)
 175         if err != nil {
 176                 return false, false, err
 177         }
 178
 179         // Find the previous checkpoint and perform some additional checks based
 180         // on the checkpoint.  This provides a few nice properties such as
 181         // preventing old side chain blocks before the last checkpoint,
 182         // rejecting easy to mine, but otherwise bogus, blocks that could be
 183         // used to eat memory, and ensuring expected (versus claimed) proof of
 184         // work requirements since the previous checkpoint are met.
 185         blockHeader := &block.MsgBlock().Header
 186         checkpointNode, err := b.findPreviousCheckpoint()
 187         if err != nil {
 188                 return false, false, err
 189         }
 190         if checkpointNode != nil {
 191                 // Ensure the block timestamp is after the checkpoint timestamp.
 192                 checkpointTime := time.Unix(checkpointNode.timestamp, 0)
 193                 if blockHeader.Timestamp.Before(checkpointTime) {
 194                         str := fmt.Sprintf("block %v has timestamp %v before "+
 195                                 "last checkpoint timestamp %v", blockHash,
 196                                 blockHeader.Timestamp, checkpointTime)
 197                         return false, false, ruleError(ErrCheckpointTimeTooOld, str)
 198                 }
 199                 if !fastAdd {
 200                         // Even though the checks prior to now have already ensured the
 201                         // proof of work exceeds the claimed amount, the claimed amount
 202                         // is a field in the block header which could be forged.  This
 203                         // check ensures the proof of work is at least the minimum
 204                         // expected based on elapsed time since the last checkpoint and
 205                         // maximum adjustment allowed by the retarget rules.
 206                         duration := blockHeader.Timestamp.Sub(checkpointTime)
 207                         requiredTarget := CompactToBig(b.calcEasiestDifficulty(
 208                                 checkpointNode.bits, duration))
 209                         currentTarget := CompactToBig(blockHeader.Bits)
 210                         if currentTarget.Cmp(requiredTarget) > 0 {
 211                                 str := fmt.Sprintf("block target difficulty of %064x "+
 212                                         "is too low when compared to the previous "+
 213                                         "checkpoint", currentTarget)
 214                                 return false, false, ruleError(ErrDifficultyTooLow, str)
 215                         }
 216                 }
 217         }
 218
 219         // Handle orphan blocks.
 220         prevHash := &blockHeader.PrevBlock
 221         prevHashExists, err := b.blockExists(prevHash)
 222         if err != nil {
 223                 return false, false, err
 224         }
 225         if !prevHashExists {
 226                 if !dryRun {
 227                         log.Infof("Adding orphan block %v with parent %v",
 228                                 blockHash, prevHash)
 229                         b.addOrphanBlock(block)
 230                 }
 231
 232                 return false, true, nil
 233         }
 234
 235         // The block has passed all context independent checks and appears sane
 236         // enough to potentially accept it into the block chain.
 237         isMainChain, err := b.maybeAcceptBlock(block, flags)
 238         if err != nil {
 239                 return false, false, err
 240         }
 241
 242         // Don't process any orphans or log when the dry run flag is set.
 243         if !dryRun {
 244                 // Accept any orphan blocks that depend on this block (they are
 245                 // no longer orphans) and repeat for those accepted blocks until
 246                 // there are no more.
 247                 err := b.processOrphans(blockHash, flags)
 248                 if err != nil {
 249                         return false, false, err
 250                 }
 251
 252                 log.Debugf("Accepted block %v", blockHash)
 253         }
 254
 255         return isMainChain, false, nil
 256 }