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 5package blockchain 6 7import ( 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. 15type ThresholdState byte 16 17// These constants are used to identify specific threshold states. 18const ( 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. 50var 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. 59func (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. 68type 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 associated 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. 95type 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. 101func (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. 108func (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. 114func 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). 129func (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. 266func (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. 278func (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). 299func (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. 314func (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} 357