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

   1 // Copyright (c) 2016-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
  10         "github.com/btcsuite/btcd/chaincfg/chainhash"
  11 )
  12
  13 // ThresholdState define the various threshold states used when voting on
  14 // consensus changes.
  15 type ThresholdState byte
  16
  17 // These constants are used to identify specific threshold states.
  18 const (
  19         // ThresholdDefined is the first state for each deployment and is the
  20         // state for the genesis block has by definition for all deployments.
  21         ThresholdDefined ThresholdState = iota
  22
  23         // ThresholdStarted is the state for a deployment once its start time
  24         // has been reached.
  25         ThresholdStarted
  26
  27         // ThresholdLockedIn is the state for a deployment during the retarget
  28         // period which is after the ThresholdStarted state period and the
  29         // number of blocks that have voted for the deployment equal or exceed
  30         // the required number of votes for the deployment.
  31         ThresholdLockedIn
  32
  33         // ThresholdActive is the state for a deployment for all blocks after a
  34         // retarget period in which the deployment was in the ThresholdLockedIn
  35         // state.
  36         ThresholdActive
  37
  38         // ThresholdFailed is the state for a deployment once its expiration
  39         // time has been reached and it did not reach the ThresholdLockedIn
  40         // state.
  41         ThresholdFailed
  42
  43         // numThresholdsStates is the maximum number of threshold states used in
  44         // tests.
  45         numThresholdsStates
  46 )
  47
  48 // thresholdStateStrings is a map of ThresholdState values back to their
  49 // constant names for pretty printing.
  50 var thresholdStateStrings = map[ThresholdState]string{
  51         ThresholdDefined:  "ThresholdDefined",
  52         ThresholdStarted:  "ThresholdStarted",
  53         ThresholdLockedIn: "ThresholdLockedIn",
  54         ThresholdActive:   "ThresholdActive",
  55         ThresholdFailed:   "ThresholdFailed",
  56 }
  57
  58 // String returns the ThresholdState as a human-readable name.
  59 func (t ThresholdState) String() string {
  60         if s := thresholdStateStrings[t]; s != "" {
  61                 return s
  62         }
  63         return fmt.Sprintf("Unknown ThresholdState (%d)", int(t))
  64 }
  65
  66 // thresholdConditionChecker provides a generic interface that is invoked to
  67 // determine when a consensus rule change threshold should be changed.
  68 type thresholdConditionChecker interface {
  69         // BeginTime returns the unix timestamp for the median block time after
  70         // which voting on a rule change starts (at the next window).
  71         BeginTime() uint64
  72
  73         // EndTime returns the unix timestamp for the median block time after
  74         // which an attempted rule change fails if it has not already been
  75         // locked in or activated.
  76         EndTime() uint64
  77
  78         // RuleChangeActivationThreshold is the number of blocks for which the
  79         // condition must be true in order to lock in a rule change.
  80         RuleChangeActivationThreshold() uint32
  81
  82         // MinerConfirmationWindow is the number of blocks in each threshold
  83         // state retarget window.
  84         MinerConfirmationWindow() uint32
  85
  86         // Condition returns whether or not the rule change activation condition
  87         // has been met.  This typically involves checking whether or not the
  88         // bit assocaited with the condition is set, but can be more complex as
  89         // needed.
  90         Condition(*blockNode) (bool, error)
  91 }
  92
  93 // thresholdStateCache provides a type to cache the threshold states of each
  94 // threshold window for a set of IDs.
  95 type thresholdStateCache struct {
  96         entries map[chainhash.Hash]ThresholdState
  97 }
  98
  99 // Lookup returns the threshold state associated with the given hash along with
 100 // a boolean that indicates whether or not it is valid.
 101 func (c *thresholdStateCache) Lookup(hash *chainhash.Hash) (ThresholdState, bool) {
 102         state, ok := c.entries[*hash]
 103         return state, ok
 104 }
 105
 106 // Update updates the cache to contain the provided hash to threshold state
 107 // mapping.
 108 func (c *thresholdStateCache) Update(hash *chainhash.Hash, state ThresholdState) {
 109         c.entries[*hash] = state
 110 }
 111
 112 // newThresholdCaches returns a new array of caches to be used when calculating
 113 // threshold states.
 114 func newThresholdCaches(numCaches uint32) []thresholdStateCache {
 115         caches := make([]thresholdStateCache, numCaches)
 116         for i := 0; i < len(caches); i++ {
 117                 caches[i] = thresholdStateCache{
 118                         entries: make(map[chainhash.Hash]ThresholdState),
 119                 }
 120         }
 121         return caches
 122 }
 123
 124 // thresholdState returns the current rule change threshold state for the block
 125 // AFTER the given node and deployment ID.  The cache is used to ensure the
 126 // threshold states for previous windows are only calculated once.
 127 //
 128 // This function MUST be called with the chain state lock held (for writes).
 129 func (b *BlockChain) thresholdState(prevNode *blockNode, checker thresholdConditionChecker, cache *thresholdStateCache) (ThresholdState, error) {
 130         // The threshold state for the window that contains the genesis block is
 131         // defined by definition.
 132         confirmationWindow := int32(checker.MinerConfirmationWindow())
 133         if prevNode == nil || (prevNode.height+1) < confirmationWindow {
 134                 return ThresholdDefined, nil
 135         }
 136
 137         // Get the ancestor that is the last block of the previous confirmation
 138         // window in order to get its threshold state.  This can be done because
 139         // the state is the same for all blocks within a given window.
 140         prevNode = prevNode.Ancestor(prevNode.height -
 141                 (prevNode.height+1)%confirmationWindow)
 142
 143         // Iterate backwards through each of the previous confirmation windows
 144         // to find the most recently cached threshold state.
 145         var neededStates []*blockNode
 146         for prevNode != nil {
 147                 // Nothing more to do if the state of the block is already
 148                 // cached.
 149                 if _, ok := cache.Lookup(&prevNode.hash); ok {
 150                         break
 151                 }
 152
 153                 // The start and expiration times are based on the median block
 154                 // time, so calculate it now.
 155                 medianTime := prevNode.CalcPastMedianTime()
 156
 157                 // The state is simply defined if the start time hasn't been
 158                 // been reached yet.
 159                 if uint64(medianTime.Unix()) < checker.BeginTime() {
 160                         cache.Update(&prevNode.hash, ThresholdDefined)
 161                         break
 162                 }
 163
 164                 // Add this node to the list of nodes that need the state
 165                 // calculated and cached.
 166                 neededStates = append(neededStates, prevNode)
 167
 168                 // Get the ancestor that is the last block of the previous
 169                 // confirmation window.
 170                 prevNode = prevNode.RelativeAncestor(confirmationWindow)
 171         }
 172
 173         // Start with the threshold state for the most recent confirmation
 174         // window that has a cached state.
 175         state := ThresholdDefined
 176         if prevNode != nil {
 177                 var ok bool
 178                 state, ok = cache.Lookup(&prevNode.hash)
 179                 if !ok {
 180                         return ThresholdFailed, AssertError(fmt.Sprintf(
 181                                 "thresholdState: cache lookup failed for %v",
 182                                 prevNode.hash))
 183                 }
 184         }
 185
 186         // Since each threshold state depends on the state of the previous
 187         // window, iterate starting from the oldest unknown window.
 188         for neededNum := len(neededStates) - 1; neededNum >= 0; neededNum-- {
 189                 prevNode := neededStates[neededNum]
 190
 191                 switch state {
 192                 case ThresholdDefined:
 193                         // The deployment of the rule change fails if it expires
 194                         // before it is accepted and locked in.
 195                         medianTime := prevNode.CalcPastMedianTime()
 196                         medianTimeUnix := uint64(medianTime.Unix())
 197                         if medianTimeUnix >= checker.EndTime() {
 198                                 state = ThresholdFailed
 199                                 break
 200                         }
 201
 202                         // The state for the rule moves to the started state
 203                         // once its start time has been reached (and it hasn't
 204                         // already expired per the above).
 205                         if medianTimeUnix >= checker.BeginTime() {
 206                                 state = ThresholdStarted
 207                         }
 208
 209                 case ThresholdStarted:
 210                         // The deployment of the rule change fails if it expires
 211                         // before it is accepted and locked in.
 212                         medianTime := prevNode.CalcPastMedianTime()
 213                         if uint64(medianTime.Unix()) >= checker.EndTime() {
 214                                 state = ThresholdFailed
 215                                 break
 216                         }
 217
 218                         // At this point, the rule change is still being voted
 219                         // on by the miners, so iterate backwards through the
 220                         // confirmation window to count all of the votes in it.
 221                         var count uint32
 222                         countNode := prevNode
 223                         for i := int32(0); i < confirmationWindow; i++ {
 224                                 condition, err := checker.Condition(countNode)
 225                                 if err != nil {
 226                                         return ThresholdFailed, err
 227                                 }
 228                                 if condition {
 229                                         count++
 230                                 }
 231
 232                                 // Get the previous block node.
 233                                 countNode = countNode.parent
 234                         }
 235
 236                         // The state is locked in if the number of blocks in the
 237                         // period that voted for the rule change meets the
 238                         // activation threshold.
 239                         if count >= checker.RuleChangeActivationThreshold() {
 240                                 state = ThresholdLockedIn
 241                         }
 242
 243                 case ThresholdLockedIn:
 244                         // The new rule becomes active when its previous state
 245                         // was locked in.
 246                         state = ThresholdActive
 247
 248                 // Nothing to do if the previous state is active or failed since
 249                 // they are both terminal states.
 250                 case ThresholdActive:
 251                 case ThresholdFailed:
 252                 }
 253
 254                 // Update the cache to avoid recalculating the state in the
 255                 // future.
 256                 cache.Update(&prevNode.hash, state)
 257         }
 258
 259         return state, nil
 260 }
 261
 262 // ThresholdState returns the current rule change threshold state of the given
 263 // deployment ID for the block AFTER the end of the current best chain.
 264 //
 265 // This function is safe for concurrent access.
 266 func (b *BlockChain) ThresholdState(deploymentID uint32) (ThresholdState, error) {
 267         b.chainLock.Lock()
 268         state, err := b.deploymentState(b.bestChain.Tip(), deploymentID)
 269         b.chainLock.Unlock()
 270
 271         return state, err
 272 }
 273
 274 // IsDeploymentActive returns true if the target deploymentID is active, and
 275 // false otherwise.
 276 //
 277 // This function is safe for concurrent access.
 278 func (b *BlockChain) IsDeploymentActive(deploymentID uint32) (bool, error) {
 279         b.chainLock.Lock()
 280         state, err := b.deploymentState(b.bestChain.Tip(), deploymentID)
 281         b.chainLock.Unlock()
 282         if err != nil {
 283                 return false, err
 284         }
 285
 286         return state == ThresholdActive, nil
 287 }
 288
 289 // deploymentState returns the current rule change threshold for a given
 290 // deploymentID. The threshold is evaluated from the point of view of the block
 291 // node passed in as the first argument to this method.
 292 //
 293 // It is important to note that, as the variable name indicates, this function
 294 // expects the block node prior to the block for which the deployment state is
 295 // desired.  In other words, the returned deployment state is for the block
 296 // AFTER the passed node.
 297 //
 298 // This function MUST be called with the chain state lock held (for writes).
 299 func (b *BlockChain) deploymentState(prevNode *blockNode, deploymentID uint32) (ThresholdState, error) {
 300         if deploymentID > uint32(len(b.chainParams.Deployments)) {
 301                 return ThresholdFailed, DeploymentError(deploymentID)
 302         }
 303
 304         deployment := &b.chainParams.Deployments[deploymentID]
 305         checker := deploymentChecker{deployment: deployment, chain: b}
 306         cache := &b.deploymentCaches[deploymentID]
 307
 308         return b.thresholdState(prevNode, checker, cache)
 309 }
 310
 311 // initThresholdCaches initializes the threshold state caches for each warning
 312 // bit and defined deployment and provides warnings if the chain is current per
 313 // the warnUnknownVersions and warnUnknownRuleActivations functions.
 314 func (b *BlockChain) initThresholdCaches() error {
 315         // Initialize the warning and deployment caches by calculating the
 316         // threshold state for each of them.  This will ensure the caches are
 317         // populated and any states that needed to be recalculated due to
 318         // definition changes is done now.
 319         prevNode := b.bestChain.Tip().parent
 320         for bit := uint32(0); bit < vbNumBits; bit++ {
 321                 checker := bitConditionChecker{bit: bit, chain: b}
 322                 cache := &b.warningCaches[bit]
 323                 _, err := b.thresholdState(prevNode, checker, cache)
 324                 if err != nil {
 325                         return err
 326                 }
 327         }
 328         for id := 0; id < len(b.chainParams.Deployments); id++ {
 329                 deployment := &b.chainParams.Deployments[id]
 330                 cache := &b.deploymentCaches[id]
 331                 checker := deploymentChecker{deployment: deployment, chain: b}
 332                 _, err := b.thresholdState(prevNode, checker, cache)
 333                 if err != nil {
 334                         return err
 335                 }
 336         }
 337
 338         // No warnings about unknown rules or versions until the chain is
 339         // current.
 340         if b.isCurrent() {
 341                 // Warn if a high enough percentage of the last blocks have
 342                 // unexpected versions.
 343                 bestNode := b.bestChain.Tip()
 344                 if err := b.warnUnknownVersions(bestNode); err != nil {
 345                         return err
 346                 }
 347
 348                 // Warn if any unknown new rules are either about to activate or
 349                 // have already been activated.
 350                 if err := b.warnUnknownRuleActivations(bestNode); err != nil {
 351                         return err
 352                 }
 353         }
 354
 355         return nil
 356 }