forked from decred/dcrd
-
Notifications
You must be signed in to change notification settings - Fork 0
/
thresholdstate.go
675 lines (592 loc) · 21.8 KB
/
thresholdstate.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
// Copyright (c) 2017 The decred developers
// Copyright (c) 2016 The btcsuite developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package blockchain
import (
"fmt"
"github.com/decred/dcrd/chaincfg"
"github.com/decred/dcrd/chaincfg/chainhash"
"github.com/decred/dcrd/wire"
)
// ThresholdState define the various threshold states used when voting on
// consensus changes.
type ThresholdState byte
// These constants are used to identify specific threshold states.
//
// NOTE: This section specifically does not use iota for the individual states
// since these values are serialized and must be stable for long-term storage.
const (
// ThresholdDefined is the first state for each deployment and is the
// state for the genesis block has by defintion for all deployments.
ThresholdDefined ThresholdState = 0
// ThresholdStarted is the state for a deployment once its start time
// has been reached.
ThresholdStarted ThresholdState = 1
// ThresholdLockedIn is the state for a deployment during the retarget
// period which is after the ThresholdStarted state period and the
// number of blocks that have voted for the deployment equal or exceed
// the required number of votes for the deployment.
ThresholdLockedIn ThresholdState = 2
// ThresholdActive is the state for a deployment for all blocks after a
// retarget period in which the deployment was in the ThresholdLockedIn
// state.
ThresholdActive ThresholdState = 3
// ThresholdFailed is the state for a deployment once its expiration
// time has been reached and it did not reach the ThresholdLockedIn
// state.
ThresholdFailed ThresholdState = 4
// ThresholdInvalid is a deployment that does not exist.
ThresholdInvalid ThresholdState = 5
)
// thresholdStateStrings is a map of ThresholdState values back to their
// constant names for pretty printing.
var thresholdStateStrings = map[ThresholdState]string{
ThresholdDefined: "ThresholdDefined",
ThresholdStarted: "ThresholdStarted",
ThresholdLockedIn: "ThresholdLockedIn",
ThresholdActive: "ThresholdActive",
ThresholdFailed: "ThresholdFailed",
}
// String returns the ThresholdState as a human-readable name.
func (t ThresholdState) String() string {
if s := thresholdStateStrings[t]; s != "" {
return s
}
return fmt.Sprintf("Unknown ThresholdState (%d)", int(t))
}
const (
// invalidChoice indicates an invalid choice in the
// ThresholdStateTuple.
invalidChoice = uint32(0xffffffff)
)
// ThresholdStateTuple contains the current state and the activated choice,
// when valid.
type ThresholdStateTuple struct {
// state contains the current ThresholdState.
State ThresholdState
// coice is set to invalidChoice unless state is: ThresholdLockedIn,
// ThresholdFailed & ThresholdActive. choice should always be
// crosschecked with invalidChoice.
Choice uint32
}
// thresholdStateTupleStrings is a map of ThresholdState values back to their
// constant names for pretty printing.
var thresholdStateTupleStrings = map[ThresholdState]string{
ThresholdDefined: "defined",
ThresholdStarted: "started",
ThresholdLockedIn: "lockedin",
ThresholdActive: "active",
ThresholdFailed: "failed",
}
// String returns the ThresholdStateTuple as a human-readable tuple.
func (t ThresholdStateTuple) String() string {
if s := thresholdStateTupleStrings[t.State]; s != "" {
return fmt.Sprintf("%v", s)
}
return "invalid"
}
// newThresholdState returns an initialized ThresholdStateTuple.
func newThresholdState(state ThresholdState, choice uint32) ThresholdStateTuple {
return ThresholdStateTuple{State: state, Choice: choice}
}
// thresholdConditionTally is returned by thresholdConditionChecker.Condition
// to indicate how many votes an option received. The isAbstain and isNo flags
// are accordingly set. Note isAbstain and isNo can NOT be both true at the
// same time.
type thresholdConditionTally struct {
// Vote count
count uint32
// isAbstain is the abstain (or zero vote).
isAbstain bool
// isNo is the hard no vote.
isNo bool
}
// thresholdConditionChecker provides a generic interface that is invoked to
// determine when a consensus rule change threshold should be changed.
type thresholdConditionChecker interface {
// BeginTime returns the unix timestamp for the median block time after
// which voting on a rule change starts (at the next window).
BeginTime() uint64
// EndTime returns the unix timestamp for the median block time after
// which an attempted rule change fails if it has not already been
// locked in or activated.
EndTime() uint64
// RuleChangeActivationQuorum is the minimum number of votes required
// in a voting period for before we check
// RuleChangeActivationThreshold.
RuleChangeActivationQuorum() uint32
// RuleChangeActivationThreshold is the number of votes required in
// order to lock in a rule change.
RuleChangeActivationThreshold(uint32) uint32
// RuleChangeActivationInterval is the number of blocks in each threshold
// state retarget window.
RuleChangeActivationInterval() uint32
// StakeValidationHeight is the minimum height required before votes start
// counting.
StakeValidationHeight() int64
// Condition returns an array of thresholdConditionTally that contains
// all votes. By convention isAbstain and isNo can not be true at the
// same time. The array is always returned in the same order so that
// the consumer can repeatedly call this function without having to
// care about said order. Only 1 isNo vote is allowed. By convention
// the zero value of the vote as determined by the mask is an isAbstain
// vote.
Condition(*blockNode, uint32) ([]thresholdConditionTally, error)
}
// thresholdStateCache provides a type to cache the threshold states of each
// threshold window for a set of IDs. It also keeps track of which entries have
// been modified and therefore need to be written to the database.
type thresholdStateCache struct {
dbUpdates map[chainhash.Hash]ThresholdStateTuple
entries map[chainhash.Hash]ThresholdStateTuple
}
// Lookup returns the threshold state associated with the given hash along with
// a boolean that indicates whether or not it is valid.
func (c *thresholdStateCache) Lookup(hash chainhash.Hash) (ThresholdStateTuple, bool) {
state, ok := c.entries[hash]
return state, ok
}
// Update updates the cache to contain the provided hash to threshold state
// mapping while properly tracking needed updates flush changes to the database.
func (c *thresholdStateCache) Update(hash chainhash.Hash, state ThresholdStateTuple) {
if existing, ok := c.entries[hash]; ok && existing == state {
return
}
c.dbUpdates[hash] = state
c.entries[hash] = state
}
// MarkFlushed marks all of the current udpates as flushed to the database.
// This is useful so the caller can ensure the needed database updates are not
// lost until they have successfully been written to the database.
func (c *thresholdStateCache) MarkFlushed() {
for hash := range c.dbUpdates {
delete(c.dbUpdates, hash)
}
}
// newThresholdCaches returns a new array of caches to be used when calculating
// threshold states.
func newThresholdCaches(params *chaincfg.Params) map[uint32][]thresholdStateCache {
caches := make(map[uint32][]thresholdStateCache)
for version := range params.Deployments {
caches[version] = make([]thresholdStateCache,
len(params.Deployments[version]))
for k := range caches[version] {
caches[version][k].entries = make(map[chainhash.Hash]ThresholdStateTuple)
caches[version][k].dbUpdates = make(map[chainhash.Hash]ThresholdStateTuple)
}
}
return caches
}
// thresholdState returns the current rule change threshold state for the block
// AFTER the given node and deployment ID. The cache is used to ensure the
// threshold states for previous windows are only calculated once.
//
// This function MUST be called with the chain state lock held (for writes).
func (b *BlockChain) thresholdState(version uint32, prevNode *blockNode, checker thresholdConditionChecker, cache *thresholdStateCache) (ThresholdStateTuple, error) {
// The threshold state for the window that contains the genesis block is
// defined by definition.
confirmationWindow := int64(checker.RuleChangeActivationInterval())
svh := checker.StakeValidationHeight()
if prevNode == nil || prevNode.height+1 < svh+confirmationWindow {
return newThresholdState(ThresholdDefined, invalidChoice), nil
}
// Get the ancestor that is the last block of the previous confirmation
// window in order to get its threshold state. This can be done because
// the state is the same for all blocks within a given window.
wantHeight := calcWantHeight(svh,
int64(checker.RuleChangeActivationInterval()),
prevNode.height+1)
var err error
prevNode, err = b.ancestorNode(prevNode, wantHeight)
if err != nil {
return newThresholdState(ThresholdFailed, invalidChoice), err
}
// Iterate backwards through each of the previous confirmation windows
// to find the most recently cached threshold state.
var neededStates []*blockNode
for prevNode != nil {
// Nothing more to do if the state of the block is already
// cached.
if _, ok := cache.Lookup(prevNode.hash); ok {
break
}
// The start and expiration times are based on the median block
// time, so calculate it now.
medianTime, err := b.calcPastMedianTime(prevNode)
if err != nil {
return newThresholdState(ThresholdFailed,
invalidChoice), err
}
// The state is simply defined if the start time hasn't been
// been reached yet.
if uint64(medianTime.Unix()) < checker.BeginTime() {
cache.Update(prevNode.hash, ThresholdStateTuple{
State: ThresholdDefined,
Choice: invalidChoice,
})
break
}
// Add this node to the list of nodes that need the state
// calculated and cached.
neededStates = append(neededStates, prevNode)
// Get the ancestor that is the last block of the previous
// confirmation window.
prevNode, err = b.ancestorNode(prevNode, prevNode.height-
confirmationWindow)
if err != nil {
return newThresholdState(ThresholdFailed,
invalidChoice), err
}
}
// Start with the threshold state for the most recent confirmation
// window that has a cached state.
stateTuple := newThresholdState(ThresholdDefined, invalidChoice)
if prevNode != nil {
var ok bool
stateTuple, ok = cache.Lookup(prevNode.hash)
if !ok {
return newThresholdState(ThresholdFailed,
invalidChoice), AssertError(fmt.Sprintf(
"thresholdState: cache lookup failed "+
"for %v", prevNode.hash))
}
}
// Since each threshold state depends on the state of the previous
// window, iterate starting from the oldest unknown window.
for neededNum := len(neededStates) - 1; neededNum >= 0; neededNum-- {
prevNode := neededStates[neededNum]
switch stateTuple.State {
case ThresholdDefined:
// Ensure we are at the minimal require height.
if prevNode.height < svh {
stateTuple.State = ThresholdDefined
break
}
// The deployment of the rule change fails if it expires
// before it is accepted and locked in.
medianTime, err := b.calcPastMedianTime(prevNode)
if err != nil {
return newThresholdState(ThresholdFailed,
invalidChoice), err
}
medianTimeUnix := uint64(medianTime.Unix())
if medianTimeUnix >= checker.EndTime() {
stateTuple.State = ThresholdFailed
break
}
// Make sure we are on the correct stake version.
if b.calcStakeVersion(prevNode) < version {
stateTuple.State = ThresholdDefined
break
}
// The state must remain in the defined state so long as
// a majority of the PoW miners have not upgraded.
if !b.isMajorityVersion(int32(version), prevNode,
b.chainParams.BlockRejectNumRequired) {
stateTuple.State = ThresholdDefined
break
}
// The state for the rule moves to the started state
// once its start time has been reached (and it hasn't
// already expired per the above).
if medianTimeUnix >= checker.BeginTime() {
stateTuple.State = ThresholdStarted
}
case ThresholdStarted:
// The deployment of the rule change fails if it expires
// before it is accepted and locked in.
medianTime, err := b.calcPastMedianTime(prevNode)
if err != nil {
return newThresholdState(ThresholdFailed,
invalidChoice), err
}
if uint64(medianTime.Unix()) >= checker.EndTime() {
stateTuple.State = ThresholdFailed
break
}
// At this point, the rule change is still being voted
// on by the miners, so iterate backwards through the
// confirmation window to count all of the votes in it.
var (
counts []thresholdConditionTally
totalVotes uint32
abstainVotes uint32
)
countNode := prevNode
for i := int64(0); i < confirmationWindow; i++ {
c, err := checker.Condition(countNode, version)
if err != nil {
return newThresholdState(
ThresholdFailed, invalidChoice), err
}
// Create array first time around.
if len(counts) == 0 {
counts = make([]thresholdConditionTally, len(c))
}
// Tally votes.
for k := range c {
counts[k].count += c[k].count
counts[k].isAbstain = c[k].isAbstain
counts[k].isNo = c[k].isNo
if c[k].isAbstain {
abstainVotes += c[k].count
} else {
totalVotes += c[k].count
}
}
// Get the previous block node. This function
// is used over simply accessing countNode.parent
// directly as it will dynamically create
// previous block nodes as needed. This helps
// allow only the pieces of the chain that are
// needed to remain in memory.
countNode, err = b.getPrevNodeFromNode(countNode)
if err != nil {
return newThresholdState(
ThresholdFailed, invalidChoice), err
}
}
// Determine if we have reached quorum.
totalNonAbstainVotes := uint32(0)
for _, v := range counts {
if v.isAbstain && !v.isNo {
continue
}
totalNonAbstainVotes += v.count
}
if totalNonAbstainVotes < checker.RuleChangeActivationQuorum() {
break
}
// The state is locked in if the number of blocks in the
// period that voted for the rule change meets the
// activation threshold.
for k, v := range counts {
// We require at least 10% quorum on all votes.
if v.count < checker.RuleChangeActivationThreshold(totalVotes) {
continue
}
// Something went over the threshold
switch {
case !v.isAbstain && !v.isNo:
// One of the choices has
// reached majority.
stateTuple.State = ThresholdLockedIn
stateTuple.Choice = uint32(k)
case !v.isAbstain && v.isNo:
// No choice. Only 1 No per
// vote is allowed. A No vote
// is required though.
stateTuple.State = ThresholdFailed
stateTuple.Choice = uint32(k)
case v.isAbstain && !v.isNo:
// This is the abstain case.
// The statemachine is not
// supposed to change.
continue
case v.isAbstain && v.isNo:
// Invalid choice.
stateTuple.State = ThresholdFailed
stateTuple.Choice = uint32(k)
}
break
}
case ThresholdLockedIn:
// The new rule becomes active when its previous state
// was locked in.
stateTuple.State = ThresholdActive
// Nothing to do if the previous state is active or failed since
// they are both terminal states.
case ThresholdActive:
case ThresholdFailed:
}
// Update the cache to avoid recalculating the state in the
// future.
cache.Update(prevNode.hash, stateTuple)
}
return stateTuple, nil
}
// deploymentState returns the current rule change threshold for a given stake
// version and deploymentID. The threshold is evaluated from the point of view
// of the block node passed in as the first argument to this method.
//
// It is important to note that, as the variable name indicates, this function
// expects the block node prior to the block for which the deployment state is
// desired. In other words, the returned deployment state is for the block
// AFTER the passed node.
//
// This function MUST be called with the chain state lock held (for writes).
func (b *BlockChain) deploymentState(prevNode *blockNode, version uint32, deploymentID string) (ThresholdStateTuple, error) {
for k := range b.chainParams.Deployments[version] {
if b.chainParams.Deployments[version][k].Vote.Id == deploymentID {
checker := deploymentChecker{
deployment: &b.chainParams.Deployments[version][k],
chain: b,
}
cache := &b.deploymentCaches[version][k]
return b.thresholdState(version, prevNode, checker, cache)
}
}
invalidState := ThresholdStateTuple{
State: ThresholdInvalid,
Choice: invalidChoice,
}
return invalidState, DeploymentError(deploymentID)
}
// ThresholdState returns the current rule change threshold state of the given
// deployment ID for the block AFTER the provided block hash.
//
// This function is safe for concurrent access.
func (b *BlockChain) ThresholdState(hash *chainhash.Hash, version uint32, deploymentID string) (ThresholdStateTuple, error) {
b.chainLock.Lock()
node, ok := b.index[*hash]
b.chainLock.Unlock()
if !ok {
invalidState := ThresholdStateTuple{
State: ThresholdInvalid,
Choice: invalidChoice,
}
return invalidState, HashError(hash.String())
}
b.chainLock.Lock()
state, err := b.deploymentState(node, version, deploymentID)
b.chainLock.Unlock()
return state, err
}
// isLNFeaturesAgendaActive returns whether or not the LN features agenda vote,
// as defined in DCP0002 and DCP0003 has passed and is now active from the point
// of view of the passed block node.
//
// It is important to note that, as the variable name indicates, this function
// expects the block node prior to the block for which the deployment state is
// desired. In other words, the returned deployment state is for the block
// AFTER the passed node.
//
// This function MUST be called with the chain state lock held (for writes).
func (b *BlockChain) isLNFeaturesAgendaActive(prevNode *blockNode) (bool, error) {
// Determine the version for the LN features agenda as defined in
// DCP0002 and DCP0003 for the provided network.
deploymentVer := uint32(5)
if b.chainParams.Net != wire.MainNet {
deploymentVer = 6
}
state, err := b.deploymentState(prevNode, deploymentVer,
chaincfg.VoteIDLNFeatures)
if err != nil {
return false, err
}
// NOTE: The choice field of the return threshold state is not examined
// here because there is only one possible choice that can be active for
// the agenda, which is yes, so there is no need to check it.
return state.State == ThresholdActive, nil
}
// IsLNFeaturesAgendaActive returns whether or not the LN features agenda vote,
// as defined in DCP0002 and DCP0003 has passed and is now active for the block
// AFTER the current best chain block.
//
// This function is safe for concurrent access.
func (b *BlockChain) IsLNFeaturesAgendaActive() (bool, error) {
b.chainLock.Lock()
isActive, err := b.isLNFeaturesAgendaActive(b.bestNode)
b.chainLock.Unlock()
return isActive, err
}
// VoteCounts is a compacted struct that is used to message vote counts.
type VoteCounts struct {
Total uint32
TotalAbstain uint32
VoteChoices []uint32
}
// getVoteCounts returns the vote counts for the specified version for the
// current interval.
//
// This function MUST be called with the chain state lock held (for writes).
func (b *BlockChain) getVoteCounts(node *blockNode, version uint32, d chaincfg.ConsensusDeployment) (VoteCounts, error) {
height := calcWantHeight(b.chainParams.StakeValidationHeight,
int64(b.chainParams.RuleChangeActivationInterval), node.height)
var err error
result := VoteCounts{
VoteChoices: make([]uint32, len(d.Vote.Choices)),
}
countNode := node
for countNode.height > height {
for _, vote := range countNode.votes {
// Wrong versions do not count.
if vote.Version != version {
continue
}
// Increase total votes.
result.Total++
index := d.Vote.VoteIndex(vote.Bits)
if index == -1 {
// Invalid votes are treated as abstain.
result.TotalAbstain++
continue
} else if d.Vote.Choices[index].IsAbstain {
result.TotalAbstain++
}
result.VoteChoices[index]++
}
// Get the previous block node. This function
// is used over simply accessing countNode.parent
// directly as it will dynamically create
// previous block nodes as needed. This helps
// allow only the pieces of the chain that are
// needed to remain in memory.
countNode, err = b.getPrevNodeFromNode(countNode)
if err != nil {
return VoteCounts{}, err
}
}
return result, nil
}
// GetVoteCounts returns the vote counts for the specified version and
// deployment identifier for the current interval.
//
// This function is safe for concurrent access.
func (b *BlockChain) GetVoteCounts(version uint32, deploymentID string) (VoteCounts, error) {
for k := range b.chainParams.Deployments[version] {
if b.chainParams.Deployments[version][k].Vote.Id == deploymentID {
b.chainLock.Lock()
defer b.chainLock.Unlock()
return b.getVoteCounts(b.bestNode, version,
b.chainParams.Deployments[version][k])
}
}
return VoteCounts{}, DeploymentError(deploymentID)
}
// CountVoteVersion returns the total number of version votes for the current
// interval.
//
// This function is safe for concurrent access.
func (b *BlockChain) CountVoteVersion(version uint32) (uint32, error) {
b.chainLock.Lock()
defer b.chainLock.Unlock()
countNode := b.bestNode
height := calcWantHeight(b.chainParams.StakeValidationHeight,
int64(b.chainParams.RuleChangeActivationInterval),
countNode.height)
var err error
total := uint32(0)
for countNode.height > height {
for _, vote := range countNode.votes {
// Wrong versions do not count.
if vote.Version != version {
continue
}
// Increase total votes.
total++
}
// Get the previous block node. This function
// is used over simply accessing countNode.parent
// directly as it will dynamically create
// previous block nodes as needed. This helps
// allow only the pieces of the chain that are
// needed to remain in memory.
countNode, err = b.getPrevNodeFromNode(countNode)
if err != nil {
return 0, err
}
}
return total, nil
}